운영체제-3

프로세스 스케줄링

스케줄링 여러 가지 작업의 처리 순서를 결정 하는 것 ex) 프로세스 스케줄링, 디스크 스케줄링 등

 

프로세스 스케줄링

주어진 프로세스가 여러 개인 경우, 프로세스 처리 순서를 결정하는 것

 

스케줄링 단계

시스템에 들어오는 작업들 -> 상위단계 스케줄링(자원을 효율적으로 이용할수 있게함) -> 활성화된 작업들

 

하위단계 스케줄링

준비 큐에 있는 프로세스를 선택하여 사용가능한 cpu할당(디스패치) 역할

수행 주체 : 디스패처

 

중간단계 스케줄링

시스템에 대한 단기적인 부하를 조절 하도록 함

 

기본 목표

공정성 = 모든 프로세스가 적정 수준 cpu 작업을 할수 있게 함

균형 = 시스템 자원이 충분히 활용될수 있게함

 

운영체제의 유형에 따른 스케줄링 목표

일괄처리 운영체제

처리량 극대화

반환시간의 최소화

cpu활용의 극대화

 

시분할 운영체제

빠른 응답시간

과다한 대기시간 방지

 

실시간 운영체제

처리기한 맞춤

 

정책

선점 스케줄링

- 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 cpu를 할당할 수 있는 스케줄링 방식

높은 우선순위의 프로세스를 우선 처리해야하는 경우에 유용( 실시간, 시분할)

문맥 교환에 따른 오버헤드 발생

문맥 (context)

cpu의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태

 

문맥 교환(context switching)

cpu가 현재 실행하고 있는 프로세스의 문맥을 pcb에 저장하고 다른 프로세스의 pcb로부터 문맥을 복원하는 작업

 

비선점 스케줄링

실행중인 프로세스를 바로 준비상태로 전이시킬 수 없는 방식

cpu를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이 될 때 까지 계속 실행 상태에 있게 됨

강제 문맥 교환이 없어 오버헤드 발생 없음

긴 프로세스가 실행 중이라면 짧은 프로세스가 오래 기다림

 

평가 기준

평균 대기 시간(대기시간 합 / 프로세스 개수)

각 프로세스가 수행이 완료 될 때까지 준비 큐에서 기다리는 시간의 합의 평균 값

평균 반환 시간(반환시간 합 / 프로세스 개수)

각 프로세스가 생성된 시점부터 수행이 완료된 시점 까지의 소요시간 평균 값

 

스케줄링 알고리즘

FCFS(First-Come First-Served)스케줄링

비선점 방식

준비 큐에 도착한 순서에 따라 디스패치

장점

가장 간단한 스케줄링 기법

단점

짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행 될 수 있음

 

SJF(Shortest Job First)

비선점 방식

준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치

장점

일괄처리 환경에서 구현하기 쉬움

단점

실제로는 먼저 처리할 프로세스의 cpu시간을 예상 할수 없음

새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행 될수 있음

 

SRT(Shortest Remaining Time)

SJF 알고리즘의 선점 방식

준비 큐에서 기다리는 프로세스중 남은 실행시간이 가장 ᄍᆞᆲ다고 예상되는 것을 디스패치

장점

SJF보다 평균대기시간이나 평균반환시간이 효율적

단점

실제로는 먼저 처리할 프로세스의 cpu시간을 예상 할수 없음

각 프로세스의 실행시간 추적, 선점을 위한 문맥교환등 SJF보다 오버헤드가 큼

 

- RR(Round Robin)

선점 방식

준비 큐에 도착한 순서대로 디스패치 하지만 정해진 시간 할당량 에 의해 실행 제한

시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치

장점

cpu를 독점 하지 않고 공평하게 이용

단점

시간 할당량이 너무 크면 FCFS 스케줄링과 동일

시간 할당량이 너무 작으면 너무 많은 문맥교환 발생으로 오버헤드 커짐

 

HRN(Highest Response Ratio Next)

비선점 방식

준비 큐에서 기다리는 프로세스중 응답비율이 가장 큰 것을 먼저 디스패치

대기시간 + 예상 실행시간 대기시간

응답비율 = ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ = ㅡㅡㅡㅡㅡ + 1

예상 실행시간 예상 실행시간

장점

SJF 스케줄링의 단점을 보완

예상 실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치 가능

단점

실제로는 프로세스의 cpu예상시간을 예상 할 수 없음

 

다단계 피브백 큐 스케줄링

선점방식

I/O 중심 프로세스와 연산중심 프로세스의 특성에 따라 서로 가른 시간 할당량 부여

단계 1부터 단계 n까지 하나씩의 준비 큐 존재

단계 k는 단계 k+1에 피드백

단계가 커질수록 시간 할당량도 커짐

I/O 위주의 프로세스는 높은 우선권 유지

연산위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량