[운영체제] 프로세스 스케줄링

스케줄링

 

여러 프로세스가 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것

 

스케줄링의 목적

 

- 프로세서의 이용률을 높이고 처리율을 향상

    하나의 CPU에서 여러개의 프로세스를 실행하는 다중 프로그래밍 방식은 프로세스가 입출력 등으로 대기 상태로 진입 시 다른 프로세스로 교체해 (문맥 교환) 프로세서의 유휴 시간을 줄이고 주어진 시간 동안 처리하는 작업량을 증가시킬 수 있다.

- 응답시간을 최소화

    또한 시분할 시스템에서 프로세스에 할당된 시간이 만료됨에 따라 교체하여 들어올 프로세스를 결정하는 것도 CPU 스케줄러가 담당한다.

- 자원할당의 공정성

   모든 프로세스가 자원을 공평하게 사용할 수 있도록 해야 한다.

- 실행 대기 방지

   무한히 대기하는 프로세스가 없게 해야 한다.

- 우선순위

   우선순위 정책에 따라 우선순위가 높은 프로세스를 먼저 실행할 수 있게 한다.

 

스케줄링 단계

 

1) 장기 스케줄링

 

디스크에 있는 프로그램을 프로세스화 하여 실행할지 승인(admit)하는 스케줄링으로 수행 빈도가 낮아 장기 스케줄링이라고도 한다.

admit: new -> ready

 

2) 중기 스케줄링

 

장기 스케줄링과 마찬가지로 작업 승인을 하고 프로세스를 실행 연기하거나 실행 중인 프로세스를 중단할 수 있다. 

주 메모리를 사용하고 있는 프로세스 수가 많다면 시스템 부하를 줄이기 위해 특정 과부하 프로세스를 디스크로 내보내는 (swap-out) 일을 수행할 수 있다. 단기 스케줄링과 장기 스케줄링의 중간단계 역할로 다중 프로그래밍의 정도(degree of multiprogramming)를 조절한다.

swap-out: wait -> suspended wait / ready -> suspended ready

 

3) 단기 스케줄링

 

준비 큐에 있는 프로세스 중 어떤 프로세스에 프로세서를 할당할 것 인지 순서를 정하고 가장 빈도가 높은 단기 스케줄링이다.

또한 각 프로세스에 할당하는 타임 슬라이스를 조절하여 시스템 효율성을 증가시키고 실행 시간이 만료되어 준비 상태가 된 프로세스를 다시 준비 큐에 넣는다.

dispatch: ready -> running

 

선점형 스케줄링 vs 비선점형 스케줄링

• 선점이 가능한 스케줄링은 어떤 프로세스가 CPU를 사용하고 있더라도 그 프로세스를 강제로 중단하고 새로운 프로세스에 CPU를 할당하여 실행할 수 있는 권한이 있다는 것을 의미한다.
• 프로세스 교체에 의한 문맥 교환 절차가 이루어지고 주로 우선순위가 높은 프로세스가 준비 큐에 들어왔을 때나 타임 아웃이 되었을 때 선점이 일어난다.
• 만약 비선점형 방식을 사용한다면, 프로세스가 실행 완료될 때까지 다른 프로세스는 기다리게 된다.

 

스케줄링 알고리즘 선택 기준

 

1) CPU 사용률

    전체 시스템 동작 시간 중 실제로 CPU를 사용한 시간을 측정한다.

2) 처리량 (throughput)

    단위 시간당 작업을 마친 프로세스의 수를 의미한다.

3) 대기시간 (waiting time)

    대기 시간은 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간이다.

4) 응답 시간 (response time)

    프로세스 시작 후 첫 번째 반응이 나올 때까지 걸리는 시간이다.

5) 반환 시간 (turn around time)

    자원을 모두 반환하는 데까지 걸리는 시간으로 대기시간과 실행시간을 더한 값이다.

 

프로세스 실행관련 용어

보통 평균 반환 시간과 평균 대기시간을 기준으로 알고리즘 성능을 평가한다.

 

알고리즘의 종류와 특징

 

구분	명칭	특징
비선점형 알고리즘	FCFS First Come First Serve	준비 큐에 도착한 순서대로 프로세스를 실행한다. 가장 공평한 정책으로 무한 대기하는 프로세스가 없다. 콘보이 효과: 실행 시간이 긴 프로세스에 의해 다른 프로세스가 오래 기다리게 된다. 응답시간이 중요한 대화형 시스템에 부적합하다.
	SJF Shortest Job First	실행 시간이 가장 짧은 프로세스를 먼저 실행한다. 공평하지 못한 정책으로 실행 시간이 긴 프로세스가 지속적인 짧은 프로세스의 도착으로 무한히 대기할 수 있다(기아 현상). 에이징 기법: 프로세스가 양보할 수 있는 횟수의 상한선을 제시한다. 현실적으로 프로세서의 실행 시간을 예측하기 어렵다.
	HRN High Response Next	우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간 에이징 기법을 수치적으로 반영한 방법 대기시간을 고려하여 기아 현상을 줄일 수 있으나 여전히 공평성이 위배 된다.
선점형 알고리즘	RR Round Robin	프로세스마다 실행 시간(타임 슬라이스)이 주어져 시간이 만료되면 준비 큐에 다시 진입시킨다. 반응 시간이 빠르므로 대화형 시스템에 적합하다. 문맥 시간에 따른 오버헤드가 발생하기 때문에 적절한 타임 슬라이스를 결정해야한다.
	SRT Shortest Remaining Time	준비 큐에 있는 프로세스 중 완료까지 남은 시간이 짧은 프로세스를 먼저 실행한다. 남은 시간을 프로세스마다 추적해야 되고 기아 현상이 일어날 수 있기 때문에 잘 사용하지 않는다.

- 우선순위를 부여한 정책

SJF(실행 시간 기준), HRN(실행 시간과 대기 시간 기준), SRT(남은 시간 기준)

 

- 여러 준비 큐를 사용한 스케줄링 방법

 

다단계 큐 스케줄링

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 우선순위가 높은 준비 큐에 있는 프로세스부터 먼저 실행하며 모든 프로세스가 실행 완료되어야 다음 우선순위의 큐에 있는 프로세스를 실행한다.
• 선점형 방식, 라운드 로빈을 택하면서 각 큐에 다른 타임 슬라이스를 부여하여 운영할 수 있다.
• 우선순위가 높은 큐에는 타임 슬라이스를 작게 하여 반응을 빠르게 하고 낮은 큐에 있는 프로세스는 상호작용이 덜 필요하므로 타임 슬라이스를 크게 하여 FCFS처럼 동작하게 한다.

다단계 피드백 큐 스케줄링

• 다단계 큐 스케줄링에서 우선순위가 낮은 프로세스 작업이 연기되는데 이러한 문제를 해결하고자 한다.
• 마찬가지로 라운드 로빈 방식을 택하지만 한번 타임 슬라이스를 얻어 실행된 프로세스는 우선순위가 낮아져 우선 순위가 낮은 준비 큐에 삽입된다.
• 오늘날 운영체제에서 가장 많이 쓰이는 방식이다.