프로세서 스케줄링 포스트 복사해 오기

위성 엔지니어가 꿈입니다. | 라임
http://blog.naver.com/swmem_bjm/130144776770

프로세서 스케줄링 

 

 

 

1.프로세서 스케쥴링의 개요

 [스케줄링과 문맥교환의 의미]

스케줄링의 정의:

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업

 

목적:

1. 공정성, 처리율 증가, CPU 이용률 증가, 우선순위 제도, 오버헤드 최소화

2. 반환시간 최소화, 대기시간 최소화, 균형 있는 자원의 사용, 무한연기 회피

 

문맥교환(Context Switching)

1. 하나의프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생되는 것

2. 새로운 프로세스에게 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고

   새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업

3. 오버헤드(Overhead) 시간에 포함됨

 

[프로세서 스케줄링의 분류]

비선점 스케줄링(Non - Preemptive]

1. 프로세스가 CPU를 할당 받으면 해당 프로세스가 완료될 때까지 CPU를 사용함

2. 모든 프로세스에 대한 요구를 공정하기 처리할 수 있음

3. 일괄처리 방식에 적합 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴작업)을 기다리는 경우가 발생할 수 있음

 

선점 스케줄링(Preemptive)

1. 하나의 프로세스가 실행 중 일때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있음

2. 우선 순위가 높은 프로세스를 빠르게 처리할 수 있음

3. 대화식 시분할 시스템에 사용됨

4. 종류 : SRT, 선점 우선 순위, Round Robin, 다단계 큐, 다단계 피드백 큐

 

2. 비선점 스케줄링

FCFS: First Come First Service : 큐에 도착한 순서에 따라 차례로 CPU할당

SJF : Shorest Job First: 실행 시간이 가장 짧은 프로세스에 먼저 CPU를 할당 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘

HRN : Highest Response-ratio Next 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완한 것

우선 순위 = (대기시간 + 서비스시간) / 서비스시간

우선 순위 Priority : 준비상태 큐에서 기다리는 각 프로세스마다 우선 순위를 부여하여 그 중 우선 순위가 가장 높은 프로세스에게 먼저 CPU를 할당

기한부 Deadline: 프로세스에게 일정한 시간 안에 프로세스를 완료하도록 하는 기법

 

에이징(Aging) 기법

1. 프로세스의 우선 순위가 낮아 무한정 기다리게 되는 경우 한번 양보하거나

     기다린 시간에 비례하여 일정 시간이 지나면 우선 순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당 받도록 하는 기법

2. SJF 우선 순위 기법에서 발생할 수 있는 무한 연기 상태 기아 상태 예방

 

3. 선점 스케줄링

선점 우선순위 : 큐의 프로세스 중 우선 순위가 장 높은 프로세스에게 CPU할당

SRT: Shorest Remaining Time 비선점 기법인 SJF 알고리즘을 선점 형태로 변경한 기법 현재 실행 중인 프로세스의 남은

        시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU 할당

RR: Round Robin 시분할 시스템을 위해 고안된 방식, FCFS 알고리즘을 선점 형태로 변형한 것으로 interactive(대화형) 시스템에 많이 사용됨

다단계 큐: 프로세스를 특정 그룹으로 분류 할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법

다단계 피드백 큐: 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 있도록 한 기법 (출력이 입력 으로)

 

RR:

 

다단계 큐:

 

다단계 피드백 큐: