CPU 스케줄링
프로세스에서 실행하는 작업은 두 가지로 나뉜다.
첫 번째는 cpu만 실행하는 작업이고, CPU burst라고 한다.
두 번째는 IO만 실행하는 작업이고, IO burst라고 한다.
보통 이 두 개가 섞여있는데, CPU는 짧게 쓰고 중간에 IO에 많은 시간이 필요한 작업을 I/O bound process라고 하고, CPU를 아주 길게 쓰는 계산 위주의 작업을 cpu bound process라고 한다. 이런 여러 작업들이 섞여 있기 때문에 cpu 스케줄링이 필요하다.
cpu 스케줄링은 cpu와 IO 장치 등의 시스템 자원을 골고루 효율적으로 사용하는 것을 목표로 한다.
여기서 cpu 스케줄러라는 개념이 등장하는데 cpu 스케줄러는 어떠한 장치가 아니라 운영체제 상의 코드를 의미한다. cpu 스케줄러는 ready 상태의 프로세스 중에서 cpu를 할당할 프로세스를 고르는 일을 한다.
dispatcher라는 것도 존재하는데, cpu의 제어권을 cpu 스케줄러가 고른 프로세스에게 넘기는 역할을 한다. 이 과정을 문맥 교환(context switching)이라고 한다.
cpu 스케줄링은 프로세스에게 다음과 같은 상태 변화가 있을 때 필요하다. (무조건 반드시 이렇게 분류되야 하는게 아니라, 이러한 경우가 존재하는 것이다.)
- Running -> Blocked ex) IO 요청 시스템 콜
- Running -> Ready ex) 할당 시간 만료로 timer 인터럽트
- Blocked -> Ready ex) IO 완료 후 인터럽트
- Terminate
1, 4는 nonpreemptive(비선점형)이라고 하고, cpu를 자진 반납하는 경우다.
나머지는 preemptive(선점형)이고, cpu를 빼앗는 경우다.
스케줄링 알고리즘 성능 척도
- 시스템 입장에서 성능 척도
- Cpu Utilization(이용률) : 전체 시간중에서 cpu가 놀지 않고 일하는 시간의 비율
- Throughput(처리량) : 단위 시간당 cpu가 프로세스를 얼마나 처리하는가
- 프로세스 입장에서 성능 척도
- Turnaround Time(소요시간, 반환시간) : 프로세스가 cpu를 쓰러 들어와서 다시 반납하고 나갈 때 까지의 시간
- Waiting Time(대기시간) : ready queue에서 대기하면서 소요된 모든 시간
- Response time(응답시간) : ready queue에서 최초로 cpu를 얻기 전까지 시간
스케줄링 알고리즘
FCFS(First-Come First-Served)
프로세스가 도착한 순서대로 실행하는 알고리즘으로 비선점형이다. 가장 처음에 생각할 수 있는 알고리즘이지만 소요시간이 긴 프로세스가 먼저 도착한다면 소요시간이 짧은 프로세스가 지나치게 오래 기다려야 된다는 문제점이 존재한다.(convoy effect)
SJF(Shortest-Job-First)
cpu burst time이 가장 짧은 프로세스를 제일 먼저 스케줄하는 알고리즘이다. 구현 방식에는 두 가지가 존재한다.
1. 비선점형
-> 일단 cpu를 잡으면 이번 cpu burst가 완료될 때까지 cpu를 선점 당하지 않는다.
2. 선점형
-> 만약 cpu burst time이 더 짧은 프로세스가 도착한다면 cpu를 빼앗긴다.
-> 이 방식으로 구현된 알고리즘을 SRTF(Shortest-Remaining-Time-First)라고 한다.
SJF는 다른 알고리즘보다 평균 대기 시간이 가장 작은데, 선점형 방식(SRTF)이 제일 작다.
이 알고리즘 방식의 단점은 다음과 같다.
- 계속해서 cpu burst time이 짧은 프로세스가 도착한다면 영원히 실행이 되지 않는 프로세스가 존재할 수 있다. (기아 상태)
- cpu burst time을 미리 알 수 없다. (과거의 사용 내역을 통해 추정만 가능)
Priority Scheduling
우선 순위 스케줄링 방식으로 프로세스마다 우선 순위를 매겨서 우선 순위가 높은 프로세스에게 cpu를 먼저 할당하는 방식이다.
역시 비선점 방식과 선점 방식이 존재하며, 우선 순위가 높은 프로세스가 계속 들어오면 우선 순위가 낮은 프로세스는 cpu를 할당받지 못하는 기아 현상이 발생할 수 있다. 이 문제를 해결하기 위해서 aging(노화)라는 해결책을 제시하는데, 우선 순위가 낮은 프로세스의 우선 순위를 조금씩 높여주는 방식이다. 이를 통해 우선 순위가 낮은 프로세스도 언젠가 cpu를 할당받을 수 있게 된다.
Round Robin(RR)
현대 운영체제는 라운드 로빈방식을 기반으로 한다. RR에서 각 프로세스는 동일한 크기의 할당 시간을 가진다. 할당 시간이 지나면 프로세스는 다른 프로세스에게 선점 당하고 ready queue의 제일 뒤에 가서 줄을 서게 된다.
RR에서 만약 n개의 프로세스가 ready queue에 있고 할당 시간이 q time out인 경우 어떤 프로세스도 (n-1)q time unit이상 기다리지 않는 것이 보장된다. 여기서 q가 커지면 FCFS와 비슷하게 되고, q가 작아지면 문맥 교환 오버헤드가 커진다. 따라서 적절한 할당 시간을 주는 것이 중요하다.
이러한 특성때문에 SJF보다 평균 소요시간, 반환시간은 길어지지만 응답시간이 짧아지는 것을 장점으로 가진다.
Multilevel Queue
ready queue를 여러 개의 우선 순위를 가진 queue들로 분할하여 처리한다. 이 알고리즘은 먼저 어떤 큐를 선택할지 정하고, 그 다음 각 큐에 배정된 알고리즘(RR... SJF...)을 사용하여 어떤 프로세스에게 cpu를 줄지 결정한다.
그런데, 어떤 큐를 선택할지 결정할 때 역시 우선순위가 높은 큐만 선택하게 되면 기아 상태가 발생할 수 있다. 따라서 기아 현상을 막기 위해 각 큐에 cpu time을 적절한 비율로 할당(예 : 큐1에 20%, 큐2에 80% cpu time)하는 방법을 사용할 수 있다.
Multilevel Feedback Queue
기존에 여러 개의 우선 순위를 가진 queue들이 존재하고, 그 queue에 프로세스가 들어가면 그 프로세스는 처리될 때까지 영원히 그곳에 남아서 우선 순위가 변하지 않았지만, Multilevel Feedback Queue는 프로세스가 다른 우선 순위 큐로 이동 가능하다.
만약 8ms의 q0, 16ms의 q1, fcfs의 q2 라는 queue들이 존재하고 우선 순위는 q0 > q1 > q2라고 할 때 한 프로세스가 들어오면 q0에서 cpu를 갖게 되고, 작업을 마무리하지 못하면 q1으로 밀려난다. 그 후에 다시 작업을 진행하게 되고 역시 마무리하지 못하면 q2로 밀려난다.
우선 순위가 높은 큐가 다 비워졌을 때 아래 우선 순위의 큐에 있는 프로세스를 실행하기 때문에, 막 들어온 프로세스는 cpu를 빨리 얻게 되고, 실행 시간이 짧다면 바로 작업을 끝낼 수 있게 된다. 반면에 실행 시간이 긴 프로세스는 점점 우선 순위가 낮은 큐로 밀려나게된다.
따라서 이 방식은 cpu burst time이 짧은 프로세스에게 기회를 많이 주는 알고리즘 방식이다.
멀티 프로세서에서의 스케줄링
homogenous processor
queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 조금 복잡해진다.
load sharing
일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다. 대기하는 프로세스를 넣을 별개의 큐를 두는 방법과 공동 큐를 사용하는 방법이 존재한다.
symmetric multiprocessing(SMP)
각 프로세서가 각자 알아서 스케줄링을 결정한다.
Asymmetric multiprocessing
하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따르게 된다.
Real-Time-Scheduling
Hard real-time Systems
hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야한다.
Soft real-time Systems
데드라인을 조금 어겨도 괜찮고 꼭 보장하지 못할 때 사용한다. soft real-time task는 일반 프로세스에 비해 높은 우선 순위를 갖도록 스케줄링된다.
Thread Scheduling
local scheduling
user level thread의 경우로, 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다.
global scheduling
kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄할지 결정한다.
반효경 교수님의 운영체제 강의를 바탕으로 작성했습니다
