다중 프로그래밍(Multi Programming)
- 여러 개의 프로세스가 시스템 내 존재
- 자원을 할당할 프로세스를 선택해야 함 => 스케줄링
- 자원 관리
* 시간 분할 관리
+ 프로세스 스케줄링 : 프로세서 사용시간을 프로세스에게 분배
* 공간 분할 관리
+ 하나의 자원을 분할하여 동시에 사용 => 메모리
스케줄링 목적
- 시스템 성능 향상
- 성능 지표
* 응답시간
* 작업 처리량
* 자원 활용도
용어 표현
스케줄링 기준 및 단계
1. 스케줄링 기준
- 프로세스의 특성 : I/O-bounded, compute-bounded
- 시스템 특성 : 일괄 시스템(Batch system), 대화형 시스템(interactive system)
- 프로세스의 긴급성 : Hard real-time, Soft real-time
- 프로세스 우선순위
- etc
Compute-bounded vs I/O-bounded
- 프로세스 수행 : CPU 사용 + I/O 대기
- CPU burst : CPU 사용 시간
- I/O burst : I/O 대기 시간
- compute-bounded : CPU burst가 긴 경우
- I/O-bounded : I/O burst가 긴 경우
2. 스케줄링 단계(Level)
- 발생하는 빈도 및 할당 자원에 따른 구분
- Long-term scheduling
* 시스템(Kernel)에 등록할 프로그램(작업)을 결정
* 시분할 시스템에서는 모든 작업을 일정 시간으로 나누기 때문에 long-term이 덜 중요
- Mid-term scheduling
* 메모리 할당 결정
* Ready/Suspended에게 메모리를 주고 Ready 상태로 바꿔주는 상황
- Short-term scheduling
* 프로세서를 기다리는 Ready 상태의 프로세스들에게 CPU 할당 결정
* 가장 빈번하게 발생
스케줄링 정책
- 선점 스케줄링
* 할당 받은 자원을 누가 뺏을 수 있음
* Context switching overhead가 큼
* Time-sharing system, Real-time system 등에 적합
- 비선점 스케줄링
* 할당 받은 자원을 스스로 반납할 때까지 사용
* Context switching overhead가 적음
* 평균 응답 시간 큼
- 우선순위
* 프로세스의 중요도
* 정적 우선순위(Static Priority)
+ 프로세스 생성 시 결정된 우선순위 유지
+ 구현이 쉽고, overhead가 적음
+ 시스템 환경 변화에 대한 대응이 어려움
* 동적 우선순위(Dynamic Priority)
+ 프로세스의 상태 변화에 따라 우선순위 변경
+ 구현이 복잡, overhead가 적음
+ 시스템 환경 변화에 유연한 대응 가능
기본 스케줄링 알고리즘
1. FCFS(First Come First Service)
- 비선점 스케줄링
- 스케줄링 기준 : 도착 시간
- 장점 : 시스템을 효율적으로 사용가능 why? overhead가 적고 CPU가 계속 작업
- 단점 : Convoy Effect 발생 what? 수행시긴아 긴 하나의 프로세스에 의해 다른 프로세스들의 대기시간이 길어지는 현상
- 일괄 시스템(Batch system)에 적합 why? 오는 순서대로 빠르게 처리하는 것이 목적이기 때문
- 대화형 시스템(Interactive system)에 부적합 why? 입력에 대한 반응이 빠르게 오지 않기 때문
2. RR(Round Robin)
- 선점 스케줄링
- 스케줄링 기준 : 도착한 시간
- 특징 : 할당 시간만 처리하고 다음 프로세스를 받기 때문에 특정 프로세스의 독점 방지
- 장점 : 할당 시간이 작으면, 모든 프로세스가 각각의 프로세서를 실행하는 것처럼 처리
- 단점 : Context switching overhead가 큼
- 대화형 시스템, 시분할 시스템에 적합
3. SPN(Shortest Process Next)
- 비선점 스케줄링
- 스케줄링 기준 : 짧은 실행시간
- SJF(Shortest Job First) scheduling
- 장점 : 평균 대기시간 최소화, 시스템 내 프로세스 수 최소화하여 메모리 절약과 overhead 감소
- 단점 : Startvation(무한대기) 현상 발생 what? Burst time이 긴 프로세스의 경우 자원을 오랜 시간 할당 받지 못할 수 있음
4. SRTN(Shortest Remaining Time Next)
- 선점 스케줄링
- 스케줄링 기준 : 잔여 실행 시간
- 특징 : 잔여 실행 시간이 더 적은 프로세스가 CPU를 선점
- 장점 : 평균 대기시간 최소화, 시스템 내 프로세스 수 최소화
- 단점 : 잔연 실행을 계속 추적해야 해서 overhead가 큼. 따라서 구현 및 사용이 비현실적
5. HRRN(High Response Ratio Next)
- 비선점 스케줄링
- 스케줄링 기준 : Response ratio(대기 시간, 실행시간으로 구함)가 높은 프로세스 우선
- Response ratio : (Waiting time + Burst time) / Burst time
- 장점 : SPN의 장점 + Starvation 방지
- 단점 : 실행 시간 예측 기법으로 overhead 발생
6. 비교
- FCFS, RR : 공평성
- SPN, SRTN, HRRN : 효율성, 성능 좋음, 하지만 실행시간 예측으로 인한 부하
- MLQ, MFQ는 실행시간 예측 부하 단점을 해결
7. MLQ(Multi Level Queue)
- 작업(or 우선 순위) 별 각자의 Ready Queue를 가짐
* 최초 배정된 Queue를 벗어나지 못함
* 각가의 Queue는 자신만의 스케줄링 기법 사용
- Queue 사이에는 우선순위 기반의 스케줄링 사용
- 장점 : 우선순위가 높은 프로세스는 빠르게 처리
- 단점 : 여러 개의 Queue 관리로 overhead가 큼, 우선 순위가 낮은 Queue는 Starvation 발생, 최초로 배정된 Queue에서 벗어나지 못하기 때문에 시스템 환경 변화에 적응 못함
8. MFQ(Multi-level Feedback Queue)
- 프로세스의 Queue간 이동이 허용된 MLQ
- Feedback을 통해 우선 순위 조정
- 장점 : 프로세스에 대한 사전 정보(실행 시간) 없이 SPN, SRTN, HPPN 기법의 효과를 볼 수 있음
- 단점 : 설계 및 구현이 복잡, overhead가 큼, starvation 문제
- 개선
* 각 Ready Queue마다 시간 할당량을 다르게 배정하여 프로세스 특성에 맞게 운영
* I/O 위주 프로세스들은 상위 단계 Queue로 이동 why? I/O는 금방 처리 되기 때문
* 대기시간이 지정된 시간을 초과한 프로세스는 상위 단계 Queue로 이동 what? Aging 기법
본 내용은 한국기술교육대학교 김덕수 교수님의 유튜브 강의를 듣고 정리한 내용입니다.
'Software Courses > Operating System' 카테고리의 다른 글
| [Deadlock] Deadlock and Resources types (0) | 2020.12.04 |
|---|---|
| Process Synchronization and Mutual Exclusion (0) | 2020.12.02 |
| Thread 관리 (0) | 2020.11.30 |
| Process 관리 (0) | 2020.11.30 |
| OS Overview 2 (0) | 2020.11.29 |