더보기
2022.09.19 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 1-1. 디자인 패턴(1)
2022.09.20 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 1-1. 디자인 패턴(2)
2022.09.20 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 1-2. 프로그래밍 패러다임(함수형,객체지향,절차적프로그래밍)
2022.09.22 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 2-1. 네트워크의 기초(토폴로지&성능분석 명령어)
2022.09.23 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 2-2. TCP/IP 4계층 모델
2022.09.27 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 2-3. 네트워크 기기(스위치 등)/IP주소
2022.10.02 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 2-4.HTTP
2022.10.04 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 3-1. 운영체제의 구조와 역할 및 컴퓨터의 구조
2022.10.07 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 3-2. 메모리계층 및 메모리 관리
2022.10.10 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 3-3. 프로세스와 스레드(1): 프로세스의 컴파일과정, 상태, 메모리 구조, PCB
2022.10.14 - [소소한 CS 지식/면접을 위한 CS 전공지식 노트] - 3-3. 프로세스와 스레드(2): 멀티프로세싱
CPU 스케줄링이란?
어떻게 프로세스들이 CPU를 효율적으로 사용하게 할 것인지 스케줄링한다.
- CPU 스케줄링 대상 프로세스는 Ready Queue에 있는 프로세스들로, 스케줄링 정책에 따라 Queue에 정렬을 한 후 앞에 있는 프로세스로부터 CPU를 주게 된다.
4-1. CPU 스케줄링 알고리즘
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.
- Ready Queue에 있는 프로세스 대상으로 CPU를 할당하는 순서와 방식을 결정하는 것을 의미한다.
- 프로그램이 실행될 때 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다.
- 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready queue)에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.
| 선점형(preemptive) | 비선점형(non-preemptive) |
| 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다. | 일단 CPU를 할당받으면 해당 프로세스가 끝날 때까지 CPU를 빼앗기지 않는다. |
4-2. 비선점형 방식(non-preemptive)
프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다.
| 장점 | 단점 | |
| 모든 프로세스들에게 공정하다. | 응답 시간을 예측할 수 있다. | 짧은 작업을 수행하는 프로세스라도 긴 작업이 종료될 때까지 기다려야 한다. |
| 컨텍스트 스위칭으로 인한 부하가 적다. | ||
FCFS(First Come, First Served): 선입 선처리 스케줄링
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘(큐에 도착한 순서대로 CPU를 할당한다.)
- 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료 또는 I/O 처리를 위해 CPU를 방출할 때까지 CPU를 점유한다.(CPU burst가 완료될 때까지 CPU를 반환하지 않고, 할당되었던 CPU가 반환 될 때에만 스케줄링이 이루어진다.)
- 길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상(convoy effect)'이 발생하는 단점이 있다.
| 장점 | 단점 |
| 개발이 용이하다. | Convey Effect(호위 효과): Short process behind long process |
| 공평성을 유지할 수 있다. | 소요시간이 긴 프로세스가 먼저 도달할 경우 효율성이 낮아진다. (비효율적) |
| Starvation 이슈가 발생하지 않는다. | 실행 시간이 짧은 작업이어도 뒤로 가면 대기 시간이 길어진다. |
SJF(Shortest Job First): 최단 작업 우선 스케줄링
실행시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘(CPU burst time이 짧은 작업을 우선으로)
- CPU가 이용 가능해지면, 가장 작은 next CPU burst를 가진 프로세스에 CPU를 할당한다.
- 실제로 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용한다.(실행하기 전 next CPU burst의 길이를 완벽하게 예측하기 어렵기 때문에 next CPU burst 길이의 근삿값을 계산한다.
| 장점 | 단점 |
| 최소 평균 대기 시간을 보장한다. | Starvation(기아 현상: 긴 시간을 가진 프로세스가 실행되지 않는 현상) 발생 가능성 유 |
우선순위 스케줄링(Priority Scheduling)
CPU는 가장 높은 우선순위를 가진 프로세스에 할당
- 우선순위가 같은 프로세스들은 선입선처리 순서로 스케줄된다.
- 단점으로는 Starvation과 infinite blocking이 있다.
- 무한 정지(infinite blocking): 프로세스가 CPU를 사용할 준비가 되었지만 우선순위가 낮을 경우 무한 대기하는 상태가 된다. => 이것을 해결하기 위해 Aging 기법으로 큐에 남아있었던 시간으로 가중치를 부여해, 해당 문제점을 해결할 수 있다.
4-3. 선점형 방식(preemptive)
현대 운영체제가 쓰는 방식, 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식
| 장점 | 단점 |
| 높은 우선 순위를 가진 프로세스를 빠르게 처리하려는 시스템에 유용하다. | 높은 우선 순위를 가진 프로세스들만 들어오는 경우 Overhead가 발생한다. |
| 빠른 응답 시간을 요구하는 시분할 시스템에 유용하다. |
RR(Round Robin): 라운드 로빈
각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘
- 현대 적인 CPU 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종
- 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.
- 시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.
SRF(Shortest Remaining Time First) 스케줄링
짧은 시간 순서대로 프로세스를 수행한다.
- SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행한다.
- 즉 위 SJF의 선점 버전!!!
- 새로운 프로세스가 들어올 때마다 스케줄링이 변경되므로 CPU 사용 시간(burst time)을 정확히 예측하기 어렵다.
다단계 큐(Multilevel Queue)
우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것
- 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어진다.
- 각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.
'cs > 면접을 위한 CS 전공지식 노트' 카테고리의 다른 글
| 4-2. ERD와 정규화 과정 (0) | 2022.10.28 |
|---|---|
| 4-1. 데이터베이스의 기본(엔터티의 관계, 데이터 타입 최적화, 관계, 키) (0) | 2022.10.27 |
| 3-3. 프로세스와 스레드(2): 멀티프로세싱 (0) | 2022.10.14 |
| 3-3. 프로세스와 스레드(1): 프로세스의 컴파일과정, 상태, 메모리 구조, PCB (0) | 2022.10.10 |
| 3-2. 메모리계층 및 메모리 관리 (0) | 2022.10.07 |
