[운영체제] CPU 스케줄링

CPU 바운드 프로세스와 IO 바운드 프로세스

• CPU 바운드 프로세스 : CPU 버스트가 빈번하게 나타나는 프로세스
  • CPU 버스트란? : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
• IO 바운드 프로세스 : IO 버스트가 빈번해 CPU 버스트가 매우 짧은 프로세스
  • I/O 버스트란? : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

CPU 스케줄링이란?

CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다.

• 언제 일어나는가?
  1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
  2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
  3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 프로세스 상태가 준비 상태로 바뀌는 경우
  4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

프로세스가 CPU를 할당받고 명령을 수행하다가 타이머 인터럽트가 발생하였을 때

• 이후에 CPU 스케줄러는 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 된다.

스케줄러 종류

장기, 중기, 단기 스케줄러로 나뉜다
장기 스케줄러

• 작업 스케줄러라고도 불리며, 어떤 프로세스를 준비 큐에 진입시킬지 결정하는 역할을 함

중기 스케줄러

• 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러
• 현대의 시분할 시스템에서 장기 스케줄러 대신 많이 쓰인다.

단기 스케줄러

• CPU 스케줄러라고 하며, 준비 상태의 프로세스 중에서 어떤 프로세스를 다음번에 실행 상태로 만들 것이지 결정한다.

스케줄링 방식

• 선점형 스케줄링
  • 프로세스가 CPU를 계속 사용하길 원하더라도 강제로 빼앗을 수 있는 스케줄링 방식
  • RR, SRTF, MFQ 등이 있다.
• 비선점형 스케줄링
  • CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 스케줄링 방법
  • FIFO, SJF, HRN등이 있다.

선입선출 스케줄링(FCFS)이란?

프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식

• CPU 버스트가 긴작업 1개와 짧은 작업 2개 순으로 작업큐에 들어왔을 때 뒤에 CPU 버스트가 짧은 작업들은 오랜 시간을 기다려야 하는 현상이 생긴다 (콘보이 현상)

최단 작업 우선 스케줄링(SJF)이란?

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

• 비선점형 방식과 선점형 방식 두가지로 구현될 수 있음
  • 비선점형: CPU를 자진 반납하기 전까지 빼앗지 않는 것
  • 선점형: 버스트가 더 짧은 프로세스가 도착했을 때 CPU를 빼앗는 방식(SRTF)라고 부른다
• 이 때 SJF는 프로세스의 CPU 버스트 시간을 미리 알 수 없다.
  • 예측하는 공식을 사용한다.
• 기아현상이 일어날 수 있다.

우선순위 스케줄링이란?

준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식 - CPU를 우선순위 기준으로 하면 SJF와 똑같은 방식이 된다. - 비선점형, 선점형 방식으로 구현 가능하다. - 기아현상이 일어날 수 있다.

기아 상태란?

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태, 기아 상태라고도 불린다.

어떻게 해결할 수 있을까?

• 프로세스 우선 순위를 수시로 변경해서 각 프로세스가 높은 우선 순위를 가질 기회를 준다.
• 오래 기다린 프로세스의 우선 순위를 높여준다. (aging 기법)
• 우선 순위가 아닌 요청 순서대로 처리하는 FIFO 기반 요청 큐를 사용한다.

라운드 로빈 스케줄링이란?

각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정시간으로 제한되며, 이 시간이 경과하면 CPU를 회수하여 준비 큐에 있는 다른 프로세스로 할당하는 방식

• 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식
• 적절한 할당시간 설정이 필요함
  • 할당 시간이 너무 짧으면 문맥교환 비용이 많이 일어날 것이다
  • 너무 길면 FCFS와 다를 것이 없음

멀티 레벨 큐 스케줄링이란?

준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법

• 일반적으로 대화형 작업을 담기 위한 전위 큐, 계산 위주의 작업을 위한 후위 큐로 분할하여 운영
  • 전위 큐는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을
  • 후위 큐는 응답시간이 큰 의미를 가지지 않기 때문에 FCFS를 사용해여 문맥교환 비용을 아낀다.
• 큐 자체에 대한 스케줄링이 필요하다

멀티 레벨 피드백 큐 스케줄링이란?

기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티 레벨 큐와 동일하나 프로세스가 다른 큐로 이동 가능한 스케줄링