Histogram of CPU-burst durations
> 대부분 (80%)의 CPU burst(execution time) 은 8ms 로 집중
CPU Scheduler : Process 내 Ready queue 를 core 들이 실행 할 수 있도록함.
Process state 변화
1. running -> wait (I/O대기)
2. running -> ready (할당시간 끝)
3. waiting -> ready (I/O가 끝난뒤)
4. running -> Termination (실행 종료)
T1 실행중.. T2 (high priority)
> preemptive (선점형) : T1 중지 > T2 실행
// 우선순위에 의해 계속 밀리면.. Race Condition 발생가능성 (기아)
<> NON : T2 대기 > T1 실행완료(wait, termination) > T2 실행
1. Scheduler : Task(process,Thread) 에 어떤 core를 할지 CPU 선택,계획
2. Dispatcher : 스케쥴링된 Task에 CPU를 실제로 할당
> 이때 CS 발생
Context Switching
1. P1실행중.. CS 발생! > PCB1에 저장 > PCB2 load > P2 실행
스케쥴링 단위
1. CPU utilization : CPU 가 얼마나 바쁜지
2. Threoughput : 단위 시간당 얼마나 많은 Task를 실행하는지
3. Turnaround Task : Process의 실행~완료 까지의 시간
4. Waiting time : Ready Queue 내의 Task 의 대기시간
5. Response time : Request 실행 > 첫 respone 까지의 시간
//보통은 5 == 3
// ex) sorting : 첫번째 정렬값이 나오는 time
>
1,2 : MAX , 3,4,5 : Min 이 좋은 case
스케쥴링 알고리즘
1. FCFS ( Come, Served //FIFO ~= 줄서기)
ex) P1, P2, P3 : 24,3,3
> P1 부터 들어왔다면?
> Avarage Waiting Time : (0 + 24 + 27)/3 =17
<> P2,P3,P1 순이라면?
> Avarage Waiting Time : ( 6+ 0 + 3) /3 = 3
>> Convoy Effect : FCFS 에서는 BurstTime 이 짧은것부터 실행! // 최적화
2. SJF (shortest Job First) : burst time 작은것부터 // optimal but 어려움
> CPU Burst Time 을 User 에게 ask OR 예측함.. > 쓰기어려움
> 1. 예측 2. 정렬 3. 배치
> 이전과 비슷할것이라 예측
// t : tn
// T : 타우
// α = 0.5 로 보통 셋팅
1. α = 0
: Tn+1 = Tn
> 과거의 예측값 즉, 처음 예측값 그대로를 앞으로도 쭉 반영
// P1 <- 10
// P2 : 10
// P3 : 10
2. α = 1
: Tn+1 = α tn
> n번째 즉, 현재 CPU 타임값을 매번 반영
// P1 :10 > 미래 :10
// P2 : 8 > 미래 : 8
// P3 : 7 > 미래 : 7
>>>
τn+1=αtn+(1−α)αtn−1+(1−α)^2 αtn−2+…
> 예측에는 가장 가까웠던 (n) 의 Burst Time이 영향이 제일큼
> α = 0.5 로 과거값들은 계속 깎여나가기 때문
3. 선점형 SJF (shortest_remaning_time first)
A B // A: Arive , B : Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5
> 0 1 2 3 4 5 6 7 8 9 10
P1 ,P2 P3 P4 : 도착
>>
0~1 : P1 실행, P2 도착
> P2 가 더 B 짧음 // P1 : 7남음
1~2 : P2 실행 , P3 도착
> P2 가 더 짧음 // P2 : 3 남음
2~3 : P2 실행, P4 도착
> P2가 더 짧음
3~5 : P2 종료
> 젤적은 P4 5실행
5~10 : P4 종료
> 젤 적은 P1 남은 7실행
10~17 : P1 종료
17~26 : P3 종료
>>>
WaitingTime
1. P1 : 10-1 // 0~1 까지 대기 X
2. P2 : 1-1 // 1에서 도착함, 1에서 실행함
3. P3 : 17-2
4. P4 : 5-3
:: 26/4 = 6.5
RR (Round Robin)
: Tasks 을 순차적으로 q 만큼 돌아가며 실행
> q (time quantum) : 10~100ms // 최근 10us
> Program의 Max Wait : (n-1)q
// 1은 이미 실행중 , n : process 수
>> P1 에서 Q만큼 하고 C/S 한뒤 P2
: Q > C/S : FIFO 방식으로 잘 동작
<> Q < C/S : 수행 시간보다CS Time 이 더큼> 성능 X
ex) P1, P2,P3 : 24,3,3,, Q=4
0~4 : P1
4~7 : P2 // P2 < Q
....,
>특징)
1. 한 core 가 오랫동안 Burst Time 갖는걸 방지
2. Q 만큼의 시간만큼은 실행 보장
대신.. turnaround Time 은 클수있음
// Burst 가 큰경우 짧게 짧게 여러번 기다려야 하기때문에
Q with CS
: Q 가 클수록 Turnaround Time 은 줄어듦
> Q : 10~100ms <> BurstTime : 8ms //일반적으로
> 80%정도의 Process는 다 처리됨 > 대기시간X > Turnaround Time : low
// TurnAroundTime : Arive 부터 실행완료까지의 시간== WaitingTime + BurstTime
Priority Scheduling (우선순위) with SJF
: 선점형 //SJF <> Non
// SJF : BurstTime 이 길수록 우선순위를 높게 == 짧은것부터 // Convoy effect
>but) Starvation (Race condition) : 우선순위가 낮으면 계속 wait 해야할수도
>> Aging 기법! : 즉, 오래 기다릴수록 우선순위를 점점 높이는 기법
일반적인 OS : Priority + RR Scheduling
: 우선순위대로 하되 q 시간만큼만!
MultiLevel Queue
: Prioriy 마다 각각의 Queue 가 존재
ex) Priority = 0 : T1,T2,T3,,,
Priority = 1 : T4,T5,T6,,,
// 다른 Priority 의 Queue에 들어갈수없음
Process Priority Type
1. RT process // RealTime Process
2. System Process // OS scheduler ,,
3. Interactive Process // 짧은 I/O 그에 따른 간단한Computation
4. batch //주기적, 대량
: 우선순위 1 > 2 > 3 >4 // 즉시성!
MultiLevel FeedBack Queue
> 한 Process 가 Queue 들을 옮겨다님
> Aging도 구현 가능! // 오래된걸 위로 올리는식으로
ex) Q0 : RR , Q=8
Q1 : RR , Q=16
Q2 : FCFS (FIFO)
Q0 에서 안끝나면 Q1 로 보내고 안끝나면 Q2 로 보내서 먼저 온 순서대로 쭉 보내는(Aging) 방식
Thread Scheduling
: Scheduling 의 단위는 Thread !! (Ready Queue에 올라와있는)
User ) n:1, n:n (lib) PCS (process_condition_scope)
> Kernel 내의 ULT 끼리 경쟁!
Kernel) 1:1 SCS (system " " )
> All Thread in system (여러 Process들) 의 CS 를 통해 전환!
// LINUX ,MAC 방식