스케줄링이 나오게된 배경

CPU I/O 버스트 사이클

• 프로세스의 실행은 CPU의 실행과 I/O 대기의 사이클로 구성

1. 실행과 함께 CPU 버스트
2. I/O 버스트 발생
3. 다시 CPU 버스트(버스트로 끝이난다)
   위와 같은 과정이 반복하게됩니다

위와 같은 반복과정이 빈번하게 되면 버스트 지속시간이 짧고, 반복과정이 드물다면 버스트 지속기간이 길게됩니다.

다중 프로그래밍

프로세스가 I/O 요청과 같은 대기시간이 생길때에 CPU는 대기하게됩니다.
이렇게 CPU의 대기시간이 생기는 것이 비효율적이기에 이러한 문제점을 해결하는 방법으로 CPU의 이용률을 최대화하여 대기 시간을 최대한으로 줄이는 것이 목적이고 이를 실행하기위한 방법이 필요했다.
1. CPU를 바쁘게 유지한다.
2. 다수의 프로세스를 메모리에 유지한다.
3. 어떤 프로세스가 대기하면 OS가 CPU를 회수한뒤 다른 프로세스에 할당
4. 프로세스가 대기할때마다 다른 프로세스가 CPU를 양도받을 수 있다.
이를 스케줄링이라고 한다.

스케줄링 알고리즘을 구현할때 위에 설명했던 CPU-I/O 버스트의 분포가 중요하다.

---

스케줄링

• 운영체제의 기본적인 기능이자 핵심적인 기능
• 모든 컴퓨터 자원들은 사용되기전에 스케줄링 된다.

CPU 스케줄러

• 운영체제가 준비 큐에 있는 프로세스를 고를 때 무엇을 선택할지에 대한절차를 실행하는 곳
• CPU가 대기할때마다 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해서 실행(유후 상태라고 함)
  _준비 큐에 있는 레코드들을 일반적으로 프로세스들의 프로세스 제어 블록(PCB) 입니다.

CPU 스케줄링의 발생 상황

• 실행 상태 -> 대기 상태

  • I/O 요청이나 자식 프로세스의 종료를 기다리기 위한 wait() 호출
  • 스케줄링의 선택이 없음 : 비선점의 경우

• 실행 상태 -> 준비 완료 상태

  • 인터럽트(다른 프로세스에게 양도 상황)
  • 스케줄링의 선택이 가능 : 선점 가능한 경우

• 대기 상태 -> 준비 완료 상태

  • I/O 종료시
  • 스케줄링의 선택이 가능 : 선점 가능한 경우

• 종료 상태

  • 비선점의 경우

• 비선점 스케줄링

  • 프로세스가 종료하거나 대기 상태가 될때까지 CPU를 점유한다.

• 선점 스케줄링

  • 다른 프로세스를 중지 시키고 CPU를 가로챈다.
  • 두 프로세스가 한 자원을 공유하고 있을 때에 타이밍이나 순서에 따라 결과값에 영향을 줄 수 있고 데이터 일관성이 깨질 수 있음
    • 이러한 상태를 경쟁 상태라고 하고 이 위험을 경쟁 위험이라고 한다.

• 대부분의 최신 OS들은 선점 스케줄링 방식을 사용

---

운영체제 커널 설계에 사용되는 방식( 추가 학습필요)

• 비선점형 커널
• 선점형 커널

---

디스패처(Dispatcher)

• CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세다른게 제공하는 기능 담당
• Context Switching(문맥교환)을 담당
  • 자발적 문맥교환 : 사용 불가능한 자원을 요청해서 프로세스가 CPU의 제어를 포기한 경우(I/O 대기)
  • 비자발적 문맥교환 : CPU를 빼았겼을 때
• 사용자 모드로 전환을 담당
• 프로그램을 다시 시작하기위한 적절한 위치로 이동을 담당

디스패치 지연

• 디스패처가 하나의 프로세스를 중지시키고 다른 프로세스를 시작하는데 걸리는 시간
• 가능한 빨리 수행되어야 한다.
  

---

스케줄링 기준(스케줄링의 성능)

CPU 스케줄링 알고리즘을 비교하기 위한 기준

• CPU 이용률 : 가능한 CPU를 바쁘게 유지하기를 원한다.
• 처리량 : 단위 시간당 완료된 프로세스의 개수
• 총 처리 시간 : 프로세스의 제출 시간과 완료 시간의 간격
• 대기 시간 : 준비 큐에서 대기하면서 보낸 시간의 합
• 응답 시간 : 응답이 시작되는데 걸리는 시간
  이러한 기준을 효율적으로 만족시킬 수 있는 스케줄링이 바람직

---

스케줄링 알고리즘 종류

준비 큐에서 대기하고있는 프로세스 중에서 어떤 프로세스를 CPU 코어에 할당할 것인지를 결정하는 것을 다룬다.
현재에는 많은 코어가 있지만 이 알고리즘을 다룰때에는 처리 코어가 하나라고 가정한다.

스케줄링 전략이 중요한 이유

Context Switching으로 CPU의 점유 권한을 넘겨주는 과정에서는 CPU을 사용하고 있는 것이아닌, CPU를 점유를 하고있는 것이다. 이때, CPU는 점유는 당하고있는지만 일하고 있는 상태가 아니다. 즉, 프로세스가 점유를 하고있지만 프로세스가 사용중인 것은 아니다. CPU가 일을 하지 못하는 상태가 되고 이는 CPU의 자원이 낭비되는 상태를 말하고 결과적으로 이는 오버헤드가 발생하는 것을 의미합니다.
때문에, Context Switching이 발생하는 빈도를 최대한으로 줄이기 위해서 스케줄링의 전략이 중요한 것이다. 스케줄링의 전략이 효율적이라면 적은 횟수의 Context Switching으로 일을 처리하면 CPU도 최대한 사용할 수 있다.

비선점 스케줄링

• 프로세스가 CPU를 놓아주기 전까지 스케줄링이 발생하지 않는다.
• Context Switching을 최소화 할 수 있는 장점, 일괄처리에 적합
• 급하게 처리되어야할 프로세스가 처리되지 못한다는 단점

FCFS 스케줄러

• ready queue에 도착한 순서대로 CPU에 할당
• 단순하다, 구현이 편리하다
• 중요한 작업이 오래기다리고, 덜 중요한 작업이 빠르게 처리되는 상황이 발생한다(Convy Effect : 호위 상태)

최단 작업 우선(SJF) 스케줄러

• 프로세스가 준비 큐에 도착하게 되면 CPU 스케줄러는 실행 시간을 확인하고 실행 시간이 짧은 순서로 정렬 시키게 되고 가짱 잛은 실행 시간을 갖은 프로세스에게 CPU를 할당합니다.
• 평균 대기 시간을 가장 최소화 시킬 수 있는 알고리즘입니다.
• 프로세스의 실행 시간을 정확하게 예측하기 어려워 구현하기 어렵다.
• 실행 시간이 긴 프로세스는 계속해서 기다려야하는 기아 현상(starvation)이 발생한다.

HRN (Highest Response Ratio Next) 스케줄러

• SJF 방식의 기아 현상을 해결하기위해 고안된 방식
• (대기시간 + CPU 처리 시간) / CPU 처리 시간 을 기준으로 결정 -> 즉, 기다린 시간에 비례하여 우선순위를 높인다(에이징 기법)
• 선점으로 진행되면 너무 많은 Context Switching이 발생하게됩니다.

우선순위 스케줄러

• 대기중인 프로세스들에게 우선순위를 부여하여 처리하는 방식(에이징 기법사용가능)
• 선점으로 진행할 수 있다.
• starvation 현상이 발생할 수 있기 때문에 우선순위는 정적 or 동적이다.

선점 스케줄링

• 우선순위가 높은 프로세스가 점유를 뺏음
• 긴급한 프로세스를 처리할 수 있다
• Context Switching이 많이 발생하는 비효율

SRT(Shortest Remaining Time) 스케줄링

• SJF 스케줄링 방식을 선점으로 변경한 기법
• 점유 중인 프로세스보다 짧은 실행 시간을 갖는 프로세스에게 CPU를 뺏김

우선순위 스케줄링

• 우선순위가 더 높은 프로세스에게 CPU 점유를 빼았김

라운드 로빈(Round-Robin) 스케줄링

• 일정시간을 정해두고 그 시간을 사용하면 다음 프로세스에게 점유권을 빼앗김
• FCFS + 선점 + Time Quantum
  • Time Quantum : CPU가 연속적으로 사용할 수 있는 시간
• 사용이 끝내면 ready queue 맨 뒤로 보낸다.
• Time Quantum 을 얼마로 설정할지가 중요

다단계 큐 스케줄러

• 이름 그대로 여러개의 대기 큐를 사용하고 어떤 프로세스냐에 따라서 그룹으로 나눠서 대기합니다.
• 각각의 큐는 서로 다른 스케줄링 방식을 적용할 수 있다.
• 프로세스의 종류
  • 사용자와 상호작용하는 프로세스
    • 중요하기에 빠르게 처리되어야함
    • Round Robin과 같은 스케줄링을 적용
  • 백그라운드에서 돌아가는 프로세스
    • 비교적 나중에 처리되어도 됨
    • FCFS 와 같은 스케줄링을 적용
• 여러개의 대기 큐가 존재하여 어떤 대기 큐에게 CPU를 할당할지 문제
  • 고정 우선순위 방식
    • 대기 큐 마다 우선순위를 부여한다.
    • 선정된 대기큐가 끝나야 다음 대기 큐에 할당
  • 타임 슬라이스
    • 대기 큐에 대한 기아 문제를 해결하기위한 방식
    • 예를 들어, 중요한 큐는 75% 덜 중요한 큐는 25% 와 같은 시간을 지정

다단계 피드백 큐 스케줄러

• 이름 그대로 오래기다린 프로세스에게 피드백(도와줌)해준다.
• 낮은 우선순위 대기 큐에서 너무 오래 기다린 프로세스의 우선순위를 올려서 높은 우선순위의 대기 큐로 옮겨준다.
• 큐를 이동시켜준다.
• 기아문제 해결