4-2주차. CPU 스케줄링

나우히즈·2024년 7월 16일

CS OS 운영체제

OS

목록 보기

7/27

지난시간

사람과 상호작용이 많은 프로그램의 경우 I/O burst를 자주해야함 -> I/O Bound job
계산, 응용 등 연산이 많은 경우 CPU burst 시간이 긺 -> CPU Bound job

이렇게 프로그램 간 동작 형태가 다르므로, CPU 스케줄링이 필요.

non-preemptive scheduling: CPU를 강제로 뺏지 않고 자진 반납하는 스케줄링
preemptive scheduling: CPU를 사용중인 프로세스로부터 강제로 가져오는 스케줄링

Scheduling Algorithms

FCFS(First-Come First-Served)

: Non-preemptive scheduling.

먼저 오는대로 CPU를 처리하게 한다.
CPU 스케줄링에선 굉장히 비효율적인 방식.
Convoy effect: short process behind long process. 오래걸리는 작업이 먼저 오면 조금만 작업해도 되는 프로세스들이 다 오래 기다려야함.

SJF (Shortest-Job-First)

CPU를 가장 짧게 쓰려는 프로세스(CPU burst time 가장 적은)에 먼저 제어권을 준다.
주어진 프로세스들에 대해 최소 평균 대기시간을 보장함.

SJF: Non-preemptive

일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 빼앗기지 않음.

SJF: Preemptive

현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗겨 짧은 프로세스에 넘김.
이 방법을 Shortest-Remaining-Time-First(SRTF)라고도 부른다.
평균 대기시간 측면에서 조금 더 optimal한 방식. 전체적인 큐의 길이를 짧게 해준다.

SJF: 치명적인 약점

이 방법은 starvation을 발생시킨다. 프로세스가 굶어죽는 일 발생.
Long job 은 CPU를 얻지 못하는 경우가 발생할 수 있다.
CPU burst time을 정확히 알지 못한다는 약점이 있다.
누가 짧고 누가 긴지 추정(예측)을 통해서만 계산할 수 있기때문에 정확하지 못하다.
과거의 CPU burst time을 이용하여 추정한다.

1. 실제 과거 CPU burst의 값. n 번째 CPU burst 값이 얼마였는지.
1. n + 1 번째 CPU burst의 예측값
1. 가중치
두 변수를 통해 n + 1 번째의 CPU burst 값을 예측할 수 있다. n 번째 예측값과 실제값의 선형보간.
점화식을 풀면 이와 같이 정리하게 될 수 있다.

Priortiy Scheduling

각 프로세스에 우선순위를 부여하고 우선 순위가 높은 프로세스에게 먼저 제어권을 준다.
SJF 와 동일하게 Preemptive, non-preemptive 방식이 존재한다.
SJF도 일종의 priority scheduling. (priority = predicted next CPU burst time)
Starvation: 우선순위가 낮은 프로세스는 실행이 안될 수 있다.
Aging: 시간이 지날수록 (오래 기다릴수록) 우선순위 값을 높여주는 방식.

Round Robin (RR)

타이머 하드웨어에 할당 시간(time quantum, 10-100 ms)을 세팅하여 일정 시간동안만 CPU를 사용하게끔 하는 방식.
시간이 다 되면 CPU가 인터럽트 걸려서 운영체제로 넘어가게 된다. 해당 프로세스는 대기 큐에 줄을 섬
preemptive 방식.
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
어떤 프로세스도 (n - 1) * q time unit 이상 기다리지 않는다.
q 값이 너무 크면 -> FCFS와 유사해짐
q 값이 너무 작으면 -> context switch 오버헤드가 커진다.
일반적으로 SJF보다 average turnaround time이 길지만, response time은 더 짧다.
짧은 job, 긴 job이 섞여 있을 때 효과적. 동일한 길이의 일들만 있다면 비효율적(average turnaround time이 너무 늘어짐)

Multilevel Queue

큐가 2개인 경우, foreground, background로 분할.

foreground(interactive)
background(batch - no human interaction)

각 큐는 독립적인 스케줄링 알고리즘을 가짐.
foreground - RR 로 진행
background - FCFS 로 진행.
큐에 대한 스케줄링이 필요

Fixed priority scheduling
serve all from foreground then from background.
Possibility of starvation
Time slice
각 큐에 CPU time을 적절한 비율로 할당
Eg. 80% to foreground in RR, 20% to background in FCFS

프로세스의 신분에 따라 CPU 사용에 우선순위가 있다.

Multilevel feedback queue

프로세스가 다른 큐로 이동 가능
에이징을 이와 같은 방식으로 구현할 수 있다.

Multilevel-feedback-queue scheduler 를 정의하는 파라미터들

queue의 수
각 큐의 scheduling algorithm
process를 상위 큐로 보내는 기준
process를 하위 큐로 내쫓는 기준
프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준.

RR과 달리, 다양한 프로세스의 요구를 보다 유연하게 처리하기 위해 고안됨. 각 큐마다 다른 특성을 가지며, 프로세스가 CPU 시간을 더 많이 필요로 하면 하위 큐로 내려가고, 그렇지 않으면 상위 큐에 머뭄.
큐를 여러개 두고, 피드백을 통해 작업이 큐를 옮겨다닐수 있게끔 한다.

Example of multilevel feedback queue

Q0 - time quantum 8 ms
Q1 - time quantum 16 ms
Q2 - FCFS
Scheduling
1) new job이 queue Q0로 들어감.
2) CPU 를 잡아서 할당시간 8ms 동안 수행
3) 8 ms 동안 일을 다 끝내지 못하면 Q1으로 내려감
4) Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms동안 실행
5) time quantum 내 끝내지 못한 경우 Q2로 쫓겨남.

Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐.

Homogeneous processor인 경우 (모두 동일한 CPU이고 제약조건이 없는 경우)

큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐. (특정 프로세서에 종속적인 프로세스가 있을 때 발생하는 문제)

일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘 필요
별개의 큐를 두는 방법과 공동 큐를 사용하는 방법으로 나뉨.
: 별개의 큐를 두는 방법은 각 CPU마다 개별 큐를 두는 것이고, 공동 큐를 사용하는 방법은 모든 CPU가 하나의 큐를 공유하는 방법