Process는 그 특성에 따라 다음 두 가지로 나눈다
CPU bound job- CPU를 길게 쓰고, I/O를 짧게 쓰는 작업
- few very log CPU bursts
- 계산 위주의 job
- ex) 과학적 연산 등 연산이 오래 걸리는 작업을 수행하는 경우
- CPU를 길게 쓰고, I/O를 짧게 쓰는 작업
I/O bound job- CPU를 짧게 쓰고, I/O를 길게 쓰는 작업
- many short CPU bursts
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- ex) 사람과 Interaction을 많이 하는 경우
- CPU를 짧게 쓰고, I/O를 길게 쓰는 작업
- 여러 종류의 job(=process)이 섞여 있기 때문에 CPU Scheduling 이 필요하다
- Interactive job에게 적절한 response 제공 요망
- 사람과 Interaction을 하는 job
- CPU와 I/O 장치 등 system 자원을 골고루 효율적으로 사용
- Interactive job에게 적절한 response 제공 요망
- I/O bound job이 CPU를 빨리 얻을 수 있도록 하는 목적
- CPU를 먼저 주어야 빨리빨리 CPU를 쓰고 나가기 때문
- 사람과 interaction 하기 때문에 빠른 응답성 제공 필요
- 쓰고 나서는 바로 I/O 작업이 아루어지는데, CPU를 못주고 있으면
- 운영체제 코드 중 CPU scheduling을 하는 code
- Ready 상태의 process 중에서 CPU를 줄 process를 고른다
- CPU의 제어권을 CPU Scheduler에 의해 선택된 process에게 넘긴다
- 이 과정을 context switch 라고 한다
Process에게 다음과 같은 상태 변화가 있는 경우
- Running → Blocked (e.g. I/O 요청하는 system call)
- Running → Ready (e.g. 할당 시간 만료로 timer interrupt)
- Blocked → Ready (e.g. I/O 완료 후 interrupt)
- Terminate
→ 1, 4 에서의 scheduling은 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)
→ 그 외 다른 scheduling은 preemptive (= 강제로 빼앗음)
Performance Index (= Performance Measure, 성능 척도)
- CPU Utilization (이용률)
- keep the
CPU as busy as possible - CPU를 놀게 하지 않고 이용률은 높을 수록 좋다
- keep the
- Throughput (처리량)
number of processesthatcompletetheir execution per time unit- 처리량은 많을수록 좋다
- Turnaround Time (소요 시간, 반환 시간)
- amount of time to
execute a particular process - CPU burst를 하고 나서, I/O burst를 하러 나가기까지 전체 시간
- ready queue에서 기다린 시간 + 실제로 CPU를 쓴 시간
- amount of time to
- Waiting Time (대기 시간)
- amount of time a process has been
waiting in the ready queue - 처음으로 기다리는 시간이 아닌, CPU를 쓰러 와서 기다린 전체 시간의 합
- amount of time a process has been
- Response Time (응답 시간)
-
amount of time it takes
from when a request was submitted until the first response is produced, not output(for time-sharing environment)
-
CPU를 쓰러 들어와서 처음 쓰기까지의 시간을 뜻함
- process가 시작해서 처음 CPU를 쓰기 까지의 시간 아님!!
-
- 설명
- ready queue에 먼저 들어온 process 순으로 실행한다
- 문제점
Convoy effect (호위 효과)- short process behind long process
- 오래 걸리는 process가 먼저 도착해서 CPU를 오래 쓰는 탓에 짧게 걸리는 process가 오래 걸리게 되는 것
-
설명
- 각 process의 다음번 CPU burst time 을 가지고 scheduling에 활용
- CPU burst time이 가장 짧은 process를 제일 먼저 schedule
- CPU를 가장 짧게 쓰려는 job에게 제일 먼저 CPU를 주는 것
-
종류
Two schemes
Non-preemptive (비선점)- 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 선점 (preemption) 당하지 않음
Preemptive (선점)- 현재 수행중인 process의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 process가 도착하면 CPU를 빼앗김
- 이 방법을
Shortest-Remaining-Time-First (SRTF)라고도 부름
-
특징
- SJF is
optional- 주어진 process들에 대해
minimum average waiting time을 보장한다 - 대기 시간 측면에서 최적이다
- 주어진 process들에 대해
- A priority number (integer) is associated with each process
- high priority를 가진 process에게 CPU 할당
- (smallest integer = high priority)
- high priority를 가진 process에게 CPU 할당
- SJF는 일종의 priority scheduling이다
priority = predicated next CPU burst time
- SJF is
-
문제점
Starvation- low priority processes may never executed
Aging- as time progresses increase the priority of the process
-
다음 CPU Burst Time 의 예측
다음번 CPU burst time을 어떻게 알 수 있을까? (input data, branch, user …)
- 추정만이 가능하다
- 과거의 CPU burst time을 이용해서 추정 (exponential averaging)
A priority number (integer) is associated with each process
- 특징
highest priority를 가진 process에게 CPU를 할당- smallest integer == highest priority
- SJF는 일종의 priority scheduling이다
- 문제점
Starvation: low priority process may never execute
- 해결
Aging: as time progresses, increase the priority of the process
-
특징
-
각 process 는 동일한 크기의 할당 시간 (time quantum) 을 가진다
- 일반적으로 10 - 100 ms
-
할당 시간이 지나면 process는 선점당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다
-
n개의 process가 ready queue에 있고, 할당 시간이 q time unit인 경우, 각 process는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
→ 어떤 process도 (n-1)q time unit 이상 기다리지 않는다
-
-
Performance
- q large → FCFS
- q small →
context switchoverhead가 커진다
-
장점
- 일반적으로 SJF보다 average turnaround time이 길지만,
response time은 더 짧다
- 일반적으로 SJF보다 average turnaround time이 길지만,
-
Ready queue를 여러개로 분할
foreground- interactive job
background- batch job (no human interaction)
-
각 queue는 독립적인 scheduling algorithm을 가짐
foreground- RR
background- FCFS
-
Queue에 대한 scheduling이 필요
각 queue 마다 wait을 주는 것
- Fixed priority scheduling
- 두 개의 우선 순위 그룹을 나눈다 (foreground, background)
- serve all from foreground then from background
- foreground에 속한 process들이 먼저 모두 실행되고 나면, 그 다음에 background group에 속한 process들을 실행한다
- possibility of starvation
- Time slice
- 각 queue에 CPU time을 적절한 비율로 할당
- e.g.
- 80% to foreground in RR
- 20% to background in FCFS
- Fixed priority scheduling
-
Priority 별 queue 분배
한번 정해진 queue는 바뀌지 않는다
-
Process가 다른 queue로 이동 가능
- 상위 queue가 우선순위가 높다
- 상위 queue가 비어야 하위 queue가 채워진다
-
aging을 이와 같은 방식으로 구현할 수 있다
- aged job을 상위 queue로 보내기
-
Multilevel feedback queue scheduler 를 정의하는 Parameters
- Queue의 수
- 각 queue의 scheduling algorithm
- Process를 상위 queue로 보내는 기준
- Process를 하위 queue로 내쫓는 기준
- Process가 CPU 서비스를 받으러 할 때, 들어갈 queue를 결정하는 기준
-
e.g.
-
Three queues
- Q0 - time quantum 8 ms
- Q1 - time quantum 16 ms
- Q2 - FCFS
-
Scheduling Flow
- new job이 queue Q0로 들어감
- CPU를 잡아서 할당 시간인 8ms 동안 수행됨
- 8ms 동안 다 끝내지 못했으면 Q1으로 내려감
- Q1에 줄서서 기다리다가, CPU를 잡아서 16ms 동안 수행됨
- 16ms 안에 끝내지 못한 경우 Q2로 쫓겨남
-
CPU가 여러 개인 경우 scheduling은 더욱 복잡해짐
-
Homogeneous process인 경우누구나 처리할 수 있는 역량이 똑같은 CPU
- Queue에 한줄로 세워서 processor가 알아서 꺼내가게 할 수 있다
- but, 반드시 특정 processor에서 수행되어야 하는 process가 있는 경우에는 문제가 더 복잡해진다
-
Load sharing(= Load balancing)- 일부 processor에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 queue를 두는 방법 vs 공동 queue를 사용하는 방법
-
Symmetric Multiprocessing (SMP)- 각 processor가 각자 알아서 스케줄링 결정
- 균일한 작업을 여러곳에서 할 때는 조율하는 processor가 없는게 효율적일 수도 있다
-
Asymmetric multiprocessing- 하나의 processor가 system data의 접근과 공유를 책임지고, 나머지 processor는 거기에 따름
Hard real-time systems- 정해진 시간 안에 반드시 끝내도록 scheduling 해야 함
- 그러기 위해 process들의 CPU 도착 시간을 미리 알고 scheduling 하는 경우도 있다 (off-line scheduling)
- ↔ online scheuluing
- system이 실행중에 동적으로 process를 scheduling
- 작업이 도착하는 시점에서 결정을 내릭 때문에, 실행 시점에 알려진 정보만 사용할 수 있다
- ↔ online scheuluing
Soft real-time computing- 일반 process에 비해 높은 priority를 갖도록 해야 함
- e.g. 동영상이 끊기지 않도록 동영상 재생 process가 먼저 CPU를 얻을 수 있도록 priority를 높이기
하나의 process 안에 CPU 수행 단위가 여러개 있는 것
Local Scheduling- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 scheduling 할지 결정
Global Scheduling- Kernel level thread의 경우 일반 process와 마찬가지로, kernel의 단기 scheduler가 어떤 thread를 scheduling 할지 결정
Queueing models- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
Implementation & Measurement- 실제 시스템에 알고리즘을
구현하여 실제 작업에 대해서 성능을측정하여 비교
- 실제 시스템에 알고리즘을
Simulation- 알고리즘을 모의 프로그램으로 작성 후
trace를 입력으로 하여 결과 비교 - trace 란?
- simulation의 input이 되는 data
- 신빙성이 있어야함 (실제 프로그램의 동작을 대변할 수 있어야 함)
- 알고리즘을 모의 프로그램으로 작성 후