[운영체제] CPU 스케줄링의 개념

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

---

모든 프로세스들은 CPU를 필요로 하고, 모든 프로세스들은 먼저 CPU를 사용하고 싶어 한다.

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 한다.

CPU 스케줄링은 컴퓨터 성능과도 직결되는 중요한 문제이다.

 

프로세스 우선순위

단순히 생각하면 CPU를 사용하고 싶어 하는 프로세스들을 줄 세워서 차례대로 쓰게 하면 된다.

하지만 프로세스마다 우선순위(priority)가 다르기 때문에 적절하지 못한 방법이다.

우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스이다.

입출력 작업이 많은 프로세스(=입출력 집중 프로세스(I/O bound process))의 우선순위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스(CPU bound process)) 의 우선순위보다 높다.

왜냐하면 입출력 집중 프로세스는 입출력 장치를 많이 사용하다 보니 자연스럽게 "실행 상태"보다 "대기 상태"에 더 많이 머물기 때문에 입출력 집중 프로세스를 먼저 처리하면 CPU 집중 프로세스에 집중적으로 CPU를 할당시킬 수 있기 때문이다.

이렇게 운영체제는 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

• 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위를 부여한다.
• 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.
• 자연스럽게 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행된다.

CPU 버스트와 입출력 버스트
CPU를 이용하는 작업을 CPU 버스트(CPU burst)라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst)라고 한다.
프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행된다.
그래서 입출력 집중 프로세스는 입출력 버스트가 많은 프로세스, CPU 집중 프로세스는 CPU 버스트가 많은 프로세스라고 정의할 수 있다.

 

---

 

스케줄링 큐

PCB에 우선순위가 적혀있지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 탐색하는 것은 비효율적이다.

그래서 운영체제는 줄을 서서 기다릴 것을 요구한다.

CPU를 사용하고 싶은 프로세스, 메모리에 적재되고 싶은 프로세스, 입출력 장치를 사용하고 싶은 프로세스들 모두 줄을 세우는 것이다.

운영체제는 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리한다.

큐(queue)
자료구조 관점에서 큐는 선입선출(FIFO) 구조이지만, 스케줄링에서 말하는 큐는 반드시 선입선출은 아니다.

스케줄링 큐에는 아래와 같은 종류가 있다.

• 준비 큐(ready queue) : CPU를 이용하기 위해 프로세스들이 서는 줄
• 대기 큐(waiting queue) : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

준비 상태

• 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행한다.
• 우선순위가 높은 프로세스가 있다면 높은 프로세스부터 실행한다.
• 위 방식은 선점형 스케줄링이라고 한다.

 

대기 상태

• 대기 상태에 있는 프로세스도 마찬가지로 준비 상태와 마찬가지인 규칙을 따른다.
• 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 작업을 기다린다.
• 입출력이 완료되면 해당 PCB를 찾고 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거 후, 해당 PCB를 준비 큐로 이동시킨다.

---

위 과정들을 상태 다이어그램으로 나타내면 아래와 같다.

 

---

 

선점형과 비선점형 스케줄링

선점형 스케줄링(preempitve schduling)

프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미

• 우선순위가 높은 프로세스가 언제든 끼어들어 사용할 수 있는 방식
• 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용
• 정해진 시간을 모두 써서 타이머 인터럽트가 발생하면 운영체제가 CPU를 빼앗고, 다른 프로세스에게 CPU를 할당한다.

 

장점과 단점은 아래와 같다.

• 장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원 배분 가능
• 단점 : 문맥 교환 횟수가 많아서 오버헤드 발생 횟수가 높다.

 

비선점형 스케줄링(non-preempitve schduling)

하나의 프로세스가 CPU를 비롯한 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링

• 우선순위가 높은 프로세스가 끼어들어 사용할 수 없는 방식
• 어느 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
• 어떤 프로세스가 CPU를 사용 중이라면 해당 프로세스가 CPU를 원하는 만큼 다 쓸 때까지 다른 프로세스들은 기다려야 한다.

 

장점과 단점은 아래와 같다.

• 장점 : 문맥 교환 횟수가 적어서 오버헤드 발생 횟수가 적다.
• 단점 : 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 프로세스라도 무작정 기다릴 수밖에 없다.

오버헤드(overhead)
오버헤드는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.
여기서 오버헤드는 문맥 교환을 할 때 지금까지 작업해야 하는 내용을 백업하거나 다시 불러올 때 생기는 비용을 뜻한다.