[16] CPU Scheduling(1)

-- cpu scheduler 는 'dispatcher' 나 'short-term scheduler' 라고 불린다.

++ ready que 에 있는 프로세스를 하나 선택해서 cpu 에 실행시킨다.

++ scheduler 가 매우 빠르기에 모든 프로세스는 메모리 안에 있고 그 중 한 프로세스가 cpu 에서 돌고 있다고 가정한다.

 

++ 멀티 프로그래밍 환경에서 가장 중요한 것은 CPU 활용도를 최대로 하는 것이다.

 

-- Non-preemptive scheduling 은 중간에 resource를 뺐기지 않는 것을 말한다. 

++ Non-preemptive : priority 가 높은 process가 있어도 해당 time-quantum 에는 본인 process 만 실행하는 것이다

++ 발생하는 시점 : 1. CPU 에서 실행하던 프로세스가 종료된 시점. 2. running-> block 으로 상태 변환이 일어나는 시점

--> 즉 정상적으로 cpu 에 있던 프로세스가 나오는 시점???

 

process execution behavior

-- 가정 : 1 사용자 - 1 프로세스 - 1 스레드

++ 유저 한 명에 프로세스 한 개 사용한다고 가정

++ 프로세스 하나에 스레드 하나를 실행한다고 가정

++ 모든 프로세스는 resource 를 가지려고 한다고 가정 ( cpu 는 not resource , cpu time-quantum 이 resource )

 

-- 프로세스는 CPU - I/O burst 사이클에서 실행된다

++ 중요) 입출력을 해야 computing 을 할 수 있다.

++ computing 을 하는 동안 I/O 를 수행하고 이 동작을 반복한다.

 

-- 프로세스의 두 가지 타입

++ CPU-bound : 연산 위주고 I/O 는 매우 적은 프로세스

++ I/O-bound : I/O 가 대부분이고 연산은 매우 적은 프로세스, short-CPU burst ( 바이러스 check )

 

 

First-Come-First-Served ( FCFS )

-- 들어간 process 가 끝날 떄까지 running 한다. I/O 할 때도 CPU 를 놓아주지 않는다.

++ 다른 이름 : first-in-first-out, run-until-done

 

-- policy

++ 도착한 순서대로 선택해서 process 가 CPU 를 할당 받음

++ 우선 순위 없이 한 번 잡으면 안 뺏기고 끝날 떄까지 실행함 ( non-preemtive )

++ 초창기 FCFS 의 non-preemtive 는 프로세스가 끝날 때까지, 심지어 입출력할 때도 cpu 를 놓지 않는 상황을 말했는데 오늘날에는 입출력하는 상황과 같은 block 상태에서는 cpu 를 놓아주는 것이다. 

++ nachos 에서 구현해보는 것이 좋을 듯 하다.

순서대로

++ 들어온 순서대로 모든 프로세스가 끝날 때까지 다른 프로세스는 중간에 들어오지 못해서 시작조차 할 수 없다.

++ 위의 그림과 같이 첫번째로 들어온 프로세스가 가장 긴 경우 average waiting time 이 길어진다.

( average waiting time : 각 프로세스의 첫 반응이 오는 평균 시간으로 작을수록 사용자가 보기에 프로세스가 빠르게 작동하는 것으로 보임)

++ 들어온 순서를 반대로 뒤집었을 경우 가장 긴 프로세스가 뒤로 가서 average waiting time 이 감소한다.

 

Evaluation

-- Non-preemptive 스케줄링 

-- 응답시간 : burst time 이 긴 프로세스가 이른 순서에 들어오면 최소화가 어렵다.

++ "Convoy effect" : 긴 process 뒤에 따라오는 short process는 오래 기다려야 한다. 

++ cpu 와 i/o device 의 활용도를 감소시킨다. 

-- 성능 : context switching 이 적게 일어나고 단위 시간 당 수행하는 job 이 적어 좋지 않다. 

-- 공정성 : process 나 I/O burst 가 적은 경우에는 본인의 실행시간 보다 더 긴 시간을 기다려야 하므로 패널티가 간다고 느낄 수 있다.

-- starvation : 불가능함, 순서대로 모두 다 들어가기 때문이다.

-- overhead : 매우 적음, context switching 이 발생하지 않기 때문이다.

 

-> 이건 scheduling 안하는 것과 같음. 그냥 들어온 순서대로 중간에 다른 프로세스 들어오는 것 없이 실행시키기 떄문이다. 

Nachos scheduling

++ 실행하고 코드 삽입하기 ++