24.08.06 운영체제 - CPU의 작업 처리방식, CPU 스케줄링

CPU의 작업 처리 방식

컴퓨터를 이용할 때 프로그램을 수십, 수백개를 켜 놓고 이용한다. 그럼 그 수십수백개의 프로세스들을 고작 8개의 논리적인 스레드로 어떻게 처리하는 것일까?

이 원리를 알기 위해서는 병렬성과 동시성이라는 개념을 알고 있어야 한다.

동시성 vs 병렬성

동시성 (Concurrency)	병렬성 (Parallelism)
동시에 실행되는 것 같이 보이는 것	실제로 동시에 여러 작업이 처리되는 것
싱글 코어에서 멀티 쓰레드를 동작시키는 방식	멀티 코어에서 멀티 쓰레드를 동작시키는 방식
한번에 많은 것을 처리	한번에 많은 일을 처리
논리적인 개념	물리적인 개념

 

싱글 코어에서는 2개의 작업을 동시에 실행되는 것처럼 보이기 위해 번갈아가면서 작업을 수행한다. 이때 다른 작업으로 바꾸어 실행할 때 내부적으로 Context Switch 가 일어난다.

 

동시성이 필요한 이유?

1. 하드웨어적 한계

아무리 코어를 많이 넣어도 수십 개의 코어를 넣을 순 없으므로 하드웨어적 제한이 걸리게 되고 수십 수백개의 프로세스를 돌리기 위해선 결국 동시성이 필요하다.

 

2. 논리적인 효율

총 16개의 작업 중 8개는 오래걸리는 작업이고, 나머지 8개는 짧은 시간이 걸리는 작업이라고 할 때, 만약 오래 걸리는 작업이 동시에 먼저 처리되기 시작한다고 하면, 짧은 시간이 걸리는 8개는 현재 처리 중인 8개의 작업이 다 끝날 때까지 기다려야 할 것이다. 따라서 비효율적인 면을 극복하기 위해 작업을 아주 잘게 나눠 번걸아 가면서 처리하는 동시성이 필요하다.

 

---

문맥 전환 (Context Switching)

문맥 전환이란 하나의 프로세스가 CPU를 사용하다가 다른 프로세스가 사용할 수 있도록 이전 프로세스의 상태를 PCB에 저장하고 새로운 프로세스의 상태를 CPU에 적재하는 것을 말한다.

---

PCB(Process Control Block)

PCB(프로세스 제어 블록)는 운영체제에서 프로세스를 관리하기 위해 해당 프로세스의 상태 정보를 담고 있는 자료구조를 말한다. 프로세스 스케줄링을 위해 프로세스에 관한 모든 정보를 저장하는 임시 저장소이다.

 

PCB는 다음과 같은 항목들을 저장하고 있다. 

 

• Process Id: 프로세스의 고유 번호

• Process State : ready, wait, running 등의 실행 상태

• Program Counter(PC) : 프로그램 카운터, 다음 실행될 명령의 포인터

• CPU registers : CPU 레지스터

• CPU scheduling information : CPU 스케줄링 정보

• Memory-management information : 할당된 자원 정보

• Accounting information : CPU 사용시간 등

• I/O status information : 입출력 상태 정보

---

CPU 스케줄링

CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이다. CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다.

 

-  CPU 스케줄링의 목적

1. 공평성

- 모든 프로세스가 자원을 공평하게 배정받아야 한다. 

 

2. 효율성

- 시스템은 "유후 시간(idle)"이 없도록 사용되어야 한다.

- 유후 자원을 필요로 하는 프로세스에 "우선권"을 주어야 한다.

 

3. 안정성

- 시스템을 강제로 점유하거나, 파괴하려는 프로세스로부터 자원을 보호해야 한다.

 

4. 반응 시간 보장

- 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

 

5. 무한 연기 방지

- 특정 프로세스의 작업이 무한하게 연기되어서는 안 된다.

 

-  CPU 스케줄러

CPU가 idle 상태가 될 때마다, 운영체제는 Ready Queue에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다.

CPU 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

일반적으로 큐에 있는 레코드들은 프로세스의 PCB들이다.

 

CPU  스케줄러는 언제 스케줄링을 결정하는가?

1. 실행(running) 상태에서 대기(waiting) 상태로 전환될 때 (I/O 요청) 

2. 실행(running) 상태에서 준비(ready) 상태로 전환될 때 (인터럽트 발생)

3. 대기(waiting) 상태에서 준비(ready) 상태로 전환될 때 (I/O 종료)

4. 종료(Terminated) 될 때

---

비선점형 스케줄링(nonpreemptive)

어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식이다. 강제로 프로세스를 중지하지 않는다.

따라서 문맥 교환으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 된다.

 

1. FCFS(First Come, First Served)

가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식이다. 

Convoy Effect(호위 효과)가 발생할 수 있다. Convoy Effect는 긴 실행 시간을 필요로 하는 프로세스가 먼저 도착하면, 이후에 도착한 짧은 실행 시간을 필요로 하는 프로세스들은 긴 시간동안 대기해야 하는 현상이다. 이로 인해 시스템의 응답 시간이 느려지고, 전체 시스템의 처리 효율이 떨어지게 된다.

 

2. SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식이다.

하지만 실제로는 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 존재한다. 또한 긴 시간을 필요로 하는 프로세스가 우선순위가 계속 밀려 실행되지 못하고 무기한으로 대기하게 되는 기아(Starvation) 현상이 발생할 수 있다.

 

3. 우선순위(Priority)

각각의 프로세스에 우선순위 넘버가 있어 가장 높은 우선순위를 가진 프로세스에 할당하는 방식이다. 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄링된다. 

기아(Starvation) 문제를 해결하기 위해 노화(aging)을 사용하여 오래된 작업의 우선순위를 높여줄 수 있다.

---

선점형 스케줄링(preemptive)

어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식이다. 알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU를 할당할 수 있다.

처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버 헤드가 커질 수 있다.

 

1. 라운드 로빈(RR, Round Robin)

각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 하는 방식이다.

할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어간다.

 

2. SRTF(Shortest Remaining Time First)

현재 실행되고 있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꾸는 방식이다.

평균 대기 시간을 줄일 수 있지만, 역시 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 있다.

 

3. 다단계 큐(Multilevel Queue)

우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐는 각자의 스케줄링 알고리즘을 가진다.

우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아 현상이 나타날 수도 있으며, 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성이 떨어지는 특징이 있다.

---

임계영역

임계영역이란 프로세스 간에 공유 자원을 접근하는 데 있어 문제가 발생하지 않도록 한 번에 하나의 프로세스만 이용하게끔 보장해줘야 하는 영역을 말한다.

임계 영역 문제를 해결하기 위해서는 아래의 3가지 조건을 충족해야 한다.

 

1. 상호 배제(Mutal exclution) - 하나의 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.

2. 진행(Progress) - 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정 해주어야 한다.

3. 한정 대기(Bounded waiting) - 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음 번 임계 영역에 들어갈 때 제한을 두어야 한다.