9. 스케줄링

스케줄링

---

• 스케줄링
  • 스케줄링의 개요
  • 스케줄링의 단계
    • 스케줄러 관점에서 스케줄링
    • 스와핑(swapping)
  • 스케줄링의 목적
  • 스케줄링 알고리즘
    • 비선점형 스케줄링
      • FCFS(First Come First Service. 선입 선출)
      • SJF(Shortest Job First. 단기 작업 우선)
      • HRN(Highest Response-ratio Next)
    • 선점형 스케줄링
      • RR(Round Robin)
      • SRT(Shortest Remaining Time)
      • 멀티 레벨 스케줄링

---

스케줄링의 개요

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업

프로세스가 생성되어 완료될 때까지 여러 종류의 스케쥴링 과정을 거치게 된다.

스케줄링의 단계, 스케줄러 관점에서 스케줄링

스케줄링의 단계

• 장기 스케줄링

  • 준비 큐에 어떤 프로세스를 넣을지 결정해 시스템 자원을 차지하고 메모리에 올라갈 프로세스 수를 조절한다.

  • 프로세스 상태 : New->Ready(in memory)

  • 메모리와 디스크 사이 스케줄링 담당

  • 잡 스케줄링/상위 스케줄링/승인 스케줄링 이라고도 하며, 작업 스케줄러에 의해 수행된다.

• 중기 스케줄링

  • 메모리에 로드된 프로세스 수를 동적으로 조절하여 어떤 프로세스들이 CPU를 할당받을 것인지를 결정한다.

  • 프로세스의 상태 : ready -> suspended

  • 메모리에 프로세스가 많이 로드되면 일시 보류시킨 후 활성화하는 스와핑으로 일시적으로 부하를 조절한다.

  • 스왑 아웃하여 일부 프로세스를 통째로 저장 공간에 저장한다. 스왑 아웃된 프로세스는 중단 상태가 된다.

  • 중단 상태는 준비 상태에서 스왑 아웃된 '중단된 준비 상태'와 대기 상태에서 스왑 아웃된 '중단된 대기 상태'로 구분된다.

• 단기 스케줄링(CPU 스케줄링)

  • 준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행(디스패치)할 지를 스케줄링 알고리즘으로 결정한다.
  • CPU와 메모리 사이 스케줄링 담당
  • 프로세스의 상태 : ready -> running -> waiting -> ready

스케줄러 관점에서 스케줄링

1. 스케줄러가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치한다. 이때 스케줄링 알고리즘을 이용한다.

2. CPU에서 프로세스를 실행한다. 이때 프로세스는 실행 상태다.

   A. 프로세스 수행이 완료되면 프로세스를 종료한다.

   B. 일정 시간을 초과하면 인터럽트가 발생해 프로세스가 준비 큐로 들어가고 준비 상태가 된다.

   C. 입출력 요청이 들어오면 인터럽트가 발생한다. 이때 프로세스는 대기 큐로 들어가서 대기 상태가 된다. 입출력이 완료되면 프로세스는 준비 큐로 들어간다.

3. fork()가 호출되면 자식 프로세스가 생성되고, 자식 프로세스는 준비 큐로 들어간다.

스와핑(swapping)

• 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것

• 메모리 공간보다 많은 프로세스를 실행할 수 있다는 장점이 있다.

  • 스왑 아웃(swap out) :

    • 프로세스가 실행되려면 메모리에 로드되어야 하는데, 메모리 공간보다 많은 프로세스가 로드된 경우, 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간(SSD와 같은 영역)으로 옮겨 저장하는 것

  • 스왑 인(swap in) :

    • 스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 다시 메모리에 로드하는 것

스케줄링의 목적

멀티 프로세스 환경에서 모든 프로세스를 공정하게 실행하여 CPU나 자원을 효율적으로 사용

• 공평성 : 모든 프로세스에 공정하게 할당한다.
• 효율성 : 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 한다.
• 안정성 : 우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하여 안정성 보장
• 오버헤드 최소화
• 응답 시간 최소화 : 작업을 지시하고, 반응하기 시작하는 시간을 최소화
• 반환 시간 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화
• 대기 시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간을 최소화
• 무한 연기 회피 : 특정 프로세스에 대한 처리가 무한히 연기되지 않도록 한다
• 균형 있는 자원의 사용 : 메모리, 입출력장치 등의 자원을 균형 있게 사용

스케줄링 알고리즘

CPU 스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬 지 결정하는 데 사용

평가 기준

• CPU 사용률 : CPU를 효율적으로 사용
• 처리량 : 단위 시간당 실행한 프로세스 수
• 실행 시간 : 프로세스에 요청이 발생했을 때 총 실행에 걸리는 시간
• 반환 시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간(프로세스의 대기 시간과 실행 시간의 합)
• 대기 시간 : 프로세스가 대기 큐에서 대기하는 시간의 총합(바로 앞 프로세스까지의 진행 시간)

비선점형 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 기법

• 특징
  • 실행 중인 프로세스가 CPU를 할당 받아 종료될 때까지 다른 프로세스를 실행할 수 없다.
• 장점
  • 모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.
  • 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식에 적합하다.
• 단점
  • 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있다.

FCFS(First Come First Service. 선입 선출)

준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법

SJF(Shortest Job First. 단기 작업 우선)

준비 상태 큐에서 기다리고 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하여 실행하는 기법

• 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘

• 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.

기아 상태

프로세스마다 우선순위가 있는데, 우선순위가 높은 프로세스만 수행되어 우선순위가 낮은 특정 프로세스는 계속 실행되지 못하는 것

HRN(Highest Response-ratio Next)

대기 시간과 서비스(실행)시간을 이용한 우선순위를 도출하여 그에 따라 프로세스에 CPU를 할당하여 실행하는 기법

• 우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여된다.
• 우선순위 계산식 = (대기 시간+서비스 시간) / 서비스 시간

선점형 스케줄링

스케줄러가 CPU를 할당 받아 실행 중인 프로세스를 중단시키고 CPU를 강제로 빼앗아 우선 순위가 높은 다른 프로세스에게 할당하여 실행시키는 기법

• 특징
  • 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용된다.
  • 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요하다.
• 장점
  • 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
• 단점
  • 많은 오버헤드를 초래한다.

RR(Round Robin)

각 프로세스를 시간 단위(타임 슬라이스, 타임 퀀텀) 만큼만 실행한 후, 이를 초과하면 실행이 완료되지 않아도 다른 프로세스를 실행

• 특징
  • 시분할 시스템을 위해 고안된 방식. 시간 단위가 작을수록 작은 프로세스에 유리하다.
  • 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없다. 따라서 시간 단위를 적절하게 설정해야 한다.
  • n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  • RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
• 장점
  • 모든 프로세스가 반복 수행되어 응답 속도가 빠르다.

예제

다음과 같이 4개의 프로세스가 주어지고 시간 할당량은 3이라고 가장하자.

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4

모든 프로세스가 시간할당량 3만큼의 시간을 부여받고 완료하지 못한 프로세스는 준비 큐의 맨 뒤로 배치하여 순서를 기다린다.

SRT(Shortest Remaining Time)

현재 실행 중인 프로세스의 남은 시간과 준비 상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법

• 장점
  • 평균 대기 시간이 짧다
  • 시분할 시스템에 유용하다
• 단점
  • 수행시간이 긴 프로세스는 기아 상태가 되기 쉽다.
  • 준비 상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다.

예제 1

4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고 연속적으로 입력되는 경우를 가정해본다.

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4

새로운 프로세스가 도착할 때마다 [n번째 프로세스의 남은 시간 추정치]와 [n+1번째 프로세스들의 시간 추정치]를 비교하여 추정치가 가장 짧은 프로세를 먼저 디스패치하여 실행

멀티 레벨 스케줄링

준비 큐를 여러 목적에 따라 분리하여 사용하는 기법

• 특징
  • 분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용할 수 있다.
  • 여러 개의 큐는 foreground 큐와 background 큐로 나뉜다.
  • foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 중요시하는 프로세스가 들어간다.

Reference

• 기술 면접 대비 CS 전공 핵심요약집

• [정보처리기사] 스케줄링, 비선점스케줄링, FCFS, SJF, HRN

• https://technote-mezza.tistory.com/70

• https://kim6394.tistory.com/177

• https://junghyun100.github.io/Process(2)/

• https://velog.io/@sk0726/TIL-17-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC

• [운영체제 03] 스케줄링 알고리즘