선점 스케줄링/비선점 스케줄링

스케줄링

프로세스가 실행될 때 시스템에서 여러 자원을 프로세스에 할당하는 작업

 

단계

작업 스케줄링(job scheduling)

어떤 프로세스가 시스템의 자원을 차지할 수 있는지 결정하여 준비상태 큐로 보내는 작업

작업 스케줄러(job scheduler)에 의해 수행

 

프로세스 스케줄링(processor scheduling)

프로세스가 작업을 수행할 때 필요한 자원을 해당 프로세스에게 할당하는 작업

CPU 를 할당 받는 시기와 특정 프로세스를 지정하는 방법

 

분류

선점 스케줄링_{(운영체제가 프로세스의 제어권을 가지고있다.)}

• STR(Shortest Remaining Time)
• RR(Round Robin)
• MLQ(Multi-level Queue)
• MFQ(Multi-level feedback Queue)

 

비선점 스케줄링

• FCFS(First Come Frist Service 선입선출)
• SJF(Shortest Job First, 단기 작업 우선)
• HRN(Highest Responese-ratio Next)
• 기한부(deadline)
• 우선순위(priority)
•  

---

선점 스케줄링

▶SRT(Shortest Remaining Time)

가장 짧은 시간이 소요되는 프로세스를 먼저 수행시킨다.

비선점 SJF를 선점 형태로 변경한 기법이다. 선점 SJF  이라고도 한다.

 

특징

• 더 짧은 처리시간의 프로세스가 들어오면 실행 중인 프로세스라도 중단시키고 더 짧은 처리 시간의 프로세스를 처리한다.
• 준비상태 큐에 있는 프로세스들의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다.
• 긴 작업은  SJF보다 대기 시간이 길어짐

 

▶RR(Round Robin)라운드 로빈

FCFS기법을 선점 형태로 변형한 기법이다.

시분할 시스템 (time sharing system)을 위해 고안된 방법임.

 

방법

1. 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당 받음
2. 프로세스가 시간할당량(time slice, quantum)동안 실행된 후 작업이 완료되지 않으면 다음 프로세스에 cpu를 넘겨주고 준비상태 큐의 맨 뒤로 이동한다.

 

할당되는 시간이 클 경우 :  FCFS 기법과 동일함

할당되는 시간이 작을 경우 : 문맥 교환을 위한 오버헤드가 증가함

(pcb를 주기억장치에 적재하고 빼내는 과정에서 오버헤드 증가)

 

▶MLQ(MQ) 다단계 큐

프로세스를 여러 그룹으로 나누어 여러 개의 다른 준비 상태 큐를 사용하는 스케줄링 기법이다.

 

#우선순위 높음#                                                         #우선순위 낮음#

시스템 프로세스 >  대화형 프로세스  >  편집 프로세스  >  일괄처리 프로세스

 

• 각 준비상태 큐는 자기만의 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 다른 방식의 스케줄링 기법을 사용할 수 있다.
• 준비상태 큐에 있는 프로세스를 실행하는 중이라도 상위 단계 큐에 작업이 들어오면 상위 단계에 cpu를 할당해야 한다.
• 그룹별 준비상태 큐의  프로세스들은 다른 준비상태로 이동 할 수 없다.

 

 

▶MFQ(Multi-level feedback Queue) 다단계 피드백 큐

MLQ/MQ에서 그룹별 준비상태 큐에서 프로세스가 큐 사이를 이동할 수 있도록 개선한 방법이다.

 

방법 :  준비상태 큐마다 서로 다른 할당시간을 부여하여 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동하게 한다 .

 

• 작업을 처리하는데 시간이 적은 프로세스에 유리하다.
• 상위단계의 준비상태 큐일수록 우선순위가 높고 시간 할당량이 적다
• 하위 준비상태 큐에 있는 프로세스 실행 중에 상위 상태의 프로세스가 들어오면 상위 단계 프로세스에 cpu를 할당한다.
• 마지막 단계 큐에서는 작업이 완료 될 때까지 라운드 로빈 스케줄링을 사용한다.

 

---

 

비선점 스케줄링

 

▶FCFS (First Copme First Service) 선입선출

FIFO(First In First Out) = queue

가장 간단한 기법, 대기 큐에 도착한 순서에 따라 cpu 를 할당 받는다.

 

• 먼저 들어온 프로세스가 먼저 처리가 되어 공평성이 유지된다.
• 다른 기법들에 비해 완료시간 예측이 용이하다.
• 중요하지 않은 작업이 중요한 작업을, 긴 작업이 짧은 작업을 기다리게 할 수 있음
• 선착순!

 

※ 큐(Queue)

줄이라는 의미를 가지고 있다.

rear라고 정의된 리스트의 한 쪽 끝에서 삽입이 되고, front 정의된 반대 쪽에서 삭제가 일어나는 자료구조.

 

▶SJF(Shortest Job First) 단기 작업 우선

준비 상태 큐에서 기다리고 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스가 cpu를 할당 받는다.

 

FCFS보다 평균 대기시간은 감소되지만, 큰 작업에서는 FCFS보다 예측이 어렵다.

SRT와 SJF의 다른 점은 SRT는 자신보다 실행 시간이 작은 프로세스가 들어오면 자신까지 멈추고 그 프로세스를 먼저 처리하고 SJF는 자신을 처리하고 난 후에 실행 시간이 작은 프로세스를 다음으로 처리한다.

• 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘이다.
• 짧은 작업을 요구하는 측면에서는 유리한 스케줄링이다.
• 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 무한 연기가 될 수 있다.

 

▶HRN(Highest Response-ratio Next)

실행시간이 긴 프로세스에게 분리한 SJF기법을 보완하기 위한 스케줄링 기법이다.

대기 시간과 실행 시간을 활용한다.

 

한 프로세스가 작업을 실행하면 작업이 완료될 때까지 실행됨

우선순위 계산을 통해 실행 시간이 짧은 프로세스나 대기시간이 긴 프로세스에게 우선순위를 준다.

우선순위 계산식  = (대기시간 + 실행시간 = 서비스시간) / 실행시간

실행시간이 짧거나 대기시간이 긴 프로세스일 경우 우선순위가 높아진다

 

 

▶기한부(deadline)

프로세스에게 일정시간을 할당하여 그 시간 안에 작업을 완료하도록 하는 기법

시간 내에 작업을 완료하지 못할 경우, 제거가 되거나 처음부터 다시 한다.

 

• 프로세스 실행시 집중적으로 요구되는 자원관리 때문에 오버헤드가 발생한다.
• 여러 프로세스가 동시에 실행되면 스케줄링이 복잡해진다.

 

▶우선순위(priority)

준비상태에서 우선순위를 부여하며 가장 높은 우선순위의 프로세스에 cpu를 할당한다.

 

• 우선순위 동일 시 FCFS기법을 이용한다.
• 가장 낮은 순위를 받은 프로세스는 무한연기 또는 기아상태가 발생할 수 있다.

 

※에이징(aging)기법

기다린 시간에 비례하여 우선순위를 부여해 무한연기를 방지함