Scheduler

단기, 중기, 장기 스케쥴러에 대해 설명해 주세요.

스케줄링이란?

Multi-Programming은 프로세스의 CPU 이용을 최대화하여 사용되지 않는 CPU를 최소화한다. 이때 프로세스를 적절하게 배치하는 것을 스케줄링이라고 한다.

Scheduling Queue

프로세스를 스케줄링하기 위해서는 3가지 Queue를 사용한다.

1. Job Queue: 시스템 내에 있는 모든 프로세스의 집합
2. Ready Queue: 메인 메모리 내에 있으면서 Ready 상태에서 CPU의 할당을 기다리는 프로세스의 집합
3. Device Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합

⇒ 프로세스는 스케쥴러에 의해 적절한 큐에 배치되어 사용된다.

장기 스케줄러 (Long-term Scheduler)

작업 스케줄러 (Job Scheduler)라고도 불린다. 어떤 프로세스를 Ready Queue로 보낼지를 결정하는 스케줄러이다.

메모리는 한정되어 있기 때문에, 실행할 수 있는 프로세스보다 많은 프로세스가 메모리에 올라오면 대용량 메모리에 (일반적으로 하드디스크) 임시로 저장된다. 장기 스케줄러는 하드디스크의 프로세스 중 하나를 선택하여 메모리를 할당하고, Ready Queue로 보내는 역할을 한다.

• 메모리와 디스크 사이의 스케줄링 담당
• 프로세스에 Memory 할당
• Degree of Multiprogramming을 제어
  • Degree of Multiprogramming: 현재 메인 메모리에 존재하는 활성화된 일의 개수
• 프로세스가 끝날 때 다음 프로세스를 할당하는 식으로 실행되므로, 실행 주기가 매우 긺
• 프로세스의 상태: New → Ready / Running → Terminate

중기 스케줄러 (Medium-term Scheduler)

Swapper라고도 불린다. 메모리에 적재된 프로세스 수를 관리하는 스케줄러이다.

스와핑 (Swapping)

일부 프로세스를 메모리에서 디스크로 보내고, 시간이 흘러 메모리에 여유가 생기면 다시 적재하는 방식이다.

• 우선순위가 가장 낮은 프로세스나 일정 시간 동안 활성화되지 않았던 프로세스들을 디스크로 내린다.
• 프로세스의 상태: Ready → Suspended

단기 스케줄러 (Short-term Scheduler)

CPU Scheduler라고도 불린다. 어떤 프로세스에 CPU를 할당할지를 결정하는 스케줄러이다.

CPU는 하나의 작업만을 처리한다. 따라서 Ready Queue에서 CPU를 할당할 하나의 프로세스를 선택해야 한다.

• Ready 상태에 있는 작업 중에서 프로세스를 선택하여 CPU를 할당한다.
• CPU와 메모리 사이의 스케줄링을 담당한다.
• 일반적인 스케줄러는 단기 스케줄러를 의미한다.
• 프로세스의 상태: Ready → Running → Waiting → Ready
• CPU를 낭비하지 않기 위해 프로세스를 기다리는 동안 다른 프로세스를 바로 실행해야 한다. 따라서 단기 스케줄러는 짧은 주기로 수행된다.

현대 OS에는 단기, 중기, 장기 스케쥴러를 모두 사용하고 있나요?

• 장기 스케줄러: 사용하지 않는다
  • 장기 스케줄러는 일괄 처리 시스템에서 사용한다. (자원 독점 방식)
    • 일괄 처리 시스템: 비슷한 작업들을 모아서 한 번에 처리하는 시스템
    • 다중 프로그래밍 시스템: 여러 개의 프로그램을 메모리에 적재하여 실행하는데 하나를 실행하다 대기 상태가 되면 다른 프로그램을 실행하는 시스템
  • 현대 운영체제에서는 대부분 시분할 방식인 Round Robin을 사용한다. (자원 독점 X)
    • 시분할 방식에서 프로세스는 시작과 동시에 메모리를 할당해 Ready Queue에 넣는다.
  • 가상 메모리의 사용으로 잘 사용하지 않는다.
• 중기 스케줄러: 잘 사용하지 않는다
  • 가상 메모리를 사용하면 프로세스의 전체가 아닌 일부만 실제 메모리에 올라와도 된다.
  • 따라서 실제 메모리 용량보다 큰 프로그램을 실행시킬 수 있고, 메모리의 크기에 제약이 없어졌다.
• 단기 스케줄러: 여전히 잘 사용한다.

프로세스의 스케줄링 상태에 대해 설명해 주세요.

!https://velog.velcdn.com/images/zsmalla/post/0e51b2b1-d42f-46fb-a0fb-e722039c6e81/image.png

• new: 프로세스 생성 중인 상태이다.
  • 커널 공간에 PCB가 만들어지고 메모리는 할당받지 않은 상태이다.
• ready: 프로세스가 CPU를 기다리는 상태이다.
  • 프로세스가 메모리에 적재된 상태로 필요한 자원을 모두 얻은 상태이다.
• running: 프로세스가 CPU를 할당받아 명령어를 수행 중인 상태이다.
  • CPU가 하나인 경우, 여러 프로세스가 동시에 실행되어도 실제로 실행 중인 프로세스는 매 시점 하나뿐이다.
• blocked: 프로세스가 CPU를 할당받아도 당장 실행할 수 없는 상태이다.
  • 현재 프로세스가 I/O 작업 등을 처리 중인 상태이다.
  • 프로세스가 running 상태에서 디스크 I/O 작업을 하는 동안은 CPU를 점유하고 있어도 다음 명령어를 수행하지 못하기 때문에 CPU를 낭비하지 않기 위해서 I/O 작업을 하는 프로세스는 CPU를 반납하고 Device Queue에 들어간다.
• terminated: 종료 시스템 콜을 받고 PCB가 할당 해제되기 직전의 상태이다.
  • 프로세스의 실행이 완료되고 할당된 CPU를 반납한 상태이다.
  • 커널 공간 내의 PCB는 남아 있다.
  • 완전히 종료되면 더 이상 프로세스가 아니다.
• suspended: 프로세스의 중지 상태이다.
  • 메모리를 강제로 뺏긴 상태로 특정한 이유로 프로세스의 수행이 정지된 상태이다.
  • 외부에서 다시 재개시키지 않는 이상 다시 활성화될 수 없다.
  • • blocked는 잠시 중단되었다가 끝나면 다시 ready로 자연스럽게 돌아온다.

preemptive / non-preemptive에서 존재할 수 없는 상태가 있을까요?

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의 약점인 기아 현상을 약간 보완한 기법이다.

메모리가 부족할 경우 프로세스는 어떠한 상태로 변화할까요?

대기 중인 프로세스가 할당된 메모리를 반납하고 하드디스크로 swap-out 된다. (suspend 상태)

이후 메모리에 여유가 생기면 다시 메모리로 swap-in 된다.