[CS] CPU 스케줄링 알고리즘

SJF를 Preemptive한 방식으로 구현하기 위해서는 ready queue에 새로운 프로세스가 도착할 때마다 CPU에게 interrupt를 걸어야하나? 어떻게 새로운 프로세스가 도착했음을 알고, 그것이 더 짧은 프로세스임을 알고, CPU 제어권을 넘기는가?

• Shortest Job First를 선점형으로 구현하려면 도착한 프로세스의 시간과 현재 진행중인 프로세스의 남은 시간을 비교, 도착한 게 더 짧다면 인터럽트를 걸고 처리한 후 진행하던 작업으로 돌아간다. 스케줄링은 도착할때마다 일어난다.
• 더 짧은 프로세스인지 정확하게 아는 건 사실 힘들다 . - 그래서 실제로는 잘 쓰지 않는다. 굳이 알고싶다면 예측기법을 활용한다. ex) Exponential average
• 비교가 끝났다면 CPU 제어권은 디스패쳐에서 관리한다. 새로운 프로세스가 더 짧다면 CPU를 할당받고 작업을 수행할 수 있도록 한다. 이때 진행중이던 프로세스를 정지시키고 새로운 프로세스에게 CPU를 주기까지 걸리는 시간을 디스패처 지연시간이라고 한다.

 

타임 슬라이스방식에서 각 queue에 CPU time을 비율로 할당한다는 것의 의미는 무엇인가? 어떤 것에 대한 비율인가?

• CPU에 도착하는 도착율(arrival rate)과 CPU가 처리를 끝낸 처리율(service rate)의 정보가 확률분포로 주어질 때, 여러 성능척도 결과를 계산
• 고정 우선순위 스케줄링 방식에서 기아 상태가 발생할 수 있기 때문에 이를 해결하고자 생긴 스케줄링 방식이다. 운영체제가 Time Slice를 두고, 이 시간 비율에 따라 각각의 Queue를 서비스하게 된다. Queue마다 프로세스를 CPU에 할당할 수 있는 시간 비율이 다르다.
• 예를 들어, CPU 자원의 75%는 Foreground Queue, 25%는 Background Queue를 서비스하는 데 할당할 수 있다.

 

별개의 Queue를 두는 방식이 왜 load sharing과 관련이 있는가?

• cpu가 여러개가 있는 경우
  • 하나에 몰리지 않도록 적절히 배치해야하는데, 이때 한줄이 아니라 각각 별개의 queue를 두도록 하여 분배할 수있다.