💻 스케줄링의 종류
📖 장기 스케줄링
처음 프로세스 생성시 ready/suspend로 갈지 ready로 갈지 결정하는 스케줄링📖 중기 스케줄링
suspend 상태의 프로세스를 메모리로 가져올지 말지 결정하는 스케줄링📖 단기 스케줄링
어떤 순서로 dispatch 할지 선택하는 스케줄링
사실상 의미 있는 스케줄링 단계이며 앞으로 스케줄링은 단기 스케줄링을 지칭한다.💻 스케줄링 평가 기준
스케줄링의 성능은 어떤 평가 기준을 사용할 것인가에 따라 다르다.
첫번째는 사용자 관점 vs 프로세서 관점에서 평가하는 것이다.
사용자 관점 - 사용자에게 긍정적 영향을 미치는 것을 기준으로 평가, 예를 들어 응답시간을 기준으로 평가한다.
시스템 관점 - 얼마나 프로세서를 낭비없이 사용하느냐에 대한 관점, 처리량이 대표적인 기준이다.
두번째는 성능 중심의 관점에서 평가할 것이냐 성능과 관련이 없는 척도를 기준으로 평가하느냐 이다.
성능과 관련이 없는 기준은 측정이나 분석이 어렵다.
예를 들면 예측 가능성이 있는데 프로세스가 언제쯤 시작되서 끝날지 예측하는 정도를 나타낸다.
스케줄링을 위해서 매우 중요하다.
<정리>
사용자 관점
1. 성능 관련 : 반환 시간, 응답 시간
2. 기타 : 예측 가능성
시스템 관점
1. 성능 관련 : 처리량, 프로세서 이용률
2. 기타 : 공정성(스타베이션이 없어야한다)💻 다양한 스케줄링 정책
총 6가지의 스케줄링 방법을 알아보자.
1. FCFS(FIFO라고도 함)
2. round robin
3. SPN
4. SRT
5. HRRN
6. Feedback
다음과 같은 순서로 프로세스가 도착한다고 했을때를 기준으로 설명한다.📖 FCFS
말 그대로 처음 들어온 프로세스 부터 실행한다.
이때 선점은 없이 실행한 프로세스는 종료시 까지 실행한다.
<장점>
starvation 발생 없음
문맥 교환 비용 최소
<단점>
실행시간이 짧은 프로세스더라도 기다려야 함.
응답시간이 제일 김
* 초반에 배운 batched 멀티 프로세싱이 이 방법📖 Round Robin
타임 퀀텀을 정하여 프로세스에 실행 시간을 할당하며
해당 시간만큼만 프로세스들을 번갈아 실행한다.
시분할 방법에 해당하며 선점모드이다.
<장점>
starvation 발생 x
짧은 프로세스에게 좋은 응답시간 제공
<단점>
프로세스의 특징은 고려하지 않는다.
-> 입출력 중심의 프로세스는 잠깐 받은후 시간을 다 못쓰고 블락됌
-> 입출력 중심 프로세스의 성능이 떨어진다.📖 SPN(shortest process next)
실행시간이 가장 짧은 순서대로 실행한다.
비선점 모드이다.
<장점>
이론상 가장 빠른 방법이다.
페이지 교체의 optimal과 비슷하다고 보면 되는데
optimal은 구현이 불가하지만 SPN은 구현이 가능하다.
<문제점>
프로세스의 실행시간을 알아야한다.
하지만 프로세스의 실행시간을 정확히 알수 없으니 수식을 사용해서 예측한다.
기아상태에 빠질 가능성 존재실행시간 예측
프로세스를 실행시키면서 각 실행때마다 실행시간을 잰뒤
n+1 번째 실행때는 n까지 실행시간의 평균으로 예측한다.
지수적 평균 방법 또한 존재한다.
이 수식은 서로 다른 가중치를 두어 최근 예측값과 실측값의 비중을 조절한다.
위 그래프는 실제 실행 시간과 예측치를 비교한다.
단순 평균은 실제 값을 따라가지 못하지만
지수적 평균방법은 횟수가 증가함에 따라 빠르게 실측치를 따라간다.📖 SRT(shortest remaining time)
SPN과 비슷하다.
차이점은 SRT는 가장 실행시간이 적게 남은 프로세스를 고르며 선점 방식이기에
매번 계산해서 교환한다.
<장점>
SPN에 비해서 예측가능성이 높으며 짧은 프로세스에 경우 도착하자마자 서비스를 받는다.
<단점>
스타베이션 발생 가능성과
시간 계산을 해야하는 오버헤드 발생📖 HRRN
SPN과 SRT는 스타베이션 가능성이 있다.
따라서 이를 해결하기 위해서 오래 기다린 프로세스에게 가중치를 두는 방식을 사용한다.
R=1+w/s (R : 응답비율, w : 대기시간, s : 서비스 시간)
으로 구성되며 R값이 큰 순서대로 실행을 한다.
비선점 방식이므로 새로운 프로세스를 실행할때만 R값이 필요하다.📖 Feedback
SPN,SRT,HRRN은 모두 좋은 방식 같아보이지만 실제로는 사용치 않는다.
1. 서비스 시간을 알아내야 한다는 점
2. 계산을 하기위한 추가적인 오버헤드가 발생한다는 점
등의 이유로 사용치 않으면 실제 시스템에서는 Feedback 방식을 주로 사용한다.
Feedback방식은 실행 시간이 길수록 패널티를 주는 방식이다.
실행시간을 구하지않고 일단 일정 시간동안 RR방식으로 실행을 시킨후
시간을 다썼음에도 실행을 더 시켜야한다면 우선순위를 낮춘다.
같은 우선순위의 큐는 RR방식으로 실행하며 높은 우선순위의 큐가 비기 전까지
낮은 우선순위의 큐 안의 프로세스는 실행치 않는다.
또한 어떤 프로세스 실행중 더 높은 우선순위의 프로세스가 들어온다면 그 즉시 교체한다.
<방식>
1. 더 낮은 우선순위에도 똑같은 시간을 할당
2. 우선순위가 i만큼 낮아지면 실행시간도 2^i만큼 추가 할당하여 실행시 끝낼수 있게 해주기
2번을 사용하더라도 높은 우선순위의 큐가 비기는 힘들기에 스타베이션이 발생할수 있다.
위 사진처럼 한 퀀텀 실행후 우선순위가 낮아짐전통적인 Unix 방식
유닉스 방식은 좋은 응답시간과 기아상태 방지를 목표로 한다.
다단계 피드백 큐 방식을 활용하며 각 큐 내에서는 RR방식을 사용한다.
우선순위 계산이 독특한대
CPUi(j)값은 특정 구간동안 cpu를 얼만큼 점유했는가에 대한 퍼센트이다.
오래 cpu를 사용한 프로세스는 다음 사용에 패널티를 주는 방식이다.
nice는 유저가 우선순위를 조절할수 있게해준다.
단, 이때 프로세스의 기본 우선순위는 그대로여야한다.
(커널 관련 프로세스가 오래 사용된다고 유저 프로세스보다 우선순위가 밀리는 등의 일은 없어야함)
따라서 비슷한 우선순위 내에서만 우선순위가 바뀌게 하기위해
base라는 기본 우선순위값을 매우 크게 줘서 cpu와 nice값으로 변경하더라도 영향이 없게한다.
학생