스케줄링

스케줄링이란?

운영체제는 프로세스 실행 순서를 관리해야 한다. 여러 개의 프로세스를 동시에 실행할 수도 없고 프로세스를 실행하다 여러 문제들의 발생과 부하 관리를 위해 정해진 일정에 따라서 프로세스를 실행해야 한다. 그것을 스케줄링이라고 한다. 스케줄링은 프로세스 실행 순서를 정하는 것이다. 여기서 한가지 더 생각을 해본다면 운영체제는 모든 프로세스를 실행해야 한다. 단 하나의 프로세스도 놓치지 않아야 하기 때문에 프로세스를 공평하게 실행하기 위한 목적이 있다. 즉, 스케줄링은 프로세스를 공평하게 실행하기 위한 목적을 가지고 있다.

그리고 스케줄링은 다음과 같은 5가지 목적을 통해 실행한다.

스케줄링의 5가지 목적

• 공평성 : 모든 프로세스가 공평하게 실행되어야 한다. 실행되지 않은 프로세스가 없도록 한다.
• 효율성 : 자원을 효율적으로 사용해 자원이 사용되지 않은 시간이 없도록 한다.
• 안정성 : 우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링 한다.
• 반응 시간 보장 : 프로세스가 일정 시간 내에 응답할 수 있도록 한다.
• 무한 연기 방지 : 특정 프로세스에 대한 처리가 무한 연기 되지 않도록 한다.

스케줄러 (장기, 중기, 단기)

스케줄링은 실행 단계에 따라 장기, 중기, 단기로 나뉜다.

장기 스케줄러

어떤 프로세스를 준비 큐에 넣을 것인가 결정한다. 디스크에서 하나의 프로그램을 가져와 커널에 등록하면 프로세스가 되는데 이때 디스크에서 어떤 프로그램을 가져와 커널에 등록할지 결정한다.

• 메모리에 올라가는 프로세스 수를 조절한다.
• 잡 스케줄링이라고도 한다.
• 시분할 시스템에서 사용되는 운영 체제에는 일반적으로 장기 스케줄러를 두지 않는다. 스케줄러 없이 바로 그 프로세스에 메모리를 할당에 준비 큐에 넣는다.

단기 스케줄러

어떤 프로세스를 CPU에 할당할 것인가 결정한다. 스케줄링 알고리즘을 통해 CPU가 실행할 프로세스를 선택하는 단계이다.

• 우리가 많이 들어본 선점형, 비선점형 스케줄링이 여기서 사용된다.
• 디스패치되는 프로세스를 결정하는 것이다.

중기 스케줄링

메모리에 적재되는 프로세스 수를 조절한다. 프로세스에 메모리가 만힝 로드되어 시스템의 성능 저하되는 경우를 위해 스왑 아웃을 하게 된다.

• 스왑 아웃은 메모리에 올라와 있는 프로세스 중 일부를 디스크로 저장하는 것을 말한다.
• 디스크로 스왑 아웃시켜야 하는 경우 중단 상태에 있는 프로세스들을 먼저 스왑 아웃 시킨다.
• suspended block : 중단 된 프로세스가 중기 스케줄러에 의해 디스크로 스왑 아웃한 상태
• suspended ready : 준비 상태의 프로세스가 중기 스케줄러에 의해 디스크로 스왑 아웃한 상태

스케줄링 알고리즘

스케줄링 알고리즘은 준비 큐에 있는 프로세스들 중 어떤 프로세스를 실행할지 결정하는 알고리즘이다. 다음과 같은 기준으로 우선순위를 판단할 수 있다.

• CPU 사용률 : CPU를 놀리지 않고 사용하는지 판단
• 처리량 : 단위 시간당 실행한 프로세스 수
• 응답 시간 : 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
• 반환 시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
• 대기 시간 : 프로세스가 대기 큐에서 대기하는 시간의 종합

스케줄링 종류

비선점형 스케줄링

비선점형 스케줄링은 다른 프로세스가 실행 중인 프로세스가 있을 때 중간에 가로채지 못하는 방식을 뜻한다. 즉, 실행중인 프로세스가 있으면 끝날때까지 대기해야한다.

• FCFS 스케줄링 : 준비 큐에 먼저 들어온 프로세스가 먼저 실행된다.
• SJF 스케줄링 : 실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘. 준비 큐에 있는 프로세스 중 CPU를 점유하는 시간이 짧은 프로세스를 먼저 실행해서 실행 시간이 긴 프로세스는 실행이 안되는 기아 상태가 될 수 있다.

이외에도 HRRN 스케줄링이 있다.

선점형 스케줄링

비선점형에 반대 개념이다. 실행 중인 프로세스가 있어도 알고리즘에 따라 실행 조건이 충족되면 선점하여 실행하는 방식이다.

• RR 스케줄링 : 비선점형 스케줄링과 달리 프로세스 간 우선순위가 없다. 모든 프로세스를 순서대로 일정 시간 동아 나눠서 실행한다. 일정 시간을 초과하면 다른 프로세스를 실행하는 것이다. 일정 시간은 타임 퀀텀(Time Quantum) 또는 타임 슬라이스(Time slice)라고도 한다.
  • 일반적인 시간 단위는 10~100 밀리초다.
  • 특징은 컨텍스트 스위칭이 자주 일어나 오버헤드가 크다.
  • 응답 속도가 빠르다.
• SRTF 스케줄링 : 준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 실행한다. 준비 큐에 실행시간이 더 짧은 프로세스가 들어오면 우선 순위를 갖는다.
• 멀티 레벨 스케줄링 : 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다. 분리된 큐는 각각 우선 순위 알고리즘을 갖는다.
  • foreground 큐, background 큐가 있으며 foreground 큐는 응답 속도가 중요한 프로세스가 들어가고, background 큐는 성능이 우선시 되는 프로세스가 들어간다.

스케줄링 문제

FCFS 스케줄링

• 순서 : P1 → P2 → P4 → P3
• 평균 대기 시간 : (0 + (100 - 10) + (110 - 60) + (170 - 100)) / 4 = 170 / 4 = 52.5

SJF 스케줄링

• 순서 : P1 → P2 → P3 → P4
• 평균 대기 시간 : {0 + (100 - 10) + (110 - 100) + (160 - 60)} / 4 = 50

RR 스케줄링 RR 스케줄링에서 어떤 프로세스가 응답 요청이 들어왔을 때 기다리는 최대시간은

(전체 프로세스) - 1 * (시간 단위)이다. 시간 단위가 50이라 했을 때

→ (4 - 1) * 50 = 150

SRTF 스케줄링

• 순서 : P1 → P2 → P1 → P3 → P4
• 평균 대기 시간 : {(20 - 10) + (10 - 10) + (110 - 100) + (150 - 60) / 4 = 110 / 4 = 27.5

출처

• 기술 면접 대기 CS 전공 핵심요약집 (책)
• 패스트 캠퍼스 강의