단일 프로세서의 스케줄링
우리는 스케줄링을 한다. 하루 계획, 일주일 계획, 한달 계획 등등 여러 계획을 세운다.
컴퓨터 시스템에는 프로세스 스케줄링을 위해서 3가지 방법이 구현되어 있다.
- long term scheduling
- 컴퓨터 시스템에 들어오는 프로세스들을 선택하고 새로운 프로세스를 생성하는 스케줄링
- medium term scheduling
- 부분적으로 또는 메인 메모리에 전체적으로 들어와있는 프로세스의 갯수를 결정하는 스케줄링
- short term scheduling
- 레디 상태에 있는 프로세스 중에서 스레드 중에서 어느 것을 cpu 에 할당할지 결정한다
- I/O scheduling
- 여러가지 입출력 장치에 대기하고 프로세스들 중에 어느 것을 선택해서 입출력 장치를 사용하게 해줄것인지 결정해준다.
이것들은 각각 목적에 맞게 응답시간, throughput, 프로세스의 효율성에 목적에 두고 그것을 최적화하기 위해 노력한다.
스케줄링 방법을 프로세스 상태 트랜지션이랑 연관지어 본다면
시스템에 들어오는 프로세스 중에서 어떤 것을 준비상태로 만들어 주는지가 롱텀
서스팬드 된것중에서 레디상태로 결정하는게 미드텀
레디 상태에 있는 프로세스중에서 레디 상태로 하는 것이 숏텀 스케줄링
미드텀은 스와핑과 관련된 기능이다.
Long-Term Scheduler
시스템에 들어오는 프로세스를 결정
프로그램이 실행되면 어느 것을 시스템에 넣을지 결정
멀티 프로그래밍의 정도를 결정
판매장에 가면 매장 입구에 사람을 들어갈지 말지 결정하는 역할
이 스케줄러에 의해 시스템 안이 얼마나 붐빌지를 결정하게 되고 너무 많이 붐비면 서비스에 만족하지 못해서 서비스 만족도를 결정한다.
프로세스를 생성할때 생각해야 할것이 운영체제가 언제 추가적인 프로세스를 생성할 것인가와
어느 것을 프로세스를 먼저 생성하게 해줄것인가 이다
이때 어느 것을 프로세스를 먼저 생성하게 해주는 방법은 가장 먼저 온 것을 가장 먼저 서비스,와 우선순위 , 기대 수행 시간, IO 요구사항 등이 있다.
Medium-Term Scheduler
스와핑 기능의 일부이다
Swapping -in decision을 미드텀 스케줄러가 한다.
멀티 프로그래밍의 정도를 결정하게 된다.
Short-Term Scheduler
디스패처라고 부른다
가장 빈번히 자주 실행되는 스케줄러이다.
어느 프로세스를 어느 cpu에 할당할 것인지 결정해주는 함수
이것은 클럭 인터럽트 입출력 인터럽트 운영체제 콜(커널 서비스시작) 시그널(세마포어)에 쓰인다.
Short-Term 스케줄러의 목적
여러가지가 있다
- 사용자의 경험을 좋게 하기 위해
- 사용자 단말
- 사용자는 즉각 대답을 얻기를 원한다. 즉 사용자의 응답성에 목적을 둔다.
- 시스템의 성능을 좋게 하기 위해
- 서버
- 시스템의 성능이 제일 관권이다. 동시접속사수 → 시작되면 접속이 끊기지않고 유지되도록 하는 목적
스케줄링의 다양한 목적
목적에 따라 스케줄링이 다르다
크게 response time 이나 throughput을 중시하는 Performance-related가 있다.
- quantitative
- easily measured
그것과 더불어서 predictability(예측가능성)를 중시하는 Non-performance-related(실시간 처리)가 있다.
- quantitative
- hard to measured
User oriented, Performance Related(성능평가 도구)
Turnaround time
시스템에 들어가서 프로세스가 끝날때까지 간격을 가지고
Response time
요청이 대답 오는데 까지 걸리는 시간
Deadlines
어떤 프로세스가 끝날때까지 걸리는 시간이 중요한 경우에 쓰이는 도구
User oriented, other
Predictability
예측 가능한 성능, 제한된 시간내에 어떤 job이 반드시 수행되는 시간을 미리 알 수 있는 도구
실시간 처리에서 설명할때 쓰인다.
System oriented, Performance Related
Throughput
시간 당 끝낼 수 있는 프로세스의 개수로, 시간 당 시스템을 통과하는 프로세스의 개수
Processor utilization
우리가 윈도우즈에서 볼 수 있는 현재 사용하고 있는 cpu 의 퍼센트
System oriented, other
Fairness
공평한지,
Enforcing priorities
우선순위를 줄 수 있는지
Selection Function
장기 스케줄러, 중기 스케줄러는 단기 스케줄러에 비해서 상대적으로 덜 빈번히 수행되어 성능에 미치는 영향은 적다. 단기가 영향을 크게 미친다.
스케줄러는 선택기능인데 여러개의 레디 상태 프로세스 중에서 어느 것을 선택할것인지가 단기 스케줄러의 역할이다.
이러한 스케줄러들은 priority, resource requirement, or 어떤 식으로 프로세스를 사용하는지 성격에 의해서 그것에 기반해서 선택할 수 있다.
실행성격을 구분해서 선택을 한다면 중요한 물리량들은
w = 시스템 안에서 얼마나 기다렸는지
e = 시스템 안에서 얼마나 수행 했는지
s = 실행시간이 얼머나 되는지
스케줄링을 측정하기 위한 기본적 물리량
Decision Mode
스케줄링을 할때 언제 스케줄러가 실행되는지에 대한 결정 모드
Non preemptive :cpu를 뺏지 못하게
preemptive : cpu를 뺏을 수 있게
Non preemptive vs preemptive
cpu의 경우 한번 프로세스가 시작이 되면 running 상태로 있고, 끝나거나 블록이 될때까지 지속적으로 되는 상태를 Non preemptive 이라 한다.
프로세스가 실행되는 중에서 다른 프로세스에 의해 인터럽트가 되는 경우가 preemptive 라고 한다. 이러한 트랜지션을 preemption이라고 하는데, 이것은 새로운 프로세스가 도착하거나 인터럽트가 발생하거나 주기적으로 preemption을 허용하는 경우 발생할 수 있다.
First-Come-First-served(FCFS)
가장 간단한 스케줄링 방법
일상 속에서 볼 수 있다
가장 먼저 온 것을 먼저 처리한다
현재 실행하고 있는 프로세스가 실행을 끝냈을때 , 가장 오래 기다린 놈을 다음으로 실행시킨다.
가장 긴 프로세스가 유리한 스케줄러이다.
cpu가 더 많이 실행되는 프로세스들이 선호되는 스케줄링 방법이다.
Non preemptive 방법이다.
Round Robin
가장 많이 쓰이고 있다.
이것은 preemption을 하는데 clock 인터럽트에 의해서 발생한다.
Time Slicing 이라고 하고 각각의 프로세스들은 제한된 시간만을 서비스를 받는다
이러한 제한된 시간을 time quantum 혹은 slice 라고도 불린다.
여러개의 프로세스가 컴퓨터 시스템을 나눴을때, time sharing 시스템에서 널리 쓰인다.
커서 위치에서 b가 들어온다. 한 퀀텀만큼, 한 스라이스 만큼 b가 동작한다. 그 이후로도 똑같이 수행
골고루 time slice 해서 수행하는 것이 라운드 로빈이다.
라운드 로빈을 수행할때 사용자의 경험을 좋게 하기 위해서는 time quantum의 크기를 사용자의 인터렉션이 끝나는 시간보다 약간 더 크게 해준다.
그와는 대조적으로 time quantum을 사용자 인터렉션보다 적게 한다면 불편을 야기한다.
Shortest Process Next(SPN)
이것은 가장 짧게 처리해야할 것으로 보이는 프로세스를 선택하는 스케줄링이다.
마트로 비유를 하자면 10개, 1개, 2개를 구매하는 사람들의 순서를 정할때 1,2,10으로 하면 서비스 질이 올라간다고 보는 것이다. 즉 가장 짧은 프로세스 먼저 처리하는 스케줄링이다.
Non preemptive 방법이기 때문에 한번 실행이되면 끝날때까지 cpu를 차지한다.
그래서 short 프로세스들이 줄의 맨앞으로 점프하는 방법인데 실행시간이 긴 프로세스들으 starvation이 발생할 수 있다.
expected 시간을 어떻게 계산할 것인지 문제가 발생할 수 있다.
프로그램의 경우 실행 시간에도 쓰레드에 흘러가는 프로그램 카운터가 달라질 수 있기 때문에 현실적으로 정확하게 구하기 어렵다.
B가 돌아가는 동안 CDE가 도착, E가 먼저 수행
VRR
IO가 빈번한 잡의 경우 따로 큐를 만들어서 처리해주는 방법이 가상 라운드 로빈 방법이다.
별도의 큐를 만들어서 소규모의 서비스를 받는 큐를 따로 만든다. 레디 큐에서 기다리게 하고 io바운디드 잡은 다른 큐에서 기다리도록 한다.
Shortest Remaining Time(SRT)
이것은 SPN의 Preemptive 버전이다
Shortest expected Remaining Time을 갖는 프로세스를 선택하도록 한다
긴 프로세스들이 starvation이 발생할 수 있다.
서비스를 하는 중간에도 서비스 타임이 조금 남은 것이 언제든지 끼어들 수 있기 때문에 response time이 좋은 성능을 갖게 된다.
그리고 superior turnaround를 갖게 된다.
B는 6유닛 만큼 실행 c가 도착했을 때 c가 남은 시간이 더 짧아서 c가 먼저 수행된다.
Highest Response Ratio Next HRRN
Ration를 가장 크게 하는 프로세스를 선택하는 방법
오래기다린 것을 먼저 선택하도록한 방법
Shorter job을 선호하지만 aging한 starvation을 방지하는 방법이다.
Feedback Scheduling
레디 큐에 프로세스가 들어와서 실행되다가 프로세스를 충분히 사용하면, 타이머 인터럽트가 올때까지 실행이 됐다면 그 다음 레디큐로 내려가서 cpu를 충분히 쓴 job들은 밑으로 내려가서 큐에 쌓이게 되고 cpu를 적게쓴 i/o job 들은 점점 위로 올라가서 싸이게 되어 프로세스의 동작을 반영해서 큐를 관리하는 방법이다
Performance Comparison
스케줄링 방법의 성능을 비교하기 위해서 큐잉 이론이 반영이 된다.
Fair-share scheduling
프로세스 집합(process sets)에 대해서 스케줄링 하는 방법이 있다.
그중에 특히 공정성(Fairness)을 강조해서 스케줄링 하는 방법이다.
Traditional Unix scheduling
피드백 스케줄링, 라운드 로빈 스케줄링을 유닉스에서 쓰인다.
SVR3와 4.3 BSD 유닉스에서 자주 쓰인다.
좋은 response time과 low-priority background jobs이 기아상태가 안일어나게 해준다.
Band
프로세스들은 우선순위에 의해서 여러개의 bands로 나뉘게 된다.
