🎩CPU 스케줄링 개요
- CPU 스케줄링
운영체제가 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 것
🎨프로세스 우선순위
- 프로세스마다 우선순위가 다르다.
- 입출력 집중 프로세스는 대기 상태에 더 많이 머무른다.
- CPU 집중 프로세스는 실행 상태에 더 많이 머무른다.
- 입출력 작업이 많은 프로세스(입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스(CPU 집중 프로세스)의 우선순위보다 높다.
- 프로세스의 중요도에 맞게 CPU를 이용할 수 있도록 하기 위해 프로세스마다 우선순위를 부여한다.
운영체제는 PCB에 우선순위를 명시한다.
👑스케줄링 큐
- 다음 프로세스를 찾기 위해 모든 PCB를 보는 것은 비효율적이다.
- 그래서 목적에 맞는 큐에 삽입하여 줄을 세운다.
이 큐는 반드시 선입선출 방식일 필요는 없다.
준비 큐와 대기 큐
-
준비 큐
CPU를 이용하고 싶은 프로세스들이 서는 줄 -
대기 큐
입출력장치 이용을 위해 대기 상태에 접어든 프로세스들이 서는 줄
같은 장치를 요구한 프로세스들은 같은 큐에서 대기한다. -
프로세스 상태 다이어그램 세분화
🎠선점형과 비선점형 스케줄링
선점형 스케줄링
- 프로세스가 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 방식
- 자원 사용을 독점할 수 없는 방식
- 장점
- 어느 한 프로세스의 자원 독점을 막음
- 프로세스들에 골고루 자원 배분 가능
- 단점
- 문맥 교환 과정에서 오버헤드 발생 가능
비선점형 스케줄링
- 자원할 사용하고 있다면 종료되거나 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 방식
- 자원 사용을 독점할 수 있는 방식
- 장점
- 선점형에 비해 문맥 교환에서 발생하는 오버헤드가 적다
- 단점
- 모든 프로세스가 골고루 자원 이용하기 어렵다.
🔥CPU 스케줄링 알고리즘🔥
⚽선입 선처리 스케줄링
- = FCFS (First Come First Served) 스케줄링
- 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 방식
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 단점
기다리는 시간이 매우 길어질 수 있다 (= 호위 효과)
위 그림에서 C는 2ms 실행을 위해 22ms를 기다린다.
⚾최단 작업 우선 스케줄링
- SJF (Shortest Job First) 스케줄링
- 호위효과를 방지하기 위해 CPU 사용 시간이 긴 프로세스는 나중에 실행하고, 짧은 프로세스는 먼저 실행하는 방식
- 기본적으로 비선점형 알고리즘으로 분류되지만, 선점형으로도 구현 가능하다.
🥎라운드 로빈 스케줄링
- = RR (Round Robin) 스케줄링
- 선입 선처리 스케줄링에 타임 슬라이스라는 개념 더해진 방식
- 타임 슬라이스 : 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링 방식
- 큐에 삽입된 프로세스들은 정해진 시간만큼 순서대로 CPU를 이용
- 시간을 모두 사용했더라도 완료되지 않았으면 큐의 맨 뒤에 삽입(문맥교환)
- 타임 슬라이스의 크기가 중요하다.
- 타임 슬라이스가 너무 커지면 선입 선처리 방식과 다를 바 없다.
- 너무 작으면 문맥 교환에 발생하는 오버헤드 때문에 CPU 부담 커짐
🏀최소 잔여 시간 우선 스케줄링
- = SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 정해진 시간만큼 CPU를 이용, 다음으로 CPU를 이용하는 프로세스는 남은 작업 시간이 가장 적은 프로세스
🏐우선순위 스케줄링
- 프로세스들에 우선순위 부여, 우선순위 높은 프로세스부터 실행
- 우선순위 같으면 선입 선처리로 스케줄링
- 최단 작업 우선, 최소 잔여 시간은 우선순위 스케줄링이라고 볼 수 있다.
- 단점 : 기아 현상
- 우선 순위 높은 프로세스만 실행 → 우선순위 낮은 프로세스는 큐에 먼저 삽입되더라도 실행 연기
- 기아 현상을 방지하기 위한 기법 : 에이징
오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
🏈다단계 큐 스케줄링
- = Multilevel queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스 먼저 처리
- 가장 높은 큐 비었으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 프로세스 유형별로 우선순위를 구분하여 실행하는 것 편리
🏉다단계 피드백 큐 스케줄링
- = Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다.
- 기아 현상 발생 가능
작동 방식
-
새로 준비 상태가 된 프로세스가 있다면 가장 우선순위 높은 큐에 삽입되고 타임 슬라이스 동안 실행
-
해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐에 삽입
결국 CPU를 오래 사용하는 프로세스는 점차 우선순위 낮아진다.
즉, CPU 집중 프로세스들은 우선순위 낮아지고 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행된다. -
낮은 우선순위에서 오래 기다리는 프로세스가 있다면 에이징 기법을 적용해 높은 큐로 이동, 기아 현상 예방
- 구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘
미션
p. 304의 확인 문제 1번 풀고 인증하기
1 : 생성 상태
2 : 준비 상태
3 : 실행 상태
4 : 종료 상태
5 : 대기 상태
Ch.11(11-2) 준비 큐에 A,B,C,D 순으로 삽입될 때 선입 선처리, 최단 작업 우선, 라운드 로빈, 우선순위 스케줄링에서 어떤 프로세스로 CPU를 할당 받는지 정리해보기
-
선입 선처리
먼저 들어온 프로세스부터 CPU 할당
호위 효과가 발생할 수 있다. -
최단 작업 우선
CPU 이용 시간 짧은 프로세스부터 실행 -
라운드 로빈
먼저 들어온 프로세스부터 정해진 타임 슬라이스만큼 실행
타임 슬라이스가 너무 크거나 너무 작지 않아야 한다. -
우선순위 스케줄링
프로세스에 우선순위를 부여하고 높은 우선순위부터 실행
기아 현상이 발생할 수 있다. -> 에이징 기법으로 해결 가능
