스케줄링 알고리즘 [혼공컴구]

CPU 스케줄링의 목적
- 공평성
  - 모든 프로세스가 자원을 공평하게 배정
  - 자원 배정 과정에서 특정 프로세스가 배제되어서는 안됨
- 효율성
  - 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링
  - 유휴 자원을 사용하려는 프로세스에 우선권
- 안정성
  - 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함
  - 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호
- 확정성
  - 프로세스가 증가해도 시스템이 안정적으로 작동하게 조치
  - 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되도록 조치
- 반응 시간 보장
  - 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정
  - 시스템은 적절한 시간 안에 프로세스의 요구에 반응
- 무한 연기 방지
  - 특정 프로세스의 작업이 무한히 연기되어서는 안됨

 

비선점 스케줄링

  - 문맥 교환의 횟수가 선점형 스케줄링보다 적음

    - 문맥 교환에서 발행하는 오버헤드가 적음

  - 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서는 무작정 기다리는 수 밖에 없음

  - 종류

 

FCFS (선입선처리) 스케줄링

  - 준비 큐에 도착한 순서대로 CPU를 할당

  - 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스 실행

  - 큐가 하나라 모든 프로세스는 운선순위가 동일

  - 콘보이 효과로 인한 성능저하 발생 가능성

    - 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성 저하

    - 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU의 idle time이 길어져 작업 효율 저하

 

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

  - 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짮은 작업부터 CPU를 할당

  - 최단 작업 우선 스케줄링

  - 콘보이 효과를 완화

  - 프로세스의 종료시간을 정확하게 예측하기 어려움

  - 작업 시간이 길다는 이유만으로 계속 뒤로 밀리는 아사 현상 발생

    - 에이징 기법을 통해 아사 현상 방지

      - 프로세스가 양보할 수 있는 상한선을 정함

      - 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정

 

HRN(최소 응답률 우선) 스케줄링

  - SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만듬

  - 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링

  - 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상 완화

  - 프로세스의 우선순위 결정 기준

    - 우선 순위 = (대기시간 + CPU 사용시간) / CPU 사용시간

  - 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높임

  - 여전히 공평성이 위배되어 많이 사용하지는 않음

 

선점 스케줄링

  - 더 급한 프로세스가 언제든 끼어들어 사용 가능

  - 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골구루 자원을 배분 가능

  - 문맥 교환 과정의 오버헤드 증가

  - 종류

 

라운드 로빈 스케줄링

  - 한 프로세스가 할당 받은 타임 슬라이스 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다림

  - 선점형 알고리즘 중 가장 단순하고 대표적인 방식

  - 프로세스들이 작업을 완료할 때까지 계속 순화하면서 실행

  - 타임 슬라이스와 라운드 로빈 스케줄링

    - 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정

    - 타임 슬라이스가 큰 경우

      - 하나의 작업이 끝난 귀 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음

    - 타임 슬라이스가 작을 경우

      - 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제 발생

 

SRT (최소 잔여 시간 우선) 스케줄링

  - 라운드 로빈 스케줄링을 사용해, CPU를 할당 받을 프로세스를 선택할 때 작업 시간이 가장 적은 프로세스를 선택

  - 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 SJF 스케줄링에는 없는 작업이 추가됨

  - 운영체제가 프로세스의 종료시간을 예측하기 어렵고 아사 현상이 일어나 잘 사용하지 않음

 

우선순위 스케줄링

  - 프로세스의 중요도에 따른 우선순위를 반영

  - 비선점형

    - SJF

      - 작업 시간이 짧은 프로세스에 높은 우선순위

    - HRN

      - 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위

  - 선점형

    - SRT

      - 남은 시간이 짧은 프로세스에 높은 우선순위

  - 고정 우선순위 알고리즘

    - 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정

    - 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율설 저하

  - 변동 우선순위 알고리즘

    - 일정 시간마다 우선순위가 변하여 일정 시간마다 우선순위를 개호 계산하고 이를 반영

    - 복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능

  - 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사현상 발생

  - 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔랴하기 때문에 오버헤드가 커짐

 

다단계 큐 스케줄링

  - 우선 순위에 따라 준비 큐를 여러개 사용

  - 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입

  - 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작

 

다단계 피드백 큐 스케줄링 

  - 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤

  - 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화

  - 우선순위가 낮아져도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않음

  - 우선순위가 낮아질수록 CPU를 얻은 확률이 적어짐

    - 한번 CPUF를 잡을 때 많이 작업하라고 낮은 우선순위의 타임슬라이스를 크게 설정

  - 마지막 큐에 들어 있는 프로세스 (우선순위 가장 낮음)는 무한대의 타임 슬라이스를 얻음

  - 마지막 큐에 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작