다중 프로그래밍 (Multi-Programming)
여러개의 프로세스가 시스템 내에 존재
자원을 할당할 프로세스를 선택해야 함
스케줄링(Scheduling)
자원 관리
시간 분할 (time sharing) 관리
하나의 자원을 여러 스레드들이 번갈아 가며 사용
예) 프로세서 (Processor)
프로세스 스케줄링 (Process scheduling)
프로세서 사용시간을 프로세스들에게 분배
공간 분할 (space sharing) 관리
하나의 자원을 분할하여 동시에 사용
예) 메모리 (memory)
스케줄링 (Scheduling)의 목적
시스템의 성능 향상
대표적 시스템 성능 지표
응답시간 (response time)
작업 요청(submission)으로부터 응답을 받을때까지의 시간
작업 처리량 (throughput)
단위 시간 동안 완료된 작업의 수
자원 활용도 (resource utilization)
주어진 시간 동안 자원이 활용된 시간
목적에 맞는 지표를 고려하여 스케줄링 기법 선택
시스템 성능 지표들
평균 응답 시간
처리량
자원 활용도
공평성
실행 대기 방지
예측 가능성
자원 할당의 공정성 보장
단위시간당 처리량 최대화
적절한 반환시간 보장
예측 가능성 보장
오버헤드 최소화
자원 사용의 균형 유지
반환시간과 자원의 활용 간에 균형 유지
실행 대기 방지
우선순위
서비스 사용 기회 확대
서비스 수 감소 방지
스케줄링 정책 (Policy)
선점(Preemptive) vs 비선점(Non-Preemptive)
선점 스케줄링 (Preemptive Scheduling)
타의에 의해 자원을 빼앗길 수 있음
Context switch overhead가 큼
Time-sharing System, real-time System 등에 적합
비선점 스케줄링 (Non-Preemptive Scheduling)
할당 받을 자원을 스스로 반납할 때까지 사용
장점: Context switch overhead가 적음
단점: 잦은 우선순위 역전, 평균 응답시간 증가
우선순위(Priority)
프로세스의 중요도
Static priority (정적 우선순위)
프로세스 생성시 결정된 priority가 유지됨
구현이 쉽고, overhead가 적음
시스템 환경 변화에 대한 대응이 어려움
Dynamic priority (동적 우선순위)
프로세스의 상태 변화에 따라 priority 변경
구현이 복잡, priority 재계산 overhead가 큼
시스템 환경 변화에 유연한 대응 가능
Basic Scheduling algorithms
FCFS
비선점 스케줄링
먼저 도착한 프로세스를 먼저 처리
자원을 효율적으로 관리가능
Batch system에 적합, 대화형 시스템에 부적합
단점: 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게된다.
RR(Round-Robin)
선점 스케줄링
먼저도착한 프로세스를 먼저처리
자원 사용 제한시간(타임 슬라이스)이 있음
대화형, 시분할 시스템에 적합
장점: 특정 프로세스의 자원 독점을 방지한다.
단점: 문맥교환 overhead가 크다
SJF (= SPN)
비선점 스케줄링
실행시간이 가장 적은 프로세스를 먼저 처리
장점
평균 대기시간 최소화
시스템 내 프로세스 수 최소화
많은 프로세스들에게 빠른 응답시간 제공
단점
starvation(아사) 현상 발생 -> HRRN에서 Aging등으로 해결
정확한 실행시간을 알 수 없음
HRRN (= HRN, SJF의 변형)
비선점 스케줄링
응답률이 높은 프로세스 우선
응답률 = 반환시간/실행시간
SJF의 장점 + starvation 방지
실행시간 예측기법 필요(overhead)
[출처] https://drive.google.com/file/d/1hRfvONw25cGbHqtOxUu61M9qDonqmOPD/view
Beginner_Developer