Process Scheduling 1

Types of Process scheduling

프로세스 스케줄링은 4종류로 나눌 수 있습니다.

 

1. Long-term scheduling (job scheduler)
   
   • 어떤 프로그램이 실행하기 위해 시스템에 들어갈지 결정하는 스케줄링
2. Medium-term scheduling (swapper)
   • 메인메모리로 어떤 프로세스를 추가할지 결정하는 스케줄링
3. Short-term scheduling (CPU scheduler)
   • 실행할 프로세스를 결정하는 스케줄링
4. I/O scheduling
   • 어떤 I/O 리퀘스트를 처리할지 결정하는 스케줄링

 

- Long-term scheduling이 가장 먼저 실행됩니다.

- Long-term scheduling이 Ready Queue에 올릴 프로그램을 정합니다.

- Ready Queue에 있는 프로세스들 중에서 어떤 프로세스를 실행할지 Short-term scheduling으로 정합니다.

- Medium-term scheduling은 Multiprogramming의 정도를 결정합니다.

 

 

Selection Function

Ready 상태에 있는 프로세스 중에서 다음에 실행할 프로세스를 결정하는 함수

여기서는 Multi process가 아닌 Uni process 환경이라고 가정합니다.

 

• w : 시스템에서 지금까지 사용한 시간
• e : 지금까지 실행에 소요된 시간
• s : 프로세스를 실행하는데 요구되는 서비스 시간 (e를 포함합니다.)

 

 

Desicion Mode

Selection Function에는 두가지 Desicion Mode가 있습니다.

Selection Function이 실행되는 순간을 정합니다.

• Nonpreemptive 비선점형
  
  • 프로세스가 running상태에 있으면 종료되거나, I/O를 기다리거나 일부 운영체제 서비스를 요청하기 위해 자체적으로 차단할 때까지 계속 실행됩니다.
  • = 특별한 일이 없다면 끝까지 실행합니다.
• Preemptive 선점형
  • 현재 실행중인 프로세스가 운영체제에 의해 중단되고 준비 상태로 이동할 수 있습니다.
  • 선점은 새로운 프로세스가 도착할 때 수행될 수 있습니다.
  • 차단된 프로세스를 Ready 상태로 만드는 인터럽트가 발생할 때, 또는 주기적으로 클럭 인터럽트가 발생할 때 수행될 수 있습니다.
  • process switch가 빈번할 수 있습니다.

 

 

FIFO (First In, First Out) = FCFS (First Come, First Served)

현재 프로세스의 실행이 중단되면 Ready Queue에서 가장 최근의 프로세스가 선택됩니다.

• Selection Function : Max[w]
  • 시스템에서 가장 오래 머물러 있던 프로세스를 선택하는 함수를 사용합니다.
• Decision Mode: Non-preemption 비선점
• 장점
  • 가장 간단한 스케줄링 입니다.
• 단점
  • 짧은 프로세스보다 긴 프로세스 수행에 더 좋습니다. = pair하지 않습니다.
  • convoy effect가 있을 수 있습니다.
  • convoy effect 란 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상을 의미합니다. 

 

 

Shortest-Process-Next (SPN) = SJF (Shortest-Job-First)

예상되는 processing 시간이 가장 짧은 프로세스를 다음에 선택하는 비선점 스케줄링입니다.

FCFS에서 긴 프로세스를 선호하는 편향을 줄이기 위해 고안되었습니다.

• Selection Function : min[s]
  • 프로세스의 서비스 시간이 가장 짧은 프로세스를 선택합니다.
• Decision Mode: Non-preemption 비선점
• 장점
  • turnaround time 측면에서도 전반적인 성능이 향상되었습니다.
• 단점
  • 짧은 프로세스들이 계속 있다면 긴 프로세스들의 starvation 이 발생할 수 있습니다.
  • 각 프로세스들의 서비스 시간을 알아야만 실행할 수 있어서 구현이 어렵습니다.

 

뿌끄럽습니다

 

 

Round-Robin = Time Slicing

인터럽트가 발생하면 실행중인 프로세스는 Ready queue에 배치되고 다음 프로세스가 FCFS 기준으로 선택됩니다.

Timer 기반으로 time quantum (=time slice)를 사용하는데 이 때 이 길이를 정하는 것이 제일 중요합니다.

why?

이 길이가 매우 짧으면 SPN과 비슷해지고, 매우 길면 FCFS와 비슷해지기 때문입니다.

 

• Selection Function :constant
• Decision Mode: preemption 선점
• 장점
  • FCFS 에서의 short job 패널티를 줄일 수 있습니다. 
• 단점
  • time slice가 너무 짧을 때 context switch의 오버헤드가 많이 일어날 수 있습니다.

 

 

 

Shortest-Remaining-Time (SRT)

remaining time이 가장 짧은 프로세스를 선택합니다.

• Selection Function : min[s-e]
  • 서비스 시간에서 현재까지 실행된 시간을 뺀 값 중 제일 작은 값을 선택합니다.
• Decision Mode: preemption 선점
• 장점
  • SPN보다 turnaround time 성능이 향상되었습니다.
• 단점
  • overhead가 클 수 있습니다.
  • Why? switching이 일어날 때마다 remaining time을 계산해야 하기 때문입니다.
  • 계속 shorterm process가 들어올 때 여전히 starvation이 발생할 수 있습니다.

 

 

Highest-Response-Ratio-Next (HRRN)

응답 비율이 가장 큰 프로세스를 선택합니다.

• Response ratio: 정규화된 turnaround time 
• R = (q + s) / s

 

• Selection Function : max[(q + s) / s]
• Decision Mode: non-preemption 비선점
• 장점
  • starvation을 없앨 수 있습니다.
  • why? 긴 프로세스들이 오래 있을 수록 짧은 프로세스와 경쟁하기 때문입니다.
• 단점
  • 마찬가지로 서비스 시간을 예상해야합니다.