업데이트:

태그:

카테고리:



minitalk에서 프로세스의 개념이 나와서 운영체제에 대해 공부하며 과제를 진행했다.
자연스럽게 뒤에 나오는 쓰레드에 대해서도 공부해야한다는 걸 알았는데, 강의 주제 중 philosopher에 대한 내용도 있더라…

minitalk/pipex 에서 프로세스의 개념에 대해 공부하고,
philosophers에서 쓰레드에 개념에 대해 익히는 순서대로 공부를 하게된다.

순서대로 따라가다보면 체계적인 느낌으로 과제를 준다는게 느껴진다.

쓰레드

overview

  • 메모리에 올라간 여러 프로세스들은
  • concurrently하게 state가 변하고,
  • CPU time sharing을 통해 context switching을 하며
  • 사용자가 각 프로세스들이 동시에 동작하고 있다라고 느끼게된다.

minitalk에서 공부했던 프로세스들은 단일 프로세스로 프로그램을 구동하는 것이었는데,
process는 사실 multi threads로 동작할 수 있다.

  • thread란
    • lightweight process이다.
    • CPU utilization의 기본 단위이다.
    • thread ID, program counter, register set, stack으로 이루어져 있다. IMG_9C1C151F1080-1
    • code, data, files 는 공유하되,
    • 각 쓰레드는 register set, stack, program counter를 달리한다.


  • multithreading 의 장점
    • server-client를 예시로하자.
    • client의 request를 server가 처리해야하는데,
      • 서버가 이를 처리하기위해 프로세스를 새로 만든다면(fork)
        • 시간과 자원을 많이 사용하게된다.
      • 만약 쓰레드를 만들어 처리한다면
        • 서버는 client의 request를 처리하는 thread를 따로 만들어 처리하고,
        • 추가적인 request를 listening 하고있게 된다.


  • kernel
    • 대부분의 운영체제 커널들또한 multithread이다.
      • 예를들어, 리눅스 시스템이 부팅될때,
        • 장치 관리, 메모리 관리, interrupt 핸들러와 같은 쓰레드들이 만들어진다.
        • pid 2인 kthreadd가 모든 커널 쓰레드들의 부모이다.
      • 기본적인 정렬, 트리, 그래프 알고리즘이 멀티쓰레딩의 장점을 이용할 수 있다.


  • 장점
    1. Responsiveness
      • 시간이 오래 걸리는 작업을 하더라도, 프로그램이 계속 구동된다.
      • 단일 쓰레드였다면 해당 동작이 끝날때까지 멈추겠지만,
      • 비동기 쓰레드로 구분해 시간이 오래걸리는 작업을 처리하면 어플리케이션은 유저에게 반응할 수 있다.
    2. Resource sharing
      • 프로세스들은 shared memory와 message queue 로만 자원을 공유할 수 있는데,
      • 쓰레드는 프로세스의 자원을 공유한다.
      • code영역와 data 영역을 공유함으로써, 같은 주소 공간에서 다른 동작을 하는 쓰레드를 만들 수 있다.
    3. Economy
      • 프로세스를 만들어 메모리와 자원을 할당하는건 비용이 많이 든다.
      • 하지만 쓰레드는 프로세스의 자원을 공유하기때문에
      • 생성할때 경제적이고, context-switch 할때도 경제적이다.
        • 일반적으로 프로세스를 생성하는게
          • 시간, 메모리가 많이 들며,
          • context switching 또한 많이 든다.
    4. Scalability
      • 단일 쓰레드 프로세스는 1개의 프로세서만 사용할 수 있지만,
      • 멀티 쓰레드 프로세스는 멀티프로세서 아키텍처에서
      • 각각 다른 프로세싱 코어에서 병렬적으로 구동될 수 있다.



multicore programming

  • multicore 시스템에서 multithreading
    • 1개의 물리적 칩에 여러개의 코어가 달려있는 걸 multicore라고한다.
      • multicore 시스템을 더 효율적으로 사용할 수 있고, concurrency를 향상시킬 수 있다.
        • single core에서는 쓰레드가 중간중간 기다려야한다. Screen Shot 2022-05-16 at 1 23 11 PM

        • multi core에서는 쓰레드를 병렬적으로 처리할 수 있다. Screen Shot 2022-05-16 at 1 22 48 PM


  • 멀티코어 프로그래밍 도전과제
    1. identifying tasks
      • 작업을 나눌 수 있는(쓰레드를 나눌 수 있는) 구역을 찾아야함
    2. Balance
      • 각 쓰레드에 작업량을 적절히 배분해야함
    3. data splitting
      • data는 각각의 코어로 나눠져 처리되어야한다.
    4. data dependency
      • 데이터간 의존성에따라 데이터를 동기화시켜야한다.
    5. testing and debugging
      • 위와 같은 도전과제로 인해 테스트하고 디버그하는게 까다롭다.


  • Parellelism 종류
    1. Data parallelism
      • 데이터를 쪼개서 코어에 할당하고, 각 코어에서는 동일한 작업을 수행한다. Screen Shot 2022-05-16 at 1 49 51 PM
      • 0부터 N까지 데이터가 있다면,
      • 0 ~ N/2 - 1까지는 core0의 thread A가
      • N/2 ~ N - 1까지는 core1의 thread B가 수행
    2. Task parallelism
      • 데이터가 아닌 task를 다수의 코어에 분배한다. Screen Shot 2022-05-16 at 1 51 53 PM
      • 각 코어는 고유의 연산을 수행한다.
      • 서로 다른 스레드가 동일한 데이터에 연산을 할수도 있고, 서로 다른 데이터에 연산을 할수도 있다.


  • Amdahl’s Law - CPU 코어는 많을수록 좋은가? Screen Shot 2022-05-16 at 1 54 54 PM

    • S : 순차적으로 실행되어야하는 요소
    • N : 코어의 갯수

    Screen Shot 2022-05-16 at 1 55 54 PM

    순차적으로 실행되어야하는 요소가 많아질수록, core를 추가하는 것의 효과는 체감한다.



다중 스레드 모델

  • user thread & kernel thread

    • 사용자 스레드
      • 사용자 수준에서 제공되는 스레드
      • 커널의 지원 없이, user mode에서 쓰레딩을 하는 것
      • 자바의 경우, JAVA VM이 스레드를 관리해 운영체제의 CPU를 직접 넘나들수는 없었음.(최근 지원시작)
    • 커널 스레드
      • 운영체제가 직접 관리하는 스레드

    Screen Shot 2022-05-16 at 2 02 09 PM

    • 사용자 스레드와 커널 스레드 간의 관계
      • 다대일 모델
        • 위에서 본 JAVA VM이 제공한 green thread를 의미.
        • 한번에 하나의 스레드만이 커널에 접근 Screen Shot 2022-05-16 at 2 03 51 PM
      • 일대일 모델
        • 사용자 스레드 하나에 커널 스레드 하나를 할당.
        • 많은 수의 커널 스레드는 시스템 성능에 영향줄수도 있음. Screen Shot 2022-05-16 at 2 03 57 PM
      • 다대다 모델
        • 위 모델을의 단점을 상쇄
        • 필요한 만큼 사용자 수준 스레드를 생성할 수 있고, 필요에따라 커널 스레드가 병렬적으로 수행가능
        • 한 사용자 스레드를 한 커널 스레드에 할당을 허용하면 two-level model이라고 불리기도 한다. Screen Shot 2022-05-16 at 2 04 04 PM



쓰레드 라이브러리

  • 스레드를 생성하고 관리하는 API를 제공한다.
  • POSIX pthreads
  • Windows thread
  • java thread


  • pthreads
    • 스레드 동작에 대한 명세, 구현은 아님.
      • sys/types.h 에 정의된 pthread 관련 자료형 Screen Shot 2022-05-16 at 2 23 54 PM



암묵적 쓰레딩

  • Implicit Threading
    • 개발자들에게 multicore system에서 multithreading
      • 즉, 동시적 - 병렬적 어플리에키션의 디자인은 너무 어렵다.
    • 따라서 라이브러리(java.concurrent)와 컴파일러(openmp)에게 이런 어려움을 전가할 수 있다.
      1. Thread Pools
      • pool에 쓰레드를 생성해놓고 필요할 때 꺼내쓴다.
        • 개발자가 직접 쓰레드를 만들도록 하는게 아닌, 미리 만들어져있는 쓰레드를 개발자가 빌려쓰는 개념.
          1. Fork & Join
      • 명시적으로 쓰레딩을 하는데, 이를 Implicit하게 쓰레딩을 할 수 있다.
        3. OpenMP
      • 컴파일러 지시어를 주어 C/C++에서 병렬처리할 수 있다.
        4. Grand Central Dispatch(GCD)
      • macOS나 IOS에서 사용된다.


  • Open MP
    • 병렬처리할 코드블럭을 명시해주면 컴파일러가 이를 처리해준다.



CPU 스케쥴링

basic

  • 단순한 시스템에서 CPU 동작
    • 프로세스는 wait전까지(일반적으로 I/O 요청이 끝날때까지) 실행되고있다.
    • 단순한 컴퓨터시스템에서는 이후에 단순히 idle상태로 변하고,
    • 이 대기시간(waiting time)은 낭비된다.


  • CPU 스케쥴링은
    • multiprogrammed OS의 기본이된다.

    • multiprogramming의 목적은
      1. 몇몇 프로세스들이 항상 구동하는것(time sharing하면서)
      2. CPU 사용효율을 최대화하는 것
    • multiprogramming으로 인해
      • 이 waiting 시간을 생산적으로 사용할 수 있다.
      • 프로세스가 wait 상태가 되면 해당 프로세스가 점유하던 CPU를 다른 프로세스에 할당한다.


  • CPU-I/O Burst Cycle

    • 프로세스 실행은
      • CPU 실행과
      • I/O wait의 사이클로 구성된다.


    • 프로세스의 실행
      • CPU burst로 시작됨
      • 뒤이어 I/O burst가 발생하고
      • 그 뒤를 이어 또 다른 CPU burst가 발생하면서 또 다른 I/O burst가 실행된다.
      • 마지막 CPU burst는 I/O burst대신, terminate execution으로 끝난다. Screen Shot 2022-05-16 at 4 39 17 PM


    • CPU burst 지속시간
      • 대부분 많은 빈도를 가진, 짧은 CPU burst를 가진다.
      • CPU 지향 프로그램은 긴 CPU burst를 많이 가질 것. Screen Shot 2022-05-16 at 4 54 38 PM


  • CPU scheduler
    • 메모리에 로드된 프로세스 중 어떤 프로세스에 할당할 것인가.
      • ready 상태에 있는 프로세스 중,
      • CPU를 할당해줄 수 있는 프로세스를 선택한다.
    • 그렇다면, 다음 프로세스를 어떻게 선택할 것인가?
      • FIFO Queue : 선입선출 큐
      • Priory Queue : 우선순위 큐 (프로세스에 우선순위 부여)


  • 선점 / 비선점 스케줄링(Preemptive & Nonpreemptive Scheduling)
    • Non-preemptive
      • 프로세스가 terminating 또는 waiting state로 변할때까지
      • CPU를 놓아줄때까지 점유
    • Premptive
      • 프로세스가 스케쥴러에의해 CPU를 놓아주게된다.


  • CPU 스케쥴링의 의사결정
    • 프로세스의 state가
      1. running to waiting(wait호출)
      2. running to ready(I/O발생)
      3. waiting to ready(I/O가 종료)
      4. terminate
    • 1 & 4 : -> 선택권이 없으므로, non-preemptive
    • 2 & 3 : -> 선택권이 있으므로 non-preemptive or preemptive


  • dispatcher
    • CPU 코어의 제어를 CPU 스케쥴러가 선택한 프로세스에 주는 모듈.

    • dispatcher의 역할
      • 한 프로세스에서 다른 프로세스로 context switching
      • usermode로 전환
      • user 프로그램을 다시 시작하기위해 적절한 위치로 jump
    • dispatch latency
      • dispatcher는 모든 프로세스의 context switching에 사용된다.
      • 따라서, 가능한 빠르게 수행되어야한다.
      • 하나의 프로세스를 정지하고, 다른 프로세스를 execution하는데 걸리는 시간을
      • dispatch latency라고 한다. Screen Shot 2022-05-16 at 5 37 44 PM


  • 스케쥴링 기준
    • CPU utilization(CPU 사용효율)
      • CPU를 가능한 많이 사용해야한다.
    • Thoughput(처리량)
      • 단위시간당 완료된 프로세스 개수
    • Turnaround time(총처리 시간)
      • 프로세스를 실행하는데에 소요된 시간
      • 프로세스의 제출시간과 완료시간의 간격(도착시간 - exit시간)
      • ready queue에서의 대기시간, CPU에서 실행하는 시간, I/O시간 합한 시간
    • Waiting time(대기 시간)
      • ready queue에서 프로세스가 기다린 시간의 합
    • response time(응답 시간)
      • 응답이 시작되는데에 걸리는 시간


  • CPU 스케쥴링 문제
    • ready queue에서 기다리고 있는 어떤 프로세스에
      • CPU 코어를 할당할 것인가?


  • Solution
    • FCFS : First Come First Served
      • 가장 먼저 CPU 할당을 요청한 프로세스에 CPU할당
      • FIFO queue로 쉽게 구현 가능.
      • 예시
        • 프로세스 별 버스트 시간 Screen Shot 2022-05-16 at 7 45 45 PM
        • P1 -> P2 -> P3 순으로 도착 시, Screen Shot 2022-05-16 at 7 46 25 PM
          • P1 대기시간 : 0밀리초
          • P2 대기시간 : 24밀리초
          • p3 대기시간 : 27밀리초
          • 평균 대기시간 : 17밀리초
          • 총 처리시간 : 24 + 27 + 30 = 81
        • P2 -> P3 -> P1 순으로 도착 시, Screen Shot 2022-05-16 at 7 50 30 PM
          • P2 대기시간 : 0밀리초
          • P3 대기시간 : 3밀리초
          • P1 대기시간 : 6밀리초
          • 평균 대기시간 : 3밀리초
          • 총 처리시간 : 3 + 6 + 30 = 39
      • FCFS하에
        • 평균 대기시간은 일반적으로 가장 작지 않고,
        • CPU 버스트 타임에 따라 많이 변화한다.
      • 선점인가 비선점인가
        • 일단 CPU가 할당되면 처리될때까지 기다려야하므로 비선점형임
      • 동적 상황(호위효과, convoy effect)
        • CPU를 많이 사용하는 프로세스(CPU bound)1개와 CPU적게 사용하는 프로세스(I/O중심)여러개
        • CPU-bound 프로세스가 먼저 처리되어 뒤의 많은 프로세스들이 처리를 기다리고 있는것
        • 다른 모든 프로세스들이 하나의 긴 프로세스가 CPU 양도를 기다리고 있는 것을 의미


  • SJF : Shortest Job First(SRTF : Shortest Remaining Time First)
    • 각 프로세스의 다음 프로세스의 CPU-burst를 계산한다.
    • 가장 작은 CPU-burst를 가진 프로세스에 CPU를 할당한다.
    • 만약 동일하면, FCFS를 적용한다.
    • 예시
      • 프로세스별 버스트 시간 Screen Shot 2022-05-16 at 8 29 51 PM
      • SJF 스케쥴링 이용시 Screen Shot 2022-05-16 at 8 30 35 PM
      • P4 대기시간 : 0밀리초
      • P1 대기시간 : 3밀리초
      • P3 대기시간 : 9밀리초
      • P2 대기시간 : 16밀리초
      • 평균 대기시간 : 7밀리초
    • SJF 스케쥴링 알고리즘은 최적임을 증명할 수 있다.
      • 짧은 프로세스를 긴 프로세스 뒤에 놓음으로써
        • 짧은 프로세스의 대기시간을 줄어드는 대기시간이
        • 긴 프로세스의 대기시간이 증가하는 것보다 더 많이 줄어든다.
    • 하지만 구현할 수 없다.
      • next CPU burst time을 알 수 있는 방법이 없다.
      • 하지만 근사적으로 구할수는 있다.
      • 일반적으로 측정된 이전 CPU burst time의 길이를 지수평균해서 예측한다.


    • 비선점형 또는 선점형이다.
      • 새로운 프로세스(버스트 시간 : 0.5)가 ready queue에 들어왔는데,
      • 이전의 프로세스(버스트 시간 : 1)가 여전히 실행중이라면
        • 선점형이라면 현재 실행중인 프로세스를 선점해 새로운 프로세스에 CPU를 할당하고
        • 비선점형이라면 현재 실행하고 있는 프로세스가 끝날때까지 기다린다.
    • SRTF 스케쥴링
      • 선점형 SJF 스케쥴링을 의미한다.
      • 최소 잔여 시간 우선 스케쥴링.
      • 현재 실행중인 프로세스의 CPU 버스트보다, ready queue에 들어온 프로세스의 CPU 버스트가 짧다면
      • ready queue에 들어온 프로세스를 선점한다.
      • 예시
        • 도착시간, 버스트시간 Screen Shot 2022-05-16 at 9 24 09 PM
        • Gantt차트 Screen Shot 2022-05-16 at 9 24 51 PM



  • RR : Round-Robin
    • 시간할당량(time quantum, time slice)를 사용한 선점FCFS이다.
      • time quantum, time slice는 시간의 작은 단위.
        • 일반적으로 10 ~ 100 밀리초
      • ready queue는 원형 큐로 동작한다.
        • 스케쥴러는 ready queue를 돌면서 한 번에 한 프로세스에 1 time quantum을 할당한다.
    • 이렇게 동작하면 2가지 경우 중, 하나의 경우가 발생한다.
      1. 프로세스가 1 time quantum보다 적은 CPU burst 시간을 가진다.
        • 프로세스는 알아서 CPU를 반납한다.
        • 스케쥴러는 다음 프로세스를 ready queue에서 가져와 진행한다.
      2. 프로세스가 1 time quantum보다 큰 CPU burst 시간을 가진다.
        • 타이머가 끝나면 OS에 interrupt를 건다.
        • context switch가 일어나고,
        • 프로세스는 ready queue의 맨 뒤에 놓인다.
    • 예시
      • 버스트시간 Screen Shot 2022-05-16 at 9 41 54 PM
      • time quantum 4ms Screen Shot 2022-05-16 at 9 42 40 PM
    • 성능
      • time quantum의 크기에 영향을 많이 받는다.
        • time quantum의 크기가 작을수록, context switch가 자주 발생한다.
        • context switch가 자주 발생한다는 것은 dispatch latency가 자주 발생한다는 것이다.
        • 따라서, context switch의 횟수와 time quantum울 벤치마킹을 통해 잘 조정해야한다.



  • Priority-based
    • 각 프로세스에 우선순위를 배정한 후,
      • CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
      • 같은 우선순위를 가진 프로세스는 FCFS로 스케쥴링된다.
    • SJF는 사실, 우선순위 스케쥴링이었다.
      • 우선순위는 next CPU burst의 역이었다.(CPU burst 시간이 클수록 낮은 우선순위)
    • 선점형 또는 비선점형일 수 있다.
    • starvation의 문제(indefinite blocking)
      • blocked process : CPU를 waiting하고있는, ready상태의 프로세스
        • 낮은 순위의 프로세스는 높은 우선순위의 프로세스가 계속 들어오면 영원히 CPU를 얻지 못한다.
          • 결국 실행되거나
          • 아니면 시스템이 crash되어 해당 프로세스는 영원히 봉쇄된다.
    • starvation 해결책
      • aging
        • 오랜 시간 대기한 프로세스의 우선순위를 점진적으로 증가시킨다.
      • RR과 Priority scheduling을 결합해서 해결
        • 가장 높은 순위의 프로세스를 실행하되,
        • 같은 우선순위의 프로세스는 RR 스케쥴링으로 실행한다.



  • MLQ : Multi-Level Queue
    • Priority-based와 round-robin은 모든 프로세스가 단일 큐에 존재한다.
    • 근데, 우선순위마다 별도의 큐를 갖는게 더 쉽다.
      • 우선순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄한다.
      • 이 방법을 Multi-Level Queue라고 한다.
    • 같은 우선 순위 내의 프로세스는 라운드 로빈으로 실행된다.
    • 프로세스 유형에 따라 큐를 나누어 줄 수도 있다.
      • 프로세스 유형에 따라 다른 우선순위를 할당한다.
      • 작업이 많은 실시간 프로세스가 높은 우선순위에, 백그라운드 프로세스는 낮은 우선순위에 속한다.

      • 그림 Screen Shot 2022-05-17 at 12 25 30 PM


  • MLFQ : Multi-Level Feedback Queue
    • MLQ에서는 프로세스들의 유형별로 영구적으로 큐에 할당된다.
      • 프로세스들이 특성을 바꾸지 않기 때문.
    • MLFQ는 융통성이 적은 문제를 해결한 알고리즘이다.
      • 프로세스가 큐 사이를 이동할 수 있다.
    • 그림 Screen Shot 2022-05-17 at 12 38 50 PM
      • 스케줄러는 처음에 시간 할당량 8인 큐의 프로세스를 먼저 실행한다.
      • 만약 프로세스가 여기서 끝나지 않으면 큐1의 꼬리로 이동한다.
      • 큐0이 비워지면 큐1을 실행한다. 여기선 시간 할당량 16이다.
      • 큐1이 비워지면 큐2는 FCFS방식으로 실행된다.



쓰레드 스케쥴링

  • 최신 운영체제에서는
    • 스케줄 되는 대상은 프로세스가 아닌 쓰레드이다.
    • 사용자 수준 쓰레드는 쓰레드 라이브러리가 관리하므로, 커널에서는 이를 인식하지 못한다.
    • 따라서, 커널수준 쓰레드에 사용자수준 쓰레드를 연결해야한다.



실시간 CPU 스케줄링

  • 실시간 OS에서 스케줄링
    • 주어진 시간 내에 task를 완료
      • soft Real time
        • 중요한 실시간 프로세스가 시간내에 완료된다는 걸 보장하지 않음
        • 다만, 중요한 실시간 프로세스가 덜 중요한 실시간 프로세스에 우선권 가짐을 보장.
      • hard Real time
        • task는 반드시 주어진 시간 내에 완료.



댓글남기기