Scheduling Algorithm

프로세스 스케줄링 알고리즘에는 어떤 것들이 있나요?

preemptive scheduling

• 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식이다.
• 비교적 응답이 빠르다는 장점이 있지만, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세들이 계속 들어오는 경우 오버헤드를 초래한다.
• 실시간 응답 환경, Deadline 응답 환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우 등에 유용하다.

라운드 로빈

• 프로세스마다 같은 크기의 CPU 시간을 할당한다.
• 프로세스가 할당된 시간 내에 처리 완료를 못 하면 준비 큐 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어간다.
• 균등한 CPU 점유 시간을 보장하며, 시분할 시스템을 사용한다.

SRT

• 가장 짧은 시간이 소요되는 프로세스를 먼저 수행한다.
• 남은 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점된다.

Multi Level Queue

• 작업들을 여러 종류의 그룹으로 분할, 여러 개의 큐를 이용하여 상위 단계 작업이 선점한다.
• 각 큐는 자신만의 독자적인 스케줄링을 가진다.

Multi Level Feedback Queue

• 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU 시간 할당량을 부여한다.
• FIFO와 라운드 로빈 기법을 혼합한 것이다.
• 새로운 프로세스는 높은 우선순위릘 가지지만 프로세스의 실행 시간이 길어질수록 점점 낮은 우선순위 큐로 이동하며, 마지막 단계에서 FIFO 방식을 적용한다.
• 유연성이 뛰어나며, 한 번 해당 큐에 들어가면 다른 프로세스는 다른 큐로 이동하지 못하는 다단계 큐의 약점 보완했다.

non-preemptive scheduling

• 한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 PCU 점유가 불가능한 스케줄링 방식이다.
• 따라서 running → ready 의 과정이 없다.
• 모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야 할 수도 있다.

Priority

• 각 프로세스 별로 우선순위가 주어지고, 우선순위에 따라 CPU를 할당한다.
• 우선순위가 같을 경우 FIFO를 사용한다.
• 설정, 자원 상황 등에 따른 우선순위를 선정해 주요, 긴급 프로세스에 대한 우선 처리가 가능하다.

Deadline

• 작업들이 명시된 기간이나 기한 내에 완료되도록 계획한다.

FIFO

• 먼저 대기 큐에 도착한 프로세스부터 CPU 할당한다.

SJF (Shortest Job First)

• 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료될 때까지 자원 선점한다.
• 준비 큐 작업 중 가장 짧은 작업부터 수행하기 때문에 평균 대기 시간이 최소이다.
• CPU 요구 시간이 긴 프로세스는 영영 실행되지 않는 기아 현상 발생 가능성이 있다.

HRN (Highest Response Ratio Next)

• 대기 중인 프로세스 중 현재 Response Ratio가 가장 높은 것을 선택한다.
  • Response Ratio = (대기 시간 + 서비스 시간) / 서비스 시간
• SJF와 Aging 기법을 합쳐 SJF의 약점인 기아 현상을 약간 보완한 기법이다.

RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

라운드 로빈 스케줄링은 정해진 타임 슬라이스의 시간만큼 돌아가며 CPU를 사용하기 때문에 모든 프로세스가 한번씩 CPU를 할당받을 수 있는 선점형 스케줄링이다.

프로세스들의 CPU 이용 시간보다 크게 Time Slice 값을 정한다면, 이는 결국 큐에 먼저 삽입된 순서대로 프로세스를 처리하는 FCFS 스케줄링이랑 비슷하게 동작할 것이다. 이는 선점형 방식인 라운드 로빈의 특성에 위배된다고 할 수 있다.

하지만 Time Slice의 값을 너무 작게 설정한다면, 계속 CPU의 전환이 일어나기 때문에 문맥 교환이 빈번하게 발생해 이에 대한 오버헤드가 커질 수 있다.

싱글 스레드 CPU에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

아주 짧은 Time Slice를 가진 라운드 로빈을 사용하면 동시에 실행하는 것처럼 느낄 수 있다. 상시 실행 중이어야 하는 프로그램이 싱글 스레드 CPU를 독점한다면 다른 프로세스는 영원히 실행될 수 없기 때문에, 동시성이 보장되는 스케줄링 알고리즘을 적용해야 한다.

동시성과 병렬성의 차이에 대해 설명해 주세요.

동시성 (Concurrency)

하나의 시스템이 여러 작업을 동시에 처리하는 것처럼 보이게 하는 것이다. 실질적으로는 한 번에 하나의 작업만 처리하고 있다. 동시성은 대개 스레드, 코루틴, 비동기 프로그래밍 등의 방법을 사용하여 구현된다. 동시성은 여러 작업을 번갈아 가면서 처리하므로 작업이 빠르게 완료될 수 있다. 예를 들어 웹 서버에서 여러 클라이언트 요청을 동시에 처리하면서 각 요청을 번갈아 처리할 수 있다. 이와 비슷한 개념으로는 멀티태스킹이 있다.

멀티태스킹

운영 체제에서 하나의 컴퓨터에서 여러 개의 프로그램이 동시에 실행될 수 있는 기능을 말한다. 멀티태스킹은 일반적으로 CPU 시간을 분할하여 여러 프로그램이 동시에 실행되는 것처럼 보이도록 한다.

동시성 VS 멀티태스킹

• 동시성: 하나의 작업 내에서 여러 개의 서브태스크를 동시에 처리하는 것
• 멀티태스킹: 하나으 시스템에서 여러 개의 작업을 동시에 실행하는 것

병렬성 (Parallelism)

병렬성은 여러 작업을 실제로 동시에 처리하는 것이다. 여러 CPU 또는 코어를 사용하여 여러 작업을 병렬로 처리할 수 있다. 예를 들어, 대용량 데이터 처리나 과학 계산 분야에서 여러 계산 작업을 병렬로 처리할 수 있다.

병렬로 처리할 작업들은 병렬처리기에서 실행되며, 각각의 작업은 별도의 프로세스나 스레드에서 실행된다. 이러한 병렬처리기는 여러 개의 CPU 또는 CPU 코어가 있어서 각각의 작업이 서로 다른 CPU 또는 CPU 코어에서 병렬적으로 실행된다.

병렬성은 멀티코어 컴퓨터에서 많이 사용되며, 실행 시간을 줄이거나 처리량을 늘리려는 데에 사용된다.

타 스케쥴러와 비교하여 Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

MLFQ는 우선 순위가 낮은 프로세스들은 영원히 실행되지 않는 기아 현상 문제를 해결할 수 있습니다. 그 이유는 오래 실행되지 않는 프로세스들의 우선 순위를 높여 주는 boost 기능이 있기 때문이다. 예를 들어 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. 대신에 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다. 이렇게 MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.

만약 같은 큐에 우선 순위가 동일한 작업이 두 개 이상이라면, RR 방식으로 진행된다.

• 규칙 1 : Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행X)
• 규칙 2 : Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.

FIFO 스케줄러는 정말 쓸모가 없는 친구일까요? 어떤 시나리오에 사용하면 좋을까요?

FIFO (First-Come-First-Out) 스케줄러는 가장 간단한 스케줄링 알고리즘 중 하나로, 먼저 도착한 프로세스를 먼저 실행하는 방식이다. 이 스케줄러는 간단하고 공정한 특징을 가지고 있지만, 특정 상황에서는 쓸모가 없거나 비효율적일 수 있다.

FIFO 스케줄러의 특징 및 언제 사용할 수 있는지에 대한 몇가지 고려사항은 다음과 같다.

FIFO 스케줄러의 특징

1. 비선점

   프로세스가 CPU를 할당받으면 완료되거나 이벤트가 발생할 때까지 CPU를 계속 사용한다.

2. 단순하고 공정한 방식

   구현이 간단하며, 도착한 순서대로 프로세스를 처리하여 공정한 특징을 가진다.

3. 반복적인 데드락

   데드락의 발생 가능성이 높아질 수 있다. 특히 선점 없이 계속해서 프로세스를 실행하다 보면 다수의 프로세스가 I/O 이벤트를 기다리는 상황이 발생할 수 있다.

FIFO 사용 시나리오

1. 단순한 환경

   운영체제가 간단한 환경에서 동작할 때 사용할 수 있다.

2. 우선순위가 중요하지 않은 경우

   프로세스의 우선순위가 중요하지 않고 도착한 순서대로 처리해도 문제가 없는 경우에 사용할 수 있다.

3. 프로세스의 실행 시간이 비슷한 경우

   모든 프로세스의 실행 시간이 비슷하고, 도착한 순서대로 처리해도 성능에 큰 영향을 주지 않는 경우에 유용할 수 있다.

우리는 스케줄링 알고리즘을 ‘프로세스’ 스케줄링 알고리즘이라고 부릅니다. 스레드는 다른 방식으로 스케줄링을 하나요?

스레드도 프로세스와 마찬가지뢰 스케줄링이 필요하다. 스레드는 프로세스 내에서 실행되는 경량 프로세스로, 각각의 스레드는 독립적인 실행 흐름을 가지고 있다. 따라서 스레드 스케줄링은 프로세스 스케줄링과는 약간 다르게 이루어진다.

1. 프로세스 스케줄링과 스레드 스케줄링의 차이
   • 프로세스 스케줄링: 각각의 프로세스에 CPU 시간을 할당하는 작업이다. 여러 프로세스간의 스케줄링이 이루어지며, 각 프로세스는 독립적인 메모리 공간을 가진다.
   • 스레드 스케줄링: 프로세스 내의 각 스레드에게 CPU 시간을 할당하는 작업이다. 스레드는 같은 프로세스 내에서 공유하는 메모리를 가지고 있으므로, 스레드간의 스케줄링은 프로세스간의 스케줄링보다 경량화되어 있다.
2. 스레드 스케줄링의 특징
   • 스레드 우선순위
     • 각 스레드에는 우선순위가 할당되어 있고, 스레드 스케줄러는 이 우선순위를 기반으로 어떤 스레드가 실행될지 결정한다.
   • 강제 스레드 스케줄링
     • 명시적인 스레드 전환이 가능하며, 스레드가 I/O 작업을 기다리는 동안에도 다른 스레드가 실행될 수 있다.
3. 멀티코어 환경에서 스레드 스케줄링
   • 멀티코어 환경에서는 여러 개의 코어가 동시에 실행되므로, 각각의 코어에 어떤 스레드가 할당될지에 대한 스케줄링이 필요하다.

스레드 스케줄링은 프로세스 스케줄링과는 다르게 프로세스의 주소 공간을 공유하고 있기 때문에, 스레드간의 상호작용과 동기화에 대한 고려가 필요하다. 이러한 차이점을 고려하여 운영체제나 스레드 라이브러리에서는 적절한 스레드 스케줄링 알고리즘을 사용하여 효율적인 작업 분배를 수행한다.

유저 스레드와 커널 스레드의 스케줄링 알고리즘은 똑같을까요?

유저 스레드

• 관리가 사용자 수준에서 이루어진다.
• 운영체제는 유저 스레드의 존재를 모르고, 유저 스레드의 생성과 스케줄링은 사용자 공간의 라이브러리나 스레드 관리자에 의해 담당된다.
• 유저 스레드의 스케줄링 알고리즘은 사용자 수준의 라이브러리에 의해 결정되며, 주로 우선순위 기반의 알고리즘이 사용된다.
• 유저 스레드간의 스케줄링은 커널이 아닌 사용자 수준에서 이루어지기 때문에 더 빠르게 이루어질 수 있다.

커널 스레드

• 커널 스레드는 운영체제 커널 수준에서 직접 관리된다.
• 운영체제가 커널 스레드를 인식하고 각 스레드에 대한 스케줄링을 진행한다.
• 커널 스레드의 스케줄링은 주로 운영체제의 커널 스케줄러에 의해 결정되는 것이며, 이는 시스템 레벨에서 실행되기 때문에 보다 높은 권한과 자원에 대한 접근을 갖는다.