3강. 프로세스 스케줄링

 

스케줄링 : 여러 가지 작업의 처리순서 결정

프로세스 스케줄링: 주어진 프로세스 처리 순서를 결정

 

스케줄링 단계

상위단계 : 작업 큐에 있는 작업을 선택 해 프로세스를 생성한 후 프로세스 준비 큐에 전달

중간단계 :  프로세스를 일시적으로 메모리에서 제거해 중지시키거나 중지된 프로세스에 다시 메모리 할당하여 활성화. 
하위단계 : 준비 큐에 있는 프로세스 선택 해 사용 가능한  CPU에 할당

 

스케줄링 목표

1. 공정성 : 모든 프로세스가 적정 수준에서 CPU작업을 할 수 있게 하는 것

2. 균형성 : 시스템의 자원들이 충분히 활용될 수 있게 하는 것

 

스케줄링 정책

1. 선점 스케줄링 정책 : 실행 중인 프로세스에 인터럽트를 걸어 사용하지 못하게 한 후 뺏어서 다른 프로세스에 CPU 할당하는 방식.

높은 우선순위 프로세스를 우선적으로 처리

실시간 시스템, 시분할 시스템

문맥(CPU의 프로세스 상태 ) 교환에 따른 오버헤드 발생

 

 

2. 비선점 스케줄링 정책 : 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식. 종료나 대기로는 가능하나 실행에서 준비로는 갈 수 없다.

강제적인 문맥 교환이 없어 오버헤드 발생하지 않음

 

스케줄링의 평가 기준

평균 대기시간: 프로세스가 실행되지 못하고 준비 큐에서 기다리는 시간의 합의 평균값

 

 

평균 반환시간: 프로세스가 생성되고 완료된 시점까지의 평균값

 

스케줄링 알고리즘 6개

1. FCFS(First Come First Served): 비선점방식(한 번  cpu 할당 받으면 완전 종료될 때까지 자동으로 뺏기지 않음)

장점: 가장 간단

단점: 짧은 프로세스는 자기 순서가 올 때까지 기다려야함. 시분할 운영체제나 실시한 운영체제에 부적함.

 

2. SJF(shortest job first) : 가장 짧은 작업을 먼저 처리 . 비선점 방식

기다리는 동안 준비 큐에 기다리는 작업들이 예상 실행시간이 가장 짧은 것이 다음번에 실행됨.

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

단점: 짧은 프로세스가 들어왔는데 긴 프로세스 실행 중일 때 기다려야 함. 먼저 들어와도 프로세스가 길면 계속 기다려야  함

 

3. SRT(Shortest Remaining Time) : SJF 알고리즘의 선점 방식 . 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치.

장점: SJF 보다 평균 대기시간, 평균 반환시간이 효율적

단점: CPU시간 예상할 수 없음

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

 

 

4. RR(Round Robin):  선점 방식(프로세스 중에 뺏길 수도 있음 ), 준비 큐에 도착한 순서대로 디스패치하지만 정해진 시간 할당량에 의해 실행 제한 . 시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치됨.

장점: CPU를 독점하지 않고 공평하게 이용. 시분할 운영체제에 적합

단점: 시간 할당량이 너무 크면 FCFS 스케줄링과 동일. 시간 할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드가 커짐

 

5. HRN(Highest Response Ratio Next): 비선점 방식

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

대기시간/예상 실행시간 +1  : 예상 실행시간이 짧을수록 응답비율 커짐. 대기시간 길수록 응답비율 커짐

장점: SJF 스케줄링 단점 보완

 

6. 다단계 피드백 큐 스케줄링: 선점방식, 라운드로빈을 확장시킨 개념

여러 단계로 나누고 각 단계마다 준비 큐 존재. 시간할당량이 끝나버리면 그 다음 단계에 감. 각 시간 할당량의 크기는 다른데 단계가 커질수록 시간 할당량도 커짐. 앞 단계의 준비큐가 다 비워야 다음 단계에 있는 준비큐를 실행시킬 수 있음.

특징:  입출력 위주 프로세스는 높은 우선권 유지 . 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량.

 

 

 

 

 

반환시간: 언제 들어와서 언제 끝난는지 시간