CPU Scheduling
운영체제는 CPU를 프로세스들 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만들어준다. 스레드를 지원하는 운영체제에서는 실질적으로 프로세스가 아니라 커널 수준 스레드를 스케줄한다. 그러나 프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용한다.
기본 개념
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.
따라서 어느 한 순간에 다수의 프로세서들을 메모리 내에 유지한다. 어떤 프로세스가 대기(Waiting)해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스로 할당한다.
CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)
버스트(burst)란 특정 기준에 따라 한 단위로서 취급되는 연속된 신호나 데이터의 모임을 말한다. 즉, 입출력 요청을 위해 CPU 사용을 사용했다가 쉬었다가를 반복한다.
프로세스가 CPU를 사용할때를 CPU버스트, 입/출력을 기다릴때를 입/출력 버스트라고 한다.
프로세스의 실행은 CPU 버스트를 시작으로 뒤이어 입출력 버스트가 발생하는 식으로 두 버스트의 사이클로 구성된다. 마지막 CPU버스트는 또 다른 입출력 버스트가 뒤따르는 대신에 실행을 종료하기 위한 시스템 요청과 함께 끝난다.
입출력 중심의 프로그램은 CPU 버스트 시간이 짧을 것이다. 반대로 CPU 지향 프로그램은 CPU 버스트 시간이 길 것이다. 이러한 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는데 매우 중요할 수 있다.
CPU 스케줄러(Scheduler)
운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행해야 한다. 이를 수행하는게 바로 단기 스케줄러, 또는 CPU 스케줄러이다. (장기, 중기, 단기가 헷갈린다면 다시보고 오시길 🤷♂️)
실행 준비가 되어 있는 메모리 내의 프로세스들 중 하나를 선택하여 이들 중 하나에게 CPU를 할당한다.
CPU 스케줄링 발생 상황
CPU 스케줄링은 다음과 같은 4가지 상황에서만 생긴다.
- 프로세스가 종료(terminates)될때
- 프로세스가 실행상태(running)에서 대기상태(waiting)로 전환될 때(예를 들어 입출력 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait를 호출할때)
- 프로세스가 실행상태(running)에서 준비완료상태(ready)로 전환 될 때(예를 들어 인터럽트가 발생했거나 시간이 다 된경우, time slice 만료. 더 큰 우선순위가 들어올 경우)
- 프로세스가 대기상태(waiting)에서 준비완료상태(ready)로 전환 될때(예를 들어 입출력의 종료시)
CPU 스케줄링 방식
또한, 선점 스케줄링과 비선점 스케줄링에 따라 상황별 스케줄링 발생 경우가 다르다.
-
선점형(preemptive) 스케줄링 : 상황 1과 2뿐만 아니라 3과 4의 경우에도 스케줄링이 발생할 수 있는 방식. 동작하고 있던 프로세스를 강제로 멈추고 스케줄링할 수 있는 방법이다. 강제성을 띈다.
-
비선점형(non-preemptive) 스케줄링 : 상황 1과 2의 경우는 스케줄링 면에서는 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다.
디스패처(dispatcher)
스케줄링한다 : 프로세스가 교체된다. 즉, 문맥교환(context switching)이 일어나는 것을 말한다.
- dispatcher : 이제 너가 CPU를 차지하러 들어가라 라고 해주는 것(문맥 교환보다 넓은 의미. 문맥을 교환하고 사용자 모드로 전환하고 적절한 위치까지 이동해주는 것을 포함)
- dispatch latency : 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간(지연시간)
스케줄링 평가기준
서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가지고 있으며 서로 다른 특성을 반드시 고려해야 한다. 이를 비교하기 위한 여러 기준이 제시되어있는데 아래와 같다.
-
CPU 이용률 : 우리는 가능한 CPU를 바쁘게 이용해야 좋은 스케줄링이라고 할 수 있다
-
처리량(throughput) : 작업량 측정. 단위시간당 완료된 프로세스의 개수로 계산. 클수록 좋음
-
총 처리시간(turnaround time) : 반환시간, 소요시간이라고도 함. 프로세스가 메모리에 들어가기 위해 기다리며 소비한 시간 부터 프로세시가 종료되는 그 시간까지. 짧을수록 좋음
-
대기시간(waiting time) : 준비완료 큐에서 대기하면서 보낸 시간의 합
-
응답시간(response time) : 하나의 요구를 제출한 후 첫 번째 응답이 나올때까지의 시간. 응답이 시작되는데까지 걸리는 시간이지 그 응답을 출력하는데 걸리는 시간은 아님
👉 이미지 출처 : http://blog.skby.net/cpu-%EC%84%A0%EC%A0%90-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EA%B8%B0%EB%B2%95/
비선점형 스케줄링
FCFS(First Come, First Served) scheduling
| process | burst time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
이런식으로 존재한다고 했을때 선입 선처리 방식이므로 가장 먼저 도착한 P1, P2, P3 순으로 처리가 된다.
효율을 비교하기 위해 평균 대기시간(waiting time)을 계산해보도록 하자. (0+24+27) / 3 = 17
다만 위에 처럼 가장처음에 나온 프로세스가 오래걸리는 경우 뒤에 프로세스들은 상당히 오래 기다려야한다. 만약 P2, P3, P1 순서였다면 평균대기시간은 어떻게 달라질까? (0+3+6) / 3 = 3 😲. 좀 전보다 엄청나게 시간이 감축되었다.
shortest-job-first(SJF) scheduling
| process | burst time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
shortest-job-first. 이름그대로 job의 길이가 제일 짧은 놈부터 할당. 만약 동일한 길이를 갖는다면 선입선출방식으로 처리한다.
가장 짧은 놈이 먼저니까 P4, P1, P3, P2 순서로 처리가 된다. 비선점방식이기 때문에 프로세스가 종료되거나 waiting 상태가 되면 스케줄링이 발생한다.
문제점 1
waiting time을 최소화하는데는 최적이지만 burst time이 긴 프로세스은 오랜 시간 굶주려야 하므로 기아 현상이 발생할 수 있다.
문제점 2
또한 다음 cpu버스트의 길이를 정확히 알 수 있는 방법이 없다(각 명령마다 크기가 있고 개수가 있으니 단순계산이 가능하지만 프로그램은 그 안에 루틴도 있고 해서 정확한 시간을 알 수 없다). 아래는 그나마 예측할 수 있는 방법이다.
-
tn은 방금 수행한 실제 cpu 버스트 시간.
-
τn+1 은 다음 cpu버스트 예측값(우리가 알고 싶어하는 그 값)
-
τn 은 그 이전에 대한 예측값
-
a는 0과 1사이 값. 최근의 값과 이전 값의 상대적인 무게 제어. a=0이라면 τn+1 = τn 이므로 최근의 역사는 아무 영향이 없다. a=1이면 τn+1 = tn이므로 단지 가장 최근의 버스트만 중시된다(과거 역사는 관계없다)
priority(우선순위) scheduling
| process | burst time | 우선순위 |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
우선 순위가 높은 프로세스에 CPU를 우선 할당하는 방식의 스케줄링이다. 우선 순위는 시간 제한, 메모리 요구량, 프로세스의 중요성, 자원사용 비용 등에 따라 달라질 수 있다.
선점형과 비선점형 둘다 가능한데 선점형은 내가 도착하자 마자 바로 우선순위를 비교해서 높다면 cpu를 선점한다. 비선점형은 도착을 했지만 cpu사용이 끝날때 까지 기다림. 그다음 cpu스케줄링을 할때 우선순위를 비교한다.
이 방식의 문제점은 우선순위가 높은 놈이 실행. 우선순위가 낮은 놈은 기다림. 근데 또 자기보다 높은 우선순위를 가진 놈이 들어오면 계속 우선순위 낮은 놈은 실행하지 못해서 기아 상태 또는 무한봉쇄가 나타날 가능성이 있다.
해결책으로는 aging-노화. 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키면 된다.
선점형 스케줄링
shortest-remaining-time-first(SRT 혹은 SRTF) scheduling
SJF가 선점형이면 이를 선점형 SJF, 혹은 SRT라는 다른 명칭으로 부른다.
| process | Arrival time | burst time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
선점형이기 때문에 P1이 가장 먼저 도착해서 실행중이던 상황에서 P2가 P1의 남은시간보다 더 짧은 burst time을 가지므로 P2가 강제적으로 선점해버렸다.
이런식으로 기본은 SJF와 비슷하지만 선점형인 방식이 바로 SRT 스케줄링 방식이다.
Round Robin(RR) scheduling
| process | burst time |
|---|---|
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
모든 프로세스마다 정해진 시간. 즉 한번에 한 프로세스에게 한번의 시간 할당량 동안 CPU를 할당한다. 시간할당량(time quantum. q)는 일반적으로 10~100ms동안이다
time quantum은 20이라고 가정해보자. 1~4순서로 공평하게 20 단위로 실행. 근데 중간에 종료가 되거나 I/O가 있을때는 20을 다 채우지 못하고 다음으로 넘어간다.
time quantum가 너무 짧으면 스위칭이 많이 일어나 오버헤드가 발생할 수 있고 time quantum가 너무 길면 다른 프로세스 대기 시간이 길어지겠지? 따라서 적당한 값이 필요하다.
다단계 큐(Multilevel Queue) scheduling
준비 완료 큐를 다수의 별도의 큐로 분류한다. 각 큐는 자신의 스케줄링 알고리즘을 갖고 있다.
위에처럼 각 큐는 우선순위가 있고 낮은 우선순위의 큐보다 절대적인 우선순위를 가지게 된다.
다단계 피드백큐(Multilevel Feedback Queue) scheduling
다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 즉, 프로세스는 한 큐에서 다른 큐로 이동하지 못한다.
다단계 피드백큐는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동한다. 위 그림은 8안에 끝나는 놈은 맨위에 놓이며, 8안에 끝나지 못하는 놈은 밑으로 내려가는 식이다.
이러한 노화 형태는 기아 상태를 예방할 수 있다.
References
