운영체제) 스케줄링

▣ 언제 스케줄링 하는가?

- 새 프로세스가 생성될 때

- 프로세스가 종료될 때

- 프로세스가 블록 될 때

- I/O interrupt가 발생할 때

▣ 스케줄링 결정

- running -> waiting

- running -> ready

- waiting -> ready

- 종료

▣ 스케줄링 알고리즘

- 비선점 (nonpreemptive) : 완료되기전에 스위칭 불가능

- 선점 (preemptive) : 완료되기전에 스위칭 가능

▣ 스케줄링 최적화

- max : CPU utilization , throughput

- min : turnaround / waiting / response time

▣ 스케줄링 알고리즘 부류

- 배치 시스템

- 대화식 시스템

- 실시간 시스템

▣ 스케줄링 목표

- 공평함 : 각 프로세스에게 공평한 목의 CPU 할당

- 정책 집행 : 정책이 집행되는지 관찰

- 균형 : 시스템의 모든 부분이 활동하도록 함

▣ 배치 스케줄링

- FCFS ( First-Come First-Service )

- SJF (Shortest Job First ) : nonpreemptive ver

- SRTF (Shortest Remaining Time First ) / SRTN (Shortest Remaining Time Next )

- HRN ( Highest Response-ratio First )

*  이론적으로는 SRTF / SRTN > SJF

그러나, Context Switiching에 의한 Overhead 고려한다면 꼭 그렇다고 단정지을 수 없다.

; 배치의 3-level scheduling

- admission scheduler

- memory scheduler

- CPU scheduler

▣ 대화식 시스템 스케줄링

- RR ( Round Robin Scheduling )

a. preemptive

b. time quantum / slice

c. time quantum이 크다면 -> FIFO 와 유사 / 작다면 -> 문맥교환이 자주 일어날 것

- Priority Scheduling

a. 각 프로세스는 우선순의 가짐

b. starvation 문제 --> aging 기법 사용 ==> 위에서의 HRN이 한 예

c. 프로세스들을 그룹화 --> 우선 순위 클래스 형성

d. 각 클래스에 우선순위 할당 --> 각 클래스 내에 라운드 로빈

==> 낮은 우선순위 클래스의 기아현상 (starvation)

- Multilevel Queue Scheduling

a. preemptive

b. ready queue ( foreground : interactive / background : batch )

c. 각 큐는 각기 다른 스케줄링 알고리즘 사용 --> foreground : RR / background : FCFS

==> 전체적으\로 보면 괜찮지만, 각 큐에서는 기아현상이 발생할 수 있음

- Multilevel Feedback Queue Scheduling

a. preemptive

b. 멀티레벨 큐 스케줄링의 기아현상을 해결

- SPN (Shortest Process Next)

a. SJF 방식 --> 응답시간이 짧다. --> 문제 : 프로세스의 Burst Time을 알수 없음

b. aging 기법 --> 기존 사용 정보를 토대로 Burst Time을 추론

- 보장(guaranteed) 스케줄링

a. 허가한 CPU 시간에 대한 사용비율 계산

b. 가장 비율이 낮은 프로세스를 선택하여 실행

- 복권 스케줄링

a. 당첨자 프로세스는 상금으로 CPU 시간을 받는다.

- 공평-몫(fare-share) 스케줄링

a. 스케줄링 전에 소유자를 고려하여 스케줄링

b. 사용자에게 속한 프로세스의 수와는 무관하다

▣ 실시간 시스템 스케줄링

- 시간이 핵심 역할

- 경성 실시간 (hard real-time) : deadline 존재

- 연성 실시간 (soft real-time) : 어느 정도 허용

▣ 정책과 메커니즘

- 한 프로세스가 자신의 통제하에 실행되는 많은 자식을 갖게 되는 경우

- 정책은 사용자 프로세스에 의해 결정

- 메커니즘은 커널에 의해 결정

▣ 스레드 스케줄링

- 유저 레벨 : 주의 깊은 사용이 필요

- 커널 레벨 : 완전환 context switching이 필요 --> 오버헤드