한재원

한재원

🛠️ 저는 커서 백엔드 개발자가 될래요!

[운영체제] 스케줄링

Updated: Categories:

운영체제의 스케줄링에 대해 알아보자

스케줄러

  • 어떤 프로세스에게 자원을 할당할지 결정하는 커널 모듈

장기 스케줄러

  • 작업(job) 스케줄러
  • 준비 큐에 넣을 프로세스를 선택하는 스케줄러
    • 메모리와 디스크 사이의 스케줄링을 담당
    • 디스크에 저장된 프로세스를 준비큐 메모리에 올린다
  • 현대의 시분할 시스템에서는 사용되지 않음

중기 스케줄러

  • ready 큐 관리
  • 메모리에 적재된 프로세스 수를 관리하는 스케줄러
    • 메모리에 프로세스가 너무 많아질 경우 각 프로세스에 할당되는 메모리가 적어지게 됨
    • 이 경우 봉쇄상태의 프로세스 메모리를 빼앗아 디스크의 스왑영역에 저장해버림(Swap out)
    • 만약 이래도 해결되지 않으면 준비 큐로 이동하는 프로세스까지 스왑 아웃 시킴

단기 스케줄러

  • CPU 스케줄러
  • ready -> running
  • CPU를 할당할 프로세스를 선택하는 스케줄러
    • 준비 큐에 있는 프로세스를 스케줄링 알고리즘을 통해 선택


CPU 스케줄링

  • 준비 큐에 있는 프로세스를 스케줄링 알고리즘을 통해 선택
  • 프로세스의 CPU 교체 과정에서 CPU 이용률을 최대화하기 위함
  • CPU 스케줄링은 다음과 같은 상황에서 일어난다
    • running -> ready : 인터럽트 발생
    • running -> terminated : 프로세스 종료
    • running -> blocked : I/O 발생
    • blocked -> : I/O 종료

선택기준

  • CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용 된 시간을 측정
  • 처리량 : 단위 시간 당 작업을 마친 프로세스의 수
  • 대기 시간 : 프로세스가 생성된 후 자원의 할당을 대기하는 총 시간
  • 응답 시간 : 프로세스 시작 후 첫번 째 출력까지 걸리는 시간
  • 반환 시간(CPU burst time) : 프로세스가 생성된 후 사용하던 자원을 모두 반환하는데 까지 걸리는 시간 (대기시간 + 실행시간)
  • 실행 시간 : 프로세스의 작업이 시작 된 후 종료되기 까지의 시간
  • 평균 대기시간 : (모든 프로세스의 대기시간의 합) / (프로세스의 수)
  • 평균 반환시간 : (모든 프로세스의 반환시간의 합) / (프로세스의 수)


비선점 스케줄링 알고리즘

  • 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식
    • 프로세스 종료 or 대기 아니면 CPU를 계속 차지하고 있음
  • 장점
    • 응답시간 예측이 편함
    • 일괄처리에 적합
  • 단점
    • 우선순위가 높은 프로세스가 와도 계속 대기해야함

FCFS (First Come First Serve)

  • 준비 큐에 도착한 순서대로 CPU 할당
  • 장점
    • 모든 프로세스의 우선순위가 동일하여 공평함
  • 단점
    • Convoy Effect 발생 : CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들의 대기 시간이 늘어나는 현상

SJF (Shortest Job First)

  • 예상 작업시간(CPU 사용시간)이 가장 짧은 프로세스가 높은 우선순위를 가짐
    • 유사한 선점 알고리즘으로 SRT가 있음
  • 장점
    • Convoy Effect를 해결
  • 단점
    • 기아 문제 발생 : 우선순위가 낮은 프로세스가 순서가 계속 밀려 공평성 위배
      • 에이징 기법으로 해결 : 오래 기다린 프로세스는 에이징 카운트롤 올려 우선순위를 높여줌
    • 우선순위 책정이 힘듦 : 사용자와 상호작용이 빈번한 프로세스는 작업시간을 정확히 판단하기 힘들다

HRN (Highest Response Ratio Next)

  • SJF 단점을 보완한 알고리즘. 우선순위 책정에 대기시간이 포함됨
    • 우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간
  • 장점
    • 기아 문제 해결
  • 단점
    • 우선순위를 계속 계산해야하므로 오버헤드 증가


선점 스케줄링 알고리즘

  • 프로세스가 CPU를 점유하고 있어도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식
  • 장점
    • 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
    • 실시간 응답을 요구하는 시스템에 적합
  • 단점
    • 잦은 문맥교환으로 인해 오버헤드가 발생

RR (Round Robin)

  • 모든 프로세스가 동일한 우선순위와 CPU 사용시간(Time Slice)을 할당받음
    • 시간 내 작업이 끝나면 종료
    • 시간 내 작업을 모두 끝내지 못하면 준비 큐로 이동
  • 장점
    • Convoy Effect를 해결
  • 단점
    • Time Slice가 클 때 : FCFS와 동일하게 동작함
    • Time Slice가 작을 때 : 잦은 문맥교환으로 인해 시스템 전체 성능 하락

SRT (Sortest Remaining Time)

  • 예상 작업시간이 짧은 프로세스가 높은 우선순위를 가지고 CPU 사용시간을 할당받음
    • SJF + RR 혼합 방식 (SJF의 선점형 방식)
  • 장점
    • RR보다 Convoy Effect를 좀 더 해결가능
  • 단점
    • 우선순위를 계속 계산해야 하므로 오버헤드 증가
    • 기아 문제 발생
    • 문맥교환이 잦음


인터럽트

  • 프로세스가 CPU를 선점하여 Running 상태일 때, 입출력 이벤트 등의 예외상황이 발생한 경우 CPU에게 알려 이를 먼저 처리하게 하는것
    • Running 상태의 프로세스를 Waiting or Ready 상태로 변경한다

소프트웨어 인터럽트

  • 내부/동기적 인터럽트
    • trap, exception이라고 함
  • CPU 내부에서 실행한 명령 때문에 일어남 (프로그램상의 문제)
    • 오버플로우, 산술연산 오류(0으로 나누기) 등
    • 터미널 작업중단 (ctrl + c)
  • Running -> Ready

하드웨어 인터럽트

  • 외부/비동기적 인터럽트
    • 인터럽트는 일반적으로 하드웨어 인터럽트를 뜻함
  • CPU 외부의 인터럽트 요구 신호때문에 발생함
    • 정전, 하드웨어 고장
    • 입출력 이벤트 발생
  • Running -> Waiting

인터럽트와 이중모드

  • 사용자모드에서 커널모드로 변경되는 경우는 두가지임
    1. 시스템 호출을 한 경우
    2. 인터럽트를 발생 시킨 경우 -> 인터럽트 처리는 커널모드에서 해야하기 때문