더보기
- [운영체제] 1강. 컴퓨터 통신망의 소개
- [운영체제] 2강. 프로세스와 스레드
- [운영체제] 3강. 프로세스 스케줄링
- [운영체제] 4강. 병행 프로세스 I
- [운영체제] 5강. 병행 프로세스 II
- [운영체제] 6강. 교착상태 I
- [운영체제] 7강. 교착상태 II
- [운영체제] 8강. 메모리 관리
- [운영체제] 9강. 가상 메모리
- [운영체제] 10강. 페이지 교체 알고리즘
- [운영체제] 11강. 장치관리
- [운영체제] 12강. 저장장치 및 파일 관리
- [운영체제] 13강. 분산 운영체제
- [운영체제] 14강. 운영체제 보안
- [운영체제] 15강. 운영체제 사례
프로세스 스케줄링
스케줄링
여러가지 작업의 처리순서를 결정하는 것
ex. 프로세스 스케줄링, 디스크 스케줄링 등
프로세스 스케줄링
주어진 프로세스가 여러 개인 경우, 프로세스 처리순서를 결정하는 것
스케줄링 단계
상위단계 스케줄링
시스템 요청이 들어오는 작업큐의 작업들을 준비큐 상의 프로세스로 만드는 작업
중간단계 스케줄링
시스템에 대한 단기적 부하를 조절하기 위해 작업들을 대기시켜 일시중지함
하위단계 스케줄링
준비큐에 있는 프로세스를 선택하여 사용가능한 CPU를 할당(디스패치)하는 역할. 수행주체: dispatcher
스케줄링 기본 목표
공정성
모든 프로세스가 적정 수준에서 CPU작업할 수 있도록
균형
시스템 자원이 충분히 활용될 수 있도록
운영체제 유형에 따른 스케줄링 목표
일괄처리 운영체제
- 처리량 극대화
- 반환시간 최소화
- CPU 활용 극대화
시분할 운영체제
- 빠른 응답시간
- 과다한 대기시간 방지
실시간 운영체제
- 처리기한 맞춤
스케줄링 정책
스케줄링 목표에 따라 우선적으로 고려해야 할 기본적인 정책
선점(preenotive) 스케줄링 정책
- 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식
- 높은 우선순위의 프로세스를 우선 처리하는 경우에 유용 (실시간시스템, 시분할 시스템)
- 문맥 교환에 따른 오버헤드 발생 (운영체제는 문맥교환이 매우 빠르게 실행되도록 만들어져야 함)
문맥(context)
CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태
문맥 교환(context switching)
CPU가 현재 실행중인 프로세스의 문맥을 PCB에 저장하고
다른 프로세스의 PCB로부터 문맥을 복원하는 작업
비선점(nonpreenotive) 스케줄링 정책
- 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식
- CPU를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이될 때까지 계속 실행상태에 있게 됨
- 강제적인 문맥교환이 없기에 오버헤드가 발생하지 않음
- 긴 프로세스가 실행 중이라면 짧은 프로세스가 오래 기다리게 되는 경우 발생
스케줄링 평가 기준
평균대기시간
각 프로세스가 수행완료 시까지 준비큐에서 기다리는 시간의 합의 평균값 (다 더하고/프로세스 개수 )
평균반환시간
각 프로세스가 생성시점부터 수행완료시점까지의 소요시간의 평균값
스케줄링 알고리즘
FCFS 스케줄링 (First-Come-First-Served)
- 비선점 방식
- 준비 큐에 도착한 순서에 따라 디스패치
- 가장 간단한 스케줄링 기법
- 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음 (실시간, 시분할 OS ❌)
- 프로세스들의 도착순서에 따라 평균반환시간이 크게 변환
SJF 스케줄링 (Shortest Job First)
- 비선점 방식
- 준비 큐에서 기다리는 프로세스 중 예상실행시간이 가장 짧은 것부터 먼저 디스패치
- 일괄처리 환경에서 구현하기 쉬움
- 실제로는 먼저 처리할 프로세스의 CPU시간을 예상할 수 없음
- (비선점 방식의 단점)
SRT 스케줄링 (Shortest Remaining Time)
- SJF 알고리즘의 선점 방식
- 준비 큐에서 기다리는 프로세스 중 남은 예상 실행시간이 가장 짧은 것부터 디스패치
- SJF보다 평균대기시간이나 평균반환시간에서 효율적
- 실제 프로세스의 CPU시간 예상 불가
- 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 더 큰 오버헤드
HRN 스케줄링 (Highest Response Ratio Next)
- 비선점 방식
- 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
- 응답비율 = (대기시간/예상 실행시간) +1
- 예상실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커짐
- SJF 스케줄링의 단점 보완: 예상실행시간 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치 가능
- 실제로는 프로세스의 CPU시간 예상 불가
RR 스케줄링 (Round Robin)
- 선점 방식
- 준비 큐에 도착한 순서대로 디스패치하지만 정해진 시간 할당량에 의해 실행 제한
- 시간 할당량 내 종료하지 못한 프로세스는 준비 큐 마지막에 배치됨
- CPU를 독점하지 않고 공평하게 이용 (시분할 OS 적합)
- 시간 할당량이 너무 크면 FCFS 스케줄링과 동일
- 시간 할당량이 너무 작으면 과도한 문맥교환 발생으로 오버헤드 증가
다단계 피드백 큐 스케줄링
- 선점 방식
- I/O 중심 프로세스와 연산 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
- 단계 1부터 단계 n까지 하나씩의 준비 큐 존재
- 단계 k는 단계 k+1에 피드백
- 단계가 커질수록 시간 할당량 증가
- 디스패치 후 대기상태로 갔다가 준비상태가 될 때는 현재와 동일 단계의 준비 큐에 배치
- 시간할당량을 다 썼으면 다음 단계의 준비큐로 이동 배치
- 단계 k의 준비 큐에 있는 프로세스가 디스패치되려면 단계 1부터 단계 k-1까지의 모든 준비큐가 비어있어야 함
- I/O 위주 프로세스 : 높은 우선권 유지
- 연산 위주 프로세스 : 낮은 우선권 & 긴 시간할당량
정리하기
- 프로세스의 스케줄링을 위해 상위단계, 하위단계 및 중간단계 스케줄링이 사용된다.
- 선점 스케줄링 정책은 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식이고, 비선점 스케줄링 정책은 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식이다.
- FCFS 스케줄링은 준비 큐에 도착한 순서에 따라 디스패치하는 비선점 방식의 스케줄링 알고리즘이다.
- SJF 스케줄링은 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 비선점 방식의 스케줄링 알고리즘이다.
- SRT 스케줄링은 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 선점 방식의 알고리즘이다.
- RR 스케줄링은 프로세스가 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한하는 선점 방식의 스케줄링 알고리즘이다.
- HRN 스케줄링은 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치하여 실행하는 비선점 방식의 스케줄링 알고리즘이다.
- HRN 스케줄링의 응답비율은 예상실행시간이 짧을수록, 그리고 대기시간이 길수록 커진다.
- 다단계 피드백 큐 스케줄링은 입출력 위주의 프로세스가 연산 위주의 프로세스보다 우선권을 갖도록 하는 선점 방식의 알고리즘이다.
'방송통신대학교 > 운영체제' 카테고리의 다른 글
| [운영체제] 2강. 프로세스와 스레드 (0) | 2023.04.16 |
|---|---|
| [운영체제] 1강. 운영체제 소개 (0) | 2023.04.16 |