6.4 CPU 스케줄링

CPU 스케줄
선점형 : CPU를 빼앗길 수 있다
비선점형 : CPU를 빼앗기지 않는다.
1)FCFS(First Come First Served)
프로세스가 하나씩 끝나므로 평균 대기시간/소요시간은 짧음.
프로세스별로 CPU 버스트/ I/O버스트 시간이 다른 경우 프로세스마다 편차가 심함.
대표적 단점
convoy effect(콘보이 현상): CPU 버스트가 짧은 프로세스가 나중에 도착해서 오랜 시간을 기다려야하는 것.
2.SJF(Shortest-Job First) : CPU 버스트가 짧은 순. 평균 대기시간이 가장 짧음(선점형/비선점형 중 비선점형이 더 짧음)
SRTF(shorted Remaining Time First): 도중에 CPU 버스트가 더 짧은 프로세스가 오면 CPU를 빼앗아서 할당함.
기아(starvation) 현상: CPU 버스트가 짧은 프로세스가 계속 도착하면, CPU 버스트가 긴 프로세스는 계속 처리되지 못함.
CPU 버스트 시간은 실제로 알 수 없으므로, 예측.
T_n+1 = alhpa * t_n + (1-alpha)*T_n
T_n: 예측시간, t_n: 실제 CPU 버스트 시간

3) 우선순위 스케줄링
aging(노화): 대기 시간이 길어지면 우선순위를 조금씩 높임.

4) 라운드 로빈
할당시간이 너무 긺: FCFS와 차이가 없음
할당시간이 너무 짧음: context switch 오버헤드가 크다.
-> 수십 ms: 대화형 프로세스의 대기시간이 너무 길지 않을 정도.
여러 이질적인 프로세스를 처리할때 유용
SJF보다 평균 대기시간은 길지만 응답시간은 짧음.
할당시간 초과: 타이머 인터럽트를 통해 CPU회수
중간 산출물이 없으므로 평균 대기시간/소요시간은 길지만, 응답시간은 짧음.


5) 멀티레벨 큐
준비큐를 여러개로 분할하여 관리하는 스케줄링 기법
성격이 다른 프로세스를 관리하기 위함.
전위 큐 : 빠른 응답이 필요한 대화형 프로세스. 라운드 로빈
후위 큐: 응답 속도가 주요하지 않은 계산 프로세스. FCFS

어떤 큐를 먼저 사용할것인가?
고정 우선순위 방식 : 전위 큐 > 후위 큐
타임 슬라이스 : 전위 큐 80%, 후위 큐 20%. 기아 현상 해결

6) 멀티레벨 피드백 큐
멀티레벨 큐 + 하나의 프로세스가 다른 큐로 이동 가능.
노화(aging) 등 구현 가능

7) 다중처리기 스케줄링(multi-processor scheduling)
CPU가 여러 개인 환경
-1) 대칭형 다중처리: 각 CPU가 알아서 스케줄링 결정
-2) 비대칭형 다중처리 : 하나의 CPU가 스케줄링 담당.

8) 실시간 스케줄링
경성 실시간 시스템(hard real-time system) : 정해진 시간 내에 완료되야하는 시스템
연성 실시간 시스템(soft real-time system) : 데드라인이 존재하지만 지키지 않는다고 위험 상황이 발생하지 않는 시스템
EDF(Earliest Deadline First): 데드라인이 얼마 남지 않은 요청 먼저
연성 실시간 + 일반 작업의 경우: 데드라인이 존재하는 프로세스에 우선순위 할당

5.스케줄링 알고리즘의 평가
큐잉 모델: 확률 분포를 통해 프로세스의 도착률과 CPU의 처리율을 바탕으로 CPU의 처리량(throughput). 프로세스의 평균 대기 시간 계산.
시뮬레이션
구현 및 실측
트레이스(trace): 실제 시스템에서 추출한 CPU 입력값. 몇 초에 어떤 프로세스가 도착하고 CPU 버스트 시간이 얼마이다.