CPU-I/O Burst Cycle
- Cpu burst는 cpu의 명령을 실행하는 것이고, I/O burst는 입출력을 요청한 다음 기다리는 시간이다.
- Cpu burst와 I/O burst는 번갈아가면서 실행된다.
CPU Scheduler
- CPU 스케줄러는 실행 준비가 된 프로세스들 중에서 순서를 정해주는 일을 한다.
Dispatcher
- CPU를 받을 프로세스에게 CPU를 넘겨주는 역할을 하는 운영체제 커널 코드
- 이 과정은 문맥 교환이다(context switch)
- 유저 모드로 전환
- 선택된 프로세스를 재시작하기 위해 적절한 위치로 점프
- Dispatch latency
- 디스패처가 하나의 프로세스를 멈추고 다른 프로세스를 시작하는데 걸리는 시간
- 스케줄링 오버헤드
Scheduling Criteria
- CPU utilization: CPU가 얼마나 많이 사용되고 있는가
- Throughput: 단위 시간당 완료하는 프로세스의 개수
- Turnaround time: 수행을 요청한 다음 완료할 때까지 시간
- Waiting time: 큐에서 기다리는 시간의 합
- Response time: 첫 번째 응답이 올 때까지의 시간
Scheduling algorithm's goals(목표)
- CPU utilization 증가
- throughput 증가
- turnaround 시간 감소
- waiting 시간 감소
- response 시간 감소
- 반응 시간의 평균 보다 변동폭을 줄이는 것이 중요하다.
Scheduling algorithms
First-Come First-Served(FCFS)
- 먼저 온 것을 먼저 처리
- Waiting time -> P1 = 0, P2 = 24, P3 = 27
- 평균 waiting time = 17
- 비효율적임
- non-preemptive(비선점형)
- 새로운 것이 들어와도 원래 하던 것을 우선적으로 처리
Shortest-Job-First(SJF)
- CPU burst time이 작은 것부터 할당
- 비선점 방식과 선점 방식으로 나뉨
- 선점 방식의 경우 수행하다가 남은 시간보다 작은 시간이 걸리는 프로세스가 오면 멈추고 해당 프로세스로 변경
- 평균 waiting time이 제일 적은 알고리즘
- 평균 waiting time = (0+6+3+7)/4 = 4
- 평균 waiting time = (9+1+0+2)/4 = 3
Priority Scheuling
- 우선순위 숫자는 각 프로세스마다 정해져 있음
- CPU는 우선순위가 높은 프로세스에 할당이 된다.
- SJF는 우선순위 스케줄링의 한 종류이다.
- 문제점
- Starvation: 우선 순위가 낮은 프로세스는 평생 실행되지 않을 수 있다.
- 해결 방법
- Aging: 오래된 프로세스의 우선순위를 높여줌.
Round Robin(RR)
- 각각의 프로세스는 CPU time의 일정 부분을 똑같이 할당받는다.
- 예를 들어 n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- q가 커지면 -> FCFS
- q가 작아지면 -> 문맥 교환 오버헤드가 너무 커진다.
- 일반적으로 RR은 SJF보다 높은 turnaround시간을 가지고, 낮은 response시간을 가진다.
Multilevel Queue
- 레디 큐는 부분 큐로 나누어져있다.
- 우선순위가 높은 애들은 foreground(interactive 대화형)
- 우선순위가 낮은 애들은 background(batch 배치식)
- 각각의 큐는 각자의 스케줄링 알고리즘을 가지고 있다.
- foreground - RR - background - FCFS
Multilevel Feedback Queues
- 프로세스는 다양한 큐들 사이에서 이동할 수 있다.
Multi-Processor Scheduling
-
싱글 프로세서 스케줄링보다 복잡하다.
-
두 가지 종류의 스케줄링
-
Asymmetric multiprocessing
- Master processor가 존재하여 스케쥴링 결정, 나머지 processor에게 일을 시킴
-
Symmetric multiprocessing(SMP)
- 각 처리기(Processor)가 독자적인 스케줄링을 수행하는 방식, 평등함
-
-
멀티 프로세서 스케줄링에 대한 이슈
-
Processor affinity
- 프로세스를 계속해서 같은 프로세서에서 작동시킬 수 있도록 한다.
-
Load balancing(부하 균등화)
-
Processor가 하나 이상이라는 것을 최대한 활용하려면, 부하를 모든 처리기에 균등하게 배분하는 것이 중요하다.
-
push migration
- 주기적인 작업은 각 프로세서의 부하를 확인하고, 과부하된 CPU에서 작업을 다른 CPU로 이동한다.
-
pull migration
- 유휴 프로세서는 바쁜 프로세서에서 대기 중인 작업을 가져온다.
-
-
