[CS] CPU 스케줄링

하이안뇽방가

오늘은 운영체제의 핵심개념인 CPU 스케줄링에 대해 알아보겠스빈다

렛츠 고도리

 

---

CPU 스케줄링이란?

CPU의 코어는 한 코어당 하나의 프로세스밖에 처리하지 못합니다.

따라서 하나의 코어에서 여러 개의 프로세스들을 짧은 시간동안 처리하려면 시분할로 작업을 처리해야 하는데요.

여러 프로세스를 효율적으로 처리하려면 각 프로세스를 언제, 얼마나 작업을 처리할지 신중히 선택해야합니다. (저희가 해야하냐고요? 아뇨 커널이 해줍니다 ㅋ)

커널은 각 프로세스마다 형평성과 효율성에 맞게 작업 순서와 시간을 배분하는데요. 이를 CPU 스케줄링이라고 말합니다.

 

---

CPU 스케줄링의 주요 목표

CPU 스케줄링의 목표는 다음과 같습니다.

• 공정성 : 각 프로세스나 스레드가 공정하게 CPU를 사용할 수 있어야 합니다.
• 응답 시간 최소화 : 프로세스의 요청에 대한 응답 시간을 줄여야 합니다.
• 처리량 최적화 : 주어진 시간 동안 최대한 많은 작업을 처리하는 것이 중요합니다.
• 대기 시간 최소화 : 각 프로세스의 작업이 대기하는 시간을 줄여야 합니다.
• CPU사용율 최적화 : 유휴 상태에 빠진 CPU가 없이 최대한 많이 사용되도록 관리해야 합니다.

---

프로세스의 우선순위

CPU 스케줄링은 프로세스의 우선순위를 바탕으로 작업 배분을 하게 됩니다.

그렇다면 프로세스의 우선순위는 어떠한 기준으로 정해질까요?

• 커널 프로세스 vs 일반 프로세스 : 커널 프로세스는 운영체제의 중요한 작업을 처리하기 때문에, 일반 프로세스보다 우선순위가 높습니다.
• CPU 집중 프로세스 vs 입출력 집중 프로세스 : CPU를 많이 사용하는 작업을 CPU 집중 프로세스, 입출력(I/O)작업을 많이 수행하는 작업을 입출력 집중 프로세스라고 합니다. 입출력 집중 프로세스는 빠르게 입출력 대기 상태로 전환되기 때문에 시스템 효율성을 높일 수 있어 CPU 집중 프로세스보다 우선순위가 높습니다. 이를 사이클 훔치기라고 합니다.
• 전면 프로세스 vs 후면 프로세스 : 전면 프로세스는 사용자와 상호작용하는 프로세스, 후면 프로세스는 사용자와 상호작용이 없는 프로세스입니다. 전면 프로세스는 사용자와 상호작용을 통해 즉각적인 응답을 요구하므로 후면 프로세스보다 우선순위가 높습니다.

---

프로세스 상태의 다중 큐

 

프로세스의 우선순위는 프로세스 제어 블록(PCB)에 표시됩니다.

CPU스케줄러는 프로세스의 제어 블록을 탐색해서 우선순위가 가장 높은 프로세스를 작업하게 되는데요, 하지만 매번 모든 프로세스를 탐색하기는 부담이 상당히 많이 갑니다.

때문에 다중 큐 (Multiple Queue) 라는 것을 사용하게 되었습니다.

● 준비 상태의 다중 큐

왼쪽 - 정리 X , 오른쪽 - 우선순위 정렬

왼쪽 그림은 우선순위 별로 정렬하지 않은 상태입니다.

이러면 우선순위가 높은 프로세스를 찾기 위해 일일히 찾아야 해서 비용이 큽니다 ㅠ.

때문에 오른쪽 그림처럼 우선순위 별로 큐를 만든 후, 우선순위 단위로 큐를 처리하면 편합니다.

 

준비 상태의 다중 큐는 프로세스 우선순위를 배정하는 방식이 2가지가 존재하는데, 바로  고정 우선순위 방식과 동적 우선순위 방식입니다.

 

고정 우선순위란, 프로세스가 생성될 때 우선순위가 결정되며, 실행 중에 바꿀 수 없는 방식입니다. 보통 시스템이 자동으로 설정하거나 사용자가 지정합니다.

ㄴ ex) 운영체제의 중요한 작업이나 시스템 프로세스는 높은 우선순위를 가지고 실행됩니다.

 

동적 우선순위란, 프로세스가 실행되는 도중에 우선순위가 변동될 수 있는 방식입니다. 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스에 밀려 실행이 밀리는 기아 문제 (Starvation)현상을 방지하기 위해 사용합니다.

ㄴ ex) 오래 대기하는 프로세스의 우선순위를 점점 높이는 에이징(Aging) 기법을 사용할 때 자주 씁니다.

 

 

●대기 상태의 다중 큐 

입출력 단위로 큐를 만듬.

대기 상태의 다중 큐란, 위 사진처럼 각각의 입출력에 대해 대기 중인 프로세스들의 큐를 말합니다. 대기 큐는 여러 Pcb를 동시에 꺼내어 준비 상태로 옮기는 역할을 합니다.

입출력 장치들이 동시에 많이 처리될 경우 여러 개의 인터럽트를 한번에 처리해야 하는데, 이를 위해 인터럽트 벡터를 사용합니다.

 

인터럽트 벡터란,  인터럽트가 발생했을 때 어떤 인터럽트가 발생했는지 식별하고, 해당 인터럽트에 맞는 처리를 하기 위한 일종의 테이블입니다.

 

대기 큐는 사실 이름과 달리 무조건 선입선출이 아닙니다. 작업 속도를 높이기 위해 작업 순서를 뒤바꾸는 경우가 있기 때문입니다.

---

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

CPU 스케줄러는 스케줄링을 작성할 때 2가지 방식을 고려합니다. 바로 선점형 스케줄링과 비선점형 스케줄링인데요.

 

선점형 스케줄링이란, 어떤 프로세스가 작업중일 때 다른 프로세스가 작업을 위해 현재 프로세스의 작업을 중단하고 해당 프로세스의 작업을 할당받는 방식입니다. 즉 한 코어가 여러 프로세스를 작업하는 방식입니다.

 

비선점형 스케줄링이란, 선점형 스케줄링의 반대로 어떤 프로세스가 작업중일 때 다른 프로세스가 작업을 할당받지 못하도록, 즉 한 프로세스가 한 코어의 작업을 독점하는 방식입니다.

---

스케줄링 알고리즘

CPU 스케줄러는 스케줄링을 효율적으로 작성하기 위해 여러 알고리즘을 사용한다.

당연히 효율적인 알고리즘을 사용하기 위해선 평가 기준이 있어야한다. 

---

●스케줄링 알고리즘 평가 기준

CPU 스케줄러의 알고리즘 평가(목표) 기준은 다음과 같다.

• 대기 시간 (Waiting Time) : 각 프로세스가 CPU할당을 기다리는 시간을 최소화 하는 것.
• 반환 시간 (Turnaround Time) : 프로세스가 시작부터 끝날 때까지 걸리는 시간을 최소화 하는 것.
• 응답 시간 (Response Time) : 사용자가 요청을 시작한 후 첫 번째 응답을 받는 시간을 최소화하는 것.
• CPU 이용률 (CPU Utilization) : CPU가 유휴없이 최대한 많은 시간을 작업 처리에 사용하도록 하는 것.
• 문맥 전환 오버헤드(Context Switching Overhead) : 문맥 전환에 소모되는 자원을 최소화하는 것.
• 공정성(Fairness) : 기아(Starvation) 문제 없이 모든 프로세스가 공평하게 CPU를 할당받는 것.
• 처리량(Throughput) : 단위 시간당 처리할 수 있는 프로세스의 수를 최대화하는 것.
• 우선순위(priority handling) : 우선순위가 높은 프로세스에 더 많은 CPU 자원을 할당하는 것.

---

●스케줄링 알고리즘 종류

스케줄링 알고리즘에는 다양한 종류가 있지만, 크게 선점형 알고리즘과 비선점형 알고리즘을 사용하는지에 따라 나눌 수 있다.

 

●비선점형 알고리즘

 

1. FCFS 스케줄링(First Come First Served)

준비 큐에 도착한 순서대로 CPU에 작업을 할당하는 방식입니다. 준비 큐가 하나라 모든 프로세스의 우선순위가 동일합니다. 때문에 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스가 작업을 못하기 때문에 효율성이 낮아진다.

 

2. SJF 스케줄링(Shortest Job first)

준비 큐에 있는 프로세스 중에 실행 시간이 가장 짧은 작업부터 처리하는 방식입니다. 최단 작업 우선 스케줄링이라고도 합니다. 하지만 현대의 프로세스는 사용자와 빈번하게 상호 작용하기 때문에 프로그램의 실행 시간을 파악하기가 어려워 이 알고리즘을 사용하기 힘듭니다. 작은 작업부터 처리하기 때문에 효율적일 수 있으나, 실행 시간이 긴 프로세스의 CPU할당이 연기될 수 있는 기아 문제가 발생할 수 있으므로 공평성에 위배된다. 이 때, 대기 시간이 길수록 우선 순위를 높이는 에이징 방식으로 완화할 수 있다.

 

3. HRN 스케줄링(Highest Response Ratio Next)

SJF 스케줄링에서 발생할 수 있는 기아 상태를 기아 상태를 해결하기 위해 만들어진 알고리즘입니다. 최고 응답률 우선 스케줄링이라고도 합니다. SJF의 우선순위 판단 기준이 프로세스의 실행 시간이었다면, HRN은 대기 시간과 사용 시간에 대한 연산을 통하여 우선순위를 정하는 방식입니다.

HRN 스케줄링의 연산 기준

 

●선점형 알고리즘

1. 라운드 로빈 스케줄링(Round Robin)

한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 완료하지 못하면 다시 큐에 집어 넣습니다. 우선순위를 적용하지 않는 단순한 방식의 알고리즘입니다.

 

2. SRT 스케줄링(Shortest Remaining Time)

SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식의 알고리즘입니다. 최소 잔류 시간 우선 스케줄링이라고도 합니다.

라운드 로빈 스케줄링의 방식을 기본적으로 쓰되, CPU가 다음 프로세스를 할당할 때, 남은 작업 시간이 가장 적은 프로세스를 선택합니다. 하지만 이 또한 기아 문제때문에 잘 사용하지 않습니다.

 

3. 다단계 큐 스케줄링(Multi-Level Queue)

우선순위에 따라 준비 큐를 여러 개 사용하는 방식입니다. OS로부터 부여받은 우선순위에 따라 각 우선순위에 맞는 큐에 삽입됩니다. 각 우선순위 큐는 라운드 로빈 알고리즘 방식으로 운영되며, 고정 우선순위 방식을 사용합니다. 제일 상위 우선순위 큐의 모든 프로세스 작업이 끝나야 다음 우선순위 큐 작업이 시작됩니다. 때문에 하위 우선순위 큐의 작업들이 연기되는 문제가 있습니다.

3. 다단계 피드백 큐 스케줄링(Multi-Level Feedback Queue)

다단계 큐 스케줄링에서 에이징 기법을 적용해 단점을 보완한 방식입니다.

다단계 피드백 큐 방식의 특징은, CPU 할당이 끝난 프로세스가 원래 우선순위의 큐에 되돌아 가지 않고 한 단계 아래의 우선순위 큐에 들어가게 됩니다. 때문에 변동 우선순위 방식을 사용합니다. 또한 우선순위에 따라 할당하는 시간(타임 슬라이스)가 다릅니다. 우선순위가 낮은 큐의 프로세스는 CPU를 좀 더 사용할 수 있도록 타임 슬라이스를 크게 부여합니다.

요즘 운영체제가 많이 채용하는 방식입니다.

---

오늘은 CPU스케줄링에 대해 포스팅 해봤는데요?

생각보다 적을게 많아서 고생했습니다.. ;;;;;

그럼 20000 좋은 하루 되십시오