[컴퓨터 구조] 혼자 공부하는 컴퓨터구조 + 운영체제 Chapter 11 CPU 스케줄링

Chapter 11. CPU 스케줄링

 

 

요약

CPU 스케줄링의 개념과 방법들에 대해 공부할 수 있었다.

 

내용 정리

11-1. CPU 스케줄링 개요

 

CPU 스케줄링

 

CPU 스케줄링 (CPU scheduling)

• 운영체제가 프로세스들에게 정해진 규칙으로 CPU 자원을 배분하는 것
• CPU 스케줄링에 따라 컴퓨터 성능에 큰 영향을 미침
  • 반드시 실행되야 할 프로그램이 적절히 실행되야 함
  • 급한 프로세스는 우선 실행되고, 급하지 않은 프로세스들은 차선으로 실행할 수 있어야 함
  • 프로세스에 CPU 자원 배분이 질서적으로 가능해야 함

 

프로세스 우선순위

 

프로세스

• 프로세스는 일의 중요도에 따라 우선순위가 존재한다.
• 우선순위가 높은 프로세스: 우선순위가 낮은 프로세스들 보다 빨리 처리 되야 하는 프로세스
• 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다.
• 프로세스마다 입출력장치나 CPU를 이용하는 시간의 차이가 존재한다.

 

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

• 입출력 작업이 많은 프로세스
• 비디오 재생, 디스크 백업 프로세스 등이 해당한다.
• 입출력 상태 (대기 상태)에 시간을 많이 사용한다.
• 입출력 버스트가 많은 프로세스다.
  • 입출력 버스트(I/O burst): 입출력장치를 기다리는 작업

 

 

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

• CPU 처리 작업이 많은 프로세스
• 수학 연산, 컴파일, 그래픽 처리 작업 등이 해당된다.
• CPU 사용 (실행 상태)에 시간을 많이 사용한다.
• CPU 버스트가 많은 프로세스다.
  • CPU 버스트(CPU burst): CPU를 이용하는 작업

 

프로세스의 우선 순위

• 대표적으로 입출력 작업이 많은 프로세스의 우선순위(priority)가 높다.
• 입출력 집중 프로세스를 빨리 실행해 입출력 장치를 먼저 작동시키고, 다음으로 CPU 집중 프로세스에 CPU를 집중적으로 할당하는 것이 효율적이기 때문
• 입출력 집중 프로세스는 입출력 장치 사용이 완료되기 전까지는 어짜피 대기상태이며, 이 때 CPU 집중 처리 프로세스를 먼저 끝내는 것이 효율적임
• 입출력작업이 많은 프로세스 외에도 실시간 프로세스, 백그라운드 프로세스 등의 우선순위도 높게 나타난다.

 

프로세스에 CPU를 효율적으로 배분하는 방법

 

1. CPU 사용 요청을 우선한 프로세스부터 실행

• 간단하고 합리적으로 보임
• 하지만 프로세스마다 일의 우선순위가 다른 경우 반영하기 어려움

 

2. 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행

• 운영체제는 각 프로세스의 PCB에 우선순위를 명시한다.
• PCB에 적힌 우선순위 기준으로 처리할 프로세스를 결정한다.
• 우선순위가 높은 프로세스는 더 빨리, 자주 실행된다.

 

프로세스 우선순위 확인하기

• 리눅스에서는 ps -el 명령어를 통해 우선순위 확인이 가능하다.

 

• 리눅스는 nice 명령어를 통해 일부 프로세스 우선순위를 변경할 수 있다.

 

• 윈도우는 별도의 소프트웨어를 통해 우선순위 확인과 변경이 가능하다 (Process Explorer).

 

 

---

스케줄링 큐

 

운영체제의 프로세스 관리 비효율성

• 운영체제가 프로세스마다의 우선순위를 확인하는 것은 비효율적이며 시간이 오래 걸린다.
• CPU뿐만 아니라 메모리, 입출력장치, 보조기억장치를 사용하려는 프로세스들을 운영체제가 모두 관리하기 어렵다.

 

스케줄링 큐(scheduling queue)

• 프로세스들은 사용할 자원을 요청하고, 해당 자원의 대기줄에서 허가 응답을 기다린다.
• 여기서 큐는 일반적인 큐와 달리 선입선출일 필요는 없다.
• 운영체제는 자원을 큐로 관리하고, 대표적으로 준비 큐와 대기 큐가 존재한다.
  • 준비 큐(ready queue): CPU를 이용할 프로세스들이 서는 줄
  • 대기 큐(wating queue): 입출력장치를 이용하기 위해 대기 상태에 있는 프로세스들이 서는 줄

 

준비 큐

• 준비 상태에 있는 프로세스의 PCB는 준비 큐에 삽입돼 CPU 사용을 기다린다.
• 운영체제는 PCB들이 삽입된 순서대로 프로세스를 인출하나, 우선순위가 높은 프로세스는 먼저 실행한다.
• 즉, 우선순위가 낮은 프로세스보다 높은 프로세스가 순서보다 먼저 처리될 수 있다.

 

대기 큐

• 같은 입출력장치를 요구한 프로세스들은 같은 대기 큐에 존재한다.
• 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 해당 프로세스의 PCB를 대기 큐에서 제거하고 준비 큐에 이동한다.

 

준비 큐와 대기 큐를 반영한 프로세스의 상태 다이어그램

 

 

---

 

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

 

선점형 스케줄링(preemptive scheduling)

• 프로세스가 자원을 사용하더라도 운영체제가 해당 프로세스로부터 자원을 강제로 뺏어 다른 프로세스에 할당할 수 있는 스케줄링 방식
• 하나의 프로세스는 자원을 독점할 수 없다.
• 보통 프로세스마다 특정 시간만큼 자원을 사용하고, 시간이 지나면 타이머 인터럽트가 발생한다.
• 타이머 인터럽트가 발생하면 CPU는 자원을 빼앗아 다른 프로세스에 할당한다.
• 현재는 대부분 선점형 스케줄링 방식을 차용하고 있다.

 

 

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

• 하나의 프로세스가 사용이 종료되거나 스스로 대기상태로 변경되기 전까진 다른 프로세스가 해당 자원을 사용할 수 없는 스케줄링 방식
• 프로세스는 자원 사용을 독점할 수 있다.
• 동일한 자원을 요구하는 다른 프로세스들은 특정 프로세스의 자원 사용이 끝날 때 까지 대기해야 한다.

 

 

선점형과 비선점형의 장단점

 

선점형 스케줄링

• 장점
  • 더 급한 프로세스 언제든지 끼어들 수 있다.
  • 특정 프로세스의 자원 독점을 막고, 프로세스에 자원을 골고루 배분할 수 있다.
• 단점
  • 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

비선점형 스케줄링

• 장점
  • 문맥 교환 횟수가 적어 오버헤드 발생이 적다.
• 단점
  • 하나의 프로세스가 자원을 사용하면 동일 자원을 사용하는 다른 프로세스들은 모두 기다려야 한다.
  • 프로세스들이 자원을 골고루 활용할 수 없다.

 

 

 

---

 

 

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

 

 

스케줄링 알고리즘 핵심

• CPU 스케줄링 알고리즘 종류는 매우 다양하고, 운영체제마다 다른 스케줄링 알고리즘을 사용한다.
• 중요한 것은 스케줄링 알고리즘에 사용된 "아이디어"이다. 종류가 많기 때문에 용어를 모두 숙지할 필요는 없다.
• 각 알고리즘의 작동방식과 장단점을 이해하는데 집중하는 것이 좋다.

 

스케줄링 알고리즘 대표 종류

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

 

---

 

1. 선입 선처리 스케줄링 (First Come First Served Scheduling)

• 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식
• FCFS 스케줄링으로도 불린다.

 

선입 선처리 스케줄링 단점

• 방식은 공정해 보이지만 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 단점이 있다.
• 호위효과(convoy effect)가 발생할 수 있다.
  • 단지 늦게 입력됐다는 이유로 프로세스가 앞에 프로세스들을 무작정 기다려야 하는 현상

 

 

2. 최단 작업 우선 스케줄링 (Shortest Job First Scheuling)

• 준비 큐에 삽입된 프로세스 중 CPU 이용 시간 길이가 가장 짧은 프로세스부터 실행하는 비선점형 스케줄링 방식
• SJFS 스케줄링으로도 불린다.

 

 

3. 라운드 로빈 스케줄링 (Round-Robin scheduling)

• 선입 선처리 스케줄링 + 타임 슬라이스 개념이 더해진 스케줄링 방식
  • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 프로세스들이 타임 슬라이스 시간만큼 돌아가며 CPU를 사용하기 때문에 선점형 스케줄링이다.
• 프로세스가 타임 슬라이스안에 완료되지 못하면 문맥 교환이 발생한다 (자원 사용이 중지되고, 큐의 맨뒤에 재삽입).

 

타임 슬라이스의 크기가 매우 중요하다.

• 지나치게 긴 경우: 선점형 스케줄링과 차이가 없어 호위 효과가 발생할 수 있음
• 지나치게 짧은 경우: 문맥 교환 발생 비용이 커 프로세스 전환에 오버헤드가 크게 발생할 수 있다.

 

 

4. 최소 잔여 시간 우선 스케줄링 (Shortest Remaining Time)

• 최단 작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘을 합친 스케줄링 방식
• SRT 스케줄링으로도 불린다.
• 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하고, 다음 프로세스는 남아있는 작업 시간이 가장 작은 프로세스가 선택된다.

 

 

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

• 프로세스에 우선순위를 부여하고, 가장 높은 우선수위인 프로세스부터 실행하는 스케줄링 알고리즘이다.
• 우선순위가 같은 프로세스들은 선입 선처리 방식으로 스케줄링된다.

 

우선순위 스케줄링 단점

• 기아(starvation) 현상이 발생할 수 있다.
  • 우선순위가 낮은 프로세스는 준비 큐에 삽입된 순서에 상관없이 우선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 현상

 

 

6. 다단계 큐 스케줄링(multi-level queue scheduling)

• 우선순위별로 준비 큐 여러 개를 사용하는 스케줄링 방식
• 우선순위 스케줄링의 발전 형태
• 우선순위가 가장 높은 큐의 프로세스를 먼저 처리하고, 우선순위가 높은 큐가 비어있으면 그 다음 순위의 큐 프로세스들을 처리하는 방식
• 즉, 우선순위에 따른 큐가 여러개 존재한다.

 

다단계 큐 스케줄링 장점

• 프로세스 유형별 우선순위를 큐로 구분해 실행하기 편하다.
• 큐별로 타임 슬라이스를 다르게 설정할 수 있다.
• 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
  • ex> 우선순위 낮은 큐의 타임슬라이스 크기는 크게, 높은 큐의 타임 슬라이스 크기는 작게..
  • ex2> 우선순위가 낮은 큐는 라운드 로빈 스케줄링, 우선순위가 높은 큐는 선입 선처리 스케줄링으로..

 

다단계 큐 스케줄링 단점

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

 

 

7. 다단계 피드백 큐 스케줄링(multi-level feedack queue scheduling)

• 다단계 큐 스케줄링 + 프로세스들이 큐 사이를 이동할 수 있다.
• 새로 준비 상태가 된 프로세스는 우선순위가 가장 높은 큐에 삽입되고 일정 시간 실행된다.
• 실행 시간 동안 종료되지 못한 경우 프로세스의 우선순위는 점점 낮아진다.
• 즉, CPU를 오래 사용하는 프로세스는 우선순위가 점차 낮아지고, 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 종료된다.
• 가장 일반적인 CPU 스케줄링 알고리즘이다.

 

다단계 피드백 큐 스케줄링 장점

• 프로세스들이 큐 사이를 이동할 수 있어 에이징(aging) 기법을 통해 기아 현상을 예방할 수 있다.
  • 에이징 기법: 오래동안 대기한 프로세스들의 우선순위를 점차 높이는 방식

 

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

• 구현이 복잡하다.

 

 

 

주요 Point

• 같은 장치를 요구하는 프로세스들은 같은 대기큐에서 대기한다.
  • 즉, 장치가 다르면 다른 대기큐로 분리된다.

 

• 선점형 스케줄링은 인터럽트가 발생했을 때 프로세스가 사용하는 CPU 자원을 빼앗아 다른 프로세스에 자원을 할당한다.
  • 타이머 인터럽트: 특정 시간이 지나서 CPU 자원을 할당받는 시간이 지났을 때 발생

 

• 오버헤드: 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등이 추가적으로 사용되는 현상을 말한다.