sy9723
2023. 6. 12. 00:12
2023. 6. 12. 00:12
- CPU 스케줄링 비교 기준
- CPU utilization (CPU 이용률)
- 가능한 CPU를 바쁘게 만들어야 함
- 실제 시스템에서 40% ~ 90% 까지 가능함
- Throughput (처리량)
- 작업량 측정 방법
- 시간 단위 당 완료된 프로세스의 수
- Turnaround time (처리 시간)
- 프로세스 실행에 소요되는 시간
- 대기 시간 + 실행 시간 + I/O 시간
- Waiting time (대기 시간)
- Response time (응답 시간)
- 첫 응답이 시작되는 데까지 걸리는 시간
- 요구 제출 ~ 첫 응답 까지의 시간
- First-Come, First-Served Scheduling (FCFS)
- 가장 간단한 CPU 스케줄링 알고리즘
- CPU를 처음 요청한 프로세스가 CPU를 처음으로 할당 받음
- 프로세스가 ready queue에 들어가면, 큐의 끝에 PCB가 연결됨
- CPU가 가용해지면, 큐의 앞에 있는 프로세스에 할당됨
- 단점
- 프로세스의 대기 시간이 종종 꽤 김
- Convoy effect (호위 효과): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하길 기다림
- Shortest-Job-First Scheduling (SJF)
- 각 프로세스를 다음 CPU burst와 연관시켜서 스케줄링함
- smallest next CPU burst를 가진 프로세스에 할당함
- 두 프로세스의 값이 동일하면, FCFS가 적용됨
- 프로세스의 전체 길이가 아닌, next CPU burst의 길이에 좌우됨
- 주어진 프로세스 집합에 대해 평균 대기시간이 최소임
- short 프로세스를 long 프로세스보다 앞으로 이동 => short 프로세스의 대기시간을 줄이고 long 프로세스의 대기시간이 증가
- next CPU burst 길이를 알 수 없으므로, CPU 스케줄링 수준에서 구현 불가함
- 하지만 값을 예측하여 구현 가능 (next CPU burst는 이전의 값과 비슷하다고 기대함, 측정한 이전 CPU burst의 길이를 지수평균하여 예측할 수 있음)
- 선점 / 비선점 방식이 있음
- Round-Robin Scheduling (RR)
- FCFS 스케줄링과 유사함
- 시스템이 프로세스 간 전환이 가능하도록 선점이 추가됨 (FCFS + Preemption)
- 원형 큐를 돌며 하나의 시간 할당량 동안 CPU를 할당함
- 새로운 프로세스는 준비 큐의 tail에 추가됨
- 준비 큐의 첫 프로세스 선택 -> 시간 할당량 후 interrupt 되도록 timer 설정 -> 프로세스를 dispatch
- RR 알고리즘의 성능은 시간할당량 크기에 크게 좌우됨
- context swiitch time < time quantum(시간 할당량)
- 시간할당량은 너무 커도 안됨, 너무 크면 FCFS로 퇴보함 => 프로세스의 80%가 시간 할당량 내에 끝나도록 설정해야 함
- Priority Schedule
- 우선순위는 각 프로세스와 연관, 우선순위가 높은 프로세스에 CPU 할당됨
- 우선순위는 기준(내부적 요인: 시간 제한, 메모리 요구, 사용한 파일의 수, IO 대 CPU 비율, 외부적 요인: 프로세스 중요도, 비용, 작업 후원 부서, 정치적 요인)에 의해 정해짐
- 우선순위가 낮은 일부 프로세스는 무한 대기할 수 있음
- 해결방법 1) aging: 장시간 대기중인 프로세스의 우선순위를 점차 높여줌
- 해결방법 2) Priority Scheduling + RR
