CPU Scheduling

이연중·2021년 11월 4일

OS

목록 보기

5/9

I/O bound job(Interactive Job): CPU burst 시간이 짧은 프로그램의 종류(I/O 작업이 자주 끼어드는 경우. CPU를 짧게 자주 씀. 주로 사람과 Interaction을 많이 함)

CPU bound job: CPU burst 시간이 긴 프로그램의 종류(CPU 사용 시간이 긴 경우. 계산 위주의 job)

=> 위처럼 여러 종류의 job이 섞여있기에 CPU 스케쥴링이 필요(Interactive Job(사용자와 상호작용이 잦은 작업)에 CPU를 우선적으로 주자 for 효율성(not 공정성)(CPU bound job 위주면 사용자 입장에서 너무 오래 기다려야 함))

Non-preemtive(비선점형. CPU 뺏기지 않음)

FCFS(First-come First-served): 먼저 들어온 순서대로 처리(프로세스들의 수행 시간에 따라 응답 시간, 대기 시간이 길어질 수 있음(convoy effect))
SJF(Shortest-Job-First): 도착한 프로세스 중 수행시간이 짧은 프로세스부터 처리

평균 대기 시간이 짧음.

Starvation(기아 현상. CPU 수행시간이 긴 프로세스는 CPU 사용이 계속 밀림)문제.

매번 CPU 사용 시간을 미리 알기가 어려움(보통 과거의 CPU 사용 이력을 보고 예측))

(n+1)번째 CPU 사용 예측 시간= a x n번째 CPU 사용시간 + (1-a) x n번째 CPU 사용 예측시간 ---(exponential averaging. 현재에서 과거로 갈수록 반영비율 적게)
Priority Scheduling: 높은 우선순위를 가진 프로세스에 CPU 할당(SJF는 일종의 Priority Scheduling).

우선순위가 낮은 프로세스에 대해 기아 현상 발생(Aging 기법(우선순위를 조금씩 올려줌)을 사용해 해결)

Preemtive(선점형. CPU를 뺏을 수 있음. 현대적 CPU Scheduling 방법)

SJF || SRTF(Shortest-Job-First, Shortest-Remaining-Time-First): 대기 프로세스 중 수행시간이 더 짧은 프로세스가 있으면, CPU를 뺏어 그 프로세스에 줌(평균 대기 시간 짧음)
Priority Scheduling: 높은 우선순위를 가진 프로세스에 CPU 할당(SJF는 일종의 Priority Scheduling)
RR(Round Robinn): 각 프로세스는 동일한 크기의 할당 시간을 가짐. 각 프로세스는 할당 시간만큼 CPU 사용. 현대적인 CPU 스케쥴링 방법(응답 시간 빠름)

할당 시간을 길게 해놓으면, FCFS랑 다를게 없을 것이고, 짧게 해놓으면, 문맥 교환이 잦게된다(오버헤드가 큼)

일반적으로 SJF보다 평균 반환시간이 길지만, 응답 시간은 빠름

시스템 입장에서의 성능 척도

프로그램 입장에서의 성능 척도

큐의 우선순위에 따라 CPU를 할당(위에 큐가 제일 높은 큐. 해당큐가 비어있으면, 그 다음 우선순위...)

Ready Queue를 여러 개로 분할
- foreground: interactive한 job을 넣음
- background: batch- no human interaction job을 넣음
각 큐는 독립적인 스케쥴링 알고리즘을 가짐
- foreground: RR
- background: FCFS
큐에 따른 스케쥴링 필요
- Fixed Priority Scheduling
  - 모든 foreground가 수행되고, background를 수행
  - starvation문제
- Time Slice
  - 각 큐에 CPU Time을 적절한 비율로 할당
  - ex) foreground 80%(RR), background 20%(FCFS)

프로세스가 경우에 따라 큐를 이동할 수 있음

보통 3개의 큐가 있음
- 첫 번째 큐는 quantum time이 8ms(RR)
- 두 번째 큐는 quantum time이 16ms(RR)
- 세 번째 큐는 FCFS
스케쥴링 메커니즘
- 새로운 프로세스가 첫 번째 큐로 들어감
- CPU를 점유하며 8ms 동안 수행
- 그 안에 다 끝내지 못했으면, 두 번째 큐로 강등
- 두 번째 큐에서 기다리다가 차례가 되면 CPU를 점유해서 16ms 동안 수행
- 그 안에 다 끝내지 못했으면, 세 번째 큐로 강등

CPU가 여러 개인 경우 스케쥴링

CPU가 여러 개인 경우 스케쥴링은 더욱 복잡
Homogeneous Processor인 경우
- 큐에 한줄로 세워 각 프로세서가 알아서 꺼내가게 함
- 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 있음
Load Sharing
- 일부 프로세서에 프로세스가 몰리지 않게 부하를 적절히 공유하는 매커니즘 필요(노는 CPU가 있으면 안됨)
- 프로세서 별 별도의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케쥴링 결정
Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서가 따르는 구조

Hard real-time systems
- Hard real-time task는 반드시 deadline 안에 끝내도록 스케쥴링 해야 함
Soft real-rime computing
- Soft real-time task는 일반 프로세스보다 높은 우선순위를 갖도록 함(반드시 deadline 안에 끝내지는 않아도 됨)

Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴할지 결정
Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커넣의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정

CPU Scheduling Algorithm을 평가하는 방법

Queueing Models(이론적인 방법)
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값 계산
Implementation & Measurement(실제 구현, 측정)
- 실제 시스템에 알고리즘을 구현해 실제 작업에 대해 성능 측정, 비교
Simulation
- 알고리즘을 모의 프로그램으로 작성 후 trace(input data)를 입력으로 해 결과 비교(ex) SJF와 내가 만든 알고리즘을 비교)