cpu 스케줄러

[youngreal]

1. 스케줄링 이라는건 무엇이고 목적이 무엇일까요?

2. 선점 스케줄링, 비선점 스케줄링이 무엇인가요?

3. 책의 4장에서 라운드로빈 스케줄링이 언급됐습니다. 라운드로빈 스케줄링 알고리즘은 어떤메커니즘인가요?

[Jaeeun1083]

작업 스케줄링은 준비 대기열로 가져와야 하는 프로세스를 선택하는 메커니즘 CPU 스케줄링은 다음에 실행할 프로세스를 선택하고 해당 프로세스에 CPU를 할당하는 메커니즘

CPU 스케줄링이란?

• 다중 프로그래밍의 목적은 CPU 이용률을 최대화하는 것이다. 가능한 CPU가 항상 실행 중인 프로세스를 가지게 한다.
• 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할 것인가 정하는 것을 뜻한다.
• 운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치라고 한다.

CPU 스케줄링 평가 항목

• CPU 이용률 : CPU를 얼마나 사용하고 있는가
• 처리량 : 단위 시간 당 완료된 프로세스의 개수
• 총 처리 시간 : 프로세스의 제출 시간과 완료 시간의 간격 (ready queue에서의 프로세스의 대기 시간 + CPU 실행 시간 + I/O 시간)
• 대기 시간 : (ready queue에서의) 프로세스의 대기 시간
• 응답 시간 : 요구한 후, 첫 응답이 나올 때 까지의 시간

CPU 이용률, 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

CPU 스케줄링의 종류

• 비선점 스케줄링
  • 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할수 없는 스케줄링 기법이다.
  • 종류 : FCFS, SJF, 우선순위, HRN, 기한부 ...
• 선점 스케줄링
  • 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.
  • 선점으로 인한 오버헤드가 발생할 수 있다.
  • 종류 : SRT, 선점 우선순위, RR, 다단계 큐, 다단계 피드백 큐 ...

CPU 스케줄링 알고리즘

• FCFS (First Come First Served)

  • 먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.
  • Queue의 FIFO와 동일하다.
  • 수행 시간이 큰 프로세스가 먼저 들어올 경우 그 뒤의 다른 프로세스들이 하나의 긴 CPU 실행 시간을 갖는 프로세스를 기다리는 상황(콘보이 효과)이 발생한다.
  • 먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

• SJF (Shortest Job First)

  • 프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
  • 수행 시간을 정확히 알 수 없다. 앞서 처리한 프로세스들의 기록을 보고 추측한다.
  • 수행 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
    • 이 문제점은 프로세스가 순서를 양보할 때마다 카운트하여 양보의 한계점까지만 양보하게 하는 에이징 기법으로 해결 가능하다.
  • SJF는 비선점형 방식(SRF())과 선점형 방식(SRTF(Shortest Remaining Time First))으로 구현될 수 있다.

• SRTF (Shortest Remaining Time First)

  • SJF의 선점형 방식이다.
  • 프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
  • 수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

• 우선순위 (priority scheduling)

  • 준비 큐에서 기다리는 프로세스 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당한다.
  • 우선순위 값이 작을 수록 높은 우선순위를 가지는 것으로 가정한다.
  • 우선순위 결정 방식은 여러가지가 있을 수 있다.
    • CPU 버스트 시간을 우선순위 값으로 정의하면 우선 순위 스케줄링은 SJF 알고리즘과 동일한 의미를 가지게 된다.
    • 시스템 관련 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여할 수도 있다.
  • 우선순위 스케줄링은 비선점형 방식과 선점형 방식으로 구현할 수 있다.
  • 수행 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
    • 이 문제점은 프로세스가 순서를 양보할 때마다 카운트하여 양보의 한계점까지만 양보하게 하는 에이징 기법으로 해결 가능하다.

• RR (Round Robin)

  • 일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
  • 시스템의 time-sharing과 같은 방식이다. (앞선 스케줄링 방식과 달리 시분할 시스템의 성질을 가장 잘 활용한다.)
  • 주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
  • 시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

• 멀티레벨 큐

  • 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법이다.
  • 일반적으로 성격이 다른 프로세스들을 별도로 관리하고 프로세스 성격에 맞는 스케줄링 적용을 위해 준비 큐를 별도로 둔다.
    • 예를 들어 빠른 응답을 필요로 하는 대화형 작업과 그렇지 않은 작업을 별도의 큐에 세우고 대화형 작업이 기다리고 있다면 이들에게 우선적으로 CPU를 할당한다.
  • 일반적으로 멀티레벨 큐에서는 대화형 작업을 담기위한 준비 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운영한다.
    • 전위큐에서는 응답시간을 짧게 하기 위해 라운드로빈 스케줄링을 사용하는 반면 계산 위주의 작업을 위한 후위큐에서는 응답 시간이 큰 의미를 가지지 않으므로 FCFS 스케줄링 기법을 사용해 문맥 교환 오버헤드를 줄인다.
  • 멀티레벨 큐에서는 여러개 준비 큐에 대해 어느 큐에 CPU를 먼저 할당할지 결정하는 큐 자체에 대한 스케줄링이 필요하다.

• 멀티레벨 피드백 큐

  • 멀티레벨 큐에 프로세스가 하나의 큐에서 다른 큐로 이동이 가능한 방식이다.
  • 우선순위 스케줄링에서 에이징 기법을 멀티레벨 큐 방식으로 구현할 수 있다.
    • 우선순위가 낮은 큐에서 오래 기다리면 우선순위가 높은 큐로 이동시키는 방식

[this-is-spear]

스케줄링 이라는건 무엇이고 목적이 무엇일까요?

여러 개가 동시에 실행되는 특성상 순서를 정해줄 필요가 있습니다. 순서를 대기하는 곳을 큐(Queue)라 하고, 순서를 정해주는 알고리즘을 스케줄링(Scheduling) 이라 합니다. 큐에 따른 스케줄링 종류에는 Job Queue - Job Scheduler, Ready Queue - CPU Scheduler, Device Queue - Device Scheduler가 있습니다.

선점 스케줄링, 비선점 스케줄링이 무엇인가요?

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며 강제로 프로세스를 중지하지 않습니다. 따라서 컨텍스트 스위칭으로 인한 부하가 적습니다. 비선점형 방식에는 FCFS, SJF, 우선순위 등이 있습니다.

선점형 방식은 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말합니다. 선점형 방식에는 RR, SRF, 다단계 큐 등이 있습니다.

책의 4장에서 라운드로빈 스케줄링이 언급됐습니다. 라운드로빈 스케줄링 알고리즘은 어떤메커니즘인가요?

라운드로빈(RR)은 현대 컴퓨터가 사용하는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘입니다. 할당시간이 너무 크면 FCFS가 되고 너무 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드가 많아집니다. 일반적으로 전체 작업 시간이 길어지지만 평균 응답 시간은 짧아진다는 특징이 있습니다. 그리고 라운드 로빈 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로 사용된다고 합니다.

[lee-ji-hoon]

스케줄링

자원을 효율적으로 사용하기 위해 자원을 사용한느 순서를 결정짓는 작업이다!

스케줄링 비교 척도

• CPU 이용률: 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율을 말합니다.
• 응답 시간: 첫 응답이 오기까지 걸린 시간입니다.
• 대기 시간: 프로세스가 준비상태 큐에서 대기하는 시간입니다.
• 반환 시간: 프로세스가 시작해서 끝날 때까지 걸린 시간입니다.
• 처리량: CPU가 단위 시간당 처리하는 프로세스의 개수입니다.

선점, 비선점 스케줄링

비선점 스케줄링

어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실해도록 보장한다.

• 순서대로 처리되는 공정성이 있고, 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있다.
• 모든 프로세스에 요구에 대해 공정하다.

선점 스케줄링

한 프로세스가 cpu를 할당받아서 실행하고 있을 때 다른 프로세스가 cpu를 사용하고 있는 프로세스를 중지시키고 cpu를 차지할 수 있는 스케줄링 기법을 선점 스케줄링 기법이다.

• 우선순위가 높은 프로세스를 먼저 수행할 때 유리하고 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용하다.
• 많은 오버헤드가 초래한다. (계속 바뀌기 때문)

라운드로빈 스케줄링

Time Sharing System 에서는 주기적으로 Context Switching을 진행한다.
Running 상태의 프로세스가 I/O 작업을 수행하지 않더라도 일정시간이 되면 Ready 상태로 만든다. 이때 사용하는 스케줄링 방법이 라운드로빈 스케줄링이다. -> 말 그대로 뺑뺑 돌면서 프로세싱을 수행하게 된다.

Time Slice(Time Quantum)

라운드로빈은 위에 적은거처럼 일정시간마다 프로세스가 강제로 교체된다. 이 때 사용되는 일정시간이 바로 Time Slice이다.

• 다른 말로 Time Quantum 이라고도 한다.
• 라운드로빈의 ATT은 Time Slice에 매우 큰 영향을 받게 된다.

Time Slice를 무한대로 선정할 경우 FCFS 스케줄링과 동일해지게 됩니다.
그 이유는 해당 프로세스가 끝나야만 다음 프로세스로 전환되기 때문입니다. 반대로 0인 경우 Sharing된 상태입니다. 프로세스3개가 존재하면 그 3개가 동시에 수행되게 되는데, 이럴경우 Context Switching의 Overhead가 너무 커지게 됩니다.

[this-is-spear]

장기, 중기, 단기 스케줄러

각 스케줄러로 확인하는 전페 프로세스 진행 과정