[OS / 운영체제] CPU-I/O Burst Cycle, CPU Scheduler, Preemptive Scheduling, Scheduling Criteria, Shortest Job First Scheduling

 

CPU-I/O Burst Cycle

read from file을 하면 IO를 사용한다. 프로세스가 실행을 하다보면 어떨 때는 IO를 쓰고 어떨 때는 CPU를 쓴다. IO를 사용하는 구간을 IO Burst라고 부른다. 교대로 배치가 되게 된다. Process가 만들어지면 Ready Queue로 들어간다. 강제 종료를 시키면 마지막이 IO일수도 있지만 정상적인 경우 처음과 마지막은 CPU이다. 

 

 

Historgram of CPU burst Duration

CPU burst의 대부분은 짧다. 전체적으로 보면 짧은 것이 많지만 가끔식 긴 burst가 나온다. 짧은 경우는 IO Bound에서 온 거고 긴 부분은 CPU Bound에서 온 경우가 많다. 

CPU Scheduler

short term scheduler로 불린다. dispatch는 CPU로 올리는 것을 말한다. Context Switching을 Dispatcher가 한다. Ready queue는 PCB의 Linked List로 구현한다고 했었다. 

 

Preemptive Scheduling

MultiProgramming과 Multitasking은 Scheduling의 알고리즘이 다른 것이 주된 차이점이다. nonpreemptivev scheduling의 경우는 Multiprogramming에 해당한다. 지금 돌고 있는 프로그램을 끊을 수 있는 것이 Preemptive scheduling이다.

 

 

When Scheduling Occurs?

running -> switching

running -> ready

waiting -> ready

process terminated

4가지의 경우 Scheduling이 관여를 한다. 1번과 4번은 필수이다. 안하면 CPU가 놀기 때문이다. 

2번과 3번의 경우 필수는 아니다. 김범수가 오든 말든 노래를 부르는 경우. 

Preemtive와 NonPreemtive를 구분하는 기준. 

 

 

Preemptive Scheduling

race condition은 bug의 일종이고 막아야 한다. 

 

 

Preemptive of OS kernel

preemptive scheduling은 usermode에서 preemtive kernel mode는 kernelmode에서 되느냐 안되느냐를 다룬다.(**********). 일단 System call에 들어오면 끝나기 전까지 Switching되지 않는다는 것이 Windows nonpreemptive kernel이다. 

non의 장점

: performance가 좋다. 

preemp의 장점

: real time application에 좋다. 일정 시간 내에 무조건 끝나야 하는 것. Multiprogramming이 performance가 더 좋지만 Multitasking을 사용하는 이유와 동일

 

 

Scheduling Criteria

CPU utilization - CPU가 놀면 안됀다. 최대한 활용할 수 있는 스케줄러가 좋은 것이라는 것.

Throughput - 단위 시간이 끝날 때 완성되는 프로세스의 개수.

Turnaroundtime - 

Waiting time - ready queue에서는 기다리는 시간이 적을 수록 좋다. ready queue에서 기다리는 시간을 얘기한다.

Response time - 

 

 

Scheduling Algorithm

 

 

First-Come First Served Scheduling

non-preemptive 한 scheduling을 의미한다. P1을 먼저 실행시킨다. 중간에 끊을 수 없다. 

 

 

Shortest Job first Scheduling

가장 짧은 것을 먼저 실행시키는 알고리즘이다. 그래서 optimal하다고 표현을 한다. 이보다 짧게 구현할 수 없다. 과거에 어떻게 동작했는지의 history를 가지고 예측할 수 없다. 

 

 

Shortest Job First Scheduling

현재까지의 예측치와 측정치를 가지고 다음 시간에서의 예측지를 계산하겠다라는 것이다. 

 

 

처음 예측치가 10에 해당한다. 현재의 값은 6에 해당한다. 그것들을 평균내면 다음 번 예측치가 8이 되는 것이다. 검은색은 실측이고 파란색은 예측이다. 파란색을 가지고 Shortest 를 구현할 수 있다.

 

 

Shortest Job First Scheduling

바뀔 수 있는 경우가 있다. 여러가지의 경우가 존재한다. 7ms 이후에 끝나는데 들어오는 시점이 그 안에 있다면 P2가 들어오는 순간에 스케줄링을 할지 말지를 결정하는 것이다. P1의 경우 Burst Time은 5로 수정해야 한다. P2의 우선순위가 높다, 그렇기 때문에 P2가 2ms에서 돌기 시작하는 것이다. P2가 끝날 때 다른 프로세스가 들어왔을 때를 다시 생각해봐야 한다. 4ms에 도착한 것이면 2ms 이후로부터 2ms 이따가 발생한다. 2초 후에 P3가 들어왔고. 7이 5, 4가 2, 1이 0으로 변해야 한다. 다시 생각해볼 것.,....