학습 목표
•
프로세스 우선순위
•
스케줄링 큐의 개념과 필요성
•
선점형 스케줄링과 비선점형 스케줄링
•
다양한 CPU 스케줄링 알고리즘
CPU 스케줄링 개요
•
모든 프로세스는 자신이 먼저 CPU를 사용하고 싶어 한다
•
운영체제는 어떻게 CPU를 공정하고 합리적으로 할당할까?
•
컴퓨터 성능과도 직결되는 중요한 문제
프로세스 우선순위
•
내가 운영체제라고 생각
◦
각자 CPU 달라는 프로세스들에게 어떻게 할당해줘야 할까
◦
⇒ 이게 CPU Scheduling
•
프로세스는 우선순위가 있다
◦
대표적으로, 입출력이 많은 프로세스는 우선순위가 높다
◦
빨리 시작해야 효율적이기 때문
•
입출력 집중 프로세스
◦
IO bound process
◦
비디오 재생, 디스크 백업 등
◦
실행 상태 < 입출력을 위한 대기 상태
•
CPU 집중 프로세스
◦
CPU bound process
◦
복잡한 수학 연산, 컴파일, 그래픽 작업 등
◦
실행 상태 > 입출력을 위한 대기 상태
•
이렇듯 운영체제는 프로세스마다 우선순위(Priority)를 부여하여 PCB에 명시
•
우선순위가 높은 프로세스는 더 빨리, 자주 실행
우선순위 확인하기
우선순위가 높은 프로세스: 입출력 많은 프로세스, 실시간 프로세스, 일부 백그라운드 프로세스
•
unix, linux, macOS → ps -el
•
nice 명령을 통해 우선순위 변경도 가능
•
윈도우 → Process Explorer라는 소프트웨어로 확인, 변경p
스케줄링 큐
•
PCB에 우선순위가 명시 돼 있긴 하지만, 운영체제가 일일이 확인하는 것은 비효율적
•
OS가 찾아가는 대신, 프로세스가 줄을 선다 ⇒ 스케줄링 큐
◦
스케줄링에서 큐는 선입선출 큐와는 조금 다를 수도
•
OS가 관리하는 대부분의 자원은 이렇게 큐로 관리
•
다양한 큐 ⇒ 대기 큐, 준비 큐
•
준비 큐, ready queue
◦
CPU를 이용하고 싶은 프로세스들이 서는 줄
•
대기 큐, waiting queue
◦
입출력장치를 이용하고자 하는 프로세스들이 서는 줄
입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 준비상태로 변경시킨 뒤 대기 큐에서 제거 → 준비 큐로
프로세스 다이어그램
선점형과 비선점형 스케줄링
CPU: 현재 사용중인 프로세스가 있음
→ 이 때 다른 급한 프로세스가 당장 사용하길 원한다면?
1.
지금 CPU를 사용중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
→ 선점형
2.
CPU를 사용 중인 프로세스의 작업이 끝날 때까지 다른 급한 프로세스를 기다리게
→ 비선점형
선점형 스케줄링
Preemptive Scheduling
프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
•
어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
•
타이머 인터럽트가 발생해서 자원을 뺏는, 지금까지 살펴본 것도 선점형 스케줄링의 일종
비선점형 스케줄링
Non-Preemptive Scheduling
하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기상태에 접어들기 전까지는 다른 프로세스가 개입할 수 없는 스케줄링 방식
•
하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
CPU 스케줄링 알고리즘
선입 선처리 스케줄링, 최단 작업 우선 스케줄링, 라운드 로빈 스케줄링, 우선순위 스케줄링, 다단계 피드백 큐 스케줄링
•
매우 다양한 스케줄링 알고리즘이 있다. 중요한 건 여기 나온 것들을 외우는 게 아니라 대표적인 예시의 원리를 이해하고 장단점을 이해하는 것이다
선입 선처리 스케줄링
FCFS 스케줄링, First Come First Service Scheduling
단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링
•
CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
•
공정해 보이지만 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다
→ 호위 효과, Convey Effect
최단 작업 우선 스케줄링
SJF 스케줄링, Shortest Job First Scheduling
•
FCFS 의 단점을 생각하면 자연스럽게 대두될 수 있는 알고리즘
•
기본적으로 비선점형 스케줄링 알고리즘으로 분류
◦
선점형으로 구현될 수도 있긴 하다 → 이게 최소 잔여 시간 우선 스케줄링
라운드 로빈 스케줄링
Round Robin Scheduling
선입 선처리 스케줄링 + 타임 슬라이스
•
타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
•
RR은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
•
A, B, C 순으로 왔으면 ABC 반복. 위에서는 B가 끝나서 ABC후 AC 반복
•
중요! 타임 슬라이스의 크기 고려
◦
너무 크다 = FCFS와 다를 바 없어서 호위 효과 발생
◦
너무 작다 = CPU가 프로세스를 처리하는 일보다 Context Switching에 더 힘을 쓸 것
최소 잔여 시간 우선 스케줄링
SRT, Shortest Remaining Time Scheduling
최단 작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘
•
최소 잔여 시간 우선 스케줄링이 베이스
•
프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하고
•
CPU를 사용할 다음 프로세는 남아있는 작업 시간이 가장 적은 프로세스
우선순위 스케줄링
Priority Scheduling
•
가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
◦
같은 우선순위 = 선입 선처리 스케줄링
•
최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 → 넓은 의미의 우선순위 스케줄링
◦
최단 작업 우선 ← 작업 시간이 짧은 프로세스에 높은 우선순위를
◦
최소 잔여 시간 우선 ← 남은 시간이 짧은 프로세스에 높은 우선순위를
•
근본적인 문제: starving, 기아 현상
◦
우선순위가 낮은 프로세스들이 CPU를 할당받지 못하는 현상
•
해결 방법: 에이징, aging
◦
오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방법
◦
대기 중인 프로세스의 나이를 점차 늘리는 것
다단계 큐 스케줄링
Multilevel Queue Scheduling
우선순위 스케줄링의 발전된 형태
•
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링
•
우선순위가 높은 큐가 비어야 아래 큐에 할당
•
큐가 여러개 → 프로세스 유형별로 우선순위를 구분하여 실행하기 용이
◦
또한 큐마다 다양한 다른 스케줄링 알고리즘, 타임 슬라이스의 크기 지정 가능
◦
→ 구체적인 예시. 입출력 장치를 기준으로 알고 있으면 좋을 듯
다단계 피드백 큐 스케줄링
Multilevel Feedback Queue Scheduling
•
다단계 큐 스케줄링의 발전된 형태
◦
차이: 프로세스들이 큐 사이를 이동할 수 없다 → 있다
◦
하나의 큐에만 있으면 우선순위가 낮은 큐는 계속 연기될 여지 → 기아 현상
1.
새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 큐에 삽입 → 일정 타임 슬라이스만큼 실행
2.
프로세스가 해당 큐에서 끝나지 않았다면 다음 우선순위 큐에 삽입되어 실행 → 계속 밑으로
•
CPU를 오래 사용해야하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고 CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝남
•
여기에 에이징 기법을 적용해서 기아현상도 예방 가능 ← 다시 우선순위 높이는 것
