[Operating System 8th] 9. 단일처리기 스케쥴링

처리기 스케쥴링의 유형

스케쥴링의 정의 : 어떤 목적을 위해 시스템 자원을 프로세스에게 할당하는 것
- 목적 : 응답시간 낮추기, 처리량 향상, 효율성 증대
- 자원 : 시스템, 실 메모리, 처리기, I/O 장치
스케쥴링은 3단계로 나눌 수 있음
1. 장기 스케쥴링 : 프로세스에게 실행될 수 있는 자격을 부여할지 여부 결정
2. 중기 스케쥴링 : 프로세스 이미지를 주기억장치에 적재할 것인지를 결정
3. 단기 스케쥴링 : 처리기에 의해 실행될 다음의 프로세스를 결정
⇒ 스케쥴러가 수행되는 기간
스케쥴링과 프로세스 상태 전이의 관계

장기 스케쥴링

새로운 프로세스의 시스템 진입 허용 여부를 결정
- 다중 프로그래밍의 정도를 제어하는 역할
장기 스케쥴러가 실행되는 시점
- 일괄처리 작업의 진입 : 생성⇒준비/보류
- 대화형 작업의 로그인 : 생성⇒준비
장기 스케쥴러의 결정 사항
- 새로운 프로세스의 진입 허용 시점
  - 시스템 내의 부하에 따라 결정
- 진입을 허용할 다음 프로세스 선택 방법
  - FCFS, 우선순위 기반, I/O 중심 프로세스 우대, 여유 자원 사용 예정 프로세스 우대
  *I/O 중심 프로세스 우대 : CPU와 I/O가 동시에 작동해야 효율적 (평상시 계산 중심(CPU) 프로세스가 더 많음)

중기 스케쥴링

스와핑 (Swapping) 기능의 일부
- 다중 프로그래밍 정도를 제어하기 위해 프로세스 이미지 전체를 가상 메모리(또는 스왑 공간)로 Swap Out/In 함
중기 스케쥴러의 실행 시점
- 과도한 페이지 폴트로 인해 쓰레싱 현상이 발생할 때
- 처리기 이용률이 매우 낮을 때

단기 스케쥴링

주목적은 시스템의 전체 성능을 높이기 위해 처리기 시간을 효율적으로 프로세스에게 할당하는 것
단기 스케쥴러 실행 시점
- 클럭(타이머) 인터럽트 발생
- I/O 인터럽트 발생
- OS System Call (커널 내 Preemption Point 또는 사용자 모드로 복귀하기 전)
- 신호 (Signal, 예: 세마포어)

*인터럽트 서비스 루틴에 스케쥴러 코드가 있다. 다른 프로세스의 사용을 막기 위해 세마포어를 쓴다.

단기 스케쥴링 알고리즘

우선순위 기반 스케쥴링 정책
우선순위를 고려하지 않은 스케쥴링 정책
- 선입선처리 (FCFS: First-Come First-Served) 정책
- 라운드로빈 (Round-Robin) 정책
- SPN (Shortest Process Time) 정책
- HRRN (Highest Response Ratio Next) 정책
- Feedback 정책

단기 스케쥴링 평가 기준

기준 1: 사용자 중심 관점 Vs. 시스템 중심 관점

사용자 중심 관점
- 개별 사용자 또는 개별 프로세스 입장에서 스케쥴러를 평가
- 대화형 시스템에서 응답시간
- 일괄처리 시스템에서 반환시간
시스템 중심 성능 관점
- 스케쥴러가 처리기를 얼마나 효율적으로 활용했는가가 가장 중요한 척도
- 처리량 (단위 시간당 수행되는 Task의 수)
모든 시스템에서 중시해야할 관점 : 사용자 중심 관점
시스템 유형별로 중시해야할 관점이 다를 수 있음
- 단일 사용자 시스템 ⇒ 시스템 중심 관점이 상대적으로 덜 중요

기준 2: 성능 중심 관점 Vs. 성능 외적 관점

성능 중심 관점
- 대부분 정량적인 척도 ⇒ 측정이 용이함
- 사용자 : 반환시간, 완료기한
- 시스템 : 처리기 이용률
성능 외적 관점
- 대부분 정상적인 척도 ⇒ 측정이 어려움
- 사용자 : 예측 가능성
- 시스템 : 공정성, 균형있는 자원 사용

우선순위 기반 스케쥴링

⇒ 우선순위가 높은 프로세스 먼저 실행

같은 우선순위 큐 내에서는 어떤 정책을 쓸 것인가?
- 라운드 로빈 정책
순수 우선순위 기반 스케쥴링 방식의 문제점
- 낮은 우선순위의 프로세스는 기아의 가능성이 존재

⇒ 해결책 : 프로세스가 시스템 내에 머무른 시간(Age)이나 과거 실행 경력 등을 감안하여 우선순위를 조정해줌

다양한 스케쥴링 정책

스케쥴링 정책의 원리를 비교하기 위한 알고리즘
- 선택함수 : 다음 번 실행을 위해 준비 큐에서 대기 중인 프로세스 중 하나를 선택하는 알고리즘
- 결정모드 : 선택함수가 호출되는 시점을 결정하는 알고리즘

선택함수

함수 인자
- w = 대기한 시간과 실행한 시간을 모두 합쳐 시스템에 들어온 후 지금까지 경과한 시간
- e = 지금까지 실행하는데에만 걸린 시간
- s = 프로세스가 요구한 총 서비스 시간
선택함수의 예
- max[w] : 시스템에 진입한 후 가장 오랜 시간을 보낸 프로세스를 선택함 ⇒ FCFS

결정모드

비선점 모드
- 프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않음 ⇒ 아무도 안건드림
선점 모드 (Preemptive)
- 현재 실행중인 프로세스라 할지라도 OS에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있음 ⇒ 강제
- 비선점 모드보다 문맥(Context) 교환 횟수가 많아짐
- 한 프로세스가 처리기 시간을 독점하는 것을 방지할 수 있음

FCFS (First-come, First-served)

= FIFO (First-In, First-Out)

선택함수 : max[w]

준비 큐에서 대기 중이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음 번 실행 프로세스로 선정됨

결정모드 : 비선점형

실행중인 프로세스가 종료하거나 자발적으로 처리기를 양도할 때
일괄처리 시스템에 적합

스케쥴링 분석

FCFS는 짧은 프로세스보다 긴 프로세스에 유리 ⇒ 비선점 모드로 동작하기 때문
정규화된 반환 시간(Tr/Ts) : 어떤 프로세스가 시스템에 진입한 후 대기하느라 실행이 지연된 시간의 비율 ⇒ 이 값의 크기와 스케쥴링 서비스의 질은 반비례함 = 낮아야 좋다.
반환 시간(Tr) : 프로세스가 시스템에 진입한 후 대기시간과 실행시간의 합 ⇒ 시스템에 머문 총 시간
- Tr = 대기 시간 + 서비스 시간
스케쥴링이 진행됨에 따라 I/O 프로세스보다 처리기 중심(계산 중심) 프로세스를 우대하는 경향이 나타난다. ⇒ 처리기 및 I/O 장치의 이용률이 저하됨 (Convoy Effect)

FCFS 정책 하에서 평균 대기 시간은 최소가 아님

짧은 프로세스가 긴 프로세스 직후에 도착했을 때 발생
FCFS 정책 하에서 프로세스 서비스 시간이 크게 변할 경우 평균 대기 시간도 상당히 변할 수 있다.

Process	서비스 시간
P1	24 (제일 김)
P2	3
P3	3

1. 평균 대기 시간 = (0+24+27) /3 = 17

2. 평균 대기 시간 = (0+3+6)/3 = 3

라운드-로빈 (Round-Robin)

FCFS에서 짧은 프로세스가 피해보는 현상을 완화하는 방법 ⇒ 시간 할당량 기법 (Time Slicing)

선택함수 : 일정한 시간 할당량 종료

타이머를 이용하여 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 선점시킴 ⇒ 뒤로 보낸다.

결정모드 : 선점형

⇒ 먼저온 프로세스 먼저 But. 시간 제한

라운드-로빈 스케쥴링 기법 동작 방식

할당된 시간량이 다 소모되면, 클럭 인터럽트가 발생하여 클럭 인터럽트 서비스 루틴 실행
클럭 인터럽트 서비스 루틴은 현재 실행 중이던 프로세스를 준비 큐로 이동시킴
시간 할당량 설정 및 선택된 프로세스 실행

스케쥴링 분석

타임슬롯 사이즈 : q = 1

시간 할당량의 길이가 라운드-로빈 성능에 미치는 영향

시간 할당량이 너무 짧은 경우 : 문맥 교환 횟수 증가
시간 할당량이 너무 긴 경우 : FCFS와 비슷해짐

선점 시간 할당량의 크기가 스케쥴링에 미치는 영향

시간 할당량이 사용자와의 일반적인 대화 시간보다 긴 경우

*시간 할당량보다 일찍 끝남 ⇒ 문맥 교환 횟수 증가 = 오버헤드 증가

시간 할당량이 사용자와의 일반적인 대화 시간보다 짧은 경우

시간 할당량의 권장 크기

프로세스가 사용자와 최소한 한 번 이상 대화하기에 충분한 크기
프로세스 내의 어떤 한 함수정도는 실행을 마칠 수 있는 충분한 크기

프로세스의 특징은 고려하지 않는 대신 매우 공평

⇒ 시분할이나 트랜잭션 처리 시스템에 효과적

I/O 중심 프로세스보다 CPU 중심 프로세스를 우대

⇒ 계산 중심 우대

처리기 중심 프로세스는 시간 할당량을 전부 소비한 후 선점, 준비 큐 대기 ⇒ 처리기 과다 사용
I/O 중심 프로세스는 처리기를 잠깐 사용한 후 I/O 요구, 블록, 준비 큐 대기
I/O 중심 프로세스 성능 저하, I/O 장치의 사용률 저하, 프로세스간 응답시간의 편차 증가

⇒ 가상 라운드 로빈(VRR) 스케쥴링 방식으로 극복 가능

가상 라운드-로빈 (VRR) 스케쥴링 방식

*보조 큐가 준비 큐보다 우선순위가 높음

도착한 프로세스는 준비 큐 진입
실행 중이던 프로세스의 할당 시간이 끝나면 다시 준비 큐로 가서 대기
I/O 요구 프로세스의 경우 I/O가 완료될 때까지 I/O 큐에서 대기
I/O 완료 시 보조 큐로 이동
다음 번 프로세스를 선점할 때, 보조 큐에 있던 프로세스를 먼저 처리기에 실행
⇒ 단, 저번 실행 때 못하고 남은 시간 만큼만 실행하고 준비 큐 뒤로 가서 대기

SPN (Shortest Process Next)

⇒ 처리기(CPU) 관점의 Next, SPN = SJF

SJF (Shortest Job First)라고도 한다. ⇒ Queue 관점의 First
FCFS가 긴 프로세스를 우대하는 편향성 완화

선택함수 : min[s]

종료시까지 남아 있는 실행 시간이 가장 짧은 프로세스를 다음 실행할 프로세스로 선택
실행 시간이 짧은 프로세스가 (비록 늦게 도착 했더라도) 긴 프로세스들 보다 먼저 스케쥴링될 수 있다.

결정모드 : 비선점형

스케쥴링 분석

비선점 방식이기 때문에 시분할 시스템이나 트랜잭션 시스템에서는 바람직하지 못한 스케쥴링 정책
짧은 프로세스가 지속적으로 시스템에 진입한다면 이들보다 상대적으로 긴 프로세스가 기아 상태에 빠질 수 있음
사용자가 작업을 제출할 때, 프로세스 서비스 시간을 지정하는 일괄처리 시스템의 장기 스케쥴링에 사용 가능

SRT (Shortest Remaining Time)

⇒ SPN의 선점형 정책

선택함수 : min[s-e]

예상되는 남아있는 실행 시간이 가장 짧은 프로세스보다 다음 실행될 프로세스로 선택됨

결정함수 : 선점형

새로 도착한 프로세스의 예상되는 남아있는 실행 시간이 현재 실행중인 프로세스의 것보다 짧다면 늦게 도착했더라도 현재 실행중인 프로세스를 중단하고 곧장 선택됨

스케쥴링 분석

SPN보다 반환 시간 측면에서 우수
매 스케쥴링때 마다 프로세스들의 남아 있는 실행 시간을 평가해야 하는 부담 ⇒ Overhead
서비스 시간이 긴 프로세스가 기아 상태에 빠질 가능성

HRRN (Highest Response Ratio Next)

선택함수 : max[R=(w+s)/s]

w : 처리기를 기다리며 대기한 시간 (Process Age)
s : 예상되는 서비스 시간
준비 큐에 있는 프로세스 중 응답비율(R, 정규화된 반환시간)이 가장 큰 프로세스를 다음 번 프로세스로 선택

결정모드 : 비선점형

스케쥴링 분석

동일한 대기 시간(w)에 대해 서비스 시간(s)이 짧은 프로세스의 R값이 상대적으로 크기 때문에 짧은 프로세스를 우대하는 면이 있다.
동일한 서비스 시간(s)에 대해 대기 시간(w)이 큰 프로세스의 R값이 상대적으로 커짐
- 시스템에 오래 머문 긴 프로세스도 오래 머물면 머물 수록 R값이 커지기 때문에 홀대 받지는 않음

Feedback

프로세스의 예상되는 서비스 시간(s)을 알 수 없다면? ⇒ SPN, SRT, HRRN 스케쥴링 정책을 사용불가
짧은 프로세스에 대한 선호도를 높일 수 있는 방법
- 오랫동안 실행하고 있는 프로세스에게 단계적으로 불이익을 주는 것
- 남아 있는 실행 시간이 아닌 지금까지 실행한 시간에 관심을 두면 유사한 효과를 얻을 수 있음
- 다단계 피드백 큐 스케쥴링(Multi-Level Feedback Queue)라고도 한다.

선택함수

시스템에 진입하면 처음에는 우선순위가 가장 높은 준비 큐로 들어가 FCFS로 선택됨
실행 중 중단점(선점형, 강제 중단)을 만날 때마다 프로세스는 한 단계 낮은 우선순위의 준비 큐로 강등되어 진입
가장 낮은 우선순위 준비 큐에서는 라운드로빈 방식으로 스케쥴링됨
프로세스는 자신이 저장되어 있는 준비 큐보다 우선순위가 높은 준비 큐가 비었을 때 실행 선택됨

결정모드 : 선점형

피드백 스케쥴링

⇒ 새로 도착한 프로세스일수록, 짧은 프로세스일수록, 오래된 프로세스나 긴 프로세스보다 우대받는 정책

⇒ 상위 큐가 안비면 하위 큐에 대기하는 프로세스는 기아

스케쥴링 분석 (q=1)

스케쥴링 분석 (q=2^i, i는 index번호)

⇒ 프로세스 선점 시점을 RQ_i에 대해 2^i를 할당

Q0 = 2^0 = 1

Q1 = 2^1 = 2

Q2 = 2^2 =4

…

Qn = 2^n

⇒ 큐의 우선순위가 낮아질수록 할당 시간을 많이 주면 완료할 가능성이 높아짐, 기아를 줄일 수 있다.

실행 시간이 긴 프로세스는 기아 상태에 빠질 수 있다.

⇒ 해결책 : 대기 시간이 일정 시간 이상이 되면 우선순위가 더 높은 큐로 올려줌

공정-공유 스케쥴링 FSS(Fair-Share)

공정 공유란?
- 공정함을 나누어 갖는다는 뜻
- 공정성이란 할당된 가중치만큼 자원 사용
사용자 환경
- 시분할 시스템에서 부서별 사용자 그룹, 각 사용자는 단일 프로세스에 의해 표현될 때, 같은 부서 사용자가 실행시킨 프로세스들을 하나의 프로세스 집합으로 간주
- 스케쥴링은 각 부서에 비슷한 서비스를 제공한다고 가정
- 로그인해있는 사용자가 많은 부서의 프로세스는 차별을 당함
FSS의 목적은 사용자(사용자 그룹)에게 처리기 자원 중에 이 사용자가 사용할 수 있는 지분을 나타내는 가중치를 할당하여 처리기 사용률을 지분에 맞게 통제하는것.
- 프로세스 그룹의 실행 이력을 유지하여 나중에 각 그룹별 지분 할당을 위해 사용함
- 스케쥴링은 우선순위에 기반하여 진행됨
  - 프로세스별 우선순위
  - 최근 처리기 사용시간
  - 프로세스가 속한 그룹이 최근에 소비한 처리기 시간
세 개의 프로세스와 두 개의 그룹에 대한 예
- 각 그룹의 가중치 = 0.5
- 프로세스의 기본 우선순위 = 60
- 프로세스는 1초당 60번 인터럽트되고, 이 때 실행중인 프로세스의 CPU 사용량과 속한 GCPU 사용량은 증가함
- 우선순위는 초당 한 번씩 다시 계산됨

저작자표시 비영리

처리기 스케쥴링의 유형

장기 스케쥴링

중기 스케쥴링

단기 스케쥴링

단기 스케쥴링 알고리즘

단기 스케쥴링 평가 기준

기준 1: 사용자 중심 관점 Vs. 시스템 중심 관점

기준 2: 성능 중심 관점 Vs. 성능 외적 관점

우선순위 기반 스케쥴링

다양한 스케쥴링 정책

선택함수

결정모드

FCFS (First-come, First-served)

선택함수 : max[w]

결정모드 : 비선점형

스케쥴링 분석

FCFS 정책 하에서 평균 대기 시간은 최소가 아님

라운드-로빈 (Round-Robin)

선택함수 : 일정한 시간 할당량 종료

결정모드 : 선점형

라운드-로빈 스케쥴링 기법 동작 방식

스케쥴링 분석

시간 할당량의 길이가 라운드-로빈 성능에 미치는 영향

선점 시간 할당량의 크기가 스케쥴링에 미치는 영향

시간 할당량의 권장 크기

프로세스의 특징은 고려하지 않는 대신 매우 공평

I/O 중심 프로세스보다 CPU 중심 프로세스를 우대

가상 라운드-로빈 (VRR) 스케쥴링 방식

SPN (Shortest Process Next)

선택함수 : min[s]

결정모드 : 비선점형

스케쥴링 분석

SRT (Shortest Remaining Time)

선택함수 : min[s-e]

결정함수 : 선점형

스케쥴링 분석

HRRN (Highest Response Ratio Next)

선택함수 : max[R=(w+s)/s]

결정모드 : 비선점형

스케쥴링 분석

Feedback

선택함수

결정모드 : 선점형

피드백 스케쥴링

스케쥴링 분석 (q=1)

스케쥴링 분석 (q=2^i, i는 index번호)

공정-공유 스케쥴링 FSS(Fair-Share)

검색 태그

티스토리툴바