OS 공부 - CPU 스케줄링, FCFS, SJF, SRTF,

 

선입 선처리 스케줄링(First-Come, First-Served Scheduling)
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)
우선순위 스케줄링(Priority Scheduling)
라운드 로빈 스케줄링(Round-Robin Scheduling)
다단계 큐 스케줄링(Multilevel Queue Scheduling)
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

 

배운점

 

CPU Scheduling Problem:
ready queue에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당해 줄 거냐

 

The solutions for the scheduling problem:
-FCFS: Fisrt-Come, First-Served -> 먼저온것 순서대로 처리(아무도안씀)
-SJF: Shortest Job first(SRTF: Shortest Remaining Time First)
짧은 job(남은 시간이 가장 짧은 것)
-RR: 시분할(time-sharing) Round-Robin
ㄴ 정해진 시간만큼만 시간 정해두고 잘라서 실행
우선순위 두지않고 시간단위로 CPU할당

 

 

-priority-based : 우선순위를 부여하겠다.
-MLQ: Multi-Level Queue: 우선순위마다 ready queue 생성, 어떤 경우에이거, 어떤경우엔 이거,
-MLFQ: 멀티레벨인데 feedback을 먹인다.

 

선입 선처리 스케줄링(First-Come, First-Served Scheduling)
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)
우선순위 스케줄링(Priority Scheduling)
라운드 로빈 스케줄링(Round-Robin Scheduling)
다단계 큐 스케줄링(Multilevel Queue Scheduling)
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

 

FCFS Scheduling

First-Come, First-Served: the simplest CPU-scheduling algorithm CPU를 먼저 요청한 process한테 무조건 배정, FIFO Queue
먼저 요청하는 프로세스가 CPU를 먼저 할당
선입 선처리 스케줄링의 문제점은 평균 대기 시간이 매우 길수 있음

 

 

수행시간이 긴 프로세스가 먼저 와버려서 수행시간이 짧은 프로세스들은 긴시간을 대기하여야 하고 총 처리 시간도 높다.

 

turnaroud time = P1=24, P2=27, P3=30
total turnaround: 24+27+30 = 81
Average Trunaround Time: 81/3 = 27

 

waiting time
P1=0, P2=24, P3=27
Total waiting Time: 51
Average Waiting Time: 51/3=17

 

순서교체: P2 P3 P1(수행시간이 짧은 순서)

 

 

waiting time
P1=6, P2=0, P3=3
Total Waiting Time: 9
Average Waiting Time: 9/3 = 3

 

turnaround time: P2=3, P3=6, P1=30
total turnaround time: 39
Average Turnaround Time: 13

 

=> 순서만 바꼈는데 Average waiting time 줄어듦 17->3
평균 대기시간에 영향을 미치는 요인: 프로세스가 도착한 순서
수행시간이 짧은 프로세스는 긴 프로세스가 끝날때까지 대기해야한다. 호송효과

 

Covoy Effect : 호송효과(똥차효과): 똥차하나 막혀 있어서 뒤에 있는 슈퍼카들이 못감

 

turnaround time: 출발부터 종료까지 시간
average waiting time이 최소가 아님, 순서에따라 다양함
CPU bursttime이 얼마냐에 따라서 이 프로세스 waiting time or turnaround time이 확 달라진다.

 

도착하는 순서대로 CPU선점하면 얘가 끝날때까지 CPU 안내려놓는다-> non-preemptive
CPU가 한 프로세스에게 할당되면 그 프로세스가 종료하든지 또는 입/출력 처리를 요구하든지 하여 CPU를 방출할때까지 CPU를 점유한다.

 

SJF(Shortest-Job-First)
Shortest-next-CPU-burst-first 타임이 적은걸 먼저 해보자. 오는 순서에 무관하게. 같다면 FCFS(먼저온거)
CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당
Burst Time이 짧은 순서대로 !!

 

 

waiting time
P1=3, P2=16, P3=9, P4=0
total 28
average 28/4=\7

 

turnaround time
P1=9, P2=24, P3=16, P4=3
total 52
average 52/4=13

 

FCFS 보다 waiting time과 turnaround time을 줄일 수 있다.
average waiting time 중에서 최소다.

 

짧은걸 앞에 두면(시간) -> waiting time 감소
그러나 next CPU burst time 을 알 수가 없다. =>예측
다음 CPU 요청의 길이를 파악하는 것이 힘듦

 

예측하는 방법:
과거에 측정된 시간-> exponential average (지수적 평균)
최근에 많이 썼으면 가중치를 둔다.
SJF 스케줄링의 근사치를 구하기 위하여 다음 CPU의 길이를 예측
전 CPU 버스트의 측정된 길이의 지수 평균(Exponential Average)

 

 

T_n : n번째 CPU 버스트의 길이
T_n+1 : 다음 CPU 버스트의 예측된 값
0<=a<=1
a : 확률을 의미

 

 

ㄴ 대충 비슷하다.

 

SJF preemtive 할 수도, non-preemptive할 수도 있다.
실행되고 있는 거 context switch하고 짧은거를 갖다 넣는다. -> preemtive
기존꺼 끝나고 넣는다 -> non preemptive
성능차이가 있다 !

 

SRTF Scheduling:
SJF에서 excuting 된 때보다 짧으면 걔를 실행시킬거냐?
preemtive SFJ Scheduling
새로 도착한 프로세스가 현재 프로세스의 remaining time보다 적으면 선점시켜서 쫓아내겠다.

 

 

=> remaining time 보다 더 짧은게 도착시 선점

 

 

total waiting time: [(10-1)+(1-1)+(17-2)+(5-3)]= 26
Average waiting time: 26/4 = 6.5

 

SRTF < SJF waiting time 더 길다.
다른 케이스로 프로세스의 도착시간과 버스트시간에 따라 비선점형 스케줄링이 더 좋을 수 있다.

 

RR Scheduling
Round-Robin: preemptive FCFS with 시분할(time quantum)(=time slice)
process 들어 왔을 때 일정 time quantum 지나면 너, 나가(watch dog라는애가 시킴)
ready Queue: circular queue

 

 

 

quantom보다 더 긴 CPU burst time 을 갖고 있으면 interrupt를 걸어준다 -> context switch -> ready queue

 

 

waiting time
P1 =10-4=6 ,P2 = 4, p3 = 7

 

RR에서 Average waiting time 오히려 더 길어질 수 있다.
RR은 preemptive다.

 

time quantum에 따라 RR성능 좌지우지 된다.
turnaround time 도 다양함
time quantum 많이 줘도, 적게줘도 안좋음

 

Priority-base Scheduling 우선순위
각 process에 priority를 associate 한다. 우선순위가 같으면 FCFS
SJF 처럼 next CPU burst time이 적은 애에게 낮은 가중치를 준다.

 

average waiting time: 8.2

 

preemptive(SRTF) 하게 할거냐 non preeptive(SJF) 하게 할거냐

 

starvation(기아) : 무한대 대기
계쏙 짧은거 (priority)가 높은게 들어와서 실행 못하고 대기만 한다.
=> aging을 하자(나이): 오랜 시간 대기하면 priority를 높여주자

 

RR(퀀텀)+Priority scheduling(우선순위) 섞자
높은 우선순위 부터 하다가 우선순위 같으면 RR로 하자

 

 

 

MULTI-Level Queue(MLQ)

 

 

하나의 스마트폰에 동시에 일어나는 process 들이 있고 , 저마다 priority를 갖는다.

 

 

분리된 ready Queue에 각각 priority 부여한다.

 

highest priority

 

 

맨위에 큐 비면 다음거 실행, 큐 비면 다음꺼 실행, 큐 비면 다음 꺼실행..

 

Multi-Level Feedback Queue (MLFQ)
우선 순위 높은거만 해주다가 Queue 실행 안 될 수도 있기 때문에,,

 

짧게 실행하고 빠져나가자, 다 실행 못하고 waiting 큐에 들어가는데
두번째는 16을 줬다. 여기서 빠져나오는건 CPU를 더 많이 쓸 수 있다.
점점 더 많은 CPU burst time을 할당받기 때문에 그 다음은 남은시간 다 쓸 수 있다.

 

CPU-bound(CPU 많이 쓰는 애)는 CPU 할당 시간 점점 많이 받고 적게 쓰는 애는 우선순위가 높으니까 빨리 처리하고 빠져나가고 , 자주 들어올 기회가 생긴다.
=> 실제 OS CPU스케줄링 알고리즘이다