프로세스 스케쥴링

4. 프로세스 스케쥴링

배치 처리 시스템과 시분할 시스템/멀티 프로그래밍

  • 여러 프로그램을 순차적으로 실행시킬 수 있도록 해주세요!
    • 어떤 프로그램은 실행이 너무 시간이 많이 걸려서, 다른 프로그램이 실행하는데 시간을 많이 기다려야 한다.
    • 나는 MP3 음악을 들으면서, 문서 작성을 하고 싶어요! (동시에 여러 응용 프로그램 실행)
    • 여러 사용자가 동시에 하나의 컴퓨터를 쓰려면 어떻게 해야 하나요? (다중 사용자 지원)

멀티 프로그래밍/시분할 시스템이 나왔다


시분할 시스템

  • 시분할 시스템: 다중 사용자 지원을 위해 컴퓨터 응답 시간을 최소화하는 시스템

멀티 태스킹

  • 멀티 태스킹: 단일 CPU에서, 여러 응용 프로그램이 동시에 실행되는 것처럼 보이도록 하는 시스템
    • 나는 MP3 음악을 들으며, 문서 작성을 한다.

실제 멀티 태스킹

  • 1000 밀리초(ms) = 1 초
  • 10 ~ 20 ms 단위로도 실행 응용 프로그램이 바뀌더라
  • 사용자에게는 동시에 실행되는 것처럼 보임

멀티 태스킹과 멀티 프로세싱

  • 멀티 태스킹과 멀티 프로세싱

  • 출처: http://donghoson.tistory.com/15

  • 멀티 태스킹: 단일 CPU

  • 멀티 프로세싱: 여러 CPU에 하나의 프로그램을 병렬로 실행해서 실행속도를 극대화시키는 시스템

정리

  • 배치 처리 시스템
  • 시분할 시스템 (다중 사용자 지원, 응답시간 최소화)
  • 멀티 태스킹 (동시 실행하는 것 처럼 보이도록)
  • 멀티 프로세싱 (여러 CPU에 하나의 프로그램을 병렬로 실행시키는 시스템)

멀티 프로그래밍

  • 최대한 CPU를 많이 활용하도록 하는 시스템
    • 시간 대비 CPU 활용도를 높이자
    • 응용 프로그램을 짧은 시간 안에 실행 완료를 시킬 수 있음
  • 응용 프로그램은 온전히 CPU를 쓰기 보다, 다른 작업을 중간에 필요로 하는 경우가 많습니다.
    • 응용 프로그램이 실행되다가 파일을 읽는다.
    • 응용 프로그램이 실행되다가 프린팅을 한다.

Code example


메모리 계층 - 컴퓨터 구조 복습

출처: http://computationstructures.org/lectures/caches/caches.html


System Bus - 컴퓨터 구조 복습


정리

실제로는 시분할 시스템, 멀티 프로그래밍, 멀티 태스킹이 유사한 의미로 통용된다.

  • 핵심
    • 여러 응용 프로그램 실행을 가능토록 함
    • 응용 프로그램이 동시에 실행되는 것처럼 보이도록 함
    • CPU를 쉬지 않고 응용 프로그램을 실행토록 해서, 짧은 시간 안에 응용 플오그램이 실행완료될 수 있도록 함
    • 컴퓨터 응답 시간도 짧게 해서, 다중 사용자도 지원
  • 주요 스케쥴링 기법
    • 시분할 시스템: 다중 사용자 지원, 컴퓨터 응답시간을 최소화하는 시스템
    • 멀티 태스킹: 단일 CPU에서 여러 응용 프로그램을 동시에 실행하는 것처럼 보이게 하는 시스템
    • 멀티 프로세싱: 여러 CPU에서 하나의 응용 프로그램을 병렬로 실행하게 해서, 실행속도를 높이는 기법
    • 멀티 프로그래밍: 최대한 CPU를 일정 시간당 많이 활용하는 시스템

스케쥴링 알고리즘 기본


프로세스 (process) 란?

  • 실행 중인 프로그램은 프로세스라고 함
    • 프로세스: 메모리에 올려져서, 실행 중인 프로그램
    • 코드 이미지(바이너리): 실행 파일, 예:ELF format

프로세스라는 용어는 작업, task, job 이라는 용어와 혼용


여기서 잠깐!

  • 응용 프로그램 =! 프로세스

    • 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있음
  • 하나의 응용 프로그램은 여러 개의 프로세스(프로그램)가 상호작용을 하면서 실행될 수도 있음

간단한 C/C++ 프로그램을 만든다면 -> 하나의 프로세스 여러 프로그램을 만들어서, 서로 통신하면서 프로그램을 작성할 수도 있음 (IPC 기법)


스케쥴러와 프로세스

누가 프로세스 실행을 관리할까요? - 스케쥴러


스케쥴링 알고리즘

어느 순서대로 프로세스를 실행시킬까?

  • 목표
    • 시분할 시스템 예: 프로세스 응답 시간을 가능한 짧게
    • 멀티 프로그래밍 예: CPU 활용도를 최대로 높혀서, 프로세스를 빨리 실행

FIFO 스케쥴러

프로세스가 저장매체를 읽는 다든지, 프린팅을 한다든지 하는 작업 없이, 쭉 CPU를 처음부터 끝까지 사용한다.

  • 가장 간단한 스케쥴러 (배치 처리 시스템)
  • FCFS (First Come First Served) 스케쥴러

여기서 잠깐!

  • FIFO 는 어디서 배웠을까?

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

  • SJF(Shortest Job First) 스케쥴러
    • 가장 프로세스 실행시간이 짧은 플오세스부터 먼저 실행을 시키는 알고리즘

여기서 잠깐!

  • RealTime OS(RTOS): 응용 프로그램 실시간 성능 보장을 목표로 하는 OS

    • 정확하게 프로그램 시작, 완료 시간을 보장
    • Hardware RTOS, Software RTOS
  • General Purpose OS(GPOS):

    • 프로세스 실행시간에 민감하지 않고, 일반적인 목적으로 사용되는 OS, 예: Windows, Linux등

우선순위 기반 스케쥴러

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

Round Robin 스케쥴러


정리

  • 다양한 기본 스케쥴링 알고리즘
    • FIFO (FCFS) 스케쥴링 알고리즘 (배치 처리 시스템)
    • 최단 작업 우선(SJF) 스케쥴링 알고리즘
    • 우선순위 기반 스케쥴링 알고리즘
      • 정적 우선순위, 동적 우선순위
    • Round Robin 스케쥴링 알고리즘
      • 시분할 시스템 기반

프로세스 상태와 스케쥴링


멀티 프로그래밍과 Wait

  • 멀티 프로그래밍: CPU 활용도를 극대화 하는 스케쥴링 알고리즘
  • Wait: 간단히 저장매체로부터 파일 읽기를 기다리는 시간으로 가정

프로세스 상태

  • running state: 현재 CPU에서 실행 상태
  • ready state: CPU에서 실행 가능 상태(실행 대기 상태)
  • block state: 특정 이벤트 발생 대기 상태(예: 프린팅이 다 되었다!)

프로세스 상태간 관계

  • ready, running, block states

OS.xlsx -> Process Status (BASIC) & (QUEUE)


선점형과 비선점형 스케쥴러

  • 선점형 스케쥴러 (Preemptive Scheduling) : 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할수 있음

  • 비선점형 스케쥴러 (Non-preemptive Scheduling) : 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없음


선점형과 비선점형 스케쥴러 차이

  • 비선점형: 프로세스가 자발적으로 blocking 상태로 들어가거나, 실행이 끝났을 때만, 다른 프로세스로 교체 가능

선점형과 비선점형 스케쥴러 차이

  • 선점형: 프로세스 running 중에 스케쥴러가 이를 중단시키고, 다른 프로세스로 교체 가능

OS.xlsx -> Process Status + FIFO + RR


스케쥴러 구분

  • FIFO(FCFS), SJF, Priority-based 는 어떤 프로세스를 먼저 실행시킬지에 대한 알고리즘
  • RoundRobin 은 시분할 시스템을 위한 기본 알고리즘 (선점형 스케쥴러)

가볍게 듣기

랙?: 마우스 / 키보드 반응이 느린 경우?

스케쥴러가 해결해야하는 이슈! 다양하고 복잡한 스케쥴링 알고리즘 필요

  • 리눅스 스케쥴러: O(1), CFS 와 같이 다양한 방식으로 변경시도 중

    • 인터렉티브, IO, CPU 중심 프로세스로 구분할 수 있다면???
  • 딥러닝으로??? 스케쥴러를???

  • 프로세스 많이 띄우면 당연히 반응이 느리겠죠...

여러 스케쥴링 알고리즘 조합 예

  • RoundRobin + FIFO(FCFS)/SJF/Priority-based 도 가능합니다.