비선점 스케줄링
비선점 스케줄링이란?
이미지 출처 : https://hyunah030.tistory.com/4
프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 정책이다.
작업 실행 시간 전체 또는 한 번의 CPU배당에 대해 적용되며, 비선점 스케줄링의 예로는 우선순위, FCFS, SJF, HRN 스케줄링 등이 있다.
FCFS 스케줄링 (First Come First Served Scheduling)
프로세스의 도착순
으로 CPU를 배정 (실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS 적용)- Batch 작업등, 장기 스케줄러에서 사용 가능
- 수행 중인 긴 작업을 여러 개의 짧은 작업들이 기다리게 되는 호위효과 (Convoy Effect)의 문제가 발생 할 수 있음
작업 | Burst Time |
---|---|
P1 | 24 |
P2 | 3 |
P3 | 3 |
위와 같은 작업의 도착 순서는 P1 -> P2 -> P3
이고, 간트차트로 나타내면 다음과 같다.
- 평균 반환시간 = (24+27+30) / 3 = 27
- 평균 대기시간 = (0+24+27) / 3 = 17
최단 작업 우선 스케줄링 (SJF, Shortest Job First Scheduling)
- 대기하는 작업 중
CPU Burst Time이 가장 작은 작업에 CPU를 할당
하는 기법 - 평균 대기 시간에 있어 최적의 알고리즘
- CPU 요구시간(Burst TIme)을 미리 알기가 어렵다.
작업 | Burst TIme |
---|---|
P1 | 6 |
P2 | 3 |
P3 | 8 |
P4 | 7 |
위와 같은 작업이 있다면 순서는 Burst Time이 작은 P2 -> P1 -> P4 -> P3
이다. 간트차트로 나타낸다면 다음과 같다.
- 평균 반환시간 = (3+9+16+24) / 4 = 13
- 평균 대기시간 = (3+0+16+9) / 4 = 7
HRN 스케줄링
- 실행시간이 긴 프로세스에 불리한 것으로, 대기 시간과 서비스 시간을 이용하는 기법
- SJF의 약점을 본완한 기법으로 긴 작업과 짧은 작업 간 불평등 완화
- 우선순위 계산 공식 = (대기시간 + 서비스시간) / 서비스시간
- 우선순위 계산 결과값이 높은 것 부터 우선 순위가 부여, 대기 시간이 긴 프로세스일 경우 계산 결과값이 높게 나옴
작업 | 대기시간 | 서비스시간 |
---|---|---|
P1 | 5 | 5 |
P2 | 10 | 6 |
P3 | 15 | 7 |
P4 | 20 | 8 |
위와 같은 작업일 경우,
- P1 우선순위 = (5+5)/5 = 2
- P2 우선순위 = (10+6)/6 = 2.66..
- P3 우선순위 = (15+7)/7 = 3.14..
- P4 우선순위 = (20+8)/8 = 3.5
이므로
작업 순서는 P4 -> P3 -> P2 -> P1
이다.
우선순위 스케줄링 (Priority Scheduling)
각 프로세스의 우선순위가 정해지면,
우선순위가 제일 높은 프로세스에게 CPU를 할당하되, 우선순위가 같은 경우 FCFS 방식
을 적용한다.일반적인 연산 위주 프로세스보다 입출력 위주 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.
우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업은 준비상태에서 보장 없이 머물게 된다 (기아상태). 이런 문제는 시스템에 머무는 시간이 증가할수록 우선순위를 높여주는 에이징으로 해결한다.
우선순위 스케줄링 알고리즘은 일반적으로 가장 많이 쓰이는 스케줄링 기법이다.
내부적 우선순위 고려 : 제한 시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst의 비율 등
외부적 우선순위 고려 : 사용료, 정책적인 변수 등
작업 | Burst Time | 우선순위 |
---|---|---|
P1 | 10 | 3 |
P2 | 1 | 1 |
P3 | 2 | 3 |
P4 | 1 | 4 |
P5 | 5 | 2 |
위와 같은 작업이 있다면 순서는 우선 순위 순대로 가되, 우선순위가 같은 P1,P3의 경우 먼저 도착한 순인 P1 -> P3 순이다.
작업순서 : P2 -> P5 -> P1 -> P3 -> P4
- 평균 반환시간 = (16+1+18+19+6) / 5 = 12
- 평균 대기시간 = (6+0+16+18+1) / 5 = 8.2
면접에 나올 수 있는 질문
Q. 비선점 스케줄링이란?
A. 프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 정책
Q. 비선점 스케줄링 알고리즘의 특징과 차이점
A. 각 방식의 특징과 차이점에 대해 서술
참고
- [운영체제 OS] 스케줄링 알고리즘 - FCFS, RR, SJF, SRT, Priority, MLQ, MFQ 스케줄링
- 도리의 디지털라이프 - CPU 비선점 스케줄링 기법
- [운영체제] CPU 스케줄러 - FCFS, SJF, SRT, RR, Priority Scheduling
기여자
Jongminfire
📦