CPU 스케줄링

CPU 스케줄링

• 작업 처리를 위해 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 것

• CPU 스케줄링은 모든 프로세스가 공평하게 작업할 수 있도록 하는 것임, 여기서 어느정도의 안정성과 효율성을 높이기 위해 공평성의 일부분을 희생해야함

• 여기서 몇 가지 기준이 존재함

  • CPU Utilization : CPU가 쉬고 있지 않게 해야함

  • Throughput : 단위 시간 당 처리량

  • Turnaround Time : 수행을 요청한 후 작업이 끝날 때까지 걸린 시간

  • Waiting Time : 수행을 요청한 후 작업이 시작될 때까지 걸린 시간(Running이 되고, Ready Queue에 들어간 시간)

  • Response Time : 요청한 후 응답이 올 때까지 걸린 시간

• 여기서 CPU Utilization, Throughput은 늘리고, Time 지표들은 감소하는 것이 스케줄링의 목표임

단계

• 큰 틀에서 단계 과정을 보면 고수준 -> 중간 수준 -> 저수준으로 진행한다고 볼 수 있음

• 고수준 스케줄링은 long-term, job, admissin 스케줄링이라고도 하는데 큰 틀에서 이루어지는 CPU 스케줄링으로 시스템 내의 전체 작업 수를 조절함, 시스템 내에서 동작 시에 실행 가능한 프로세스의 총개수가 정해짐

• 중간 수준 스케줄링은 중지(suspend), 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절함, 이로 인해 저수준 스케줄링이 원만하게 이루어지도록 완충 역할을 함

• 저수준 스케줄링은 short-term으로도 보는데, 이는 가장 작은 단위의 스케줄링으로 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정함, 스케줄링에 대해 공부하는 대부분은 이 저수준 스케줄링에 해당함

스케줄링 시 고려사항

• 먼저 선점과 비선점으로 나눌 수 있음

• 선점형 스케줄링(preemptive)

  • 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식

  • CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능함

  • 하지만 잦은 교환으로 오버헤드가 많이 발생함

• 비선점형 스케줄링(non-preemptive)

  • 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식

  • 필요한 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만, 프로세스의 배치에 따라 효율성 차이가 많이 남

• 프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하면 CPU burst, 입출력 작업을 하면 I/O burst라고 함

  • CPU bound process : CPU를 많이 사용하여 CPU burst가 많은 프로세스

  • I/O bound process : 입출력을 많이 사용해 I/O burst가 많은 프로세스

• 두 프로세스가 같이 대기상태에 있다면 I/O bound process를 먼저 CPU에 할당시키는게 효율적임, I/O는 CPU를 빠르게 쓰고 입출력 burst를 하러 나가기 때문에 다른 프로세스가 오래 기다리지 않아도 됨

• 전면 프로세스와 후면 프로세스도 고려해야함

  • 전면 프로세스 : GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓여 현재 입출력이 사용되고, 사용자와 상호작용이 가능해 상호작용 프로세스라고 불림

  • 후면 프로세스 : 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고 불림

• 전면 프로세스는 사용자의 요구에 즉각 즉각 반응해야 하지만, 후면 프로세스는 그럴 필요가 없음, 그래서 전면 프로세스를 먼저 처리해줘야함

• CPU 스케줄러 대부분은 프로세스에 우선순위를 매겨 우선순위가 높은 프로세스부터 처리함

스케줄링 알고리즘

FCFS(First Come First Served)

• 선입선출 방식으로, 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식임

• 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법임

• 하지만 CPU 처리 시간이 긴 프로세스가 앞에 올 경우 뒤의 프로세스가 한없이 기다려야 하기 때문에 비효율적이게 됨(Convoy Effect)

SJF(Shortest Job First)

• 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식임

• 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있음, 그래서 FCFS를 개선한 방식으로도 볼 수 있고 Convoy Effect를 완화할 수 있음

• 하지만 비선점형 방식이기 때문에 CPU를 사용중인 프로세스보다 처리 시간이 짧더라도 빼앗기지 못함

• FCFS보다 효율성은 높지만, 그에 따른 단점도 존재함, 공평성이 어긋나는 것인데 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어온다면 대기 큐에서 영영 CPU를 할당받지 못할 수 있음(Starvation 현상)

HRN(Highest Response Ratio Next)

• SJF 스케줄링에 Aging 기법을 합친 비선점형 방식임

• Aging 기법은 Starvation 현상을 해결하기 위해 대기 시간이 길어지면 우선순위를 높이는 방식임

• SJF와 마찬가지로 실행 시간이 적은 프로세스의 우선순위가 높지만 대기 시간이 너무 길어지면 실행 시간이 길더라도 CPU를 할당받을 수 있음(그렇다고 해도 여전히 공평성이 말끔히 해결되지는 않음)

• 우선순위 = (대기시간 + 실행시간) / (실행시간)

SRTF(Shortest Remaning Time First)

• SJF의 선점형 방식임, 먼저 온 프로세스가 CPU를 할당받고 있더라도 남은 처리 시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗김

• 어떤 알고리즘보다 평균 대기 시간이 가장 짧은 알고리즘임

• 하지만 이 방식은 기본적으로 선점형 방식이어서 그만큼 잦은 교환이 일어나 오버헤드가 커짐, 그리고 Starvation 현상이 더 심각하게 발생할 수 있음

• 그리고 CPU 예상 시간을 예측하기도 힘들어서 실제 사용도 힘듬

Priority Scheduling

• 프로세스의 중요도에 따라 매긴 우선순위를 반영한 알고리즘임, 선점형,비선점형 모두 접목이 가능함

• 하지만 이 알고리즘 역시 Starvation 문제와 공평성 문제가 있음

RR(Round Robin)

• 프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 함

• 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘김, 빼앗긴 프로세스는 준비 큐의 맨 뒤로 감, 그러므로 선점형 방식임

• CPU 처리 시간을 계산하지 않아도 돼서 선점형 방식의 가장 단순하고 대표적인 방법임, 우선 순위도 없어서 매우 공평함

• 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있음

• Round Robin에서 가장 중요한 부분은 타임 슬라이스의 크기 결정임

• 타임 슬라이스가 큰 경우 처리 시간이 긴 프로세스에 의해 CPU의 효율성이 떨어질 수 있음, 이게 만약 무한대로 설정되면 FCFS 스케줄링과 다를 바 없음

• 타임 슬라이스가 작은 경우 여러 프로그램이 동시에 실행되는 효과를 볼 수 있음, 하지만 너무 작으면 잦은 교환으로 오버헤드가 커짐

• 적당한 타임 슬라이스 설정이 중요함

Multilevel Queue

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식임

• 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행될 수 있음

• 한 번 우선순위가 매겨저 준비 큐에 들어가면 이 우선순위는 바뀌지 않음

• 각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있는데, 보통 전면 프로세스들이 속해있는 큐는 우선순위가 높고 Round Robin 스케줄링을 사용해 타임 슬라이스를 작게함

• 후면 프로세스에는 사용자와의 상호작용이 없으므로 가장 간단한 FCFS 방식으로 처리함

• 이 역시 Starvation, 공평성 문제가 존재함

Multilevel Feedback Queue

• 다단계 큐의 공평성 문제를 완화하기 위해 신분 하락이 가능한 알고리즘임, 이 알고리즘에선 우선순위가 변동되기 때문에 큐 사이의 이동이 가능함

• 한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아짐, 따라서 더 낮은 큐로 이동하게 됨(우선순위가 높아져 상위 큐로 이동할 수도 있음)

• 더 보완을 위해서 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 줌, 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함