Scheduler / Scheduling

• 스케줄러
  • 프로세스를 스케줄링하기 위한 Queue에 프로세스를 넣고 빼주는 역할
  • Queue
    • Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
    • Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
    • Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합
  • 장기 스케줄러 (Job Scheduler)
    • 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로는 Disk)에 임시지로 저장된다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready Queue로 보낼지 결정하는 역할을 한다.
      • Memory <-> Disk 스케줄링 담당
      • 프로세스에 메모리를 할당
      • degree of multiprogramming 제어 (실행 중인 프로세스 수 제어)
      • 프로세스의 상태를 new -> ready
  • 단기 스케줄러 (CPU scheduler)
    • CPU <-> Memory 스케줄링 담당
    • Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬 지 결정
    • 프로세스에 CPU할당 (scheduler dispatch)
    • 프로세스의 상태를 ready -> running -> waiting -> ready
    • FCFS(First Come First Served)
      • 먼저 온 프로세스를 Running
      • 비선점형 스케줄링
        • 일단 CPU를 잡으면 CPU Burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
      • convoy effect
        • 소요시간이 긴 프로세스가 먼저 올 경우 효율성이 낮아진다.
    • SJF(Shortest Job First)
      • 다른 프로세스가 먼저 도착했어도 CPU burst Time이 짧은 프로세스에게 먼저 할당
      • 비선점형 스케줄링
      • Starvation
        • 짧은 Job만을 선호하기 때문에 사용기간이 긴 프로세스는 영원히 할당받을 수 없다.
    • SRTF(Shortest Remaing Time First)
      • 새로운 프로세스가 도착할 때마다 다시 스케줄링한다.
      • 선점형 스케줄링
        • 현재 수행중인 프로세스의 남은 burst time보다 짧은 시간을 가지는 프로세스가 도착하면 CPU를 빼앗긴다.
      • starvation
      • 새로운 프로세스가 도착할 때마다 다시 스케줄링하기 떄문에 CPU사용시간을 측정하기 어렵다.
    • Priority Scheduling
      • 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링. 우선순위는 정수. 작은 숫자가 우선.
      • 선점형 스케줄링
        • 더 높은 우선순위가 들어오면 CPU를 뺏긴다.
      • 비선점형 스케줄링
        • 더 높은 우선순위가 들어오면 Ready Queue의 Head에 넣는다.
      • starvation
      • 무기한 봉쇄 : 실행 준비는 되어있으나 CPU를 사용못하는 프로세스를 CPU가 무기한 대기하는 상태
      • aging : 우선순위가 낮더라도(높은 숫자) 오래 기다릴 경우 우선순위를 높여 해결한다.
    • RR(Round Robin)
      • 현대적임
      • 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가진다.
      • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 맨 뒤로 간다.
      • CPU 사용시간이 랜덤한 프로세스들이 많을수록 효율적
      • 프로세스의 context를 save할 수 있어서 가능하다.
      • Respon Time이 빨라진다. 
        • 어떠한 프로세스도 time quantum * (n-1) 이상으로 기다리지 않는다.
      • 공정하다
      • FCFS와 다른점?
        • time quantum이 길어질수록 유사해짐.
        • 너무 작아지면 context swtich로 인한 overhead가 발생한다.
        • 적당한 time quantum이 필요함
  • 중기 스케줄러(Swapper)
    • 여유공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄(Swapping)
    • 프로세스에게서 memory deallocate
    • degree of multiprogramming 제어
    • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
    • 프로세스의 상태를 ready -> suspended(stopped)
      • Suspended : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미.
      • 프로세스 전체가 디스크로 swap out 된다.
      • blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state로 돌아갈 수 있지만, Suspended는 스스로 돌아갈 수 없다.