FCFS(First-Come-First-Served)
Example 1:
- Process : P1, P2, P3
- Burst Time : 24, 3 ,3
- 프로세스의 도착 순서 : P1, P2, P3
- Gantt Chart
Waiting Time for P1 = 0; P2 = 24; P3 = 27
Average wating time : (0+24+27)/3 = 17
Example 2 :
- Process : P1, P2, P3
- Burst Time : 24, 3 ,3
- 프로세스의 도착 순서 : P2, P3, P1
- Gantt Chart
Waiting Time for P1 = 6; P2 = 0; P3 = 3
Average wating time : (6+0+3)/3 = 3
Convoy Effect : short process behind long process
SJF(Shortest-Job-First)
- 각 프로세스의 다음번 CPU Burst time을 가지고 스케줄링에 활용
- CPU Burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
- Two schemes:
- Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU Burst가 완료될 때까지 CPU를 선점 당하지 않음
- Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU Burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부름
- Nonpreemptive
- SJF is optimal
- 주어진 프로세스들에 대해 minimum average wating time을 보장
- 문제점
- Starvation 문제점 존재 : CPU 사용시간이 긴 프로세스는 영원히 사용 못할 수 있음
- 실제 시스템에서 사용 어려움( CPU 사용 시간을 미리 알 수 없음. 대신 과거 CPU burst time을 토대로 추정(estimate)하여 예상 할 수 있음
Priority Scheduling
- A priority number(Integer) is associated with each process
- highest priority를 가진 프로세스에게 CPU 할당(smaller integer = highest priority)
- Preemptive
- nonPreemptive
- SJF는 일종의 Priority Scheduling이다
- Problem
- Starvation : low priority processes may never execute.
- Solution
- Aging : as time progresses increase the priority of the process.
RR (Round Robin) - 현대적인 scheduling
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐(일반적으로 10~100 ms)
- 할당 시간이 지나면 프로세스는 선점당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다
- n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- Performance
- q large => FCFS
- q small => context switch 오버헤드가 커진다.
Example : RR with Time Quantum = 20
- process : P1,P2,P3,P4
- Burst time : 53,17,68,24
- 일반적으로 SJF 보다average turnaround time이 길지만 response time은 더 짧다.
Multilevel Queue
- Ready Queue 를 여러개로 분할
- foreground(interactive)
- background(batch - no human interactive)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- background - FCFS
- 큐에 대한 스케줄링이 필요
- Fixed priority scheduling
- serve all from foreground then from background
- Possiblity of starvation
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- Eg., 80% to foreground in RR, 20% to background in FCFS
- Fixed priority scheduling
Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동 가능
- 에이징(aging)을 이와 같은 방식으로 구현 할 수 있다.
- Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 Scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫒는 기준
- 프로세스가 CPU서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Example
- Queues
- Q0 : Time quantum 8ms;
- Q1 : Time quantum 16ms;
- Q2 : FCFS
- Scheduling
- new job이 queue Q0로 들어감
- CPU를 잡아서 할당 시간 8ms동안 수행됨
- 8ms동안 다 끝내지 못했다면 queue Q1으로 내려감
- Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms동안 수행됨
- 16ms동안 다 끝내지 못했다면 queue Q2로 쫒겨남
Multiple-Processor Scheduling
- CPU가 여러개인 경우 스케줄링은 더욱 복잡해짐
- Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로서가 알아서 꺼내가게 할 수있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해짐
- Load Sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
- Hard real-time systems
- hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
- Soft real-time systems
- soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
Thread Scheduling
- Local Scheduling : OS가 아닌 사용자 프로세스가 직접 어느 thread에게 cpu를 줄지 결정
- User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
- Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
- Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
- Implementation(구현) & Measurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
- Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
'OS(운영체제)' 카테고리의 다른 글
Process Synchronization2 (0) | 2023.08.06 |
---|---|
Process Synchronization1 (0) | 2023.08.06 |
CPU Scheduling 1 (0) | 2023.07.29 |
Process Management 2 (0) | 2023.07.29 |
Process Management 1 (0) | 2023.07.29 |