[운영체제] 스케줄링 큐와 프로세스 상태 변화 정리

스케줄링 큐

운영체제는 여러 프로세스를 관리한다.  

각 프로세스는 자신의 정보를 담고 있는 `PCB(Process Control Block)`를 가진다.

 

PCB에는 프로세스의 상태, 프로그램 카운터, 레지스터 값, 우선순위, 메모리 정보 등 프로세스를 관리하기 위한 정보가 저장된다.

 

그런데 CPU를 사용할 다음 프로세스를 찾을 때마다 운영체제가 모든 프로세스의 PCB를 하나씩 뒤지는 것은 비효율적이다.

 

CPU를 요구하는 프로세스는 많을 수 있고, 그 순간에도 새로운 프로세스가 계속 생길 수 있다.  

따라서 운영체제가 매번 전체 프로세스를 확인하면서 “누가 CPU를 써야 하지?”라고 찾는 방식은 시간이 오래 걸린다.

 

그래서 운영체제는 `스케줄링 큐`를 사용한다.

 

스케줄링 큐는 쉽게 말해, 특정 자원을 사용하고 싶어 하는 프로세스들이 서는 줄이다.

CPU 쓰고 싶은 프로세스 → 준비 큐에서 대기
입출력 장치 쓰고 싶은 프로세스 → 대기 큐에서 대기

 

즉, 운영체제가 매번 모든 프로세스를 뒤지는 것이 아니라, 자원을 기다리는 프로세스들을 큐로 관리하는 것이다.

 

큐라고 해서 반드시 FIFO는 아니다

큐라고 하면 보통 먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 구조를 떠올린다.

하지만 운영체제의 스케줄링 큐가 반드시 FIFO 방식으로 동작하는 것은 아니다.

프로세스마다 우선순위가 다를 수 있기 때문이다.

 

예를 들어 어떤 프로세스가 먼저 준비 큐에 들어왔더라도, 나중에 들어온 프로세스의 우선순위가 더 높다면 우선순위가 높은 프로세스가 먼저 CPU를 할당받을 수 있다.

 

따라서 스케줄링 큐는 단순한 줄서기라기보다, 운영체제가 프로세스의 상태와 우선순위를 기준으로 관리하는 대기 목록이라고 이해하는 것이 좋다.

 

준비 큐

준비 큐(Ready Queue)는 CPU를 사용하기 위해 기다리는 프로세스들이 들어가는 큐이다.

준비 큐에 있는 프로세스들은 이미 실행될 준비가 되어 있다.
메모리에도 올라와 있고, CPU만 할당받으면 바로 실행될 수 있다.

다만 아직 자신의 차례가 되지 않았기 때문에 기다리고 있는 상태이다.

준비 큐 = CPU를 기다리는 줄

 

예를 들어 여러 프로세스가 동시에 CPU를 사용하고 싶어 한다고 하자.

P1: CPU 쓰고 싶습니다.
P2: 저도 CPU 쓰고 싶습니다.
P3: 저도요.

 

이 프로세스들은 준비 큐에 들어간다.
운영체제의 CPU 스케줄러는 준비 큐에 있는 프로세스 중 하나를 골라 CPU를 할당한다.

이때 선택된 프로세스가 CPU를 실제로 사용하기 시작하는 과정을 디스패치(dispatch)라고 한다.

준비 큐에 있던 프로세스
→ 디스패치
→ 실행 상태

 

대기 큐

대기 큐(Waiting Queue)는 입출력 작업이 끝나기를 기다리는 프로세스들이 들어가는 큐이다.

프로세스가 실행 중에 파일 읽기, 키보드 입력, 프린터 출력, 디스크 접근 같은 입출력 작업을 요청할 수 있다.

입출력 작업은 CPU 연산에 비해 상대적으로 오래 걸린다.
그래서 입출력이 끝날 때까지 CPU를 계속 붙잡고 있으면 비효율적이다.

따라서 프로세스가 입출력을 요청하면 CPU 사용을 멈추고 대기 상태로 들어간다.

실행 중인 프로세스
→ 입출력 요청
→ 대기 큐로 이동

 

대기 큐에 있는 프로세스는 당장 CPU를 사용할 필요가 없다.
입출력 작업이 끝나야 다시 CPU를 사용할 수 있다.

대기 큐 = 입출력 완료를 기다리는 줄

 

대기 큐는 장치별로 존재할 수 있다

대기 큐는 보통 입출력 장치별로 따로 존재할 수 있다.

예를 들어 프린터를 기다리는 프로세스와 하드디스크를 기다리는 프로세스는 서로 기다리는 대상이 다르다.

그래서 운영체제는 장치별로 대기 큐를 관리할 수 있다.

프린터 대기 큐
하드디스크 대기 큐
CD-ROM 대기 큐
키보드 입력 대기 큐

같은 입출력 장치를 요구하는 프로세스들은 같은 대기 큐에서 기다린다.

예를 들어 여러 프로세스가 프린터 출력을 요청했다면, 이들은 프린터 대기 큐에서 기다리게 된다.

 

프로세스 상태 변화

CPU 자원은 한정되어 있다.
대부분의 컴퓨터에는 실행 중인 프로세스가 많지만, CPU를 동시에 사용할 수 있는 프로세스 수는 제한적이다.

그래서 프로세스들은 CPU를 번갈아 가며 사용한다.

 

프로세스의 상태 변화는 대략 다음과 같이 이해할 수 있다.

준비 상태 → 실행 상태 → 준비 상태
준비 상태 → 실행 상태 → 대기 상태 → 준비 상태

 

먼저 준비 큐에 있던 프로세스가 CPU 스케줄러에 의해 선택되면 디스패치를 거쳐 실행 상태가 된다.

준비 큐
→ 디스패치
→ 실행 상태

 

실행 중인 프로세스가 정해진 CPU 사용 시간을 모두 사용하면 타이머 인터럽트가 발생한다.
그러면 운영체제는 해당 프로세스에게서 CPU를 회수하고, 다시 준비 큐로 보낸다.

실행 상태
→ 타이머 인터럽트
→ 준비 큐

 

반대로 실행 중인 프로세스가 입출력 작업을 요청하면 대기 상태로 이동한다.

실행 상태
→ 입출력 요청
→ 대기 큐

 

입출력 작업이 완료되면 입출력 완료 인터럽트가 발생한다.
그러면 운영체제는 대기 큐에서 작업이 완료된 프로세스의 PCB를 찾고, 프로세스 상태를 대기 상태에서 준비 상태로 변경한다.

그 후 해당 프로세스를 대기 큐에서 제거하고 준비 큐에 넣는다.

대기 큐
→ 입출력 완료 인터럽트
→ 준비 큐

 

즉, 프로세스는 CPU를 기다릴 때는 준비 큐에 있고, 입출력을 기다릴 때는 대기 큐에 있다.

 

준비 큐와 대기 큐 정리

 

준비 큐와 대기 큐의 차이는 다음과 같다.

준비 큐
- CPU를 사용하기 위해 기다리는 큐
- CPU만 할당받으면 바로 실행 가능
- 프로세스 상태는 준비 상태

대기 큐
- 입출력 작업이 끝나기를 기다리는 큐
- 당장 CPU를 사용할 수 없음
- 프로세스 상태는 대기 상태

 

준비 큐에 있는 프로세스는 CPU를 기다리는 것이고, 대기 큐에 있는 프로세스는 입출력 완료를 기다리는 것이다.

선점형 스케줄링

CPU 스케줄링 방식은 크게 선점형 스케줄링과 비선점형 스케줄링으로 나눌 수 있다.

먼저 선점형 스케줄링(preemptive scheduling)은 어떤 프로세스가 CPU를 사용하고 있더라도, 운영체제가 필요하면 CPU를 빼앗아 다른 프로세스에게 넘길 수 있는 방식이다.

 

예를 들어 실행 중인 프로세스보다 우선순위가 더 높은 프로세스가 준비 큐에 들어왔다고 하자.
선점형 스케줄링에서는 운영체제가 현재 실행 중인 프로세스를 중단시키고, 우선순위가 높은 프로세스에게 CPU를 할당할 수 있다.

또는 정해진 시간만큼 CPU를 사용한 뒤 타이머 인터럽트가 발생하면, 운영체제가 CPU를 회수하고 다음 프로세스에게 넘길 수 있다.

실행 중인 프로세스
→ CPU 회수
→ 준비 큐로 이동
→ 다른 프로세스 실행

 

즉, 선점형 스케줄링에서는 하나의 프로세스가 CPU를 독점할 수 없다.

선점형 스케줄링의 장점

선점형 스케줄링의 장점은 CPU 독점을 막을 수 있다는 것이다.

한 프로세스가 너무 오래 CPU를 사용하지 못하도록 막고, 여러 프로세스에게 비교적 골고루 CPU를 배분할 수 있다.

그래서 대화형 시스템이나 시분할 시스템에서 유리하다.
사용자 입장에서는 여러 프로그램이 동시에 실행되는 것처럼 느낄 수 있다.

장점
- 특정 프로세스의 CPU 독점 방지
- 여러 프로세스에 CPU를 비교적 공평하게 배분
- 응답성이 좋음

선점형 스케줄링의 단점

단점은 문맥 교환이 자주 발생할 수 있다는 것이다.

프로세스가 바뀔 때마다 운영체제는 현재 프로세스의 상태를 PCB에 저장하고, 다음 프로세스의 상태를 PCB에서 불러와야 한다.

이 과정을 문맥 교환(context switching)이라고 한다.

문맥 교환 자체는 실제 작업을 처리하는 시간이 아니다.
따라서 너무 자주 발생하면 오버헤드가 커질 수 있다.

단점
- 문맥 교환이 자주 발생할 수 있음
- context switching overhead 증가

비선점형 스케줄링

비선점형 스케줄링(non-preemptive scheduling)은 한 프로세스가 CPU를 할당받으면, 그 프로세스가 스스로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗을 수 없는 방식이다.

즉, 실행 중인 프로세스가 종료되거나 입출력 요청으로 대기 상태에 들어가기 전까지는 CPU를 계속 사용한다.

실행 중인 프로세스가 CPU를 반납하는 경우
- 프로세스 종료
- 입출력 요청으로 대기 상태 전환

 

비선점형 방식에서는 운영체제가 강제로 CPU를 빼앗지 않는다.

비선점형 스케줄링의 장점

비선점형 스케줄링은 선점형에 비해 문맥 교환이 적게 발생한다.

프로세스가 중간에 강제로 끊기지 않기 때문에 상대적으로 구현이 단순하고, context switching overhead가 적다.

장점
- 문맥 교환 횟수가 적음
- 오버헤드가 비교적 작음
- 구현이 상대적으로 단순함

비선점형 스케줄링의 단점

단점은 한 프로세스가 CPU를 오래 사용할 수 있다는 것이다.

만약 어떤 프로세스가 CPU를 오래 사용하고 있다면, 뒤에 있는 프로세스들은 계속 기다려야 한다.
특히 짧은 작업이나 우선순위가 높은 작업도 앞의 프로세스가 끝날 때까지 기다려야 할 수 있다.

그래서 모든 프로세스가 CPU를 골고루 사용하기 어렵다.

단점
- 특정 프로세스가 CPU를 오래 점유할 수 있음
- 다른 프로세스의 대기 시간이 길어질 수 있음
- 응답성이 떨어질 수 있음

선점형과 비선점형 비교

두 방식을 정리하면 다음과 같다.

선점형 스케줄링
- 운영체제가 CPU를 강제로 회수할 수 있음
- CPU 독점을 막을 수 있음
- 응답성이 좋음
- 문맥 교환 오버헤드가 커질 수 있음

비선점형 스케줄링
- 프로세스가 CPU를 스스로 반납할 때까지 계속 사용
- 문맥 교환 오버헤드가 작음
- 구현이 단순함
- 특정 프로세스가 CPU를 오래 점유할 수 있음

간단히 말하면, 선점형은 운영체제가 중간에 개입해서 CPU를 나눠 쓰게 만드는 방식이고, 비선점형은 실행 중인 프로세스가 CPU를 반납할 때까지 기다리는 방식이다.