6. Priority Scheduling
1) 스케줄링 기준 : 프로세스의 우선순위
- 프로세스마다 우선순위가 부여되고, 우선순위가 높은 프로세스를 스케줄링하게 된다.
- 만약 우선순위가 같을 경우에는 FCFS로 스케줄링
2) 운영체제별 '우선순위'
- 운영체제에 따라서 우선순위가 부여되는 방식이 다르다.
(1) 우선순위의 범위
우선순위 값(Numerical value)이 시스템마다 다르다.
ex) MS Windows 운영체제는 우선순위 값의 범위가 1부터 32까지이다.
ex) UNIX 운영체제는 우선순위 값의 범위가 0부터 119까지로, 120단계이다.
ex) LINUX 운영체제는 우선순위 값의 범위가 0부터 139까지, 140단계이다.
(2) 우선순위의 수치값을 우선순위 레벨로 맵핑하는 방법
우선순위 수치값을 우선순위 레벨로 맵핑하는 방법도 시스템마다 다르다.
ex) MS Windows는 32가 High priority고 1이 low priority다.
ex) UNIX 운영체제와 리눅스는 0이 우선순위가 높고, 숫자가 클수록 우선순위가 낮다.
3) 예시: on-preemptive Priority Scheduling
preemptive Priority Scheduling도 있고, Non-preemptive Priority Scheduling도 있다.
4) 단점
- Starvation : 우선순위가 낮은 프로세스는 프로세스들이 ready queue에 들어오는 상황에서 계속해서 뒤로 밀릴 수 있다.
- 이러한 경우도 aging 기법을 이용해서 waiting time이 길어지면 우선순위를 높이는 방식으로 보완할 수 있다.
7. MLQ Scheduling (Multi-level Queue)
1) 기존의 방식들과 달리 ready queue를 여러개 두는 방식
- ready queue들에 우선순위를 부여한다.
- 프로세스는 ready queue에 들어올 때, 자신의 우선순위에 해당하는 ready queue에 배정된다.
- 각 ready queue는 그만의 스케줄링 메커니즘을 갖고 있다.
- ready queue들 간의 스케줄링은 그 ready queue의 우선순위에 따라서 스케줄링 된다.
2) 예시 구조
➡️ RQ0 System Processes들
컴퓨터시스템에서 커널 대신 시스템을 관리하기 위해 운영되는 프로세스들
시스템이 처음 부팅될 때부터 꺼질 때까지 시스템을 관리한다.
➡️ RQ1 Interactive Processes
Interactive한 성격의 프로세스들
➡️ RQ2 Student Processes
학생들이 실습용으로 생성하는 프로세스
➡️ RQ3 Batch Processes
백그라운드 프로세스들
✔️ 프로세스에 따라서 시스템인지, Interactive 한지 등등에 따라 ready queue를 배정받고 영구적으로 고정된다. 그리고 스케줄링은 높은 우선순위를 가진 ready queue 0부터 진행된다. 그리고 ready queue가 비게 되면 아래 ready queue 1로 내려가고, ready queue 1도 비면 ready queue 2로 내려간다.
8. MFQ Scheduling (Multi-level Feedback Queue)
1) ready queue 를 여러개 갖는 기법
✅ MLQ와 MFQ의 차이점 : 다이나믹한 우선순위 ❗
MFQ에서는 프로세스가 Permanent하게 ready queue에 배정되지 않는다. 프로세스의 라이프 사이클동안 ready queue에 여러번 들어가게 되는데, 어떤 때는 우선순위 높은 ready queue에 가고, 어떤 때는 낮은 ready queue에 가게 딘다. 즉 dynamic하게 ready queue에 배정된다.
2) Feedback 정보 사용
프로세스가 ready queue에 들어올 때 "어떤 일"을 하다가 ready queue에 들어왔는지에 따라서, 그에 맞는 우선순위의 ready queue assignment를 진행한다.
즉, 프로세스의 CPU 사용패턴이나 I/O 사용패턴을 보고 ready queue를 배정해주는 것이다.
3) MFQ 스케줄링의 두가지 목적 ✔️
(1) burst time이 짧은 프로세스를 선택한다.
(= I/O Bound 프로세스를 선호한다는 것과 마찬가지)
SPN 기법이나 SRTN 기법, HRRN 기법과 마찬가지로!(2) Adaptability를 향상시킨다.
프로세스의 상황에 맞추어서 우선순위를 변경시키기 때문에, Adaptability를 향상시키는 기법이다.
4) MFQ 기법은 프로세스에 대한 어떠한 정보도 없이 스케줄링을 할 수 있다.
즉 Arrival Time이나 burst time 정보 모두 없이 스케줄링 할 수 있다.
➡️ burst time이 짧은 프로세스를 스케줄링 한다면서, 어떻게 정보 없이 스케줄링할까?!
100% 정확히는 아니지만, 가능해진다!
5) Preemptive Scheduling
(1) 항상 우선순위가 높은 ready queue부터 스케줄링을 하고, 그 ready queue가 비면 그 다음 우선순위의 ready queue를 스케줄링한다.
(2) ready queue 내부에서는 그 ready queue만의 스케줄링 기법을 사용한다.
(3) Time Quantum이 있는 Preemptive Scheduling이다. 프로세스 P가 cpu를 할당받고 실행하다가 time quantum이 끝나면 run out 되어서 나오고, 다시 ready queue로 들어간다. 그리고 스케줄링을 다시 해서 다른 프로세스가 cpu를 할당 받는다.
6) 스케줄링 메커니즘
(1) 처음 생성되는 프로세스(Created 된 프로세스)는 무조건 RQ0로 간다.
(2) running 하는 프로세스가 RQ i에서 스케줄 되었는데, Time Quantum을 쓰지 못하고 I/O로 Sleep하고 wake up 해서 ready queue로 들어올 때에는, 자기가 원래 있던 RQ i로 돌아온다. (자신의 원래 큐 우선순위를 유지한다)
(3) running 하는 프로세스가 자신의 Time Quantum을 다 쓰고 선점을 당해서 timerunout되어 돌아오면, 한 단계 아래 우선순위의 ready queue로 돌아간다.
(4) 우선순위가 가장 낮은 RQ n에서 dispatch된 프로세스는 I/O를 했던 Time Quantum을 다 썼던 상관 없이 다시 원래 있던 RQ n으로 돌아온다.
➡️ 2번, 3번 룰을 통해서 이 스케줄링 기법은 결국 burst time이 짧은 프로세스를 선호하게 되어 있음. (burst time이 짧은 프로세스는 더 높은 우선순위를 계속 유지하게 됨)
7) MFQ 스케줄링의 변형
MFQ 스케줄링은 여러 방식으로 변형이 가능하다.
(1) 각각의 ready queue마다 다른 time quantum을 배정할 수 있다.
✔️ 왜?!
RQ0, RQ1, RQ2,.. RQN까지 N+1개의 ready queue가 있을 때, RQ0은 스케줄링을 받을 기회가 높지만 RQN은 스케줄링 기회가 너무 적다. 더불어 CPU를 많이 사용해야 하는 프로세스들은 time quantum을 못 맞추고 계속 우선순위에서 밀릴 가능성이 높으므로 starvation이 발생할 문제가 있다.
이 불공정을 해결하기 위해서 time quantum을 RQ0은 2의 0승, RQ1은 2의 1승, RQ2는 2의 2승, RQN은 2의 N승을 주는 것이다. 즉 ready queue 우선순위가 낮아질수록 2배씩 time quantum이 높아지므로, ⭕"우선순위가 낮은 프로세스는 스케줄링 받을 기회가 적은 대신 한번 스케줄링 받으면 cpu를 훨씬 더 길게 사용 가능한 방식"⭕으로 보상하는 것이다.(2) Aging 메커니즘
RQN의 프로세스가 계속 스케줄링을 받지 못하고 ready queue에서 대기중이면, 그 waiting time이 길어지면 그 때마다 한 단계 높은 ready queue로 높여주는 것이다.
즉 waiting time이 길어질수록 프로세스가 할당된 ready queue를 한 단계식 업그레이드 시킴으로써, hrrn 기법이나 마찬가지로 priority를 높여주는 효과를 갖게 해준다. 이러한 aging 기법으로 starvation을 방지한다.(3) I/O 바운드 프로세스는 Move up 시킨다.
✔️ 어떤 문제 때문에?!
프로세스의 사이클이 i/o 사용 -> cpu 사용 -> i/o 사용으로 반복되는 프로세스가 있다고 할 때, 맨 처음 i/o 사용중일 I/O bound 때에는 자신의 우선순위를 유지한다. 그렇지만 CPU bound로 cpu 연산을 시작하면서 time quantum을 맞추지 못하고 우선순위가 계속 밀려서 어쩌면 RQN 까지 갈 수 있다. 이렇게 되면 다시 i/o를 사용해야 하는 I/O bound 때가 되었는데, 다시 스케줄링을 받기 어려운 상태가 된 문제가 발생한다.
✔️ 해결?!
RQi에서 I/O를 하고 돌아오는 프로세스는 RQi로 돌아오는 것이 아니라, RQi-1로 한 단계 우선순위 높은 ready queue로 배정해주는 것이다. 따라서 프로세스가 I/O bound였다가, CPU bound였다가, 다시 I/O bound일 수 있는데, 이러한 프로세스 특성의 변형에 따라서 ready queue의 우선순위가 올라가기도 하고 내려가기도 하기 때문에 ⭕'adaptable'⭕하다고 하는 것이다!
8) MFQ 스케줄링 기법을 구현하기 위해서 정해야 할 것
- ready queue의 개수
- 각 ready queue의 스케줄링 알고리즘(FCFS 등)
- 프로세스를 언제 더 높은 우선순위의 ready queue로 업그레이드할 것인지
- 프로세스를 언제 더 낮은 우선순위의 ready queue로 다운그레이드 할 것인지
- 프로세스가 처음 생성됐을 때 어느 ready queue에 배정할 것인지
=> MFQ 기법은 실제 컴퓨터 운영체제에서 사용되는 스케줄링 기법의 근간이다 !
