<스케줄링 알고리즘>
• FIFO(FCFS), RR, SJF, MLFQ(EQ) 등
<FCFS 스케줄링>
• 처음 프로세스는 완료될 때까지 실행
• finished = blocked
-다른 프로세스가 세마포어 기다리는 동안 한 프로세스가 CPU 사용 가능
-준비되면 실행 대기열 뒤로 이동
• 단점: 하나의 프로세스가 CPU를 독점할 가능성
• 해결책: 프로세스가 컨텍스트 전환 없이 실행할 수 있는 최대 시간 제한 -> time slice
• 긴 프로세스 뒤에 짧은 프로세스가 오면 안 좋음
<SJF 스케줄링>
• 다음 CPU burst의 길이를 각 프로세스와 연결
• 이 길이가 가장 짧은 시간으로 프로세스 선택
• 최소 평균 대기 시간 제공
• 하지만 다음 CPU 요청의 길이를 아는 것이 어려움
-예측만 가능 / 구현이 어려움 / 비용이 큼
Non-preemptive:
실행 프로세스가 완료될 때까지 선점 불가능
Preemptive:
항상 더 짧은 애가 우선. SRTF 또는 STCF로 불림
->선점형이 더 짧은 시간이지만 문맥 전환이 증가
<RR 스케줄링>
• time quantum 사용
• quantum 시간이 끝나면 준비 대기열의 끝에 추가됨
• q가 크면 한 프로세스가 CPU 독점 (FIFO)
• q가 작으면 많은 context switch overhead
• 보통 SJF보다 평균 turnaround가 높지만 응답성이 더 좋음
• q는 문맥 전환 시간보다 커야 함
• q는 일반적으로 10ms~100ms/ 문맥 전환 < 10us
• 어떤 프로세스도 (n-1)q 시간 이상 대기하지 않음
• 나쁜 경우
-라운드 로빈은 공평하지만 균일하게 비효율적
<Priority 스케줄링>
• 우선순위가 높은 프로세스 = 작은 정수
• 선점형 / 비선점형
• SJF는 우선순위가 예측된 다음 CPU burst time의 역수가 우선순위인 Priority 스케줄링
• 문제점: Starvation(기아) 발생 – 우선순위 낮은 프로세스는 실행되지 않을 가능성
• 해결책: Aging – 시간이 지남에 따라 프로세스 우선순위를 높이기
<-Multilevel Queue->-다단계 대기열
• Ready 큐는 별도의 대기열로 분할됨(큐 여러개)
-foreground(interactive) / background(batch)
• 지정된 대기열에서 영구적으로 처리
• foreground는 RR, background는 FCFS
• 대기열 간 스케줄링
-고정된 우선순위 스케줄링: 기아 상태 가능성
-시간 분할: RR에서 80%, FCFS에서 20%
<MFQ – Multilevel Feedback Queue>
• 프로세스는 다양한 큐 사이를 이동 가능
• 큐의 수, 각 큐에 대한 스케줄링 알고리즘, 프로세스를 업그레이드할 시기 결정 방법, 프로세스 강등 시점 결정 방법, 프로세스가 입력할 대기열 결정 방법
<CFS 스케줄링>-Linux Scheduling
• 스케줄링 클래스
-각각 특정한 우선순위 가짐
-높은 스케줄링 클래스에서 높은 우선순위 작업 선택
-quantum 대신 CPU 시간의 비율을 기반으로 함
(Variable quantum size)
-2개의 스케줄링 클래스 포함, 다른 클래스 추가 가능
(default, real-time)
• nice value
-특정한 weight값이 있음
(weight는 우선순위가 높으면 높음)
-nice value로 우선순위를 나타냄
-nive가 낮으면 weight와 우선순위는 높음
• target latency(목표 대기 시간)
-고정된 값이 아니고 프로세스가 증가하면 증가
-time slice들의 합이 target latency
