[17] CPU Scheduling (2)

CPU scheduling Goals

-- 스케쥴러는 한 process 에 CPU 시간을 얼마나 할당할 것인가 ?

++ 한 프로세스를 실행완료 시키기까지 정확한 시간을 알수 없기에 1/1000 초씩 할당하고 있다. 

 

-- 스케줄러는 여러 process 어느 순서로 실행킬 것인가 ?

++ average waiting time 을 최소화하기 위해 가장 짧은 프로세스를 먼저 실행시키는 것이 좋을 수 있다. 

++ 가장 짧은 프로세스를 먼저 실행시키면 해당 프로세스가 빠르게 끝나기 때문에 결과적으로 context switching 을 줄여 overhead 를 줄일 수 있다.

++ 하지만 각 프로세스가 정확히 얼마나 걸릴지 알 수 없기에 스케쥴링하기 어렵다.

++ 코드가 짧더라도 무한 루프와 같은 상황에 빠지만 무한정 시간이 걸리기 때문에 코드의 길이로 결정할 수도 없다.

 

-- 사용자 관점에서 고려해야 하는 스케쥴링 정책

++ 평균 응답 시간 ( average waiting time) 을 최소화하는 동시에 적절한 응답 시간을 갖을 수 있는 사용자 수를 최대화한다.

++ 즉 평균 응답 시간을 최소화하지만 한 유저에게 프로세스가 응답하는 시간이 과도하게 늦어지면 안된다는 것이다.

++ Turnaround time 을 최소화해야 한다.

(Turnaround time : 한 프로세스가 시작해서 끝날 때까지 걸리는 총 시간, 대기 시간도 포함, 실행시간 포함)

++ context switching 을 줄여서 대기 시간을 줄이면 turnaround time 을 줄일 수 있다.

++ 어느 프로세스의 조합으로 돌려도 평균 응답 시간이 최소화 되어야 한다. 즉 a,b,c 프로세스를 돌리든 b,c,d 프로세스를 돌리든 평균 응답 시간은 비슷하게 스케줄링해야 한다.

++ 따라서 예측성 ( 한 프로세스의 실행시간이 얼마일지 예측하는 것을 말함 ) 은 매우 중요하고 프로세스는 시스템 부하 상태에 사오간없이 같은 시간동안 실행되어야 한다. 
++ ex) a 프로세스를 실행시키는 만약 실행 시간이 10 이라고 하면 프로세스 10개를 실행시켰을 때 a process 실행시간이 10이 걸렸을 때 프로세스 30개를 동시에 실행시켰을 때에도 a process 실행시간이 10이 걸려야 한다. 

 

-- 시스템 관리자 관점에서 고려해야 하는 스케쥴링 정책

++ 성능 최대화 ( 성능, throughtput : 단위 시간 내에 시작-종료 process의 수 )

++ 프로세서 활용도 최대화 ( 쉬지 않고 일하는 것, cpu 의 경우 process out 하자마자 바로 another process in 해서 활용도 최대화 )

 

-- 기타시스템 지향 스케줄링 정책 ( 비기능적 성능과 관련 )

++ 공정성 : 모든 프로세스가 공정하게 실행되어야 한다. 

++ 우선순위가 없다고 가정할 시 -> 무한 루프에 빠지는 process 가 있는 경우 다른 process 는 cpu 차지를 못해 실행되지 못하는 경우 발생한다.  이런 경우 모든 프로세스가 실행, 즉 시작은 될 수 있도록 공정성을 가지도록 해야한다.

++ 하지만 평균 응답시간 최소화를 위해서는 어느 정도는 공정성을 고려하지 않아도 괜찮다. 프로세스 실행 시간이 매우 긴 프로세스는 짧은 프로세스들이 실행되어 끝난 후 나중에 실행되어도 괜찮다. 

++ 자원 활용의 균형 : 시스템에 있는 모든 resource 들이 사용중이거나 차있는 상태를 유지해야한다.

++ CPU, memory, disk, I/O device 등이 비어있거나 쉬고 있지 않도록 하여 균형을 맞추는 것이다. 

++ 부하가 높은 리소스를 적게 사용하는 프로세스의 우선순위를 높게 부여한다. ( 우선순위 높음 = priority number 는 작음 )

++ ??

 

Preemptive vs Non-preemptive

-- Non-preemptive : process 종료 or running -> block 으로 상태가 변했을 때 스케줄 가능하다.

-- Preemptive  : 언제든 스케줄링 가능하다

++ non-preeemptive 가 실행되는 경우 + 밑의 경우 실행 가능

- process 가 새로 생겼을 때

- block 된 process 가 ready 상태가 되었을 때

- 타이머 인터럽트가 걸렸을 때 ( 타이머는 모든 process 중에서 우선순위 제일 높음)

위의 경우 모두 우선순위를 체크하여 preemptive 실행이 가능하다

++ 긴 process 가 cpu 를 독점하지 않도록 하지만 overhead 가 많다는 단점이 있다.

++ 시스템 호출을 처리하는 동안 또는 일관되지 않은 상태에서 OS 커널을 선점해서는 안 됩니다

++ 실제 process 는 공유변수가 너무 많아서 semaphore 를 사용하기 힘들어 interrupt 를 막는 방법을 사용한다.

따라서 공유변수의 상태를 일관되게 유지하기 위해서 공유 변수의 상태가 달라지는 경우에는 preemptive 를 허용하지 않는다.

 

 

Round-Robin

-- policy

++ time slice ( cpu time quantum ) 이 고정되어 있다.

++ ready que 의 앞쪽부터 프로세스를 선택한다.

++ 선택된 프로세는 최대 time slice 만큼만 실행하고 만약 time slice 내에 끝나지 않으면 ready que 의 tail , 즉 맨 뒤로 들어간다. 

++ 만약 time slice 내에 끝난다면 다른 process 를 선택해서 해당 프로세스를 time slice 만큼 실행시킨다. 

++ 사용하는 경우

1. 주기적인 간격으로 인터럽트하는 하드웨어

2. FIFO 레디 큐, 맨 끝에 더하고 맨 앞에서 process 를 빼는 경우

 

++ time slice 는 4이지만 p2, p3 가 time slice 내에 끝났기에 바로 다른 process 를 찾아서 time slice 만큼 실행시킨다.

++ 정해 time slice 만큼 실행시키기에 일반적으로 average waiting time 은 time slice 와 같거나 작다.

++ 위의 경우는 다른데 ( 10-4 ) 를 없앤다면 3.333.. 이 나와 time slice 4 보다 작은 값이 나온다.

 

++ time slice 보다 작은 process 를 먼저 선택해서 process 를 terminate 시키면 평균 응답 시간은 훨씬 줄어들어 process 자체도 context switching 이 줄어들어 성능이 좋아진다.

 

Evaluation

-- Preemptive 방식의 스케쥴링 방식이다. 하지만 정해진 time slice 가 끝난 후에 뻈을 수 있디.

-- 응답 시간 : short-process 에서는 매우 짧게 나올 수 있다. 

++ 하지만 긴 process 의 경우 반복적으로 context switching 이 자주 발생해 대기 시간이 너무 길어지는 단점이 있다.

++ 성능 : time slice 에 따라 다르다.

1. time slice too small : context switch 가 너무 자주 발생함

2. time slice too big : FCFS 와 같은 경우 발생 가능, cpu 활용성 저하 가능

-- 공정성 : I/O 연산 위주의 프로세스는 cpu time slice 를 온전히 사용하는 것이 아니므로 패널티가 있다.

-- overhead : LOW

++ 비교적 같은 time slice 를 할당하므로 overhead 는 작은편이다. 

 

Shortest-Job-First ( SJF )

-- 현실세계에서 구현은 불가능하지만 현실적인 알고리즘 설계를 위한 기준을 설정하기 위해 존재한다.

-- 다른 이름 : Shortest-Process-Nest ( SPN )

-- policy 

++ CPU burst 가 가장 작은 프로세스를 선택해 CPU 를 할당해주고 한 번 들어가면 block or terminate 될 때까지 실행하는 non-preemptive 방식으로 실행한다.

++ 만약 cpu burst 가 같은 경우 FSFC 방식을 이용하여 먼저 들어온 process 를 수행하는 방식으로 해결한다.

-- 하지만 cpu burst 를 결정하는 것은 매우 어려운 일이다. 

++ process 길이나 과거 process 성능을 기반으로 예측을 해 근사치를 이용하여 결정할 수 있다.

++ 하지만 정확한 값이 아니기에 무한루프에 빠지는 것과 같은 경우가 발생할 수 있다. 

++ burst time 이 가장 짧은 process 먼저 실행하여 terminate 시키는 방식으로 비교적 느린편이다.

 

Evaluation 

-- Non-preemptive 

-- 응답 시간 : short process 에는 좋다.

++ 하지만 long process 는 short process 가 끝날 때까지 대기해야 하므로 대기 시간이 길어진다. 

++ 주어진 프로세스 집합에 대한 평균 대기 시간을 최소화하여 최적화할 수 있다. 

++ 이것도 다 정확한 cpu burt 를 알 때 할 수 있는 방법이란다...허허...

-- 성능 : 높음

++ cpu 가 쉬지 않고 각 프로세스의 burst 에 맞게 실행하기 때문이다.

-- 공정성 : 긴 process 에게 패널티가 간다.

-- starvation : 긴 process 에게 발생할 가능성이 있다. 

++ short process 가 끝날 때까지 기다려야 하므로 무한정 기다려야 할 수 있다.

-- overhead : cpu burst 시간 추정 및 기록을 해야하므로 높을 수 있다.