Process scheduling

CPU Scheduler
상태가 ready인 프로세스큐에서 하나 선택.
스케쥴링 결정은 프로세스가 (1) running에서 waiting으로 바뀔때, (2) running에서 ready로 바뀔 때, (3) waiting에서 ready로 바뀔때, (4) 종료될 때 nonpreemptive(자발적으로 cpu를 내놓는것)하게 발생한다. 다른 경우는 preemptive(cpu를 빼기는 것)이다.

preemptive 스케줄링의 문제점
공유데이터 일관성이 깨질 가능성 (한 프로세스가 data를 업데이트하는 중에 다른 프로세스한테 cpu 뺏기고 그 프로세스가 그 data를 읽으려고 할 때)
커널데이터의 일관성이 깨질 가능성
예) 커널이 I/O queue를 바꾸고 있었다. 다른 프로세스에게 cpu를 뺏겼다.
시스템콜을 호출할때 그것이 완료되기까지 다른 프로세스가 돌아가지 않도록 하거나, I/O block을 하는 방법이 있다.

Dispatcher
스케줄러가 프로세스를 결정하고 cpu에게 넘겨주는 작업
context switching.
user mode로 바꿈. 스케줄러는 커널에서 작동하므로.
user program에서 다시 시작할 곳의 위치로 jumping

어떻게 하는 것이 좋은 스케줄링인지 결정하는 기준
좋은 스케줄링일 수록 CPU가 노는 일 없게 한다.
Throughout - 임의 시간동안 처리가능한 프로세스갯수. 최대화
Turnaround time - 프로세스의 제출부터 종료까지 경과되는 시간. 최소화
waiting time - 프로세스가 레디큐에 머물러 있는 시간. 최소화
response time - 프로세스가 만들어졌을때부터 실행하기까지 걸리는 시간. 최소화.

First-Come, First-Served(FCFS) Scheduling
선착순방식.
프로세스 도착 순서에 따라 성능이 좌우.
CPU burst(설명, 간단하게 요구하는 시피유 시간)가 큰 프로세스가 들어오면 average waiting time이 커짐.

Shortest-Job-First (SJF) Scheduling
CPU burst가 가장 작은 프로세스를 실행하도록 스케줄링
2가지 방식이 있다.
nonpreemptive - process에게 한번 cpu가 주어지면 cpu burst가 완료될때까지 cpu를 뺏기지 않는다.
preemptive - 새로운 프로세스가 현재 실행중인 프로세스의 남아있는 burst time보다 작은 burst time를 가지고 있다면 cpu를 빼았는다.

Priority scheduling
우선순위에 따라 CPU를 주는 것.
Preemptive, nonpreemptive가 있다.
SJF도 우선순위 스케줄링 방식(cpu burst time이 작을수록 우선순위가 높은것)이니 위에 것이 이해가 될 듯.
문제점
Starvation - 낮은 우선순위는 영원히 실행 안될 가능성이 있다.
해결책 - aging. 프로세스의 우선순위를 시간이 지나면 올려준다. 나이먹는 것처럼.

Round Robin (RR)
각 프로세스가 작은 단위의 CPU time을 얻는다.
한 프로세스가 cpu 사용시간이 지나면 그 프로세스는 preempted 되고 레디큐의 끝에 추가된다.
보통 average turnaround time은 SJF보다 길지만, response time은 짧다. interaction이 중요한 프로그램에게는 이 방식이 좋을수도.

Multilevel queue
레디큐는 여러개의 큐로 나눠진다.
예) foreground용, background용
각각의 큐는 스케줄링 알고리즘을 가지고 있다.
예) foreground(RR), background(FCFS)
큐들 사이에도 스케쥴링이 있다.
예) fixed priority scheduling(foreground queue의 우선순위가 background queue의 우선순위보다 높아서 높은 우선순위의 프로세스가 무조건 cpu를 뺏어올 수 있도록), Time slice(각각의 큐마다 CPU time을 할당한다. foreground에는 80%, background에는 20% 이런식으로) 

Multilevel Feedback Queue
프로세스가 큐들 사이를 이동 할 수 있는 것.
한 프로세스가 CPU를 너무 많이 잡아먹었다싶으면 낮은 우선순위 큐로 내려보내는 것.

리눅스에서의 스케줄링 정책

출처 : http://kldp.org/node/18841
SCHED_OTHER

: 일반적인 process/thread 의 정책. priority를 0만 가질 수 있음. timeshared.

SCHED_FIFO

: realtime을 위한 정책. priority 1~99. timeshared 아님. 오직 더 높은 priority를 가진 task에게만 선점됨. block, yield, terminate되기 전까지 계속 실행.

SCHED_RR

: realtime을 위한 정책. priority 1~99. 동일한 priority를 가진 waiting SCHED_RR task와 timeshared. timeshare할 대상이 없을 때 SCHED_FIFO와 동일하게 동작.