Scheduling

기능
- CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것
조건
- 오버헤드 감소
- 사용륭 증가
- 기아 현상 감소
목표
- Batch System
  - 가능하면 많은 일을 수행
  - 시간보단 처리량(throughout)이 중요
- Interactive System
  - 빠른 응답 시간
  - 적은 대기 시간
- Real-time System
  - 기한(deadline) 맞추기

프로세스 상태

프로세스의 상태 전이

승인
- 프로세스 생성이 가능하여 승인
스케쥴러 디스패치
- 준비 상태에 있는 프로세스 중 하나를 선택하여 실행
인터럽트
- 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것
입출력 or 이벤트 대기
- 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우
- 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것
입출력 or 이벤트 완료
- 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것

선점&비선점 스케줄링

비선점

정의
- 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장(처리시간 예측 용이함)
종류
- FCFS(First Come First Served)
  - 큐에 도착한 순서대로 CPU 할당
  - 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리게 됨
- SJF(Shortest Job First)
  - 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
  - 실행 시간이 긴 프로레스가 오랫동안 실행되지 않는 Starvation 현상 발생 단점 존재
- HRN(Hightest Response-ratio Next)
  - 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
  - 우선 순위 = (대기시간 + 실행시간) / (실행시간)

선점

정의
- OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우(처리시간 예측 어려움)
종류
- Priority Scheduling
  - 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
  - 우선 순위가 낮은 프로세스가 무한정으로 기다리는 Stravation이 발생 단점 존재
    - Aging 방법으로 Stravation 문제 해결 가능
- Round Robin
  - FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU를 할당 받음
    - Time Qunatum or Time Slice : 실행의 최소 단위 시간
- Multilevel-Queue(다단계 큐)
  
  추가
```
┌──────────────────┐  ← 우선순위 가장 높음
│   System Queue    │  (Round Robin)
└──────────────────┘
┌──────────────────┐
│ Interactive Queue │  (Round Robin)
└──────────────────┘
┌──────────────────┐
│     CPU-bound     │  (FCFS)
└──────────────────┘
┌──────────────────┐
│     Batch Job     │  (FCFS)
└──────────────────┘   ← 우선순위 가장 낮음
```
  - 큐마다 스케쥴링 알고리즘을 다르게 적용
  - 큐 간 우선순위가 고정
    - ex) system queue가 비지않으면 interative queue 등 아래 큐는 동작 안됌
      
      → 기아 현상 발생
  - 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법
  - 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정하는 방식 사용
    - 우선순위가 높은 큐는 작은 Time Quantum
    - 우선순위가 낮은 큐는 큰 Time Quantum
- Multilevel-Feedback-Queue(다단계 피드백 큐)
  - 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
```
기능적으로 설명
--------------
1. 새 프로세스가 Q0에 진입
2. 주어진 시간(Time Quantum)내에 처리하지 못하면 "하위 큐"로 이동
3. 오래 기다리면 "상위 큐"로 승급(Aging)
=>
즉 비선점 + 선점 혼합 방식으로 프로세스 행동에 따라 큐를 이동시켜 응답 속도, 효율성, 공정성을 개선한 CPU 스케줄링 알고리즘
```