CPU 스케줄링(CPU Scheduling)
운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
-
프로세스들에게 CPU를 배분을 현명하게 하지 못하면 실행되어야 할 프로세스들이 실행되지 못한다.
-
급하지 않은 프로세스들만 주로 실행되는 무질서한 상태가 발생할 수 있다.
프로세스 우선순위
프로세스마다 우선순위가 다르다.
우선순위가 높은 프로세스의 대표로는 입출력 장치가 있다.
프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다.
- 입출력 집중 프로세스 (I/O bound process)
: 비디오 재생이나 디스크 백업 작업 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스- CPU집중 프로세스 (CPU bound process)
: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스
- 입출력 집중 프로세스 = 대기 상태에 머무르는 것이 많다. > 실행 상태
- CPU 집중 프로세스 = 대기 상태 < 실행 상태에 머무르는 것이 많다.
- CPU 버스트 (CPU burst)
: CPU를 이용하는 작업
: CPU 집중 프로세스 = CPU 버스트가 많은 프로세스- 입출력 버스트 (I/O burst)
: 입출력장치를 기다리는 작업
: 입출력 집중 프로세스 = 입출력 버스트가 많은 프로세스
운영체제는 프로세스마다 우선순위(priority)를 부여한다.
프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위함이다.
스케줄링 큐(Scheduling queue)
운영체제는 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세워 기다리도록 요구한다.
이 줄을 스케줄링 큐로 구현하고 관리한다.
-
큐는 선입선출(First In Frist Out) 자료 구조
스케줄링에서 큐는 반드시 선입선출 방식일 필요 없다. -
운영체제가 관리하는 대부분의 자원은 큐로 관리된다.
큐의 종류
- 준비 큐 (ready queue)
: CPU를 이용하고 싶은 프로세스들이 서는 줄- 대기 큐 (waiting queue)
: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
선점형과 비선점형 스케줄링
1. 선점형 스케줄링 (preemptive scheduling)
: 하나의 프로세스가 자원을 사용하고 있을 때 다른 프로세스가 해당 자원을 빼앗을 수 있는 스케줄링
-
장점
: 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있다. -
단점
: 자원 배분하는 만큼 문맥 교환 과정에서 오베헤드 발생
2. 비선점형 스케줄링 (non-preemptive scheduling)
: 빼앗을 수 없는 스케줄링
-
장점
: 문맥 교환 횟수가 선점형 스케줄링보다 적기 때문에 교환에서 발생하는 오버헤드는 선점형 스케줄링이 적다. -
단점
: 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야 한다. 모든 프로세스가 골고루 자원을 사용할 수 없다.
CPU 스케줄링 알고리즘
스케줄링 알고리즘의 종류
1. 선입 선처리 스케줄링 (FCFS 스케줄링 : First Come First Served Scheduling)
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
호위 효과 (Convoy effect)
: CPU를 오래 사용하는 프로세스가 먼저 실행되면 다른 프로세스는 무작정 기다릴 수밖에 없다. 그 앞의 시간들을 무작정 기다리는 것을 호위효과라고 한다.
2. 최단 작업 우선 스케줄링 (SJF 스케줄링 : Shortest Job First Scheduling)
준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 짧은 프로세스부터 실행하는 스케줄링 방식
: 기본적으로 비선점형 스케줄링 알고리즘으로 분류
: 선점형으로 구현될 수도 있다.
: 선점형 최단 작업 우선 스케줄링 뒤에 언급할 최소 잔여 시간 우선 스케줄링
3. 라운드 로빈 스케줄링 (Round robin scheduling)
선입 선처리 스케줄링 + 타임 슬라이스
정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
-
큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼 CPU를 이용 > 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. > 이때 문맥 교환이 발생
-
라운드 로빈 스케줄링은 타임 슬라이스 크기가 중요하다.
: 타임 슬라이스가 지나치게 크다면 > 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 수 있다.
: 타임 슬라이스가 지나치게 작다면 > 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는 데에 힘을 다 사용할 수 있다.
타임 슬라이스
: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
4. 최소 잔여 시간 우선 스케줄링 (SRT 스케줄링 : Short Remaining Time)
최단 작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘
: 최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
5. 우선순위 스케줄링 (Priority Scheduling)
프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
: 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
: 최단 작업 우선 스케줄링 = 작업 시간이 짧은 프로세스가 높은 우선순위
: 최소 잔여 시간 우선 스케줄링 = 남은 시간이 짧은 프로세스가 높은 우선순위
: 기아 현상의 문제가 발생
기아 (starvation) 현상
: 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 운선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 현상
에이징 (aging) 기법
: 기아 현상을 방지하기 위한 대표 기법
: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
6. 다단계 큐 스케줄링 (multilevel queue scheduling)
우선순위 스케줄링의 발전 형태
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
: 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리,
우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리
: 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리
: 큐별로 타임 슬라이스를 여러 개 지정할 수 있다.
: 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
7. 다단계 피드백 큐 스케줄링 (multilevel feedback queue scheduling)
다단계 큐 스케줄링의 발전 형태
어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘
: 다단계 큐 스케줄링은 프로세스가 큐 사이를 이동할 수 없다.
: 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있다.
: 다단계 피드백 큐 스케줄링은 큐 사이를 이동할 수 있는 방식이기 때문에 기아 현상을 에이징 기법으로 예방할 수 있다.
혼자 공부하는 컴퓨터구조 + 운영체제
11. CPU 스케줄링 (316p - 336p)
