philosophers(1), thread
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
으로 이루어져 있다.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가 모든 커널 쓰레드들의 부모이다.
- 기본적인 정렬, 트리, 그래프 알고리즘이 멀티쓰레딩의 장점을 이용할 수 있다.
- 예를들어, 리눅스 시스템이 부팅될때,
- 대부분의 운영체제 커널들또한 multithread이다.
- 장점
Responsiveness
- 시간이 오래 걸리는 작업을 하더라도, 프로그램이 계속 구동된다.
- 단일 쓰레드였다면 해당 동작이 끝날때까지 멈추겠지만,
- 비동기 쓰레드로 구분해 시간이 오래걸리는 작업을 처리하면 어플리케이션은 유저에게 반응할 수 있다.
Resource sharing
- 프로세스들은 shared memory와 message queue 로만 자원을 공유할 수 있는데,
- 쓰레드는
프로세스의 자원을 공유
한다. - code영역와 data 영역을 공유함으로써, 같은 주소 공간에서 다른 동작을 하는 쓰레드를 만들 수 있다.
- Economy
- 프로세스를 만들어 메모리와 자원을 할당하는건 비용이 많이 든다.
- 하지만 쓰레드는 프로세스의 자원을 공유하기때문에
생성할때 경제적
이고,context-switch 할때도 경제적
이다.- 일반적으로 프로세스를 생성하는게
- 시간, 메모리가 많이 들며,
- context switching 또한 많이 든다.
- 일반적으로 프로세스를 생성하는게
- Scalability
- 단일 쓰레드 프로세스는 1개의 프로세서만 사용할 수 있지만,
- 멀티 쓰레드 프로세스는 멀티프로세서 아키텍처에서
- 각각 다른 프로세싱 코어에서 병렬적으로 구동될 수 있다.
multicore programming
- multicore 시스템에서 multithreading
- 1개의 물리적 칩에 여러개의 코어가 달려있는 걸 multicore라고한다.
- multicore 시스템을 더 효율적으로 사용할 수 있고, concurrency를 향상시킬 수 있다.
-
single core에서는 쓰레드가 중간중간 기다려야한다.
-
multi core에서는 쓰레드를 병렬적으로 처리할 수 있다.
-
- multicore 시스템을 더 효율적으로 사용할 수 있고, concurrency를 향상시킬 수 있다.
- 1개의 물리적 칩에 여러개의 코어가 달려있는 걸 multicore라고한다.
- 멀티코어 프로그래밍 도전과제
- identifying tasks
- 작업을 나눌 수 있는(쓰레드를 나눌 수 있는) 구역을 찾아야함
- Balance
- 각 쓰레드에 작업량을 적절히 배분해야함
- data splitting
- data는 각각의 코어로 나눠져 처리되어야한다.
- data dependency
- 데이터간 의존성에따라 데이터를 동기화시켜야한다.
- testing and debugging
- 위와 같은 도전과제로 인해 테스트하고 디버그하는게 까다롭다.
- identifying tasks
- Parellelism 종류
- Data parallelism
- 데이터를 쪼개서 코어에 할당하고, 각 코어에서는 동일한 작업을 수행한다.
- 0부터 N까지 데이터가 있다면,
- 0 ~ N/2 - 1까지는 core0의 thread A가
- N/2 ~ N - 1까지는 core1의 thread B가 수행
- Task parallelism
- 데이터가 아닌 task를 다수의 코어에 분배한다.
- 각 코어는 고유의 연산을 수행한다.
- 서로 다른 스레드가 동일한 데이터에 연산을 할수도 있고, 서로 다른 데이터에 연산을 할수도 있다.
- Data parallelism
-
Amdahl’s Law - CPU 코어는 많을수록 좋은가?
- S : 순차적으로 실행되어야하는 요소
- N : 코어의 갯수
순차적으로 실행되어야하는 요소가 많아질수록, core를 추가하는 것의 효과는 체감한다.
다중 스레드 모델
-
user thread & kernel thread
- 사용자 스레드
- 사용자 수준에서 제공되는 스레드
- 커널의 지원 없이, user mode에서 쓰레딩을 하는 것
- 자바의 경우, JAVA VM이 스레드를 관리해 운영체제의 CPU를 직접 넘나들수는 없었음.(최근 지원시작)
- 커널 스레드
운영체제가 직접 관리
하는 스레드
- 사용자 스레드와 커널 스레드 간의 관계
- 다대일 모델
- 위에서 본 JAVA VM이 제공한 green thread를 의미.
- 한번에 하나의 스레드만이 커널에 접근
- 일대일 모델
- 사용자 스레드 하나에 커널 스레드 하나를 할당.
- 많은 수의 커널 스레드는 시스템 성능에 영향줄수도 있음.
- 다대다 모델
- 위 모델을의 단점을 상쇄
- 필요한 만큼 사용자 수준 스레드를 생성할 수 있고, 필요에따라 커널 스레드가 병렬적으로 수행가능
- 한 사용자 스레드를 한 커널 스레드에 할당을 허용하면
two-level model
이라고 불리기도 한다.
- 다대일 모델
- 사용자 스레드
쓰레드 라이브러리
- 스레드를 생성하고 관리하는 API를 제공한다.
- POSIX pthreads
- Windows thread
- java thread
- pthreads
- 스레드 동작에 대한 명세, 구현은 아님.
- sys/types.h 에 정의된 pthread 관련 자료형
- 스레드 동작에 대한 명세, 구현은 아님.
암묵적 쓰레딩
- Implicit Threading
- 개발자들에게 multicore system에서 multithreading
- 즉, 동시적 - 병렬적 어플리에키션의 디자인은 너무 어렵다.
- 따라서 라이브러리(java.concurrent)와 컴파일러(openmp)에게 이런 어려움을 전가할 수 있다.
Thread Pools
- pool에 쓰레드를 생성해놓고 필요할 때 꺼내쓴다.
- 개발자가 직접 쓰레드를 만들도록 하는게 아닌, 미리 만들어져있는 쓰레드를 개발자가 빌려쓰는 개념.
Fork & Join
- 개발자가 직접 쓰레드를 만들도록 하는게 아닌, 미리 만들어져있는 쓰레드를 개발자가 빌려쓰는 개념.
- 명시적으로 쓰레딩을 하는데, 이를 Implicit하게 쓰레딩을 할 수 있다.
3.OpenMP
- 컴파일러 지시어를 주어 C/C++에서 병렬처리할 수 있다.
4.Grand Central Dispatch(GCD)
- macOS나 IOS에서 사용된다.
- 개발자들에게 multicore system에서 multithreading
- Open MP
- 병렬처리할 코드블럭을 명시해주면 컴파일러가 이를 처리해준다.
CPU 스케쥴링
basic
- 단순한 시스템에서 CPU 동작
- 프로세스는 wait전까지(일반적으로 I/O 요청이 끝날때까지) 실행되고있다.
- 단순한 컴퓨터시스템에서는 이후에 단순히
idle
상태로 변하고, - 이 대기시간(waiting time)은 낭비된다.
- CPU 스케쥴링은
-
multiprogrammed OS의 기본이된다.
- multiprogramming의 목적은
- 몇몇 프로세스들이 항상 구동하는것(time sharing하면서)
- 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으로 끝난다.
- CPU burst 지속시간
- 대부분 많은 빈도를 가진, 짧은 CPU burst를 가진다.
- CPU 지향 프로그램은 긴 CPU burst를 많이 가질 것.
- 프로세스 실행은
- CPU scheduler
- 메모리에 로드된 프로세스 중 어떤 프로세스에 할당할 것인가.
- ready 상태에 있는 프로세스 중,
- CPU를 할당해줄 수 있는 프로세스를 선택한다.
- 그렇다면, 다음 프로세스를 어떻게 선택할 것인가?
FIFO Queue
: 선입선출 큐Priory Queue
: 우선순위 큐 (프로세스에 우선순위 부여)
- 메모리에 로드된 프로세스 중 어떤 프로세스에 할당할 것인가.
- 선점 / 비선점 스케줄링(Preemptive & Nonpreemptive Scheduling)
- Non-preemptive
- 프로세스가 terminating 또는 waiting state로 변할때까지
- CPU를 놓아줄때까지 점유
- Premptive
- 프로세스가 스케쥴러에의해 CPU를 놓아주게된다.
- Non-preemptive
- CPU 스케쥴링의 의사결정
- 프로세스의 state가
- running to waiting(wait호출)
- running to ready(I/O발생)
- waiting to ready(I/O가 종료)
- terminate
- 1 & 4 : -> 선택권이 없으므로, non-preemptive
- 2 & 3 : -> 선택권이 있으므로 non-preemptive or preemptive
- 프로세스의 state가
- dispatcher
-
CPU 코어의 제어를 CPU 스케쥴러가 선택한 프로세스에 주는 모듈.
- dispatcher의 역할
- 한 프로세스에서 다른 프로세스로
context switching
- usermode로 전환
- user 프로그램을 다시 시작하기위해 적절한 위치로 jump
- 한 프로세스에서 다른 프로세스로
- dispatch latency
dispatcher는 모든 프로세스의 context switching에 사용
된다.- 따라서, 가능한 빠르게 수행되어야한다.
- 하나의 프로세스를 정지하고, 다른 프로세스를 execution하는데 걸리는 시간을
dispatch latency
라고 한다.
-
- 스케쥴링 기준
CPU utilization
(CPU 사용효율)- CPU를 가능한 많이 사용해야한다.
Thoughput
(처리량)- 단위시간당 완료된 프로세스 개수
Turnaround time
(총처리 시간)- 프로세스를 실행하는데에 소요된 시간
- 프로세스의 제출시간과 완료시간의 간격(도착시간 - exit시간)
- ready queue에서의 대기시간, CPU에서 실행하는 시간, I/O시간 합한 시간
Waiting time
(대기 시간)- ready queue에서 프로세스가 기다린 시간의 합
response time
(응답 시간)- 응답이 시작되는데에 걸리는 시간
- CPU 스케쥴링 문제
- ready queue에서 기다리고 있는 어떤 프로세스에
- CPU 코어를 할당할 것인가?
- ready queue에서 기다리고 있는 어떤 프로세스에
- Solution
- FCFS : First Come First Served
- 가장 먼저 CPU 할당을 요청한 프로세스에 CPU할당
- FIFO queue로 쉽게 구현 가능.
- 예시
- 프로세스 별 버스트 시간
- P1 -> P2 -> P3 순으로 도착 시,
- P1 대기시간 : 0밀리초
- P2 대기시간 : 24밀리초
- p3 대기시간 : 27밀리초
- 평균 대기시간 : 17밀리초
- 총 처리시간 : 24 + 27 + 30 = 81
- P2 -> P3 -> P1 순으로 도착 시,
- 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 양도를 기다리고 있는 것을 의미
- FCFS : First Come First Served
- SJF : Shortest Job First(SRTF : Shortest Remaining Time First)
- 각 프로세스의 다음 프로세스의 CPU-burst를 계산한다.
- 가장 작은 CPU-burst를 가진 프로세스에 CPU를 할당한다.
- 만약 동일하면, FCFS를 적용한다.
- 예시
- 프로세스별 버스트 시간
- SJF 스케쥴링 이용시
- 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에 들어온 프로세스를 선점한다.
- 예시
- 도착시간, 버스트시간
- Gantt차트
- RR : Round-Robin
- 시간할당량(time quantum, time slice)를 사용한 선점FCFS이다.
- time quantum, time slice는 시간의 작은 단위.
- 일반적으로 10 ~ 100 밀리초
- ready queue는 원형 큐로 동작한다.
- 스케쥴러는 ready queue를 돌면서 한 번에 한 프로세스에 1 time quantum을 할당한다.
- time quantum, time slice는 시간의 작은 단위.
- 이렇게 동작하면 2가지 경우 중, 하나의 경우가 발생한다.
- 프로세스가 1 time quantum보다 적은 CPU burst 시간을 가진다.
- 프로세스는 알아서 CPU를 반납한다.
- 스케쥴러는 다음 프로세스를 ready queue에서 가져와 진행한다.
- 프로세스가 1 time quantum보다 큰 CPU burst 시간을 가진다.
- 타이머가 끝나면 OS에 interrupt를 건다.
- context switch가 일어나고,
- 프로세스는 ready queue의 맨 뒤에 놓인다.
- 프로세스가 1 time quantum보다 적은 CPU burst 시간을 가진다.
- 예시
- 버스트시간
- time quantum 4ms
- 성능
- time quantum의 크기에 영향을 많이 받는다.
- time quantum의 크기가 작을수록, context switch가 자주 발생한다.
- context switch가 자주 발생한다는 것은
dispatch latency
가 자주 발생한다는 것이다. - 따라서, context switch의 횟수와 time quantum울 벤치마킹을 통해 잘 조정해야한다.
- time quantum의 크기에 영향을 많이 받는다.
- 시간할당량(time quantum, time slice)를 사용한 선점FCFS이다.
- Priority-based
- 각 프로세스에 우선순위를 배정한 후,
- CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
- 같은 우선순위를 가진 프로세스는 FCFS로 스케쥴링된다.
- SJF는 사실, 우선순위 스케쥴링이었다.
- 우선순위는 next CPU burst의 역이었다.(CPU burst 시간이 클수록 낮은 우선순위)
- 선점형 또는 비선점형일 수 있다.
- starvation의 문제(indefinite blocking)
- blocked process : CPU를 waiting하고있는, ready상태의 프로세스
- 낮은 순위의 프로세스는 높은 우선순위의 프로세스가 계속 들어오면 영원히 CPU를 얻지 못한다.
- 결국 실행되거나
- 아니면 시스템이 crash되어 해당 프로세스는 영원히 봉쇄된다.
- 낮은 순위의 프로세스는 높은 우선순위의 프로세스가 계속 들어오면 영원히 CPU를 얻지 못한다.
- blocked process : CPU를 waiting하고있는, ready상태의 프로세스
- starvation 해결책
aging
- 오랜 시간 대기한 프로세스의 우선순위를 점진적으로 증가시킨다.
- RR과 Priority scheduling을 결합해서 해결
- 가장 높은 순위의 프로세스를 실행하되,
- 같은 우선순위의 프로세스는 RR 스케쥴링으로 실행한다.
- 각 프로세스에 우선순위를 배정한 후,
- MLQ : Multi-Level Queue
- Priority-based와 round-robin은 모든 프로세스가 단일 큐에 존재한다.
- 근데, 우선순위마다 별도의 큐를 갖는게 더 쉽다.
- 우선순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄한다.
- 이 방법을
Multi-Level Queue
라고 한다.
- 같은 우선 순위 내의 프로세스는 라운드 로빈으로 실행된다.
프로세스 유형
에 따라 큐를 나누어 줄 수도 있다.- 프로세스 유형에 따라 다른 우선순위를 할당한다.
-
작업이 많은 실시간 프로세스가 높은 우선순위에, 백그라운드 프로세스는 낮은 우선순위에 속한다.
- 그림
- MLFQ : Multi-Level Feedback Queue
- MLQ에서는 프로세스들의 유형별로 영구적으로 큐에 할당된다.
- 프로세스들이 특성을 바꾸지 않기 때문.
- MLFQ는 융통성이 적은 문제를 해결한 알고리즘이다.
- 프로세스가 큐 사이를 이동할 수 있다.
- 그림
- 스케줄러는 처음에 시간 할당량 8인 큐의 프로세스를 먼저 실행한다.
- 만약 프로세스가 여기서 끝나지 않으면 큐1의 꼬리로 이동한다.
- 큐0이 비워지면 큐1을 실행한다. 여기선 시간 할당량 16이다.
- 큐1이 비워지면 큐2는 FCFS방식으로 실행된다.
- MLQ에서는 프로세스들의 유형별로 영구적으로 큐에 할당된다.
쓰레드 스케쥴링
- 최신 운영체제에서는
- 스케줄 되는 대상은 프로세스가 아닌 쓰레드이다.
- 사용자 수준 쓰레드는 쓰레드 라이브러리가 관리하므로, 커널에서는 이를 인식하지 못한다.
- 따라서, 커널수준 쓰레드에 사용자수준 쓰레드를 연결해야한다.
실시간 CPU 스케줄링
- 실시간 OS에서 스케줄링
- 주어진 시간 내에 task를 완료
- soft Real time
- 중요한 실시간 프로세스가 시간내에 완료된다는 걸 보장하지 않음
- 다만, 중요한 실시간 프로세스가 덜 중요한 실시간 프로세스에 우선권 가짐을 보장.
- hard Real time
- task는 반드시 주어진 시간 내에 완료.
- soft Real time
- 주어진 시간 내에 task를 완료
댓글남기기