초이의 끄적끄적

Q. CPU 스케줄링이란 무엇이고 왜 필요한가?

• 프로세스가 최고의 성능을 내기 위해 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것을 CPU 스케줄링이라고 합니다. 프로세스들이 CPU를 효율적으로 사용하기 위해 필요합니다.
• 선점 스케줄링과 비선점 스케줄링이 있습니다.

Q. 선점형 스케줄링은 무엇이고 알고리즘은 무엇이 있나요?

• 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식으로 CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능합니다. 하지만 잦은 문맥 교환으로 오버헤드가 많이 발생합니다.
• 선점형 알고리즘으로는 SRT, 라운드로빈, 다단계큐, 다단계 피드백 큐 스케줄링이 존재합니다.
  1. SRT(Shortest Remaining Time) 스케줄링 : 짧은 시간 순서대로 프로세스를 수행합니다. 남은 처리 시간이 더 짧은 프로세스가 준비 큐에 들어오면 그 프로세스가 바로 선점됩니다. SJF의 선점 버전이라고 할 수 있습니다.
  2. 라운드로빈(Round-Robin, RR) 스케줄링 : 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당시간이 너무 크면 선입선출과 다를 바가 없어지고, 너무 작으면 문맥교환이 잦아져 오버헤드가 증가합니다.
  3. 다단계 큐(Muti-level Queue) 스케줄링 : 우선순위에 따라 준비큐를 여러 개 사용하는 방법으로 각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여합니다.
  4. 다단계 피드백 큐 스케줄링 : 다단계 큐와 비슷하나 프로세스들이 큐를 이동할 수 있습니다.

Q. 비선점형 스케줄링은 무엇이고 알고리즘은 무엇이 있나요?

• 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식으로 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 납니다.
• 비선점형 알고리즘으로는 FIFO, SJF, HRN, 우선순위 스케줄링이 존재합니다.
  1. FIFO=FCFS(First Come First Served) 스케줄링 : 선입선출 방식으로, 준비 큐에 도착한 순서대로 CPU를 할당합니다. 작업 완료 시간을 예측하기는 용이하나 덜 중요한 작업이 중요한 작업을 기다리게 할 수 있습니다.
  2. SJF(Shortest Job First) 스케줄링 : 준비 큐에 있는 프로세스 중 실행시간이 가장 짧은 작업부터 CPU를 할당합니다. 평균 대기 시간을 감소시킵니다.
  3. HRN(Hightest response ratio next) 스케줄링 : SJF + Aging을 합친 알고리즘으로, 실행시간과 대기 시간을 모두 고려해 우선순위를 정합니다.
  4. 우선순위(priority) 스케줄링 : 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리합니다. SJF, HRN, SRTF도 우선순위 스케줄링 알고리즘의 일종입니다.

Q. 비선점형 SJF와 선점형 SRT 비교하시오

• 비선점 스케줄링 SJF 기법을 선점 형태로 변경한 기법이 SRT이다.
• SJF는 실행시간이 가장 짧은 프로세스
• SRT는 현재 실행중인 프로세스의 남아 있는 실행 시간과 새로운 프로세스의 실행 시간을 비교하여 짧은 것

ex) 아래와 같은 세가지 작업이 있다고 가정한다.

비선점형 SJF(Shortest Job First)의 경우

선점형 SRT(Shortest Remaining Time)의 경우

참고자료 : CPU스케줄링, [IT 기술면접 준비자료] CPU 스케줄링 기법, 선점, 비선점 스케줄링