CS/OS

[OS] Scheduling #1

Henu 2021. 7. 9. 19:45

Scheduling

 

 

지금까지 프로세스와 스레드에 대해 알아보았다.

 

오늘 내일은 프로세스의 CPU Scheduling에 대해서 알아보자

 

 

CPU Scheduling은 크게 2가지로 나뉜다

비선점형 스케줄링(Non-preemptive scheduling)선점형 스케줄링(Preemptive scheduling)

 

비선점형 스케줄링

 - CPU가 프로세스를 실행하고 있다면 실행중인 프로세스가 종료되거나 스스로 CPU를 양보하기 전까지 다른 프로세스는 CPU는 사용할 수 없다.

 - 프로세스들 간의 협력이 중요하다.

 

선점형 스케줄링

 - 사실상 모든 현대 스케줄러가 선점형이다

 - 다른 프로세스가 CPU를 사용하고 있어도 강제로 프로세스를 쫓아내고 자신이 CPU를 사용할 수 있다.

 

 

스케줄링 알고리즘의 성능을 판단하는 척도

  • Turnaround time : 프로세스가 준비상태로 들어간 이후부터 작업이 완료되어 나오기까지 걸리는 시간(짧을수록 좋다)
  • Response time : 프로세스가 준비상태로 들어간 이후부터 작업을 시작하기까지 걸리는 시간(컴퓨터가 반응하는 시간)

 

 

CPU 스케줄링 알고리즘

  • First In, First Out (FIFO) : 우리가 알고있는 Queue의 작동방식과 동일하다.
    • 먼저 도착한 프로세스가 CPU를 먼저 사용한다.
    • 가장 먼저 도착한 프로세스의 작업시간이 길어질 수록 뒤에 도착한 프로세스가 작업을 완료하기까지의 시간이 매우 오래 걸린다. 다른 프로세스의 Turnaround time이 매우 길어지게 된다.
    • 위와 같은 현상을 Convoy Effect라고 한다.

 

  • Shortest Job First (SJF) | Shortest-Remaining-Time-First
    • 작업시간이 짧은 프로세스먼저 처리하는 방식이다.
    • 여기서 선점형 방식과 비선점형 방식을 나눌 수 있다.
      • 선점형 방식 
        1. A라는 작업이 100시간이 걸리는데 현재 10시간을 해서 90시간이 남은 상태라고 하자
        2. B라는 작업은 15시간이 걸리고 지금 준비상태에 들어와있다.
        3. 이때 A의 남은시간(90시간)보다 B의 남은시간(15시간)이 더 짧으므로 A를 중단하고 B를 먼저 실행한다.
      • 비선점형 방식
        1. 동시에 들어온 경우가 아니라면 FIFO와 동일하다.
  • Round Robin (RR) Scheduling
    • 임의의 time slice만큼 프로세스를 수행하고, 다음 프로세스로 CPU권한을 넘겨주는 방식이다.
    • time slice가 10ms이고 A, B, C 프로세스가 대기중이라면 10ms간격으로 프로세스를 실행하게 된다.
    • 선점형 방식이고 공정하다. -> CPU를 받지 못하는 프로세스가 없다.(No starvation)
    • 단점 : 빨리 끝날 수 있는 프로세스도 RR방식으로 time slice만큼만 실행이 반복된다면 turnaround time이 증가하는 경향이 있다.
    • 장점 : 모든 프로세스의 response time이 매우 빨라질 수 있다.
    • 주의사항 : time slice의 길이가 매우 중요함을 알 수 있다.
      • 짧은 time slice : 더 좋은 response time | context switching overhead가 퍼포먼스에 큰 영향을 끼침
      • 긴 time slice : 좋지 못한 response time | context switching 비용의 감소