1. 스케쥴링에 사용되는 시스템들

1.1. 배치처리 시스템

응용프로그램들을 순서대로 배치하여 실행시켜주는 시스템

1.2. 시분할 시스템

응용 프로그램이 CPU를 점유하는 시간을 분할하여 실행시키는 방법으로 다중 사용자 지원을 위해 요청과 응답 시간을 최소화할 수 있다.

1.3. 멀티 태스킹

단일 CPU에서 여러 응용 프로그램이 동시에 실행되는 것 처럼 보이도록 만들 수 있다.

1.4. 멀티 프로세싱(다중 처리)

하나의 프로그램에서 처리할 태스크를 멀티 CPU를 통해 병렬로 실행하여 실행 속도를 극대화시킨 기술이다. 이 기술은, 둘 이상의 프로세서(CPU)가 다수의 프로세스를 처리하는 능력을 의미하기도 한다.

1.5. 멀티 프로그래밍

CPU 점유율을 높이는 기술로 시간 대비 CPU 활용도를 높이는 방법이다. 응용 프로그램을 짧은 시간 안에 실행 완료시킬 수 있다. (CPU Utilization을 높이는게 목적)

• 응용 프로그램이 하는 일에 CPU를 점유하는 것 외의 작업이 포함된다. 예를들어, 저장매체에서 파일을 읽거나 프린팅 등의 작업을 수행한다. 이 때 CPU가 다른 작업을 하도록 만들어 주는 것이 멀티 프로그래밍의 핵심이다.
• CPU와 상관없는 작업을 진행중인 프로세스를 blocking 대기열(queue)에 삽입하여 상태를 변경하고 다른 프로세스를 실행한다. 그래서 일반적으로 I/O가 발샐할 때는 CPU가 DMA(Direct Memory Access)에게 메모리 접근을 명령하고 DMA는 데이터를 조달하는 역할을 수행한다.

1.6. 그 외 개념

1.6.1. 메모리 계층

• CPU가 1개의 명령을 실행하는 단위 cycle
• 메모리는 계층으로 나뉘며, 계층별 읽기/쓰기 속도에 차이가 있다.
  • cpu: Registers, L1 Cache, L2 Cache, L3 Cache
  • S-DRAM: Main Memory
  • 저장매체: Flash Drive(SSD), Hard Disk

1.6.2. 프로세스

• 메모리 위에서 실행 중인 프로그램
• 응용프로그램은 프로세스가 아니다. 하나의 응용 프로그램은 여러 개의 프로세스(프로그램)가 상호작용(IPC-프로세스 통신기법)하며 실행될 수 있다.

1.6.3. RTOS(RealTime OS)

• 응용 프로그램 실시간 성능 보장을 목표로하는 OS를 말한다. 정확하게 프로그램의 시작과 완료시간을 보장하는 특징을 가진다. 공장에서 정확한 시간을 엄수해야 하는 경우 대표적으로 RTOS를 사용한다.

1.6.4. GPOS(General Purpose OS)

• 프로세스 실행시간에 민김하지 않고, 일반적인 목적으로 사용되는 OS를 말한다. Windows, Linux 등이 대표적인 GPOS다.

출처: https://computationstructures.org/lectures/caches/slides/Slide21.png

2. 스케쥴링 알고리즘

어떤 순서로 프로세스를 실행시키는가

2.1. FIFO 스케쥴러

• 가장 간단한 스케쥴러로 배치처리 시스템을 가능하게 만드는 스케쥴러다.
• FCFS(First Come First Served) 스케쥴러 라고도 불린다.

2.2 SJF(Shortest Job First) 스케쥴러

• 실행 시간이 짧은 프로세스부터 실행하는 스케쥴러
• 프로세스 대기 시간 평균치를 최소화 할 수 있다. 단, 모든 작업의 실행 시간을 알고 있아야 SJF 스케쥴러를 구현할 수 있는 제약사항이 존재한다.

2.3. 우선순위 기반 스케쥴러

• 우선순위를 지정하여 실행시키는 스케쥴러
• 정적(프로세스마다 우선순위를 미리 지정), 동적(스케쥴러가 상황에따라 우선순위를 변경)으로 우선순위를 지정할 수 있다.

2.4 Round Robin 스케쥴러

• 시분할 시스템을 예시로 프로세스 작업 단위를 분할하여 번갈아가며 실행시킨다. 현재 진행 중인 프로세스를 Queue의 대기열에 삽입하는 구조로 반복하는 스케쥴러다.
• FIFO 스케쥴러와 동일하게 선입 선출 방식으로 스케쥴링된다.