기술 면접 대비 정리 - 1.3 스케줄링

멀티 프로세스 환경에서는 여러 프로세스가 모두 실행되어야 하지만 CPU 자원은 한정적.

그래서 스케줄링을 통해 모든 프로세스를 공평하게 실행해 한정된 자원을 효율적으로 활용하는 것이 OS의 주요 목적이다.

OS에서 스케줄링은 빠질 수 없는 개념으로 목적, 단계, 각종 용어를 숙지해야한다.

 

1.3.1 스케줄링의 목적

스케줄링의 목적은 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것이다.

 

세부적으로는 아래의 5가지 목적이 있다.

 

- 공평성 : 모든 프로세스가 공평하게 실행돼야 한다. 특정 프로세스가 실행되지 않는 경우가 없도록 스케줄링.

 

- 효율성 : 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링 해야한다.

 

- 안정성 : 우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링 해야한다.

 

- 반응 시간 보장 : 프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록 스케줄링.

 

- 무한 연기 방지 : 특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링.

 

---

1.3.2 스케줄링의 단계

스케줄링은 장기 스케줄링, 중기 스케줄링, 단기 스케줄링으로 나뉜다.

1.2.4 프로세스 상태도에서 스케줄링이 일어나는 시점을 보면 그림과 같다.

 

- 장기 스케줄링 : 준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다. 잡 스케줄링 또는 승인 스케줄링 이라고도 한다. 현대 운영체제에서는 시분할 시스템을 사용하기 때문에 대부분 사용하지 않는다.

 

- 중기 스케줄링 : 메모리에 로드된 프로세스 수를 동적으로 조절한다.

메모리에 프로세스가 많이 로드되면 스왑 아웃해서 일부 프로세스를 통째로 저장한다.

스왑 아웃된 프로세스는 중단 상태가 된다.

 

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

 

- 단기 스케줄링 : 준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정한다. 즉, 어떤 프로세스를 디스패치 할 지 결정하는데, 이를 CPU 스케줄링 이라고도 한다.

 

 

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

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

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

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

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

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

 

- 스왑 아웃 : 프로세스가 실행되려면 메모리에 로드돼야 한다.
그런데 메모리 공간 보다 많은 프로세스가 로드되는 경우가 있을 수 있다. 이럴 때 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장공간(SSD와 같은 영역)으로 옮겨 저장하는 것을 스왑아웃이라고 한다.

- 스왑 인 : 스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 닿시 메모리에 로드하는 것을 스왑 인이라고 한다.

- 스와핑 : 스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것을 스와핑이라고 한다. 스와핑하면 메모리 공간보다 많은 프로세스를 실행할 수 있다는 장점이 있다.

---

1.3.3 스케줄링 알고리즘

스케줄링 알고리즘은 CPU 스케줄러 (단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는 데 사용한다. 스케줄링 알고리즘은 스케줄링의 목적을 달성하기 위해 다음과 같은 기준으로 평가한다. 하지만 이를 모두 만족하기는 어려우므로 어떤 기준을 더 중요하게 여길지 판단해야한다.

 

- CPU 사용률 : CPU를 놀리지 않고 사용하는지 판단

- 처리량 : 단위 시간(time unit)당 실행한 프로세스 수

- 응답 시간 : 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간

- 반환 시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간

- 대기 시간 : 프로세스가 대기 큐에서 대기하는 시간의 총합

 

스케줄링 알고리즘은 선점형과 비선점형으로 나뉨.

비선점형 스케줄링

실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다.

해당 알고리즘으로는 FCFS 스케줄링, SJF 스케줄링, HRRN 스케줄링이 있다.

 

- FCFS(First Come First Served) : 준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘.

준비 큐에 먼저 들어온 프로세스를 먼저 실행\

 

- SJF(Shortest Job First) 스케줄링 : 실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘으로, SJN(Shortest Job Next) 스케줄링 이라고도 한다. 준비 큐에 있는 프로세스 중 CPU를 점유 하는 실행 시간이 가장 짧은 프로세스 부터 실행한다. 평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.

 

* 기아상태(starvation) : 프로세스마다 우선순위가 있는데, 우선순위가 높은 프로세스만 수행되어 우선순위가 낮은 특정 프로세스는 계속 실행되지 못하는 것을 의미한다.

 

비선점형 스케줄링

스케줄러가 실행 중인 프로세스를 중단 시키고 다른 프로세스를 실행할 수 있음을 의미한다.

해당 알고리즘으로는 RR(Round Robin)스케줄링, RTF(Shortest Remaining Time First) 스케줄링, 멀티 레벨(multi level)스케줄링이 있다.

 

- RR(Round Robin) 스케줄링 : 비 선점형 스케줄링과 달리 프로세스간 우선순위가 없다. 모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간을 초과하면 다른 프로세스를 실행한다. 여기서 일정 시간은 '시간 단위'를 의미하며 타임 퀀텀 또는 타임 슬라이르 라고도 한다.

  일반적으로 시간 단위는 10 ~ 100밀리초다.

  콘텍스트 스위칭이 빈번하게 일어나서 오버헤드가 크다는 단점이 있지만, 모든 프로세스가 반복수행되어 응답 속도가 빠르다는 장점도 있다.

 

- SRTF(Shortest Remaining Time First) 스케줄링 : 준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘. 한 프로세스가 실행중일 때 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 된다. 평균 대기 시간이 짧다는 단점이 있지만, 수행 시간이 긴 프로세스는 기아 상태가 되기 쉽다.

 

- 멀티 레벨 스케줄링 : 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다. 분리한 큐는 각자 우선선위가 있고 각자 다른 스케줄링 알고리즘을 적용할 수 있다. 여러 개의 큐는 foreground 큐와 background 큐로 나뉜다. foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 중요시 하는 프로세스가 들어간다.

 

---

 

예상 질문

1. 비선점형 스케줄링 알고리즘과 선점형 스케줄링 알고리즘을 설명.

비선점형 스케줄링 알고리즘은 스케줄러가 실행 중인 프로세스를 종료될 때까지 다른 프로세스가 실행될 수 없다. FCFS, SJF 스케줄링이 대표적인 예이다.

선점형 스케줄링은 하나의 프로세스가 실행 중일 때 스케줄러가 실행 중인 프로세스를 중단 시키고 다른 프로세스를 실행할 수 있다. 대표적인 예로 RR 스케줄링과 SRTF 스케줄링이 있다.

TIP ) 비선점형 스케줄링과 선점형 스케줄링의 특징과 대표적인 알고리즘을 알고있어야 한다.
특히, FCFS 스케줄링, SJF 스케줄링, RR, SRTF 스케줄링은 이름이 어떤 단어들의 약자인지도 알아야하고, 작동방식도 이해해야한다. 그래야 프로세스 실행 순서 또는 프로세스의 평균 대기 시간을 계산하는 질문이 나와도 대답할 수 있다.