운영체제 - 4

1.  스케줄링

CPU 스케줄링은 CPU에 어떤 작업을 배정할지 결정하는 것이다. 컴퓨터 시스템의 효율은 이에 따라 달라진다. 앞서 배운 것 처럼, 프로세스는 생성 상태, 준비 상태, 실행 상태, 대기 상태 등의 여러 상태를 거치며 작업이 이루어진다. CPU 스케줄러는 프로세스가 생성된 후부터 종료될 때까지 모든 상태 변화를 조정한다.

- 고수준 스케줄링: 고수준 스케줄링(high level scheduling)은 작업 스케줄링(job scheduling)이라고도 불리우며, 시스템 내의 전체 작업 수를 조절하는 것을 의미한다.

- 저수준 스케줄링: 저수준 스케줄링(low level scheduling) 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다.

- 중간 수준 스케줄링: 중간 수준 스케줄링(middle level scheduling)은 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하는 방식이다.

 

2. 스케줄링 고려 사항

A. 선점형 스케줄링: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도, 운영체제가 CPU를 강제로 빼앗아 올 수 있는 스케줄링 방식이다. 대표적으로 인터럽트가 이에 해당된다. CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 (문맥 전환) 커널을 깨워서 인터럽트를 처리하며, 인터럽트 처리 완료 시 원래의 작업으로 돌아간다.

B. 비선점형 스케줄링: 어떤 프로세스가 CPU를 점유하면, 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.

 

2.2 프로세스 우선순위

대부분의 CPU 스케줄러는 우선순위를 사용한다. 프로세스는 크게 커널 프로세스와 유저 프로세스로 나뉘는데, 당연히 커널 프로세스의 우선순위가 높다. 우선순위가 높다는 것은 해당 작업이 더 빨리 더 자주 실행된다는 의미이다. 참고로, 일반 프로세스의 우선순위는 사용자가 조절할 수 있다

수학 연산과 같이 CPU를 많이 사용하는 프로세스를 CPU 집중 프로세스라고 하며, 반대로 저장장치에서 데이터를 복사하거나 이동하는 등의 입출력을 많이 사용하는 프로세스를 입출력 집중 프로세스라고 한다. 일반적으로 입출력 집중 프로세스의 우선순위가 CPU 집중 프로세스의 우선순위 보다 높다. 입출력 집중 프로세스는 CPU를 사용하다가 입출력을 요구하면 대기 상태로 이동한다. 이 때 다른 프로세스가 CPU를 사용할 수 있기 때문에, 전체 시스템의 효율이 높아진다. 이를 사이클 훔치기(cycle stealing)이라고 부른다.

화면 맨 앞에 놓여 있어서 현재 입력과 출력을 사용하는 프로세스를 전면 프로세스라고 한다. 흔히 사용자와 상호작용하고 있는 프로그램을 의미한다. 반면 후면 프로세스는 사용자와 상호작용이 없는 프로세스이다. 당연히 전면 프로세스의 반응이 빨라야 하므로, 후면 프로세스에 비해 우선순위가 높다.

 

3. 다중 큐

프로세스의 우선순위가 다름을 배웠다. 프로세스의 중요도는 프로세스 제어 블록(process control block)에 표시된다. 준비 상태에 있는 프로세스들은 다중 큐(multiple queue) 자료구조로 이루어져 있다. 여기서 큐는 우선순위 별로 운영된다. 우선순위가 고정되어 운영되는 방식을 고정 운선순위 방식이라 하며, 이와 반대를 변동 우선순위 방식이라고 한다. 일반적으로 변동 우선순위 방식의 효율이 높다.

대기 상태에서도 다중 큐가 사용된다. 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여 있는 곳이다. 여기서 다중 큐는 입출력 장치별로 운영된다. 예를 들어 하드디스크에서 작업이 끝나서 인터럽트가 발생한 경우, 입출력을 요구한 프로세스에 이 인터럽트를 전달해야 한다. 이러한 경우의 검색 효율을 높이기 위하여, 입출력 장치별로 큐가 운영되는 것이다.

준비 큐에서는 한 번에 하나의 프로세스가 CPU를 할당 받는 반면, 대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다. 시스템에는 많은 입출력장치가 있기 때문에 입출력이 동시에 끝나는 경우 여러 개의 인터럽트가 한번에 처리된다. 이를 인터럽트 벡터 (interrupt vector)로 나타내며, 인터럽트 벡터에는 입출력 정보와 해당 인터럽트의 처리 방법이 담겨 있다.

 

4. 스케줄링 알고리즘

4.1 알고리즘의 효율성

- CPU 사용률

- 대기 시간

- 응답 시간

- 반환 시간

 

4.2 스케줄링 알고리즘

비선점형 알고리즘: FSFS, SJF, HRN

선점형 알고리즘: 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐

A. FCFS (First Come First Served)

말 그대로 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다. 작업이 오래 걸리는 프로세스가 있으면 다른 프로세스들은 한없이 기다려야 하고, 전체적으로 시스템 효율이 매우 떨어진다.

B. SJF (Shortest Job First)

큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. 이 경우, 시스템의 효율은 매우 좋으나 실행 시간이 긴 프로세스가 한없이 기다려야하는 문제가 있다. 또한 운영체제가 프로세스의 실행 시간을 예측할 수 없다는 문제가 있다.

C. HRN (Highest Response Ratio Next)

SJF 스케줄링에서 발생하는 아사 문제를 해결하기 위한 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고 한다. 우선순위를 계산함에 있어 특정한 식을 사용하는데, 이 때 우선순위에 대기 시간을 고려하는 방식으로 실행 시간이 긴 프로세스가 일정 시간이 지나면 CPU를 할당받도록 한다. 다만 여전히 프로세스의 실행 시간을 예측할 수 없다는 점이 한계이다.

D. 라운드 로빈 (Round Robin)

'순환 순서 방식' 스케줄링은 한 프로세스가 '타임 슬라이스' 동안 작업을 하다가 작업이 완료되지 못하면 준비 큐의 맨 뒤로 가서 차례를 기다리는 방식이다. 동시에 여러 프로세스가 실행되는 것처럼 시스템 운영이 가능하나, 문맥 교환 등의 추가 비용이 발생한다. 때문에 타임 슬라이스의 크기를 적절히 정하는 것이 중요하다. 참고로 유닉스 운영체제에서는 타임 슬라이스가 10~200mS로 조정된다.

E. SRT (Shortest Remaining Time)

SRT 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다. CPU 할당 시에 잔업 시간이 짧은 대로 할당되지만, CPU를 점유함에 있어 타임아웃이 적용된다.

F. 우선순위 스케줄링

프로세스의 우선순위를 반영한 스케줄링이다. 

G. 다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러개 사용하는 방식이다. 우선순위가 2인 큐의 프로세스는 우선순위가 1인 큐의 프로세스가 끝날 때까지 기다려야 한다. 이 경우 우선순위가 낮은 프로세스의 대기시간이 너무 커질 수 있는데, 이를 해결하기 위해 고안된 것이 밑의 다단계 피드백 큐 스케줄링이다.

H. 다단계 피드백 큐 스케줄링 (Multilevel Feeback Queue)

다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위를 강등시킨다. 즉, CPU를 사용한 뒤 프로세스는 원래의 큐가 아닌 우선순위가 하나 낮은 큐의 끝으로 돌아간다. 다단계 피드백 큐 스케줄링은 또한 우선순위에 따라 타임 슬라이스의 크기가 다르다. 이는 우선순위가 낮은 프로세스가 CPU를 획득하기 어렵기 때문에, 획득 시에 CPU를 좀더 오래 사용하도록 함이다.

다단계 피드백 큐 스케줄링은 대표적인 변동 우선순위 알고리즘으로, 오늘날의 운영체제가 일반적으로 사용하는 방식이다. 유닉스 운영체제가 10~200mS의 타임슬라이스 크기를 조정하는 것도 바로 다단계 피드백 큐 스케줄링을 사용하기 때문이다.

 

5. 인터럽트

초기의 프로그래밍 방식은 프로그램 혹은 코드를 위에서 한 줄씩 차례로 실행하는 순차적 프로그래밍이었다. 순차적 프로그래밍은 가장 일반적인 방식이지만 특정 문제를 해결하는 데 매우 취약하다. 예컨대 아래의 윈도우 버튼을 보자. 이 버튼을 순차적 프로그래밍으로 구현하는 것은 아주 고역이다. 순차적 프로그래밍에서는 저 버튼들이 눌렸는지 여부를 주기적으로 직접 확인해야하기 때문이다. 오늘날의 프로그래밍은 버튼이 눌리면 프로세스에 알려주는 방식을 사용하는데, 이를 이벤트 드리븐 (Event-Driven)이라고 한다.

인터럽트도 이와 유사한 개념이다. 과거에는 프로세스가 입출력을 요청하면 운영체제가 주기적으로 입출력장치를 직접 확인하여 처리하였다. 그러나 입출력장치의 수가 크게 늘어나면서 이러한 방식은 곧 폐기되었으며, 인터럽트의 개념이 도입되었다. 즉, 입출력이 완료되면 이를 프로세스에 알리는데 이를 인터럽트라고한다.

인터럽트에는 해당 인터럽트의 처리 방법이 같이 정의되어 있다. 즉 인터럽트는 인터럽트 번호와 인터럽트 처리 함수로 이루어져 있다. 여기서 인터럽트 번호는 (윈도우의 IRQ) 인터럽트의 종류를 가리킨다. 현대 컴퓨터는 입출력장치의 수가 워낙 많기 때문에 동시에 여러 인터럽트가 발생하기도 한다. 때문에 이를 처리하기 위해 인터럽트 벡터를 사용한다.

인터럽트 벡터에는 각 인터럽트를 처리하는 함수가 연결되어 있다. 이 함수를 인터럽트 핸들러 (Interrupt Handler)라고 한다. 인터럽트의 처리 과정은 아래와 같다.

- 인터럽트 발생시 현재 실행 중인 프로세스가 중단되고, 관련 정보를 임시로 저장한다.

- 문맥 전환되어 인터럽트 컨트롤러 프로세스가 CPU를 점유하고, 인터럽트 처리 순서를 결정한다.

- 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행된다.

- 인터럽트 처리 후 정지된 프로세스가 다시 실행되거나 종료된다. 

 

운영체제와 관련된 커널 프로세스가 실행되는 상태를 커널 모드 (kernel mode)라고 하며, 사용자 프로세스가 실행되는 상태를 사용자 모드 (user mode)라고 한다. 이는 특정 레지스터의 값으로 구분된다. 사용자 프로세스가 하드디스크에 입출력 따위의 커널 기능을 사용하려면 시스템 호출을 이용하여 커널 프로세스에 작업을 요청해야만 한다. 사용자 프로세스는 시스템 호출 뒤 대기 상태로 전환되고, 커널 프로세스가 요청받은 작업을 처리한다. 이렇게 운영체제가 두 모드를 전환하며 일을 처리하는 것을 이중 모드 (dual mode)라고 한다.

이중 모드는 컴퓨터 시스템을 보호하기 위해 사용하는 기법이다. 운영체제는 사용자 프로그램이 커널 함수들을 보다 쉽게 사용할 수 있도록 API (Application Programming Interface)를 제공한다.