[CS] 운영체제 스케줄링 기본 및 알고리즘 이해

📖 운영체제 스케줄링 종류

✅ 시분할 시스템

응용 프로그램이 CPU를 점유하는 시간을 잘게 쪼개어 실행될 수 있도록 하는 시스템이며 다중 사용자도 지원한다

✅ 멀티 태스킹

단일 CPU에서, 사람이 인지하기 힘든 시간 10 ~ 20ms 단위로 실행 응용 프로그램을 바꿔 여러 응용 프로그램이 동시에 실행하는 것처럼 보이게 하는 시스템.  

✅ 멀티프로그래밍

최대한 CPU를 일정 시간당 많이 활용하는 시스템

CPU를 활용한다는 말의 의미를 알아보자면,
어떤 프로세스를 실행시키는데 레지스터나 캐시 같은 메모리가 아닌 SSD, HDD 같은 저장매체에서 데이터가 필요해 가져오는 동안 CPU가 대기를 하는 일이 발생한다면 그 시간 동안 비효율이 발생한다. 그래서 효율적으로 그 대기 시간 안에 다음 진행할 프로세스를 먼저 실행시켜 CPU를 최대한 활용하는 것을 멀티프로그래밍이라고 한다.

✅ 멀티 프로세싱

여러 CPU에 하나의 응용 프로그램을 병렬로 실행해서 실행속도를 높이는 기법

💡 프로그램 성능을 높이는 방법
가능한 메모리상에서 실행하도록 해야 한다.
예시로 Redis 데이터베이스가 있다.

 

📖 스케줄링 알고리즘 구현 이해

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

✅ FIFO 스케줄러

Queue를 활용한 가장 대표적인 스케줄링 알고리즘이며, 배치처리시스템을 만든다 하였을 때 고려해 볼 만한 알고리즘이다.

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

가장 프로세스 실행시간이 짧은 프로세스부터 먼저 실행을 시키는 알고리즘이다.

현실적으론 프로세스 실행 시간이 예측이 힘들기 때문에 사용하기 애매하나 예측이 가능하다면 고려해 볼 만하다. 사용을 한다는 전제하에 최소한 우선순위 큐와 힙 자료구조 사용을 고려해 볼 수 있다

👀 용어 알아두기

RealTime OS(RTOS)
응용 프로그램 실시간 성능 보장을 목표로 하는 운영체제
정확하게 프로그램 시작, 완료시간을 보장
SJF 스케줄러를 적용할 수 있을 만큼 특정 프로세스가 얼마의 시간이 걸리는지 정보를 가지고 있을 가능성이 크다.

General Purpose OS(GPOS)
프로세스 실행시간에 민감하지 않고, 일반적인 목적으로 사용되는 운영체제
ex) Windows. Linux 등이 있다

 

✅ 우선순위 기반 스케줄러(Priority-Based 스케줄러)

• 정적 우선순위
  •  - 프로세스마다 우선순위를 미리 지정
• 동적 우선순위
  •  - 스케줄러가 상황에 따라 우선순위를 동적으로 변경

✅ Round Robin 스케줄러

큐에 순차적으로 프로세스를 넣고 하나씩 실행을 시키다 일정시간 동안 프로세스가 완료가 안되면 다시 큐에 넣는 방식이다.

✅ 프로세스 상태 기반 스케줄러

현대 운영체제의 스케줄러의 기본이 되는 스케줄러이다. 프로세스에다 상태정보를 넣는 방식이다.

상태정보는 5가지가 존재하는데 다음과 같다.

• new state : 프로세스 생성
• ready state : CPU에서 실행 가능 상태
• running state : 현재 CPU에서 실행 상태
• block state : 특정 이벤트 발생 대기 상태
• exit state : 종료 상태

기본 스케줄링 알고리즘 종류 정리

● FIFO(FCFS) 스케줄링 알고리즘 (ex. 배치 처리 시스템)

● 최단 작업 우선(SJF) 스케줄링 알고리즘

● 우선순위 기반 스케줄링 알고리즘 (ex. 정적 우선순위, 동적 우선순위)

● Round Robin 스케줄링 알고리즘 (ex. 시분할 시스템)

● 프로세스 상태기반 스케줄링 알고리즘 (ex. 멀티프로그래밍)

✅ 성능을 위해 꼭 체크해야 하는 포인트

❓ IO-bound 인가? CPU-bound 인가?

• IO-bound : 저장매체, 네트워크를 많이 사용하는 프로그램
• CPU-bound : CPU/메모리를 주로 사용하는 프로그램

IO-bound 프로그램이면 최대한 CPU-bound 쪽으로 코드를 개선할 수 있으면 성능을 개선할 수 있다.