프로세스 스케쥴링

배치 처리 시스템 Batch Processing

배치 처리 시스템(일괄 처리 시스템)은 초기의 컴퓨터 시스템에서 사용된 형태.
일정량 또는 기간동안 등록된 데이터를 모아 한번에 처리하는 시스템입니다.
배치 처리 시스템은 등록된 프로그램을 프로그램 실행 요청 순서에 따라 순차적으로 실행됩니다.

배치 처리 시스템을 사용할 경우 동시에 여러 작업을 진행할 수 없다는 치명적인 단점을 가지고 있고.
이를 해결하기 위해 시분할 시스템, 멀티 프로그래밍 시스템이 고안되었습니다.

시분할 시스템 Time Sharing System

CPU가 각 프로그램을 일정 시간(time slice) 동안 번갈아 가면서 실행하는 시스템.

멀티 프로그래밍 시스템과 결합하면 모든 작업이 동시에 진행되는 것처럼 보이는 대화식 처리가 가능합니다.

다중 사용자를 지원하고, 프로세스 응답 시간을 최소화 하는 데 목적을 두고 있습니다.

멀티 프로그래밍 시스템 Multi Programming System

다중 프로그래밍.

프로세스가 더 이상 실행할 수 없는 상태가 되면 바로 다음 프로세스를 진행합니다.

메모리 계층에 따라 데이터에 접근하는 시간에 큰 차이가 있기 때문에,

CPU 안의 메모리를 적극적으로 활용하여(CPU 이용률 최대화) 속도를 빠르게 하는 것에 목적을 두고 있습니다.

멀티 태스킹 Multi Tasking

단일 CPU에서, 여러 응용 프로그램이 동시에 실행되는 것처럼 보이도록 하는 시스템

멀티 태스킹의 스케줄링 방식에는 멀티 프로그래밍 방식, 시분할 방식, 실시간 시스템 방식이 있습니다.

프로세스 스케쥴링 정리

• 시분할 시스템 : 다중 사용자 지원, 컴퓨터 응답 시간을 최소화하는데 목적.
• 멀티 프로그래밍 시스템(다중 프로그래밍) : CPU 이용률을 최대화하는데 목적.
• 멀티 태스킹 : 단일 CPU에서 여러 응용 프로그램을 동시에 실행하는 것처럼 보이게 하는 시스템
• 멀티 프로세싱 : 여러 CPU에서 하나의 응용 프로그램을 병렬로 실행해서 실행속도를 높이는 기법

---

스케쥴링 알고리즘

스케쥴러는 운영체제 핵심 기능으로서 빈번하게 호출되므로, 스케쥴러 알고리즘은 운영체제 성능에 큰 영향을 미치게 됩니다.

FIFO 스케쥴링(First In First Out)

FCFS (First Come First Served) 알고리즘은 먼저 CPU를 요청한 프로세스가 먼저 자원을 제공 받습니다.
프로세스가 저장 매체 읽거나 프린팅을 하는 작업 없이, CPU를 순차대로 사용합니다.

SJF 스케쥴링(Short Job First)

최단 작업 우선 스케쥴링 기법. 가장 프로세스 실행 시간이 짧은 프로세스부터 먼저 실행을 시키는 알고리즘.
구현 시에는 우선 순위 큐와 힙 자료구조 사용을 고려해야 합니다.

Prioty-Based 스케쥴링

우선 순위 스케쥴링 기법은 프로세스마다 우선 순위를 부여하고, 이 우선 순위를 판별하여 더 중요하다고 판단되는 것이 먼저 실행됩니다.
프로세스별 우선 순위 변동 여부에 따라 정적 스케줄링과 동적 스케줄링으로 구분됩니다.
정적 스케줄링은 프로세스마다 우선 순위를 미리 지정해두는 것이고
동적 스케줄링은 스케줄러가 상황에 따라 우선 순위를 동적으로 변경하는 것입니다.

우선 순위 스케줄링의 단점으로는 우선 순위가 낮은 프로세스가 계속해서 수행되지 않는 기아 현상을 꼽을 수 있습니다.
이를 에이징(Aging) 기법을 통해 해결하는데, 에이징 기법이란 시간이 지날수록 오래 대기한 프로세스의 우선 순위를 높이는 방식입니다.

Round-Robin 스케쥴링

시분할 시스템을 위해 설계된 스케쥴링 기법입니다.
프로세스들 사이에 우선 순위를 두지 않고, 순서대로 시간 단위(Time Quantum)로 CPU를 할당하는 방식의 알고리즘으로
일정 시간이 지나도 해당 프로세스가 완료되지 않으면 다시 준비 큐로 이동합니다.

프로세스 상태 기반 스케쥴링

프로세스는 다음과 같은 상태를 갖습니다.

• Running state : 현재 CPU에서 실행중인 상태
• Ready state : CPU 에서 실행이 가능한 상태(실행 대기 상태)
• Block state : 특정 이벤트 발생 대기 상태

CPU는 Ready State Queue에 첫번째로 들어온 프로세스를 Running State Queue에 등록, 실행합니다.
이 때 실행된 프로세스가 계속 실행 가능한 경우 다시 Ready State Queue에 등록하고,
Wait(프로세스가 특정 자원이나 이벤트를 기다리는 상태)에 들어간다면 먼저 실행된 프로세스는 Block State Queue에 등록,
Ready State Queue 에서 다음 프로세스를 가져와 실행합니다.

대기 중인 모든 프로세스가 완료되거나 Wait 상태여서 CPU 어떠한 작업도 하지 않을 경우에는 idel 상태라고 합니다.

스케쥴링 알고리즘 정리

• FIFO (FCFS) 스케쥴링 알고리즘 (배치 처리 시스템)
• 최단 작업 우선(SJF) 스케쥴링 알고리즘
• 우선순위 기반 스케쥴링 알고리즘
  • 정적 우선순위, 동적 우선순위
• Round Robin 스케쥴링 알고리즘
  • 시분할 시스템
• 프로세스 상태 기반 스케쥴링 알고리즘
  • 멀티 프로그래밍
    
    

---

Reference

① [운영체제] 멀티 프로그램 & 시분할 시스템 https://velog.io/@profile_exe/운영체제-멀티-프로그래밍-시분할-시스템
② OS :: 멀티 태스킹, 멀티 프로세싱 https://blog.naver.com/rhkdals1206/221572073363