•
참고 강의
contents
CPU Scheduling
CPU bound job에게 CPU를 뺏겨서 사람과 interaction하는 I/O bound job이 CPU를 받기 위해 지나치게 오래 기다리지 않도록 하는 방향으로 CPU Scheduling이 이루어져야 한다.
효율적인 스케줄링
효율적인 스케줄링nonpreemptive(비선점형)
자진 반납할 때까지 CPU를 보장해주는 방식
preemptive(선점형)
강제로 CPU를 빼앗을 수 있는 방식(현재의 스케줄링 방식)
Scheduling Criteria
Performance Index(= Performance Measure, 성능, 척도)
어떤 알고리즘이 더 좋은 지 평가할 수 있는 방법
시스템 입장에서의 성능
: CPU 하나로 최대한 일을 많이 시키면 좋은 것
•
CPU utilization(이용률)
: 전체 시간 중에 CPU가 놀지 않고 이용 당한 시간 비율
◦
CPU는 가능한 바쁘게 일을 시켜라!
◦
CPU가 바쁜 것이 곧 시스템이 CPU를 잘 사용한 것
•
Throughput(처리량)
: 주어진 시간동안 몇개의 작업을 처리했는가
◦
주어진 CPU를 가지고 주어진 시간에 일을 더 많이 처리하면 좋은 것
프로그램 입장에서의 성능
: 프로세스가 CPU를 빨리 얻어서 빨리 끝나면 좋은 것
•
Turnaround time(소요시간, 반환시간)
: CPU를 쓰기 위해 들어와서 다 쓰고 나갈 때까지 걸리는 시간(CPU burst 끝나고 나갈때까지 걸린 시간)
◦
CPU를 얻어서 순수하게 Running한 시간 + Waiting time = Turnaround time(들어와서 나갈 때까지 걸린 총 시간)
◦
특정 프로세스를 실행하는 총 시간
→ 프로세스가 시작돼서 종료될 때까지의 시간
→ 이 프로세스가 CPU를 쓰기 위해 들어와서 CPU를 쓰고 I/O를 하러 나갈 때까지 걸리는 시간
•
Waiting time(대기 시간)
: CPU를 쓰기 위해 Ready Queue에 줄서서 기다리는 시간
•
Response time(응답 시간)
: Ready Queue에 들어와서 처음으로 CPU를 얻을 때까지 걸리는 시간
◦
Time Sharing 환경에서는 처음으로 CPU를 얻는 시간이 사용자 응답과 관련해서 굉장히 중요한 시간의 개념
Waiting time과 Response time의 차이
•
선점형 스케줄링의 경우에는 CPU를 강제를 빼앗길 수 있다. 따라서 한 번의 CPU burst동안에도 CPU를 얻었다 뺏겼다를 반복한다. 줄서서 기다리는 시간들이 여러 차례 발생하게 된다.
기다린 시간들을 다 합친 개념이 Waiting time•
Ready Queue에 들어와서 최초의 CPU를 얻을 때까지의 시간을 Response time
System마다 중요하게 생각하는 성능이 다르다!
공평성(Fairness)
성능 지표가 상충되는 경우
Scheduling Algorithm
FCFS(First-Come First-Served)
먼저 온 순서대로 처리
•
FIFO(First in First out) 스케줄링
•
비선점형 스케줄링 방식
•
효율적인 방식은 아니다.
ex. CPU 사용 시간이 긴 프로세스가 먼저 들어오게 된다면 Interactive한 job들이 도착하더라도 기다려야 한다.
Interactive job의 응답시간이 대단히 길어지기 때문에 좋은 스케줄링 방식 아니다. 평균 Waiting time이 늘어난다. 평균 Response time이 길어진다.Convoy effect
•
긴 프로세스때문에 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상
•
Queue에서 오래 기다리는 현상을 의미하는 말
FCFS 스케줄링은 너무 단순하고 단점이 있어서 바로 실제 System의 스케줄링 기술로 쓰기에는 힘듦.•
FCFS의 장점
1.
Ready 상태 프로세스들의 개수와 크기를 짐작할 수 있다.
2.
각각의 프로세스들이 언제쯤이면 실행될 수 있는지 예측 가능하다.
3.
도착 순서만이 실행 순서를 결정짓다는다는 관점에서 공평하다고 말할 수 있다.
•
다른 스케줄링 기법의 보조 장치로써 역할을 할 수 있다.
ex) 우선순위가 동일할 경우, FCFS 스케줄링 방식으로 프로세스 처리하기
SJF(Shortest-Job-First)
짧은 실행시간(CPU burst가 짧은) 가진 프로세스에게 먼저 순서를 주자
•
Queue가 전체적으로 짧아지게 된다.
•
Average Waiting time이 가장 짧아지게 된다.
nonpreemptive한 경우
•
SPN(Shortest Process Next) 스케줄링
•
일단 CPU를 잡으면 이번 CPU Burst가 완료될 때까지 CPU를 선점당하지 않음
example
preemptive한 경우
•
SRT(Shortest Remaining Time) 스케줄링
•
Ready Queue에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식
•
CPU를 줬다고 하더라도 더 짧은 프로세스가 도착하면 CPU를 빼앗고 그 프로세스에게 CPU를 넘겨준다.
•
해당 방식보다 더 짧은 시간의 Average Waiting time은 나올 수 없다.(minimum)
example
Average Time를 최소화하는 것은 preemptive한 버전이다. 스케줄링을 언제 진행할지에 대한 부분에서 차이가 있다.SFJ의 문제점
1.
Starvation
: CPU 사용 시간이 짧은 Job를 먼저 실행하도록 한다. 그러면 사용 시간이 긴 Job은 실행할 수가 없어진다.
•
Long Process Starvation
•
무한 대기 현상
2.
CPU 사용 시간을 미리 알 수 없다.(예측 가능성이 떨어진다)
•
각 프로세스의 크기를 실행 전에는 정확히 알 수 없음에도 불구하고 그 크기를 가지고 스케줄을 해야 한다.
•
알 수는 없지만 과거에 CPU를 사용했던 흔적(CPU burst time)을 통해서 사용 시간을 추정은 할 수 있다.
exponential averaging(지수 평균): 비슷한 환경에서 반복적으로 실행되어지는 프로세스들에 대해서 적용할 만 하다.
tn | n번째 실제 CPU 사용 시간 |
τn+1 | n+1번째 CPU 사용 시간의 예측치 |
τn+1 = atn + (1-a)τn (a, 0 < a < 1)
예측 시간은 n번째 실제 CPU사용 시간과 n번째 예측했던 CPU 사용 시간을 일정 비율씩 곱해서 더한 값이다.
•
예측한 값을 토대로 가장 burst time이 적은 프로세스에게 CPU를 주게 된다.
SPN를 수정해서 평균 응답 시간을 줄일 순 없을까?
SRT에서의 잦은 문맥교환을 줄이는 방법
Priority Scheduling
우선 순위가 가장 높은 프로세스에게 CPU를 주겠다.
nonpreemptive한 경우
•
일단 CPU를 잡으면 이번 CPU Burst가 완료될 때까지 CPU를 선점당하지 않음
preemptive한 경우
•
우선순위가 더 높은 프로세스가 들어온다면 해당 프로세스가 CPU를 빼앗을 수 있다.
프로세스마다 해당 프로세스를 나타나는 우선순위가 정수값으로 나타나게 된다. 우선 순위가 가장 높은 프로세스를 정수 중 제일 작은 정수로 나타낸다.•
SJF 스케줄링도 Priority Scheduling의 일종이다.
priority = predicted next CPU burst timePriority Scheduling의 문제점
1.
Starvation
: 우선 순위가 낮은 프로세스는 영원히 CPU를 받지 못할 수도 있다.
Aging를 도입: 우선 순위가 낮은 프로세스라도 너무 오래기다린다면 우선순위를 높혀주자. 언젠가는 CPU를 얻게 되니깐 Starvation를 막게 된다.
HRRN 스케줄링
Round Robin(RR)
CPU를 줄 때 동일한 시간의 할당시간을 세팅해서 주고 해당 시간이 끝나면 CPU를 뺏고 Ready Queue에 올린다.
•
현대에 사용하는 CPU 스케줄링은 라운드 로빈에 기반하고 있다.
•
응답 시간이 빠르다 → 줬다 뺏었다 하게 된다.(선점형 방식)
•
CPU를 짧게 사용하는 프로세스가 얼른 쓰고 나갈 수 있게 해주는 것이 Round Robin 스케줄링 방식의 중요한 장점이다.
n개의 프로세스가 있고 각각 할당받은 시간이 q라고 한다면, 내가 적어도 1/n라는 시간으로 CPU를 얻을 기회가 생긴다.
(n-1)q time unit 이상 기다리지 않는다. → 응답 시간이 빠르다. 대기 시간이 본인이 CPU를 사용하는 시간과 비례하게 된다.if, 할당 시간을 크게 잡으면 : FCFS
if, 할당 시간을 잘게 잡으면 : context switch Overhead
적당한 크기의 time quantum를 주는 것이 바람직(10-100ms, system이 발전하면서 값이 얼마든지 변경될 수 있다.) SJF보다 average turnaround time이 길지만 response time은 더 짧다.→ 시간을 할당하다보니 프로세스가 모두 동일한 시간에 끝나게 된다. 따라서 average turnaround time은 길어지지만 response time은 짧아진다.
추가