스케줄링(Scheduling)

• 여러개의 프로세스가 번갈아가며 사용하는 자원을 어떤 시점에 어떤 프로세스에게 자원을 할당할 지 결정하는 것
• 운영 체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선

스케줄링 목적

• 공평성
  모든 프로세스들에게 공정하게 배정해야함
• 처리량 최대화
  단위 시간당 가능한 최대로 많은 양이 처리될 수 있도록 함
• 오버헤드 최소화
  오버헤드가 발생하면 CPU 자원의 낭비가 심하므로 오버헤드를 줄여야함
• 반환 시간 보장
  프로세스의 요구가 있을 경우 적절한 시간 내에 반응해야함
• 무한 연기 방지
  특정 프로세스의 작업이 무한정 연기되면 안됨
• 안정성
  중요 프로세스들에게 우선권을 부여해 프로세스가 증가해도 안정적으로 돌아가야함
• 우선순위
  모든 프로세스에 우선순위를 부여하는 스케줄링 알고리즘을 통해 실행

프로세스 상태

• 생성(Create) : 프로세스가 생성되는 중
• 실행(Running) : 프로세스가 프로세서를 차지하여 명령어들이 실행
• 준비(Ready) : 프로세스가 프로세서를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리는 중
• 대기(Waiting) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태
• 종료(Terminated) : 프로세스의 실행이 종료

스케줄링 단계

• 1단계 스케줄링(장기): 작업 스케줄링
  실제로 시스템 자원을 사용할 작업을 선택
  작업들이 시스템에 들어오는 것을 승인하는 것이기 때문에 '승인 스케줄링'이라고 함
• 2단계 스케줄링(중기): 작업 승인과 프로세서 결정 스케줄링
  프로세서(CPU)를 사용할 프로세스를 결정하는 작업 승인을 해주는 역할
  프로세스들을 보류시키고 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절
  2단계는 1, 3단계의 완충 역할
• 3단계 스케줄링(단기): 프로세서 할당 스케줄링
  dispatcher가 Ready Queue에 있는 프로세스 중에서 우선순위에 따라 프로세스를 프로세서에 할당
  다음 프로세스 결정을 자주 해야하므로 '단기 스케줄링'이라고 함

스케줄링 결정 시점(적용 시점)

1. 수행 → 대기 (선점, 비선점)
2. 수행 → 준비 (선점)
3. 대기 → 준비 (선점)
4. 수행 → 종료 (선점, 비선점)

• 비선점형은 위의 결정 시점 중 1번과 4번의 상황에서만 수행
• 선점형은 1번에서 4번까지 모든 상황에서 수행

비선점형과 선점형

비선점형

• 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장

장점

• 순서대로 처리되므로 공정성이 있음
  다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있음
• 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적음
• 일괄 처리 시스템에 적합

단점

• CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있음

선점형

• 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있음

장점

• 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있음
• 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합
• 긴급한 프로세서를 제어할수 있음

단점

• 문맥 교환이 많아 오버헤드가 커질 수 있음

스케줄링 알고리즘

비선점형

1. FCFS
2. SPN/SJF
3. HRRN
4. Priority
5. FIFO

선점형

1. RR
2. SRTF
3. MFQ

참고

• https://kjhoon0330.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81#2.1.1.%201)%20%EC%9E%A5%EA%B8%B0%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%20(Long-term%20scheduler)
• https://aktnfl.tistory.com/26
• https://www.crocus.co.kr/1373