운영체제 9 - Uniprocessor Scheduling 


컴퓨터 시스템에서는 프로세서 스케쥴링을 위해서 3가지 방법이 구현되어있다.
이것들은 응답시간이나 throughput이나 프로세서의 효율성에 목적을 두고 그것을 최적하하기 위해서 노력한다.


long term scheduling - 컴퓨터 시스템에 들어오는 프로세스들을 선택을하고, 그 새로운 프로세스를 생성하는 스케줄링 
medium term scheduling - 부분적으로 또는 메인메모리 전체적으로 들어와있는 프로세스의 개수를 결정하는 역할을 한다.
short term scheduling - 레디상태에 있는 프로세스나 스레드 중에서 어느것을 cpu에 할당할지 결정한다.
io scheduling - 여러가지 io장치에 대기하고 있는 프로세스중 어느것을 선택해서 io장치를 사용하게 해줄것인지 결정


스케줄링 방법으르 process stats transitions과 관련지어서
시스템에 들어오는 프로세스 중에서 어떤것을 레디상태로 만들어줄지 결정하는게 long term
suspend 된것들중 ready 상태로, 메인메모리로 들어오게 결정하는것이 mid term 
레디상태에 있는 프로세스들 중 running 상태로 어떤것을 선정할것인가 하는것이 short term에 의해 결정

block된 경우에도
suspend 된것중 어느것을 메인메모리로 가져오게 할것인가 하는것이 mid term 
결국 mid term scheduling은 swapping과 관련된 기능


각각의 화살표는 상태들간의 천이를 나타내고, 천이를 결정하는것이 어떤것인가 표현한 그림
running,ready,block 상태간의 천이를 결정하는건 short term
suspend 된것을 그렇지 않은 상태들로 천이를 결정하는건 mid term
시스템으로 새로 들어오고 나가는걸 결정하는게 long term


구현의 입장에서 큐와 관련지어 표현해보면
레디큐에서 프로세스에 할당하는걸 결정하는게 short
suspend 된것중 레디큐에 다시 집어넣는것을 결정하는게 mid
시스템에 들어오는 job중 어느것을 레디큐에 넣을지 결정하는게 long


시스템에 들어오는 프로세스를 결정한다
프로그램이 실행이 되면 어느것을 시스템에 집어넣을지 결정하는것
멀티프로그래밍의 정도를 결정한다
예를 들어 매장에 사람을 들어가게 할지 말지 결정하는것

시스템 안이 얼마나 붐빌지 결정, 너무 붐비면 서비스에 만족하지 못할것, 서비스의 만족도를 결정

프로세스를 생성할때 생각할것이
운영체제가 언제 추가적인 프로세스를 생성할것인가, 어느것을 생성할것인가 하는 문제가 있다
간단한것은 먼저온것, 또는 우선순위나 예상 실행시간등을 고려하여 판단하는 방법이 있다.


swapping 기능의 일부
swapping-in decision을 mid term scheduler가 하게 된다
이것도 멀티프로그래밍의 정도, 실행하고 있는 프로세스의 개수를 결정하게 된다.


short term scheduler는 dispatcher라고도 한다
가장 빈번히 실행된다.
어느 프로세스를 어느 스레드를 cpu에 할당해줄지, 미세한 결정을 하는 함수
clock interrupt 불릴때, io interrupt가 불려서 현재 실행하는 프로세스가 실행할수 없게될때, operating system calls을 부름으로서 커널 서비스를 시작해야 할때, signals 세마포어 같은것을 사용해서 현재 가능한 자원을 사용할때
short term scheduling이 불려서 다음에 cpu를 할당받을 프로세스나 스레드를 결정하게 된다.


short term scheduler의 목적은
사용자의 경험을 좋게하고 - 사용자 단말
시스템의 성능을 좋게하기 위함 - 서버

사용자는 즉각 대답을 얻기를 원함 response time
서버는 언제 끝나는지, 시스템의 성능이 관건
서로 다른 목적을 갖게 되면 스케줄링 방법이 달라진다


스케줄링의 다양한 목적에 따라서, 여러 스케줄링 방법이 제안되어 있다
크게 response time ,through put 을 중시하는 performance-related 방법이 있고
predictability 예측가능성을 목표로 하는 non-performance-related 스케줄링 방법이 있다

이 장에서는 performance-related 방법을 알아보고
나중에 실시간 처리와 관련하여 non-performance-related 스케줄링 방법을 알아본다 

performance-related 방법은
정량적으로 측정가능한 부분이 많이 있고, 쉽게 측정이 가능하고, 목적에 맞춰서 스케줄링할수있는 방법이다

predictability와 관련된것은 
정성적으로 표현되고, 측정하기 어렵고 만들기도 어렵다


performance-related 방법의 성능평가 도구는
turnaround time - 시스템에 들어가서 서비스가 끝날때까지 간격
응답시간 - interactive process의 경우 요청을 했을때, 요청이 대답 오는데까지 걸리는 시간
deadline - 어떤 프로세스가 끝날때까지 걸리는 경우, 예를 들어 자동차의 브레이크 밟을시 데드라인

예측가능성 - 제한된 시간내 job이 반드시 실행이 되는 시간을 미리 알수있는것(실시간 처리에서)

throughput - 시간당 끝낼수 있는 프로세스의 개수
시스템의 utilization - 현재 사용하고 있는 cpu의 %

공정성
우선순위를 줄수있는지


보통 우리가 우선순위를 주기 위해서는 여러개의 큐를 사용하게 된다
프로세서 생성이 되면 레디큐를 여러개 둔다.
프로세스가 하나일때 short term scheduler가 선택해서 어떤곳에 할당할 것인지 결정

은행에 창구가 여러개이고, 우선순위가 높은일을 먼저 처리할수 있는것과 같다


장기 스케줄러와 중기 스케줄러는 디스패쳐에 비해 상대적으로 덜 실행된다
그래서 성능에 영향이 적다, 디스패쳐는 성능에 영향이 크다

결국 스케줄러는 선택기능
여러개의 레디상태 프로세스중 어느것을 다음에 cpu할당받게 선택할것인가 하는것이 디스패쳐의 역할
이것은 우선순위와, resource requirement와 실행 성격에 따라 기반하여 선택할수 있다

실행 성격에 기반한다면 중요한것은
w = 시스템 안에서 얼마나 기다리는지, wait time
e = 얼마나 오래동안 수행했는지, execution time
s = 실행시간이 얼마나 되는지, service time
이 세가지가 스케줄링을 하기 위한 기본 물리량이다


이러한 값을 가지고 여러가지 스케줄링 방법을 만들수 있다
각각은 preemptive, non-preemptive로 구분가능

FCFS - first come first served
가장 오래 기다린 프로세스,스레드 선택
throughput은 강조 x
...

round robin
골고루
throughput 낮다.

SPN - short process next
서비스타임 최소화
throughput 높다

SRT - shortest remain time
execution 시간 최소화하기 위해서 선택
..

HRRN - hightest response rate next
wait time, service time을 가지고 rate에 의해서 최대한을 선택

Feedback
알고리즘으로 feedback 해서 선택


스케줄링을 할때 언제 스케줄러가 실행되냐 하는것에 관한 decision mode
preemptive - 프로세스를 뺏음, 선점
non-preemptive - 프로세스를 뺏을수 없음, 비선점


cpu의 경우에는 한번 프로세스가 시작이 되면
러닝상태로 끝나거나 아니면 io때문에 블록될때까지 지속적으로 실행하는것을 비선점
프로세스가 실행중에도 다른 프로세스에 의해 interrupt 될수 있는 경우, interrupt되어 러닝상태에서 레디상태로 옮겨갈수 있는경우를 선점이라고 함, 
새로운 프로세스가 도착하거나, 인터럽트가 발생하거나, 선점을 허용하는 스케줄러에 의해서 일어날수 있다.


예시


다 배우고 각각 계산해보기


FCFS
현재 실행하고 있는 프로세스가 실행을 끝냈을때, 가장 오래기다린 프로세스를 선택
가장 긴 프로세스가 좋은 성능을 보임
마트에서 물건 많이 산 사람과 같다.
cpu가 더 많이 실행되는 프로세스가 선호되는 결과를 낳는다

비선점이기에 한번 실행시 끝까지 실행되게 된다.


라운드로빈
시간 인터럽트에 의해 선점한다
time slicing이라고도 한다.
각각의 프로세스들은 제한된 시간만을 서비스를 받고, 그외에는 선점된다
그 제한된 시간을 time quantum, slice라고 한다

여러개의 프로세스가 컴퓨터시스템을 나눴을때, time sharing에서 사용
골고루 fair하게 time slice를 나눠서 스케줄링


라운드로빈 스케줄링시 사용자의 경험을 좋게 하기 위해서는
time quantum의 크기를 사용자의 interaction이 끝나는시간보다 약간 크게 만든다면
사용자는 항상 모든 response를 time quantum 안에 끝날 수 있기 때문에, 성능을 좋게 할수 있다.
사용자가 느끼는 응답시간을 좋게 만들면서 여러 사용자가 cpu를 나눠쓸수 있다
time quantum을 interaction이 끝나는 크기보다 약간 크게 해서 좋은 성능을 얻을수 있다
response time 을 잘 측정해서 time quantum을 결정한다


만약 time quantum을 상호작용 시간보다 작게 만든다면
중간에 다른 프로세스에 의해 인터럽트가 발생하므로 사용자는 불편함을 느낀다


SPN - 가장 짧게 처리할것으로 보이는 프로세스로 선택하는 비선점 policy
마트에서 1개만 계산하는 사람을 먼저 처리하는것과 비슷
한번 cpu가 프로세스를 점유하게 되면 그것이 끝날떄까지 cpu를 차지하고 사용
short process가 줄의 맨 앞으로 점프하는 방법이다

다만 긴 프로세스는 starvation 발생할수 있고,
시작하기 이전에 expected time 계산하기는 어렵다.

그래서 require processing time을 time average 이용해서 구한다


io가 빈번한 job의 경우에는 결국 래디큐에서 많이 기다렸다가 잠시 서비스를 받고 다시 많이 기다리는 상황이 발생하기에
cpu를 많이 사용하는 job에 비해서 상대적으로 차별받게 된다
그래서 io가 빈번한 job의 경우 따로 큐를 만들어서 처리해주도록 하는 방법이 virtual round robin 방법이다

별도의 큐를 만들어서 소규모의 서비스를 받는, 물건을 조금 산 사람은 따로 줄을 서서 처리해주도록 한다.



프로세스의 실행시간 예측을 위해서 사용한 점화식을 풀면
최근것은 알파라는 factor로, 나머지는 지수적으로 시간에 비례해서 감소하도록 되어있다
알파가 크다면 최근을 많이 반영하고
알파가 작아진다면 과거를 더 많이 반영하는 estimation하게 된다

검은색이 실측치라면 알파값이 크게 하면 최근의 값을 많이 반영하기에 실측치와 더 근사한 값을 추정하는것을 알수있다
이런 exponential average는 time series에 대한 예측을 위해 OS에서 활용


SRT - SPN의 선점 버전
가장 짧은 남은시간을 갖는 프로세스를 선택, 긴 프로세스가 starvation 발생가능
서비스 중간에도 언제든 서비스 시간이 짧은것이 끼어들수 있다. 그래서 response time이 좋은 성능을 갖는다
그리고 superior turnaround time을 갖는다


HRRN - 위 raito를 maximize하는 프로세스를 선택하는 방법
waiting 시간이 긴것을 먼저 선택하는, shorter 작업을 선호하지만, 오래 기다린 프로세스를 먼저 선택해서 starvation을 방지한다
비선점 방법으로 제안되었으므로 끝까지 실행됨


feedback - 레디큐에 프로세스가 들어와서 실행되다가 프로세스를 충분히 사용하면, timer interrupt 올때까지 실행했다면, 그 다음 레디큐로... 내려가서
cpu를 충분히 쓴 job들은 점점 밑으로 내려가서 큐에 쌓이게 되고, cpu를 적게 쓴 job들을 위로 올라가서 쌓이게 해서, 프로세스 동작을 반영해서 큐를 관리
이 방법이 라운드 로빈과 함께 유닉스에서 사용되고 있다


스케줄링 방법의 성능비교를 위해 큐잉이론이 사용됨
이 책에서는 그 결과만을 보여주고 있다


그 밖의 스케줄링 방법으로
프로세스 각각에 대해서가 아니라 프로세스 집합에 대해서 스케줄링 하는 방법이 있다
그중 공정성을 강조해서 스케줄링 하는 방법이 있는데
그룹 단위로 스케줄링해서 그들 사이에 공정하게 스케줄링 한다


어떤 프로그램이 프로세스 B와 C로 동작이 된다면
그것을 스케줄링하고
단독으로 실행되는 A는 그룹별로 관리되어야


유닉스
feedback, 라운드로빈 사용됨
좋은 응답시간을 interactive user에게 제공하고 낮은 우선순위의 background job을 starvation 되지 않도록 한다

multilevel feedback queue을 사용하고 queue의 스케줄링에 의해 round robin을 사용하는 방법
multilevel feedback queue는 우선순위 큐로 관리


결국 사용량에 의해 우선순위가 결정되는 방법


uniprocessor의 경우
레디큐를 여러개 두고 
cpu를 적게 사용하는 io bounded job을 먼저, 큐에서는 라운드로빈을 해서 골고루 실행되게 해주고, 우선순위가 높은것을 먼저 할당하도록 해서 전체 스케줄링을 한다


프로세스들은 우선순위에 의해 여러 밴드로 나눔
swapper가 가장 높은 우선순위
우선순위가 높은것은 먼저 cpu를 할당받기 때문에 io bounded job일수록 먼저 서비스를 받게되고
user process가 가장 나중에 서비스를 받게 된다

user process중에서도 cpu를 가장 많이 사용하는 background job이 가장 낮은 우선순위를 받게된다