CPU 스케줄링의 정의
한정된 CPU의 작업 처리시간을 여러 프로세스 혹은 여러 쓰레드가 효율적으로 이용할 수 있도록
분배하는 정책이자 알고리즘
CPU 스케줄링 알고리즘 종류
| 종류 | 비선점 스케줄링 | 선점 스케줄링 |
| 개념 | 비선점 - 중간에 자리를 빼앗을수 없다 다른 프로세스가 CPU를 할당 받으면 그 프 로세스가 작업을 종료하고 반환할 때까지 다른 프로세스가 CPU 점유 불가 |
선점 - 중간에 자리를 빼앗아서 새치기 가능 우선순위가 높은 프로세스가 현재 프로세스 를 중지시키고 CPU점유 가능 |
| 특징 | - 어떤 Rule에 의해서 차레차례대로 처리 되기 때문에 응답시간 예상이 용이 - 모든 프로세스의 요구를 공평하게 처리 |
- 어떤 프로세스를 처리하다가도 우선순위 가 높은 프로세스가 들어오면 기존 프로 세스를 중지시키고 우선순위가 높은 프로세스를 먼저 처리하기 때문에 응답 속도가 비선점형에 비하면 빠르다. - 따라서 대화식 시분할 시스템에 적합 (바로바로 응답이 필요한 시스템) |
| 종류 | FCFS, SJF, HRN | Round Robin, SRT, MLQ, MLFQ |
FCFS (First Come First Service)
선입선출법(FIFO) 과 같은 개념으로 준비된 Queue 에 도착한 순서대로 CPU를 할당한다.
● 처리순서 : P1 , P2 , P3 P4, P5 순서로 처리됨.. 처리순서 고정불변
● 장점 : 공평함.
● 단점 : 콘보이효과 (Convoy Effect) - 처리시간이 아주 긴 프로세스가 계속 CPU를 독점
하는 현상으로 인해 전체적인 처리율 및 응답시간이 지연됨.
SJF (Shortest Job First)
평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당
하는 방식의 CPU 스케줄링 알고리즘.
● 처리순서 : P1 , P3 , P5, P2, P4 순서로 처리됨..
● 장점 : 콘보이효과 (Convoy Effect) 를 완화.
: 평균 대기 시간에 있어서 최적 알고리즘
: FCFS보다 평균 대기시간은 감소
● 단점 : 프로세스의 완료시간을 예측하기가 어려움
왜냐 짧은 프로세스가 중간중간 치고 들어오기 때문.. 따라서 작업시간이 긴
프로세스는 계속 우선순위가 뒤로 밀릴 가능성이 있음 (기아상태/Starvation)
-> 이를 해결하기 위해 우선순위가 뒤로 밀릴때마가 couting을 해서
일정 counting 을 초과하면 더이상 뒤로 밀리지 않게 하는 Aging 기법
으로 해결 가능
HRN (Highest Response Next)
대기시간이 긴 프로세스, 또는 실행시간이 짧은 프로세스의 우선순위를 높여 프로세스 간 자
원 점유 불평등을 보완하는 비선점 스케줄링 기법
즉, 대기프로세서 중 응답률이 가장 높은 것 선택
● 장점 : 긴작업과 짧은 작업간의 불평등을 어느정보 보완
: 짧은 작업이나 대기시간이 긴 작업은 우선순위 상승 (SJF 약점보완)
: 시분할 시스템에 활용 시 유용
● 단점 : 준비상태 큐에 있는 각 프로세스의 서비스시간을 지속적으로 추적해야 하므로 Overhead증가
Round Robin
들어오는 순서대로 같은 크기의 시간할당하는 방식
즉 준비큐에 있는 순서대로 각각 일정한 시간(타임 슬라이스)을 할당후 시간이 되면
하던 작업 중지하고 대기큐로 돌려보내고 준비큐에 있는 프로세스를 하나 꺼내와서
또 일정한 시간만큼 CPU를 할당하는 방식
따라서 시간할당 크기 즉 타임 슬라이스 크기가 크면 FCFS 랑 비슷해지고
, 작으면 문맥교환 빈번해짐
(주로 일괄처리시스템에 사용)
● 장점 : 공평함.
● 단점 : 타임 슬라이스의 크기에 따라 효율이 좌우됨.
SRT (Shortest Remaining Time)
Round Robin + SJF 를 합한 개념
즉 Round Robin 방식으로 일정한 타임 슬라이스 만큼 CPU를 할당해서 작업을 한 후
작업이 완료되지 않은 상태에서 시간이 완료되면 준비큐에 넣어놓고
다음 프로세스를 준비큐에서 가져올때 기준을 SJF 개념으로 작업시간이 가장 짧은
프로세스를 선택해서 일정한 타임 슬라이스 만큼 CPU를 할당한다는 개념
단점 : SJF 스케줄링 단점과 동일
: 프로세스의 완료시간을 예측하기가 어려움
: 작업시간이 긴 프로세스는 계속 뒤로 밀리는 아사(Starvation) 현상 발생 가능
(물론 Aging 기법으로 일정 부분 완화 가능)
|
MLQ(Multi Level Queue)
프로세스들에 대한 사전 실행 정보가 없는 경우 준비 상태의 큐를 여러 개 두어 스케줄링
하는 선점형 스케줄링 기법.
● 특징: 다른 큐로 작업 이동 불가, 우선순위에 따른 선점
● 큐를 구분하는 특성
① 전면작업(Foreground)와 후면작업(Background)
② 기억장치의 요구량
③ 프로세스 우선순위
④ 프로세스 유형
MLFQ(Multi Level Feedback Queue)
다단계 큐 스케줄링에서 한 단계 발전된 방식으로, 큐마다 서로 다른 CPU Time Slice
(Quantum)를 부여 가능한 선점형 스케줄링 기법
● 특징: 다른 큐로 작업 이동 가능
● MLFQ를 결정하는 파라미터
① 큐의 개수
② 각 큐를 위한 스케줄링 알고리즘
③ 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
④ 프로세스를 낮은 우선순위 큐로 내려주는 시기를 결정하는 방법
⑤ 프로세스가 들어갈 큐와 그 프로세스가 서비스를 받는 시기를 결정하는 방법