1. 스케줄링

CPU를 잘 사용하기 위해 프로세스를 배정하는 과정

• 조건: 오버헤드 감소/ 사용률 증가/ 기아현상 감소
• 목표
  • Batch System: 가능하면 많은 일을 수행. 시간보단 처리량이 중요
  • Interactive System: 빠른 응답 시간. 적은 대기 시간
  • Real-Time System: 데드라인 맞추기

2. 선점/비선점 스케줄링

• 선점 스케줄링: OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우(처리시간 에측 어려움)
• 비선점 스케줄링: 프로세스 종료 또는 I/O등의 이벤트가 있을 때까지 실행 보장(처리시간 예측 용이함)

3. 프로세스 상태

• 상태 종류: Ready, Running, Waiting

4. 스케줄링 종류

4.1. 비선점 스케줄링

4.1.1. FCFS(First Come First Served)

• 큐에 도착한 순서대로 CPU에 할당
• 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어짐

4.1.2. SJF(Shortest Job First)

• 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
• FCFS보다 평균대기신간 감소, 짧은 작업에 유리

4.1.3. HRN(Highest Response-ratio Next)

• 우선순위를 계산하여 점유 불평등을 보완한 방법
• 우선순위: (대기시간+실행시간)/(실행시간)

4.2. 선점 스케줄링

4.2.1. 우선순위 스케줄링(Priority Scheduling)

• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선순위가 낮은 프로세스가 무한정 기다리는 기아상태 발생 가능
• Aging을 통해 기아상태를 방지 가능

4.2.2. Round Robin

• FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 타임퀀텀 만큼 CPU를 할당받음
  • 타임 퀀텀: 실행의 최소 단위 시간
• 타임 퀀텀이 크면 FCFS와 유사하고, 작으면 문맥 교환이 잦아져 오버헤드 증가

4.2.3. Multilevel-Queue(다단계 큐)

• 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용해 실행하는 기법
• 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 타임 퀀텀을 설정해주는 방식
• 우선순위가 높을수로 작은 타임퀀텀을 할당
  

4.2.4. Multilevel-Feedback-Queue(다단계 피드백 큐)

• 다단계 큐에서 자신의 타임 퀀텀을 다 채운 프로세스는 밑으로 내려가고 자신의 타임퀀텀을 다 채우지 못한 프로세스는 원래 큐 그대로 사용
  • 타임 퀀텀을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문
• 짧은 작업에 유리, 입출력 위주(인터럽트가 잦은)작업에 우선권을 줌
• 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 평균 반환 시간을 줄임
  

5. CPU 스케줄링 척도

• 응답 시간: 작업이 처음 실행되기까지 걸린 시간
• 반환 시간: 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간