운영체제 - CPU 스케줄링

기아 상태

• 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태이다.
• SJF, SRT, 우선순위 스케줄링, SPN, feed back 등의 스케줄링 방법에서 발생 가능하다.

기아 상태 해결 방법

에이징(Aging)

• 프로세스가 대기 큐에서 기다릴수록 우선순위를 증가시켜주는 방식이다. 이렇게 하면 오랫동안 기다린 프로세스가 결국에는 CPU를 할당받을 수 있다.
• 우선순위 기반의 스케줄링 알고리즘에서 주로 사용된다.

피드백(Feedback)

• 프로세스가 CPU를 사용할수록 우선순위를 감소시켜주는 방식입니다. 이렇게 하면 자주 CPU를 사용하는 프로세스가 낮은 우선순위로 밀려나게 되고, 오랫동안 기다린 프로세스가 높은 우선순위로 올라가게 된다.
• 다단계 큐(Multilevel Queue)나 다단계 피드백 큐(Multilevel Feedback Queue)와 같은 스케줄링 알고리즘에서 주로 사용된다.

페어 스케줄링(Fair Scheduling)

• 모든 프로세스에게 동일한 비율의 CPU 시간을 할당해주는 방식이다.
• 예를 들어, 10개의 프로세스가 있다면 각각 10%의 CPU 시간을 받게 된다. 이렇게 하면 어떤 프로세스도 기아 상태에 빠지지 않는다.

CPU 스케줄링

• CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이다.
• 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다.

스케줄러의 종류

Long-term scheduler (Job scheduler)

• 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정한다. 프로세스에 메모리를 주는 문제와 관련되어 있으며 time sharing system에는 보통 이 장기 스케줄러를 두지 않고 새로 생성되는 프로세스를 무조건 ready queue에 넣는다.

Short-term scheduler (CPU scheduler)

• CPU 스케줄링 알고리즘에 따라 어떤 프로세스를 다음에 실행시킬지 결정한다. 프로세스에 CPU를 할당하는 문제와 연관되어 있으며 충분히 빠르게 동작해야 한다.

Medium-term scheduler (Swapper)

• 여유 공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다. 프로세스에게서 메모리를 빼앗는 것과 관련되어 있다.

선점형 스케줄링과 비전형 스케줄링의 차이

비선점 스케줄링

• 프로세스가 자발적으로 CPU를 반납하는 것을 비선점이라고 부른다. 프로세스가 종료(terminate)하거나 I/O 요청하는 시스템 콜을 보내 프로세스가 대기 상태(blocked)로 전환하는 경우가 이에 해당된다.

선점 스케줄링

• 선점은 OS가 CPU 사용권을 강제로 회수하여 우선 순위가 높은 프로세스에게 넘기는 것이다.
• 우선 순위가 높은 프로세스를 빠르게 처리해야 할 경우 유용하며, 높은 우선 순위를 가진 프로세스들만 들어오는 경우에는 오버헤드가 발생한다.
• I/O 작업 완료 후에 인터럽트가 발생하거나 할당시간이 만료되어 timer interrupt가 발생하는 등의 경우에 선점 스케줄링이 일어날 수 있다.

선입선출 스케줄링(FCFS)

• First Come First Service
• 먼저 도착한 프로세스에게 우선순위를 부여한다.
• 도착한 프로세스의 CPU 이용 시간에 따라 Waiting time과 Average waiting time에 편차가 크다.

장점

• 구현이 쉽다.
• 선착순으로 처리하기 때문에 프로세스를 공평하게 처리할 수 있다.

단점

• 짧은 작업이 긴 작업보다 늦게 도착하면 긴 작업을 기다려야 하므로 평균 대기 시간이 증가할 수 있습니다. 이를 호위 효과(convoy effect)라고 한다.
• FCFS 스케줄링은 비선점형(nonpreemptive) 방식이므로 한 프로세스가 CPU를 점유하고 있으면 다른 프로세스는 CPU를 빼앗을 수 없다. 이는 CPU 사용률을 낮추고 I/O 바운드 프로세스의 대기 시간을 증가시킬 수 있다.

최단 작업 우선 스케줄링(SJF)

• Shortest Job First
• 선점 스케줄링에서는 현재 수행 중인 프로세스의 남은 시간보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 기존에 CPU를 사용하던 프로세스는 CPU를 빼앗긴다.
• 실행 시간을 미리 알아야 하기 때문에 실제 시스템에서 구현하기 어렵다.
• 선점형 SJF 와 비선점형 SJF가 존재한다.

특징

• 실행 시간을 미리 알아야 하기 때문에 실제 시스템에서 구현하기 어렵다.

단점

• 선점형 SJF에서 기아 현상이 생길 수 있다.
• 실행 시간이 짧은 프로세스들이 새롭게 준비큐에 연속적으로 들어온다면 실행시간이 비교적 긴 프로세스는 영원히 CPU를 할당받지 못할 수 있다.

최소 잔류 시간 우선 스케줄링(SRTF) 방식에 대해 설명해주세요.

• Shortest Remaining Time First
• 최소 잔류 시간 우선 스케줄링(SRTF) 방식은 프로세스의 남은 실행 시간이 가장 짧은 것부터 우선적으로 처리하는 CPU 스케줄링 알고리즘이다.
• 선점형 스케줄링이므로, 새로운 프로세스가 도착하거나 기존의 프로세스가 종료될 때마다 CPU를 재할당한다.

장점

• SRTF 방식은 평균 대기 시간과 평균 응답 시간을 최소화할 수 있으므로, 시스템의 처리량을 높이고 사용자의 만족도를 향상시킬 수 있다.

단점

• 실행 시간이 긴 프로세스는 계속해서 선점당할 수 있어서 기아 현상이 일어날 수 있다.

우선순위 스케줄링

• 우선순위 스케줄링이란 프로세스나 작업에 우선순위를 부여하여 실행 순서를 결정하는 스케줄링 방식이다.
• 우선순위 스케줄링에는 선점/비선점 방식과 정적/동적 방식의 스케줄링이 있다.

정적 우선순위 스케줄링

• 정적 우선순위 스케줄링은 프로세스나 작업이 생성될 때 우선순위가 정해지고 변경되지 않는 방식이다.

동적 우선순위 스케줄링

• 동적 우선순위 스케줄링은 프로세스나 작업의 상태에 따라 우선순위가 변화하는 방식이다.

장점

• 중요한 작업을 빠르게 처리할 수 있습니다.

단점

• 낮은 우선순위의 작업이 계속 기다려야 하는 기아 현상이 발생할 수 있습니다.

라운드 로빈 스케줄링

• 라운드 로빈 스케줄링은 시분할 시스템에서 사용되는 선점형 스케줄링 알고리즘 중 하나이다.
• 이 알고리즘은 프로세스들에게 우선순위를 부여하지 않고, 정해진 시간 단위(Time Quantum) 만큼 순서대로 CPU를 할당합니다. 시간 단위는 보통 10ms에서 100ms 사이이다.

장점

• 모든 프로세스가 공정하게 CPU를 사용할 수 있다.
• 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.

단점

• 시간 단위 동안 수행된 프로세스는 준비 큐의 맨 뒤로 이동하고, 다음 프로세스에게 CPU를 넘긴다.
• 문맥 전환(Context Switching)의 오버헤드가 크다.

멀티 레벨 큐 스케줄링

• 운영체제에서 프로세스를 여러 개의 큐로 분류하여 실행하는 방식이다.
• 큐 자체에 대한 알고리즘과 각 큐의 자신만의 알고리즘을 스케줄링 해야한다.
• 큐 자체에 대한 스케줄링으로 가장 쉽게 생각할 수 있는 방식은 고정 우선순위 방식이다.
  • 이 방식에서는 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스한다.
  • 전위 큐가 비어 있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당될 수 있다.
• 타임 슬라이스(time slice) 방식을 사용하면 큐에 대한 기아 현상을 해소할 수 있다.
  • 이때는, 각 큐에 CPU 할당 시간을 다르게 적용할 수 있다.

장점

• 다양한 종류의 프로세스를 효율적으로 관리할 수 있다.
• 예를 들어, CPU 바운드 프로세스와 입출력 바운드 프로세스를 구분하여 실행하면, CPU의 활용도를 높이고, 입출력 장치의 대기 시간을 줄일 수 있습니다.

단점

• 복잡도가 높고, 별도의 메커니즘을 통해 큐 사이의 균형을 유지해야 한다.

멀티 레벨 피드백 큐 스케줄링

• 프로세스를 여러 개의 큐에 나누고, 각 큐는 다른 우선순위와 시간 할당량을 가진다.
• 우선순위가 높은 큐에 있는 프로세스는 먼저 실행되고, 시간 할당량이 초과되면 다음 우선순위의 큐로 이동한다.
  • 이렇게 하면, 프로세스의 응답 시간과 처리량을 균형있게 유지할 수 있다.
• 멀티레벨 큐와 다른 점은 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이다.

장점

• 프로세스의 특성에 따라 적절한 우선순위와 시간 할당량을 부여할 수 있다.
• CPU를 효율적으로 활용할 수 있다.
• 기아 현상을 방지할 수 있다.
  • aging 기법을 통해 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시킬 수 있다.

단점

• 큐의 수와 우선순위를 결정하는 것이 어렵다.
• 오버헤드가 발생할 수 있다.