[4주차] Chapter 11. 우선순위, 스케줄링 큐, 스케줄링 알고리즘

Chapter 11 CPU 스케줄링

---

11-1 CPU 스케줄링 개요

1. 프로세스 우선순위

① CPU 스케줄링 (CPU scheduling)

 -운영체제가 프로세스들에게 CPU 자원을 배분하는 것 

 

② 우선순위(priority)

 -운영체제가 각 프로세스의 중요도에 맞게 CPU를 이용할 수 있도록 프로세스마다 부여하는 것

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

 

③ 입출력 집중 프로세스(I/O bound process)

 -입출력 작업(ex. 비디오 재생, 디스크 백업 작업)이 많은 프로세스=입출력 버스트(I/O burst, 입출력장치를 기다리는 작업)가 많은 프로세스

 -입출력을 위한 대기 상태에 더 많이 머무른다. 

 -우선순위가 높다.

 

④ CPU 집중 프로세스(CPU bound process)

 -CPU 작업(ex. 복잡한 수학 연산, 컴파일, 그래픽 처리 작업)이 많은 프로세스=CPU 버스트(CPU burst, CPU를 이용하는 작업)가 많은 프로세스

 -실행 상태에 더 많이 머무른다.

 

2. 스케줄링 큐

① 스케줄링 큐(scheduling queue) 큐는 본래 선입선출의 자료 구조이나, 이 큐는 반드시 선입선출일 필요는 없다.

 -운영체제가 프로세스를 줄 세우고, 이 줄을 구현하고 관리하기 위한 자료 구조

 -메모리로 적재되고 싶은 프로세스들, CPU를 이용하고 싶은 프로세스들, 특정 입출력장치를 이용하고 싶은 프로세스들을 큐에 삽입하여 줄 세운다.

 

② 준비 큐(ready queue)

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

 -준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입된다.

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

 

③ 대기 큐(waiting queue)

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

 -특정 입출력장치를 이용하기 위해 PCB는 대기 큐의 마지막에 삽입된다.

 -입출력이 완료되어 완료 인터럽트가 발생 시, 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고 해당 PCB를 준비 상태로 변경, 대기 큐에서 제거

→해당 PCB는 준비 큐로 이동 

 

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

① 선점형 스케줄링(preemptive scheduling)

 -프로세스가 CPU를 비롯한 자원을 사용중이어도 운영체제가 강제로 자원을 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식 

 -타이머 인터럽트가 발생하면 운영체제가 CPU 자원을 빼앗아 할당하는 것이 대표적 예시

 -장점 : 언제든지 다른 프로세스가 끼어들 수 있고, 한 프로세스의 자원 독점을 막고 여러 프로세스에 골고루 자원을 배분할 수 있다.

 -단점 : 문맥 교환 과정에서 오버헤드가 발생할 수 있다. 

 

② 비선점형 스케줄링(non-preemptive scheduling)

 -한 프로세스가 자원을 사용중이라면 프로세스가 종료되거나 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식 

 -장점 : 문맥교환의 횟수가 선점형 스케줄링보다 적어서 오버헤드 또한 적다

 -단점 : 당장 자원을 사용해야하는 상황에서도 기다려야 하고, 하나의 프로세스가 자원 사용을 독점할 수 있다.   

---

확인문제

1. ④, 비선점형 스케줄링이 프로세스가 이용중인 자원을 빼앗을 수없는 방식이다.  

2. ① 준비 큐, ② 대기 큐

3. ②, 비선점형 스케줄링이 문맥 교환 과정의 오버헤드가 선점형 스케줄링에 비해 적다. 

---

11-2 CPU 스케줄링 알고리즘

1. 스케줄링 알고리즘의 종류

① 선입 선처리 스케줄링(FCFS 스케줄링(First Come First Served Scheduling))

 -준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식

 -프로세스들의 대기 시간이 길어질 수 있다는 부작용이 있다.

 -호위 효과(convoy effect, 다른 프로세스가 먼저 삽입되어서 오랜 시간 동안 기다려야 하는 현상)가 발생할 수 있다.   

 

② 최단 작업 우선 스케줄링(SJF 스케줄링(Shortest Job First Scheduling))

 -준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식 

 -기본적으로 비선점형 스케줄링 방식으로 분류

 -선점형 최단 작업 우선 스케줄링 : 선점형으로 구성된 최단 작업 우선 스케줄링(=최소 잔여 시간 우선 스케줄링) 

 

③ 라운드 로빈 스케줄링(round robin scheduling)

 -정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링 방식 

 -큐에 삽입된 순서대로 CPU를 이용하되, 정해진 시간만큼만 이용하고 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입, 이때 문맥 교환 발생

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

 -타임 슬라이스의 크기가 중요하다. (너무 크면 : 호위 효과가 발생할 수 있다. / 너무 작으면 : 문맥 교환에 발생하는 비용이 커서 비효율적이다.)  

 

④ 최소 잔여 시간 우선 스케줄링(SRT(Shortest Reamining Time) 스케줄링)

 -최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 선점형 스케줄링 방식

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

 

⑤ 우선순위 스케줄링(priority scheduling)

 -프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 비선점형 스케줄링 방식

(우선순위가 같다면 선입 선처리한다.)

 -최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링이 이 알고리즘의 일종으로 볼 수 있다.

 -기아(starvation) 현상(우선순위가 낮은 프로세스들이 먼저 삽입되어도 우선순위가 높은 프로세스들의 실행에 의해 계속 연기되는 현상)이 발생할 수 있다. 

 -에이징(aging) : 오랫동안 대기한 프로세스의 우선순위를 점차 높여 기아 현상을 방지하기 위한 기법 

 

⑥ 다단계 큐 스케줄링(multilevel queue scheduling)

 -우선순위 별로 준비 큐를 여러개 사용하는 선점형 스케줄링 방식

 -프로세스 유형별로 우선순위를구분하여 실행하는 것이 편리해진다.

 -큐별로 타임 슬라이스, 스케줄링 알고리즘을 다양하게 사용할 수 있다.   

 -프로세스들이 큐 사이를 이동할 수 없어 기아 현상이 발생할 수 있다. 

 

⑦ 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

 -다단계 큐 스케줄링과 비슷하게 작동하나, 프로세스들이 큐 사이를 이동할 수 있는 선점형 스케줄링 방식

 -프로세스가 현재 속한 큐에서 실행이 완료되지 않으면 다음 우선순위 큐로 삽입된다. (CPU를 오래 사용할수록 우선순위가 낮아진다.)

→CPU 집중 프로세스들은 우선순위가 낮아지고, 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 끝난다.

 -프로세스들이 큐 사이를 이동할 수 있으므로 에이징 기법의 적용이 가능하다.

∴CPU 이용 시간이 길면 우선순위가 낮은 큐로 이동시키고, 대기 시간이 너무 긴 프로세스를 우선순위 큐로 이동시킬 수 있다.      

---

확인문제

1. ③, 선입선처리는 먼저 삽입된 순서대로 처리하기 때문이다.  

2. ① 기아 현상, ② 에이징