[OS] 프로세스 스케줄링_방통대 교재 정리
#####. 프로세스 스케줄링
###. 프로세스 스케줄링
#. 일반적으로 스케줄링이란 여러 가지 작업의 처리순서를 경정하는 것을 의미
#. 어떤 순서로 프로세스를 처리할지를 운영체제가 결정하는 것
#. 만약 프로세스가 1개라면 OS 는 1개만 처리하면 되지만, 프로세스가 둘 이상이라면 어떤 프로세스를 먼저 처리할 지를 결정한다.
###. 스케줄링 단계
#. 상위단계, 중간단계, 하위단계 세 단계로 구성
#. 상위단계
- 장기 스케줄링
- 시스템에 들어와 작업큐에 있는 작업을 선택하여 프로세스를 생성한 후 프로세스 준비 큐에 전달하는 역할
- 보통 입출력 중심 작업과 연산 중심 작업을 균형있게 선택하도록 작업순서를 결정
#. 하위단계
- 단기 스케줄링
- 준비단계에 잇는 프로세스를 선택하여 사용 가능한 CPU를 할당하는 역할
- 디스패치된 프로세스는 실행 상태가 되어 프로세스가 처리
- 하위단계 스케줄링의 수행 주제는 디스패처가 된다.
- 상당히 빈번하게 발생 : 디스패처는 메모리에 늘 상주
#. 중간 단계
- 중기 스케줄링
- 프로세스를 일시적으로 메모리에서 제거하여 중지시키거나 중지된 프로세스에 다시 메모리를 할당하여 활성화 시켜 시스템에 대한 단기적인 부하를 조절하는 역할
- 시스템이 과부하되는 경우 메모리에서 어떤 프로세스를 제거해야 시스템 부하가 줄어들지를 결정하여 실제로 중지시키믕로 시스템이 적절히 운영되고 최적의 성능을 유지할 수 있도록 함
###. 스케줄링의 목표
#. 운영체제가 프로세스를 스케줄링할 때 고려하는 기본적인 목표는 두가지 : 공정성과 균형성
#. 공정성
- 모든 프로세스가 적정 수준에서 CPU작업을 할수 있게하는 것
#. 균형성
- 시스템의자원들이 충분히 활용될 수 있게 하는 것
- 자원의 경우 여러 프로세스가 동시에 이용할 수 없는 경우도 있을 수 있고 자동으로 할당될 수 없는 경우도 있을수 있기 떄문에 스케줄링 전에 이러한 제한 사항을 해결해야 한다.
#. 일괄처리 운영체제는 처리량의 극대화, 반환시간의 최소화, CPU활용의 극대화를 스케줄링 목표로 할수 있고, 시분할 운영체제는 빠른 응답시간, 과대한 대기시간 방지를 목표로 하낟. 실시간 운영체제는 처리기한을 맞추는 것이 스케줄링 목표
#. 용어들
- 처리량 (throughput) : 주어진 시간에 처리한 프로세스 수
- 반환시간 (turnaround time) : 프로세스 생성 시점부터 종료 시점까지의 소요시간
- 응답시간 (response time) : 요청한 시점부터 반응이 시작되는 시점까지 소요시간
- 대기시간 (waitng time) : 프로세스가 종료될 떄까지 준비큐에서 기다린 시간의 합
###. 스케줄링 정책
#. 선점 스케줄링 정책
- preemptive scheduling policy : 실행중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식 : 선점 방식
- 높은 우선순위의 프로세스를 우선 처리해야 하는 경우에 유용
- 실시간 시스템에서 선점 스케줄링 정책을 이용하면 필요한 프로세스가 CPU를 선점할 수 있도록 하기때문에 결과 예측이 가능
- 시분할 시스템에서도 빠른 응답시간을 유지하기 위해 필요
- 단점 : 오버헤드 발생 : CPU의 모든 레지스터 (특히 프로그램 카운터)와 기타 운영체제에 따라 요구되는 프로세스의 상태를 문맥 (context)라고 하는데, 프로세스가 종료되지 않은 상태에서 선점 스케줄링 정책에 따라 CPU 가 다른 프로세스에 달당 되려면 문맥 교환 (문맥 전환)이 필요. context switching 이란 CPU가 현재 실행하고 있는 프로세스의 상태를 프로세스 블록 PCB에 저장하고, 다른 프로세스의 프로세스 제어 블록으로부터 문맥을 복원하는 작업을 말한다. 이러한 문맥 교환 자체에도 일정 부분 시간과 자원이 사용되기 때문에 선점 스케줄링 정책을 적용할 떄는 문맥 교환이 매우 빠르게 실행되도록 만들어져야한다.
#. 비선점 스케줄링 정책
- nonpreemptive scheduling policy : 실행중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식
- CPU를 할당 받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이 될 때까지 ㅅ계쏙 실행상테에 있게 된다.
- 단점 : 오랜 시간이 걸리는 프로세스가 실행 중이라면 실행시간이 짧은 프로세스가 오래 기다리는 경우 발생
###. 스케줄링 알고리즘
#. FCFS(First-Come First-Served)
: 비선점 방식으로 스케줄링 알고리즘 중 가장 간단한 기법. 프로세스는 준비 큐에 도착한 수서에 따라 디스패치 된다.
#. SJF (Shortest Job First)
: 준비 큐에 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 실행하는 비선점 방식. 프로세스의 CPU사이클이 미리 주어져야 가능하다. CPU사이클 시간을측정하고 짧 것 부터 한다는 뜻
#. SRT (Shortest Remaining Time)
: 선점방식 스케줄링. 선점 방식이기에 만약 준비큐에 새로 들어온 프로세스의 예상 실행시간이 실행중인 프로세스의 남은 실행시간보다 짧다면, 새로 들어온 프로세스가 즉시 디스패치 된다.
#. RR (Round Robin)
: 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한하는 선점 방식의 스케줄링. 디스패치된 프로세스가 시간 할당량 안에 종료하지 못하면 해당 프로세스는 준비상태로 전이되어 준비큐의 마지막에 들어간다. 적절한 시간 할당량을 사용하면 프로세스들이 CPU를 독점하지 않고 공평하게 이용될 수 있게 한다. RR스케줄링은 시분할 운영체제에 적합. 시간 할당량이 각 프로세스의 실행시간보다 큰 경우 FCFS 스케줄링과동일해지지만 시간 할당이 너무 작은 경우 오버헤드가 많아진다.
#. HRN (Highest Response Ratio Next)
: 준비큐에서 기다리는 프로세스 중 응답 비율이 가장 큰 것을 먼저 디스패치하여 실행하는 비선점 방식의 스케줄링 알고리즘. HRN은 SJF스케줄링의 단점을 보완한 것이다. SJF는 예상이간이 짧은 프로세스가 계속해서 준비큐에 들어오면 시간이 긴 프로세스는 우선순위에서 계속 밀리지만 HRN은 예상시간이 긴 프로세스라 하더라도 대기시간이 길어지면 응답 비율도 커져 실행시간이 짧은 프로세스가 나중에 들어와도 밀리지 않는다.
#. 다단계 피드백 큐 스케줄링
: 입출력 중심인 프로세스와 연산 중심인 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여하는 선점 방식의 스케줄링 알고리즘