운영체제 [프로세스 스케줄링 기법]

FCFS(First Come First Service)

- 먼저 도착한 프로세스를 먼저 처리 (선입선출)
- batch 시스템에 적합
장점: 자원을 효율적으로 사용 가능
단점: convoy effect (긴 프로세스를 위해 다른 프로세스 또한 긴 시간을 대기), 긴 평균 응답시간

RR(Round-Robin)

- 자원 사용 제한 시간 존재
- 프로세스는 할당된 시간이 지나면 자원 반납
- Context switch overhead가 큼
- 대화형, 시분할 시스템에 적합
- 제한시간(time quantum)에 따라 성능 변화

 

SPN(Shortest-Process-Next)

- 실행시간 기준
- Burst time 가장 작은 프로세스를 먼저 처리
-장점 
평균 대기시간 최소화, 
시스템 내 프로세스 수 최소화--> 메모리 절약, 스케줄링 부하 감소---> 시스템 효율 향상
많은 프로세스들에게 빠른 응답 시간 제공
-단점
Starvation(기아) 현상 발생
정확한 실행시간을 알 수 없음

SRTN(Shortest Remaining Time Next)

- SPN의 변형
- 잔여 실행 시간이 더 적은 프로세스가 선점
장점: SPN의 장점 극대화
단점: 총 실행 시간 예측, 잔여 실행시간 계속 추적, 잦은 context-switching 으로 overhead가 큼

HRRN(High-Response-Ratio-Next)

- SPN의 변형
- Aging concepts: 프로세스의 대기시간을 고려하여 기회를 제공
- Response ratio를 기준으로 할당, Response ratio= ( WT+BT)/BT
장점: SPN의 장점+starvation 방지
단점: 실행시간 예측 기법 필요--> overhead가 큼

 

MLQ(Multi-level Queue)

- 작업(or 우선순위)별 별도의 ready queue를 가짐 (최초 배정 된 queue 변경x, 각각의 queue는 자신만의 스케줄링 기법 사용)
- Queue 사이에는 우선순위 기반의 스케줄링 사용
장점: 우선순위에 따른 빠른 응답시간
단점:  여러개의 Queue 관리 등 스케줄링 overhead, 낮은 우선순위 queue는 starvation 현상 발생가능

MFQ(Multi-level Feedback Queue)

- 프로세스의 Queue간 이동 허용
- Feedback을 통해 우선 선위 조정
장점: 실행시간 예측 필요x
단점: 설계 및 구현이 복잡, 스케줄링 overhead가 큼, starvation 현상 발생