[OS]
CPU Scheduling
CPU: 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치
✔️ 기계어 명령
1) CPU 내에서 수행되는 명령
Add 명령: CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장함.
2) 메모리 접근을 필요로 하는 명령 => 일반명령
Load 명령: 메모리에 있는 데이터를 CPU로 읽어들임.
Store 명령: CPU에서 계산된 결괏값을 메모리에 저장함.
3) 입출력을 동반하는 명령 => 특권명령
사용자 프로그램이 수행되는 과정은 일종의 사이클처럼 CPU 작업과 I/O 작업의 반복으로 구성됨.
CPU 버스트(burst): 사용자 프로그램이 CPU를 직접 갖고 빠른 명령을 수행하는 일련의 단계
I/O 버스트: I/O 요청이 발생하여 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
CPU 바운드 프로세스: I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
I/O 바운드 프로세스: I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
CPU 스케줄러
CPU를 사용하는 패턴이 서로 다른 여러 프로그램들이 동일한 시스템 내부에서 함께 실행되기 때문에 CPU 스케줄링이 필요!
CPU 스케줄러: 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드
- 비선점형 방식(nonpreemptive)
CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않음. - 선점형 방식(preemptive)
프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있음.
디스패처(dispatcher): 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 다음 그 프로세스에게 CPU를 넘기는 과정을 수행함.
✔️ 스케줄링 성능 평가
- CPU 이용률(CPU utilization)
전체 시간 중 CPU가 일한 시간의 비율 - 처리량(throughput)
주어신 시간 동안 끝마친 프로세스의 양 - 소요시간(turnaround time)
프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간 - 대기시간(waiting time)
CPU 버스트 기간 중 프로세스가 CPU를 얻기 위해 기다린 시간 - 응답시간(response time)
프로세스가 준비큐에 들어온 후 첫 번째 CPU를 얻기까지 기다린 시간
스케줄링 알고리즘
1) 선입선출 스케줄링(First-Come First-Served:FCFS)
프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
2) 최단작업 우선 스케줄링(Shortest-Job First:SJF)
CPU 버스트가 가장 짧은 프로세스에게 가장 먼저 CPU를 할당하는 방식
SPTF(Shortest Remaining Time First): SJF의 선점형 구현 방식
기아 현상(starvation): CPU 버스트가 짧은 프로세스가 계속 도착할 경우, CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못하는 현상
3) 우선순위 스케줄링(Priority)
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 가장 먼저 CPU를 할당하는 방식
노화 기법(aging): 기다리는 시간이 길어지면 우선순위를 조금씩 높여서 언젠가 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법
4) 라운드 로빈 스케줄링(Round Robin)
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한하고, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 있는 다른 프로세스에게 CPU를 할당하는 방식
할당시간(time quantum): 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
5) 멀티레벨 큐(Multi-level queue)
준비 큐를 여러 개로 분할해 관리하는 방식
전위 큐(foreground queue): 대화형 작업을 담기 위한 준비 큐
후위 큐(background queue): 계산 위주의 작업을 담기 위한 준비 큐
6) 멀티레벨 피드백 큐(Multi-level Feedback queue)
멀티레벨 큐와 유사하나, 프로세스가 하나의 큐에서 다른 큐로 이동할 수 있음.
7) 다중처리기 스케줄링(Multi-processor system)
CPU가 여러 개인 시스템으로, 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내가도록 함.
부하균형(load balancing): 각 CPU별 부하가 적절히 분산되도록 하는 메커니즘
대칭형 다중처리(symmetric multi-processing) | 비대칭형 다중처리(asymmetric multiprogramming)
8) 실시간 스케줄링(real-time system)
각 작업마다 주어진 데드라인(dead-line)이 있어서 정해진 데드라인 안에 반드시 작업을 처리해야 함.
경성 실시간 시스템(hard real-time system) | 연성 실시간 시스템(soft real-time system)
EDF(Earlist Deadline First): 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 방식
9) 스레드 스케줄링(Thread)
로컬 스케줄링(Local): 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정함.
글로벌 스케줄링(Global): 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정함.
✔️ 스케줄링 알고리즘 평가
- 큐잉모델(queueing model)
확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면, 복잡한 수학적 계산을 통해 각종 성능지표인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구함. - 시뮬레이션(simulation)
가상으로 CPU 스케줄링 프로그램을 작성한 후, 프로그램의 CPU 요청을 입력값으로 넣어 어떤 결과가 나오는지를 확인함.
트레이스(trace): 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일
- 구현 및 실측(implementation & measurement)
운영체제 커널의 소스코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일한 후 시스템에 설치하고, 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜봄.
Ref
[강의] KOCW 이화여자대학교 반효경 교수 <운영체제> 강의
[도서] 반효경, ⌜운영체제와 정보기술의 원리⌟ 개정판, 이화여자대학교출판문화원, 2020
