- 스레드가 작업을 하기 전까지 기다리는 스레드의 대기장소(풀)
- 프로세스는 시작할 때 여러 스레드를 만들어 놓고 풀에 넣어둔다.
- 요청이 들어오면, 서버는 풀에 있는 스레드 중 하나에게 서비스 요청을 할당한다.
- 서비스를 끝낸 스레드는 풀로 돌아와서 다른 일이 들어올 때까지 다시 기다린다.
- 풀에 가용한 스레드가 없다면, 서버는 풀 내에 가용스레드가 하나 생길때까지 기다려야한다.
- 장점
- 새로운 스레드를 만드는것보다 기존 스레드로 서비스 해주는것이 경미하게 더 빠르다.
- 풀의 사이즈에 맞게 응용프로그램 내의 스레드 개수를 제한할 수 있다. 많은 스레드를 병렬처리 할 수 없는 시스템에 도움이 된다.
Process Scheduling이란- 다중 프로그램 OS의 기본이다.
- 용어 정리
- CPU 스케줄링, 프로세스 스케줄링, 커널 스레드 스케줄링
- 이 책에서는 프로세스 스케줄링과 스레드 스케줄링을 상호 교환적으로 사용한다. 일반적인 스케줄링 개념은 프로세스 스케줄링이라고 하고, 스레드에 국한된 경우에만 스레드 스케줄링이라는 용어를 사용할 것이다.
single-processor system에서- 한 순간에는 오직 하나의 프로세스만이 실행될 수 있다.
- 나머지 프로세스는 CPU가 자유 상태가 되어 다시 스케줄될 수 있을 때까지 기다려야한다.
- 실행중인 프로세스가 대기 상태로 진입하면
- OS는 CPU 이용률을 최대화하기 위해 다른 프로세스에 CPU를 할당할 것이다.
- 즉, 실행 중인 프로세스를 항상 가지도록 하는것이 다중 프로그래밍의 목적이다.
- 한 프로세스가 대기해야 할 때마다, 다른 프로세스가 CPU 사용을 양도받을 수 있다.
- 프로세스 스케줄링은
- OS의 기본적인 기능이다.
- 준비 큐로부터 프로세스를 골라서 CPU에 할당하는 것 이다.
Maximum CPU untilization은 멀티프로그래밍에 의해 얻어진다.- 정확히는 프로세스 스케줄링에 의해 얻어진다.
- 프로세스 실행 은 CPU 실행(CPU burst)와 입출력 대기(I/O burst)로 이루어져 있다.
- 프로세스는 두 상태간을 왔다갔다 한다.
- 프로세스 실행은 CPU burst로 시작해서, I/O burst가 발생하고, 다시 또 다른 CPU burst가 발생하고.. 이의 반복이다.
- 결국, 마지막 CPU burst는 실행을 종료하기 위한 시스템콜과 함께 끝난다.
- 프로세스의
CPU burst distribution지속시간은 컴퓨터와 프로세스에 따라 아주 다르다.
- CPU 버스트 분포는 일반적으로 다음과 같은 특징을 가진다.
- 지수형 exponential 또는 초지수형 hyper-exponential 이다.
- 짧은 CPU 버스트가 많이 있으며, 긴 CPU 버스트가 적게 있다.
- 이 두가지 종류의 버스트가 랜덤하게 반복된다. 이 분포를 고려하여 CPU 스케줄링 알고리즘을 선택한다.
- 입출력 중심 프로세스는 다수의 짧은 CPU 버스트를 가질 수 있다.
- CPU 중심 프로세스는 적은 수의 긴 CPU 버스트를 가질 수 있다.
- OS 모듈의 한 종류이다.
- 메모리에서 실행 준비가 된 프로세스들 중 하나를 골라 CPU를 할당 한다.
CPU scheduling decisions은 프로세스가 다음 상황일 때 일어난다.- running -> waiting : 입출력 요청, 또는 자식 프로세스들 중의 하나가 종료되기를 기다리기 위해 wait()를 호출할 시
- running -> ready : 인터럽트 발생 시
- waiting -> ready : 입출력 종료(완료) 시
- running -> terminates : 프로세스 종료시
- new state -> ready : 프로세스 시작 시
- 상황 1, 4에서만 스케줄링이 발생할 경우,
non-preemptive(비선점적)이라고한다. - 상황 2, 3, 5에서는
preemptive(선점적)이라고 한다.
Non-preemptive Scheduling- 한 프로세스에 CPU가 할당되면, 해당 프로세스는 CPU를 release할 때까지 계속 점유한다.
- 종료나 waiting 상태로 전환함으로써 CPU를 release한다.
- Window 3.x 버전에서 사용되었다.
- '내가 수행할거니 네가 잠시 멈춰라'
Preemptive Scheduling- 현재 실행중인(running) 프로세스는 언제든 다른 프로세스와 교체될 수 있다.
- 인터럽트가 언제든 일어날 수 있기 때문이다.
- 대부분의 현대 OS는 이 방식을 사용한다. (Windows, Mac OS X, UNIX)
- 프로세스간 공유 데이터에 접근하는 경우 비용이 발생한다.
- OS 커널 설계에 영향을 준다.
- 특정 OS(UNIX)는 context switch 전에 종료 시스템콜을 기다리거나, I/O block이 일어날 때까지 기다린다.
- 인터럽트는 어느 시점에서건 일어날 수 있으므로, 인터럽트에 의해 영향을 받는 중요 코드 부분은 보호되어야한다. 이 때, 코드 진입구간에서 인터럽트를 disabling하고 코드 출구구간에서 인터럽트를 enabling한다.
- '네가 수행 다하면 내가 수행할게'
- 현재 실행중인(running) 프로세스는 언제든 다른 프로세스와 교체될 수 있다.
Dispatcher module은 Process Scheduler 의 한 요소이다.- 단기 스케줄러에 의해 선택된 프로세스에게 CPU의 제어를 넘겨준다. 이것은 다음 작업들을 포함한다.
- 문맥 교환
- 사용자 모드user mode로 전환
- 프로그램을 다시 시작하기 위하여 유저 프로그램의 적절한 위치로 이동jump
Dispatcher latency- 디스패쳐가 프로세스 하나를 중단시키고 다른 프로세스를 실행시키는 데까지 소요되는 시간
- 스케줄링 기준criteria에 근거해서 다양한 스케줄링 알고리즘의 성능을 평가할 수 있다.
- 스케줄링 알고리즘들은 각자 다른 특성을 가지고 있다.
CPU utilizationCPU 이용률- 단위 시간 당 CPU가 busy한 시간의 비율ratio.Throughput처리량 - 단위 시간당 완료된 프로세스의 개수Turnaround time총처리시간 - 해당 프로세스를 처리하는데에 소요된 시간(해당 프로세스의 시작부터 끝까지의 interval). 메모리 적재를 위해 기다린 시간, 준비 큐에서 waiting상태로 기다린 시간, CPU 수행시간, 입출력 수행시간 을 모두 포함한다.Waiting time대기시간 - 준비큐에서 waiting 상태로 기다린 시간. 스케줄링 알고리즘은 CPU수행시간, 입출력수행시간 등에는 전혀 영향을 주지 않고, 대기시간에만 영향을 준다.Response time응답 시간 - 대화형 시스템에서 요청을 제출한 후 첫 번째 응답이 나올때까지의 시간(시분할 time sharing 시스템에서)
- 최대화 해야할 것들
- CPU 이용률
- 처리량 throughput
- 최소화 해야할 것들
- 총처리시간 turnaround time
- 대기시간 waiting time
- 응답시간 response time
- 그러나 특정 환경에서는 평균보다 더 최소/최대화 되어야하는 기준들이 있을 수 있다.
- 예를 들어 대화형 시스템에서는 응답시간이 더욱 더 최소화되어야한다.
-
선입 선처리 스케줄링(FCFS)
-
최단 작업 우선 스케줄링(SJF)
-
우선순위 스케줄링
-
라운드로빈 스케줄링
-
비교 기준은 평균 대기시간 이다.
- CPU 이용률, 처리량, 총처리시간도 알아본다
 Scheduling 1.png)
- 들어온 순서대로 P1, P2, P3가 수행된다.
- Gantt Chart : 참여한 프로세스의 시작시작과 종료 시간을 포함하여 특정 스케줄 기법을 표시하는 막대형 차트
- 평균 waiting time은 17
- 그런데, 들어오는 순서를 조금 조정하면 평균 waiting time을 개선할 수 있다.
 Scheduling 2.png)
-
P2, P3, P1순으로 들어왔다고 해보자.
-
평균 waiting time이 3으로 개선될 수 있다.
-
FCFS 스케줄링은
non-preemptive하다.- 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하던지 입출력을 요구할 때 까지 CPU자원을 놔주지 않는다.
- 대화형 컴퓨팅 환경같은 시분할 시스템(time sharing)에서 문제가 될 것이다. 시분할 시스템에서는 각 사용자가 규칙적으로 CPU를 얻는것이 중요하므로.
-
Convoy effect(호위 효과)가 생긴다. - FCFS의 문제점
- 긴 CPU 버스트를 가지는 하나의 CPU 중심 프로세스와 짧은 CPU 버스트를 가지는 많은 입출력 중심 프로세스가 있다고 치자.
- 모든 입출력 중심 프로세스는 입출력이 쉬고있는(idle) 동안 CPU를 양도받기 위해 CPU 중심 프로세스를 기다리고있다.
- 모든 입출력/CPU 중심 프로세스는 CPU가 쉬고있을 때 입출력 연산을 수행한다.
- 그러니까, 하나의 긴 CPU 중심프로세스가 CPU 버스트를 수행하는동안 다른 짧은 연산의 입출력 중심 프로세스들이 '호위'하듯이 계속 기다리고 있어야한다는 말이다.
- 결과적으로 낮은 CPU / 장치 이용률을 야기한다.
- 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다.
- 최단시간 의 프로세스를 스케줄하기 위해 다음 CPU 버스트 길이를 사용한다.
- 2개의 경우가 있다.
- 비선점형 : 프로세스에게 한번 CPU가 주어지면 해당 프로세스의 CPU 버스트가 끝나기 전까지 선점될 수 없다.
- 선점형 : 현재 수행중인 프로세스의 남은 시간보다 더 짧은 CPU 버스트 길이를 가진 새로운 프로세스가 도착하면, 선점된다. 이러한 경우는 Shortest-Remaining-Time-First
SRTF로 불린다.
- SJF는 일련의 프로세스가 주어졌을때 최소 평균 대기시간을 도출한다. 따라서 optimal하다.
- 비선점적 SJF의 예시
- P1이 시작되고 나서 2초뒤 P2, 4초뒤 P3이 들어왔다. 그런데 P3의 Burst Time이 가장 짧으니(1) P3이 P1 종료 직후에 수행되고, 그 이후 같은 Burst Time을 가진 것들끼리는 FCFS로 수행된다.
- 평균대기시간은 4
-
선점적 SJF의 예시
- 매 순간 process들의 burst time 길이를 체크한다.
- P1이 시작되고 2초 뒤 P2가 들어왔는데, burst time이 5:4로 더 짧다. 따라서 P2를 수행하다가, P3이 또 새로 들어왔는데 2:1로 더 짧다. 따라서 P3를 수행하고 완료한다. 이후 P2가 가장 짧게(2) 남았으니까 P2를 수행하고, P4가 가장 짧게(4) 남았으니까 P4를 수행한 뒤, 남은 P1의 5을 수행한다.
- 평균 대기시간 3
-
그런데 SJF을 수행할 경우, 가장 긴 수행시간을 가진 프로세스는 영영 실행되지 않을 수도 있다.
- 따라서 이를 해결하기 위해 너무 오래 기다린 프로세스들을 골라서 가끔 수행해주는 방식을 사용하기도 한다.
Prioirity Number(우선순위)가 각 프로세스에 붙어있다.- CPU는 높은 우선순위를 가진 프로세스에게 할당된다. (숫자가 낮을수록 높은 우선순위를 갖는다)
- 선점형
- 비선점형
SJF는 우선순위가 (예상되는) 다음 CPU버스트시간 인 우선순위 스케줄링이다.- 문제점 :
Starvation- 낮은 우선순위를 가진 프로세스들은 영영 실행되지 않을 수 있다. - 해결책 :
Aging- 시간이 지날수록, 프로세스의 우선순위를 높여준다
- 각 프로세스는 일반적으로 10-100 밀리초의 최소 단위의 시간할당량
time quantum을 가진다. - 이 시간이 경과하면, 프로세스는 선점되고 준비 큐의 끝으로 들어간다.
- n 개의 프로세스가 시간 할당량 q 를 가지고 준비 큐에 있다면, 각 프로세스는 n*q 시간 마다 한 번씩 CPU 시간의 1/n(=q)을 얻는다.
- 어떤 프로세스도 (n-1)*q 시간 이상 대기하지 않는다.
- 성능은 time quantum의 사이즈 에 좌우된다.
- q가 크다면 -> RR은 FCFS처럼 동작한다.
- q가 작다면 ->
high concurrency를 제공한다. : n개의 각 프로세스는 프로세서 스피드의 1/n 속도로 수행된다.
- 돌아가면서 20씩 시간을 할당받아 수행된다.
- 일반적으로, 평균 총 처리시간 은 SJF보다 더 느리지만(높지만), 응답시간이 더 낫다
-
문맥 교환이 RR 스케줄링의 성능에 미치는 영향도 고려해야한다.
- time quantum이 너무 작아 문맥 교환이 자주 발생할 수록 프로세스의 실행이 느려진다.
-
시간할당량 q는 문맥교환 시간을 고려하여 충분히 커야한다. 그렇지 않으면 overhead가 너무 커진다.
-
문맥교환시간이 시간 할당량의 10%라면, CPU 시간의 10%는 문맥 교환으로 낭비되는 것이다.
-
현대의 os 들은 q의 크기를 10~100밀리초 로 정하고있다.
-
문맥 교환을 위한 시간은 일반적으로 10마이크로초보다 더 적다 . 따라서 문맥교환 시간은 시간할당량의 작은 부분을 차지한다.
- 준비 큐를 두개의 큐로 나눈다.
- foreground(대화형)
- background(일괄처리형)
- 각 프로세스는 유형에 따라 하나의 큐에만 할당된다.
- 각 큐는 각기 다른 스케줄링 알고리즘을 가지고 있다.
- 포그라운드 - RR
- 백그라운드 - FCFS
- 큐와 큐 사이에도 스케줄링이 이루어진다.
Fixed priority scheduling- 포그라운드를 전부 수행한 뒤 백그라운드를 수행한다.Starvation가능성이 있다.Time slice scheduling- 각 큐는 일정량의 CPU 시간을 할당받는다. ex) 포그라운드 80%, 백그라운드 20%
- 더 높은 우선순위의 큐가 모두 비워지지 않으면 일괄 처리 큐의 어떤 프로세스도 수행될 수 없다.
- 위 그림의 우선순위를 참고할 때, 일괄처리 프로세스가 실행되고 있는동안, 대화형 편집 프로세스가 준비 큐에 들어오면 일괄처리 프로세스는 선점될 것이다
- 프로세스는 여러개의 큐 사이를 옮겨다닐 수 있다 . 이 경우에
aging이 수행될 수 있다.- P1이 RR 큐에 들어가 수행되다가 준비 큐로 돌아왔을 경우, Feedback을 받아 FCFS 큐로 이동할 수도 있다. 더 자주 selecting되는 큐로 jump할 수 있다.
- 이 경우 queue간을 이동할 때 aging시키거나, 주기적으로 scanning하여 완료되지 않은 프로세스들에 대해 우선순위를 올려주어 starvation 문제를 해결한다.
- 멀티레벨 피드백 큐 스케줄러는 다음의 매개변수에 의해서 정의된다.
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 올려(promote)주는 시기를 결정하는 방법 (- aging)
- 한 프로세스를 낮은 우선순위 큐로 강등(demote)시키는 시기를 결정하는 방법
- 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법
- 현대 OS들이 일반적으로 이 방식을 사용한다. RR의 time quantum이 충분히 길면 마치 FCFS처럼 작동하는데, 이러한 방식으로 여러개의 큐를 두고 피드백을 준다.
- Hard real-time 시스템
- 보장된 시간 내에 critical task를 반드시 처리하도록 한다.
- 일반적으로 control system에서 사용되는 시스템이다. 특수한 경우에 사용되는 알고리즘.
- Soft real-time 시스템
- 중요한 프로세스들이 운이 덜 좋은 프로세스들에 비하여 조금 더 우선순위를 높게 받게 한다.