📅 CPU 스케줄링 개요

✔️ 프로세스 우선순위

프로세스마다 우선순위가 다르다! 우선 순위가 높을 수록 빨리 처리해야 하는 프로세스다.

프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있다

• 입출력 집중 프로세스: 비디오 재생이나 디스크 백업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스
• CPU 집중 프로세스: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스

각기 다른 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적인다! 떄문에 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

상황에 맞게, 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위를 부여한다

운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다

$*$ CPU 버스트와 입출력 버스트
CPU를 이요하는 작업을 CPU 버스트라고 하고, 입출력장치를 기다리는 작업을 입출력버스트라고 부른다
프로세스는 일반적으로 이 두 버스트를 반복하며 실행이 되는데 어떤 버스트가 더 많냐에 따라서 CPU 집중 프로세스와 입출력 집중 프로세스로 나뉘는 것이다

✔️ 스케줄링 큐

운영체제가 매번 일일이 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거로우며 오랜 시간이 걸린다

그래서 운영체제는 프로세스들에 ‘줄을 서서 기다릴 것’을 요구한다! 그리고 이 줄을 스케줄링 큐로 구현하고 관리한다

메모리로 적재되고 싶은 (새로 생성되는) 프로세스들을 큐에 삽입하여 줄을 세우고, CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다
→ 운영체제가 관리하는 대부분의 자원이 이렇게 큐로 관리 됨

👀 준비 큐 - CPU를 이용하고 싶은 프로세스들이 서는 줄

👀 대기 큐 - 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다

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

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

어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식이다

😃 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다
☹️ 문맥 교환 과정에서 오버헤드가 발생할 수 있다

🌐 비선점형 스케줄링 - 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식

하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식이다

😃 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적다
☹️ 모든 프로세스가 골고루 자원을 사용할 수 없다 (누구 하나가 자원을 사용 중이면 무작정 기다려야 함)

📆 CPU 스케줄링 알고리즘

📑 스케줄링 알고리즘의 종류

📄 선입 선처리 스케줄링

FCFS 스케줄링(First Come First Served Scheduling), 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식

공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다 (호위 효과라고 함)

📄 최단 작업 우선 스케줄링

SJF 스케줄링(Shortest Job Scheduling), 준비 큐에 삽입된 프로세스들 중 CPU 이용시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다

📄 라운드 로빈 스케줄링

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식

정해진 타임 슬라이스만큼의 시간 동안 돌아가면서 CPU를 이요하는 선점형 스케줄링으로 타임 슬라이스 크기가 매우 중요하다

$*$ 타임 슬라이스 - 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

타임 슬라이스가 지나치게 크면 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 수 있고, 너무 작으면 문맥 교환에 발생하는 비용이 커 CPU가 프로세스를 처리하는 일보다 프로세스를 전환하는데 온 힘을 다 써버릴 여지가 있다

📄 최소 잔여 시간 우선 스케줄링

SRT(Shortest Remaining Time) 스케줄링, 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식

프로세스들이 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다

📄 우선순위 스케줄링

프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
(우선순위가 같은 프로세스들은 선입 선처리로 스케줄링)

기아 현상이 발생할 수 있다!
기아 현상이란 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입이 되었음에도 불구하고 우선 순위가 높은 프로세스들에 의해서 실행이 계속 연기되는 상황을 의미한다.

이를 방지하기 위해 에이징 기법을 도입할 수 있다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식을 말한다.

📄 다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선 순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리한다

→ 큐를 여러 개 두면 프로세스 유형 별로 우선순위를 구분하여 실행하는 것이 편리해진다

📄 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링의 발전된 형태 , 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선 순위에서 너무 오래 기다리면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘

다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다 → 우선순위가 낮은 프로세스는 계속 연기될 여지가 생겨 기아 현상이 발생할 가능성이 생김!

다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있다! 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다

예를 들어, 새롭게 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행된다 → 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다 → 안끝나면 또 다음 우선순위 큐에 삽입
➡️ CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아진다

가장 일반적인 CPU 스케줄링 알고리즘