1. 프로세스 스케줄링
스케줄링
- 여러 가지 작업의 처리순서를 결정하는 것
- 예: 프로세스 스케줄링, 디스크 스케줄링 등
프로세스 스케줄링
- 주어진 프로세스가 여러 개인 경우, 프로세스 처리순서를 결정하는 것
상위단계 스케줄링 : 시스템의 자원을 효율적으로 이용할 수 있게 함
활성화된 작업들 내에서 하위단계 스케줄링 => 준비큐에서 CPU와 조율
중간단계 스케줄링: 시스템에 대한 단기적인 부하를 조절하도록 함
하위 단계 스케줄링
- 준비 큐에 있는 프로세스를 선택하여 사용 가능한 CPU를 할당(디스패치)하는 역할
- 수행 주체: 디스패처(dispatcher)
스케줄링의 기본 목표
- 공정성: 모든 프로세스가 적정 수준에서 CPU 작업을 할 수 있게 함
- 균형: 시스템 자원이 충분히 활용될 수 있게 함
운영체제의 유형에 따른 스케줄링 목표
- 일괄처리 : 처리량의 극대화, 반환 시간의 최소화, CPU 활용의 극대화
- 시분할 운영체제: 빠른 응답시간, 과다한 대기 시간 방지
- 실시간 운영체제: 처리기한 맞춤
스캐줄링 정책
- 스케줄링의 목표에 따라 우선적으로 고려하게 하는 정책
-> 선점 vs 비선점
문맥(Context)이란?
-> CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태
문맥 교환: CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고 다른 프로세스의 PCB로부터 문맥을 복원하는 작업
선점 스케줄링 정책
- 실행중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식
- 높은 우선순위의 프로세스를 우선 처리해야 하는 경우 유용: 실시간 시스템, 시분할 시스템
- 문맥 교환에 따른 오버헤드 발생
비선점 스케줄링 정책
- 실행중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식
- CPU를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이될 때까지 계속 실행상태에 있게 됨
- 강제적인 문맥 교환이 없어 오버헤드 발생하지 않음
- 긴 프로세스가 실행 중이라면 짧은 프로세스가 오래 기다리게 된느 경우 발생
평균 대기 시간
- 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균 값
평균 반환 시간
- 각 프로세스가 생성도니 시점부터 수행이 완료된 시점까지 소요 시간의 평균 값
대기 시간
A: 2
B: 3
반환 시간
A: 4
B: 6
평균 대기 시간 = (2 + 3) / 2
평균 반환시간 = (4 + 6) / 2
2. 스케줄링 알고리즘
- FCFS 스케줄링
- SJF 스케줄링
- SRT 스케줄링
- RR 스케줄링
- HRN 스케줄링
- 다단계 피드백 큐 스케줄링
FCFS(First-Come-First-Served)
- 비선점 방식
- 준비 큐에 도착한 순서에 따라 디스패치
프로세스 A B C D
도착시간 0 0 0 0
CPU 사이클 7 4 1 3
| 프로세스 | A | B | C | D |
| 대기시간 | 0 | 7 | 11 | 12 |
| 반환시간 | 0 | 11 | 12 | 15 |
평균대기시간 = (0+7+11+12) / 4 = 7.5
평균반환시간 = (7+11+12+15) / 4 = 11.25
장점 : 가장 간단하다
단점
- 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음
- 시분할 운영체제나 실시간 운영체제에는 부적합
- 프로세스들의 도착 순서에 따라 평균 반환시간이 크게 변함
=> 편차 큼
도착 순서가 다른 경우
프로세스 A B C D
도착시간 0 0 0 0
CPU 사이클 7 4 1 3
평균대기시간 = (8+4+0+1) / 4 = 3.25
평균반환시간 = (15+8+1+4) / 4 = 7
SJF 스케줄링 (Shortest Job First)
- 비선점 방식
- 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치
프로세스 A B C D
도착시간 0 2 4 5
CPU 사이클 7 4 1 3
평균대기시간 = (0+9+3+3) / 4 = 3.75
평균반환시간 = (7+13+4+6) / 4 = 7.5
장점: 일괄처리 환경에서 구현하기 쉬움
단점
- 실제로는 먼저 처리할 프로세스의 CPU 시간을 예상할 수 없음
- 새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수 있음
=> 시분할 운영체제나 실시간에서는 부적합
SRT 스케줄링 (Shortest Remaining Time)
- SJF 알고리즘의 선점 방식
- 준비 큐에서 기다리는 프로세스 중 남은 실행 시간이 가장 짧다고 예상되는 것을 먼저 디스패치
프로세스 A B C D
도착시간 0 2 4 5
CPU 사이클 7 4 1 3
평균대기시간 = (8+1+0+2) / 4 = 2.75
평균반환시간 = (15+5+1+5) / 4 = 6.5
장점: SJF보다 평균대기시간이나 평균반환시간에서 효율적임
단점:
- 실제로는 프로세스의 CPU 시간을 예측할 수 없음
- 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드가 크다
RR 스케줄링 (Round Robin)
- 선점 방식
- 준비 큐에 도착한 순서대로 디스패치 하지만 정해진 시간 할당량에 의해 실행 제한
- 시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치됨
시간 할당량 = 4
프로세스 A B C D
도착시간 0 2 4 5
CPU 사이클 7 4 1 3
평균대기시간 = (5+2+4+7) / 4 = 4.5
평균반환시간 = (12+6+5+10) / 4 = 8.25
장점: CPU를 독점하지 않고 공평하게 이용
-> 시분할 운영체제에 적합
단점:
- 시간 할당량이 너무 크면 FCFS 스케줄링과 동일
- 시간 할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드가 커짐
HRN 스케줄링 (Higest Response Ratio Next)
- 비선점 방식
- 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
응답 비율 = (대기시간 + 예상 실행시간) / 예상 실행 시간 = ( 대기시간 / 예상시간 ) + 1
=> 즉, 예상실행 시간이 짧을수록, 대기 시간이 길수록 응답 비율이 커진다.
프로세스 A B C D
도착시간 0 2 4 5
CPU 사이클 7 4 1 3
평균대기시간 = (0+6+3+7) / 4 = 4
평균반환시간 = (7+10+4+10) / 4 = 7.75
장점 : SJF 스케줄링의 단점을 보완
=> 예상실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치 가능
단점: 실제로는 프로세스의 CPU 시간을 예상할 수 없음
다단계 피드백 큐 스케줄링
- 선점 방식
- I/O 중심 프로세스와 연산 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
=> 단계 1부터 단계 n까지 하나씩의 준비 큐 존재
=> 단계 k는 단계 k+1에 피드백
=> 단계가 커질수록 시간 할당량도 커짐
기본적으로 RR처럼 돌지만 시간 할당량을 다르게 설정
앞쪽에서는 CPU를 빨리 쓰고 내뱉고 뒤로 갈수록 오래 쓰게 됨
앞의 준비 큐가 다 비어져 있어야 다음 큐에 있는 작업을 디스패치 할 수 있음
스케줄링 방법
- 디스패치 후 대기상태로 갔다가 준비상태가 될 때에는 현재와 동일한 단계의 준비 큐에 배치
- 시간 할당량을 다 썼으면 다음 단계의 준비 큐로 이동 배치
- 단계 k의 준비 큐에 있는 프로세스가 디스패치되려면 단계 1부터 단계 k-1까지 모든 준비 큐가 비어 있어야만 함
특징
- I/O 위주 프로세스는 높은 우선권 유지
- 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량
=> 입출력이 많은 것들은 빠르게 함
=> 두가지가 구분될 수 있도록 설정
관계
참고자료: 운영체제(김진욱, 이인복 공저, KNOU press 출판)
'CS > 운영체제' 카테고리의 다른 글
| 교착상태, 교착상태 특성, 교착상태 예방, 상호배제, 점유대기, 비선점, 환형대기 (0) | 2023.06.15 |
|---|---|
| 병행 프로세스의 여러가지 문제들, 생산자-소비자, 판독기-기록기, 자바 구현 코드, 프로세스 간 통신 (0) | 2023.06.15 |
| 운영체제의 병행 프로세스, 병행성 문제, 세마포어, 상호배제와 동기화 해결 세마포어 자바 구현 코드 (0) | 2023.06.15 |
| 운영체제 프로세스와 쓰레드 (0) | 2023.06.14 |
| 운영체제, 구성, 유형 (0) | 2023.06.14 |
