OS 공부 - CPU 스케줄링, RR, Priority, MLQ, MLFQ

배운점

 

RR Scheduling
Round-Robin: preemptive FCFS with 시분할(time quantum)(=time slice)
시간 할당량(time quantum) 또는 시간 조각(time slice)이라고 하는 작은 단위의 시간 정의, 일반적으로 10에서 100밀리초
process 들어 왔을 때 일정 time quantum 지나면 너, 나가(watch dog라는애가 시킴) 한 프로세스에게 한번의 시간 할당량 동안 CPU를 할당합니다.

ready Queue: circular queue

 

 

=>라운드 로빈 스케줄링은 시간 할당량을 정의하고 원형 큐에 프로세스들을 넣은 다음 각 프로세스에게 정의한 시간 할당량 만큼 CPU를 할당시키고 수행
실행하던 프로세스는 준비 완료 큐의 꼬리(tail)에 넣음

 

quantom보다 더 긴 CPU burst time 을 갖고 있으면 interrupt를 걸어준다 -> context switch -> ready queue

 

waiting time
P1 =10-4=6 ,P2 = 4, p3 = 7

 

RR에서 Average waiting time 오히려 더 길어질 수 있다.
RR은 preemptive다.

 

time quantum에 따라 RR성능 좌지우지 된다.
turnaround time 도 다양함
time quantum 많이 줘도, 적게줘도 안좋음

 

Priority-base Scheduling 우선순위

프로세스들은 우선순위를 가지고 있으며 가장 높은 우선순위를 가진 프로세스에게 CPU 권한을 할당
각 process에 priority를 associate 한다. 우선순위가 같으면 FCFS
SJF 처럼 next CPU burst time이 적은 애에게 낮은 가중치를 준다.
SJF 알고리즘은 CPU 버스트 시간이 짧을 수록 높은 우선순위를 가지는 알고리즘
일반적으로 우선순위는 0~7 또는 0~4095까지 일정 범위의 수

 

우선순위 정의 기준:
시간 제한
메모리 요구
열린 파일의 수
평균 입/출력 버스트의 평균 CPU 버스트에 대한 비율

 

선점형이거나 비선점형이 될 수 있다.
프로세스가 준비 완료 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행중인 프로세스의 우선순위와 비교
현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점
비선점형 우선순위 스케줄링 알고리즘은 단순히 준비 완료 큐의 머리 부분에 새로운 프로세스를 넣음

 

average waiting time: 8.2

 

preemptive(SRTF) 하게 할거냐 non preeptive(SJF) 하게 할거냐

 

무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)가 발생할 수 있다.
starvation(기아) : 무한대 대기
계쏙 짧은거 (priority)가 높은게 들어와서 실행 못하고 대기만 한다.
=> aging을 하자(나이): 오랜 시간 대기하면 priority를 높여주자
오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법
예를 들어, 우선순위가 127(낮음)에서 0(높음)까지의 범위라면, 매 15분마다 대기중인 프로세스의 우선순위를 1씩 증가시킬 수 있다. 결국 시간이 지나서 우선순위가 127인 프로세스도 시스템에서 최고의 우선순위를 갖게 될 것

 

---

 

RR(퀀텀)+Priority scheduling(우선순위) 섞자
높은 우선순위 부터 하다가 우선순위 같으면 RR로 하자

 

 

 

MULTI-Level Queue(MLQ)
준비 완료 큐를 다수의 별도의 큐로 분류하여 수행하는 방식

 

 

하나의 스마트폰에 동시에 일어나는 process 들이 있고 , 저마다 priority를 갖는다.

 

분리된 ready Queue에 각각 priority 부여한다.
메모리 크기, 프로세스의 우선순위 혹은, 프로세스 유형(포어그라운드, 백그라운드)과 같은 특성에 따라 다수의 큐 중 한 개의 큐에 영구적으로 할당
예를들어 포어그라운드 큐는 RR 알고리즘에 의해 스케줄링 될 수 있고 백그라운드 큐는 선입 선처리 알고리즘에 의해 스케줄링 될 수 있다.
=>다단계 큐 스케줄링 알고리즘은 프로세스들간의 우선순위를 정의하고 각 우선순위간의 큐를 생성하여 수행하는 방식. 높은 우선순위의 큐의 프로세스가 비어있지 않으면 낮은 우선순위 큐의 프로세스는 실행될 수 없다.

 

단점:
프로세스들은 한 큐에서 다른 큐로 이동하지 못한다. 이러한 방식은 적은 스케줄링 오버헤드가 장점이지만 융통성이 적다는 단점이 존재한다.

 

highest priority

 

맨위에 큐 비면 다음거 실행, 큐 비면 다음꺼 실행, 큐 비면 다음 꺼실행..

 

Multi-Level Feedback Queue (MLFQ)
우선 순위 높은거만 해주다가 Queue 실행 안 될 수도 있기 때문에,,
프로세스가 큐들 사이로 이동하는 것을 허용. 프로세스들을 CPU 버스트 성격에 따라 구분. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동. 입/출력 중심의 프로세스와 대화형 프로세스들은 높은 우선순위의 큐에 넣는다. 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 이러한 노화(aging)은 기아 상태를 예방함.

 

짧게 실행하고 빠져나가자, 다 실행 못하고 waiting 큐에 들어가는데
두번째는 16을 줬다. 여기서 빠져나오는건 CPU를 더 많이 쓸 수 있다.
점점 더 많은 CPU burst time을 할당받기 때문에 그 다음은 남은시간 다 쓸 수 있다.

 

=>다단계 피드백 큐 스케줄링 알고리즘의 방식은 여러개의 큐에 시간 할당량을 정의하고 수행시간이 긴 프로세스일수록 뒤의 큐로 넣어지게 되는 방식

 

CPU-bound(CPU 많이 쓰는 애)는 CPU 할당 시간 점점 많이 받고 적게 쓰는 애는 우선순위가 높으니까 빨리 처리하고 빠져나가고 , 자주 들어올 기회가 생긴다.
실제 OS CPU스케줄링 알고리즘이다

 

스레드 두가지 종류
유저스레드 커널 스레드가 있는데
커널 스레드만 스케줄링 하면 됨, 유저 스레드는 스레드 라이브러리로 관리함
커널은 유저스레드가 어떻게 도는지 모름, 매핑만 해주면됨(many to many)

 

=> 지금까지 배운 스케줄링 커널스레드를 대상으로 한다고 보면됨

 

Real-Time Operating System에서 스케줄링
실시간: 주어진 시간내에 task 완료

 

soft Realtime
creitical 한 리얼타임 프로세스가 반드시 그 시간안에 끝나지는 않는데 그 프로세스가 noncritical 한 프로세스보다는 빨리 실행되도록 보장한다.
스마트폰 쓴다고치면 rf패킷이 막 넘어오는데 이거를 처리해가지고 음성으로 변환해줘야함, 조금 끊겨도 듣는데 큰 지장없음 -> 음성처리를 빨리해도좋지만 좀 놓쳐도 괜찮다.

 

Hard Realtime
어떤 task가 반드시 데드라인 안에 실행되는 것
반드시 priority를 가져야한다.
로켓같은경우 궤도계산같은거 0.1초라도 안되면 목적지를 벗어남