프로세스(선점형/비선점형) 스케줄링

1) 선점형(Preemptive) 스케줄링

정의: 실행 중인 프로세스를 중간에 빼앗아(preempt) 다른 프로세스로 교체할 수 있는 방식.
장점: 응답성↑, 대화형/타임셰어링 적합. 단점: 컨텍스트 스위치 오버헤드.

RR (Round Robin)

• 정의: 준비 큐의 프로세스를 고정된 타임퀀텀(q) 만큼 돌아가며 실행.
• 포인트: q가 너무 크면 FIFO처럼, 너무 작으면 스위치 오버헤드↑.
• 장점: 공정성(모두 기회), 대화형에 적합.
• 단점: 평균 반환시간은 SJF류보다 불리할 수 있음.

SRT / SRTF (Shortest Remaining Time First)

• 정의: 남은 실행시간이 가장 짧은 작업을 항상 선택. 더 짧은 작업이 오면 즉시 선점.
• 장점: 평균 대기/반환시간 최소화 경향(이상적).
• 단점: 실행시간 정확 추정 필요, 기아 위험(긴 작업이 계속 밀림).

MLQ (Multi-Level Queue)

• 정의: 우선순위가 다른 여러 개의 준비 큐를 두고, 각 큐에 고정 우선순위를 부여(상위 큐가 먼저 다 처리). 큐 안의 정책은 RR/FIFO 등으로 고정.
• 장점: 작업 성격별 분리(포그라운드/백그라운드 등).
• 단점: 기아 가능(하위 큐가 계속 대기). → 에이징(대기 오래하면 상향)으로 완화.

MLFQ (Multi-Level Feedback Queue)

• 정의: 처음엔 높은 우선순위 큐에 넣고, CPU를 오래 쓰면 낮은 큐로 강등, 짧게 쓰면 높은 큐 유지/승급. 큐마다 다른 q(상위일수록 짧음).
• 장점: 실행시간 정보 없이도 짧은 작업/대화형 우대, 긴 작업은 하위 큐로.
• 단점: 파라미터(큐 수, q, 승급/강등 규칙) 튜닝 난이도, 여전히 기아 가능 → 주기적 승급/에이징 사용.

---

2) 비선점형(Non-preemptive) 스케줄링

정의: 한 프로세스가 CPU를 잡으면 자진 양보/종료 전까지 계속 실행.
장점: 단순, 컨텍스트 스위치 적음. 단점: 응답성↓, 대화형 부적합.

FIFO / FCFS (First Come First Served)

• 정의: 도착 순서대로 실행.
• 장점: 가장 단순, 공정성(시간 기준).
• 단점: 호위 효과(convoy effect) — 긴 작업 뒤에 짧은 작업이 몰리면 대기↑.

SJF (Shortest Job First)

• 정의: 실행시간이 가장 짧은 작업부터 실행(비선점형 버전).
• 장점: 평균 대기/반환시간 매우 우수.
• 단점: 실행시간 추정 필요, 기아(긴 작업 계속 밀림).

HRN (Highest Response Ratio Next)

• 정의: 매 선택 시 응답비율 ( HR = (실행시간+대기시간) / 실행시간)이 가장 큰 작업 선택.
• 장점: 대기 많이 한 작업의 HR이 커져 SJF 기아 완화.
• 단점: 매 선택 시 HR 재계산 필요(약간의 계산 비용).

기한부(Deadline) / 우선순위(Priority)

• 기한부(Deadline): 작업마다 마감시간이 있고, 마감 전 완수가 목적.
  • 실시간 시스템에서 EDF(Earliest Deadline First)(선점/비선점 모두 가능) 등을 사용.
  • 장점: 마감 중심 최적화. 단점: 정확한 주기/실행시간 추정 필요, 과부하 시 미스 발생.
• 우선순위(Priority): 정적/동적 우선순위 값이 높은 작업을 먼저.
  • 단점: 기아(낮은 우선순위가 영원히 대기) → 에이징으로 완화(대기 시간에 따라 우선순위 상향).