운영체제 07

zh025700·2022년 4월 15일

운영체제

목록 보기

6/20

운영체제

7) 스케줄링: 개요

프로세스 스케줄링이란?

레디 큐에 속해있는 프로세스 중 어떤 것을 다음에 실행할것인가 / OS가 결정
- 레디큐안에 cpu 권한이 없는 프로세스들이 들어가있음(나머지는 다 있음)
multi programmed OS의 기초
CPU 스케줄링 or 잡 스케줄링 이라고 불린다.(스레드 스케줄링)

어떤 스케줄링이 좋은 것인가?

다양한 스케줄링 평가 척도가 있음
- User-oriented
  - TAT, response time, Deadline
- System-oriented
  - Throughput,Processor utilization
- 공정성(특정 프로세스가 오래 방치되는거 막기), 자원을 공평하게, 우선 순위 적용, 예측
모든 척도를 동시에 최적화하는 것은 불가능
- 좋은 Response time -> 빈번한 context switching -> 오버헤드 늘림 -> 안좋은 system throughput

스케줄링 기준

CPU utilization - 최대화

CPU가 항상 일을 하도록
- 실제 시스템에선, 40~90 % 효율을 낸다

Throughput - 최대화

시간 단위당 작업 수
throughput은 responsetime과 관련이 있다, 그러나 동일하진 않음!
- response time을 줄이면 thourghput만 최대화하는 것 보다 더 많은 context switch를 일으킴
throughput을 올리는 두가지 방법
- 오버헤드 줄이기( ex) context switch)
- 자원 사용을 효울적이게(CPU,disk,memory 등등)

Turnaround time - 최소화

프로세스가 시작에서 완료까지의 시간 간격
대기시간(레디큐에서 대기하는 시간 등),CPU 실행시간, 입출력 시간을 포함해야함

Waiting time - 최소화

레디큐에서 총 대기하는 시간
CPU의 스케줄링 기법은 프로세스 실행시간, 입출력 시간에는 영향을 주지 않음
- 단! 오직 레디큐에서의 waiting time에 영향을 끼침!

Response time - 최소화

요청 시작부터 첫 번째 응답이 생성될 때까지의 시간
interactive system의 중요한 기준
response time은 사용자에게 표시되는 시간
- 에디터에서 타자를 에코하는 시간
- 프로그램을 컴파일하는 시간
- real-time Tasks: 마감일을 지켜야 한다.

Fairness

공정한 방식으로 유저 간 CPU를 공유한다
fairness는 평균 response time을 최소화하지 않는다
- 시스템을 덜 공평하게 만들어 평균 응답 시간 개선!

QOS

평균 response time을 최소화하는 것보다 response time의 분산을 최소화하는 것이 더 중요.
- QOS(quality of service)
- predictability와 연관

response time은 빠른것을 의미하는게 아니다.
특정 deadline을 넘기지 않는 시스템이다.

Process Scheduling

response time,throughput, fairness 및 프로세서 효율과 같은 시스템 목표를 충족하는 방식으로 프로세서에 의해 실행될 프로세스를 할당하는 것
3 기능으로 나뉘어짐
- Long-term scheduling
  - 어떤 프로그램이 실행될지 결정하는 것
  - 멀티 프로그램이의 정도를 조절
- Mid-term scheduling: 메모리와 디스크 사이
  - swapping 기능의 일부
- Short-term scheduling: 레디큐와 메모리 사이
  - dispatcher라고 불림
  - 빈번히 실행됨
  - 어떤 프로세스가 다음에 실행될지 최적의 결정을 함
    - 롱텀과 다름!! 이건 프로세스 롱텀은 프로그램!!

스케줄링 용어

Non preemptive 비선점 스케줄링

 프로세스가 실행이 되면, 해당 프로세스는 자발적으로 CPU 권한을 포기할때까지 cpu 권한을 유지

EX) 종료, 입출력으로 인한 block, 시스템콜
장점
- 낮은 switch context 오버헤드
- 개발 쉬움 => 간편한 시스템에 사용됨
단점
- 빈번한 priority 역행
- 평균 response time 증가

Preemptive 선점 스케줄링

CPU는 실행 중인 프로세스의 의도와는 무관하게 다른 프로세스를 실행시킬 수 있다.
OS가 프로세스를 멈출 수 있다.

time sharing 시스템, real time 시스템에 사용
OS 커널 설계에 영향을 줌
장점
- 유연함, 적응성있음, 성능 향상
단점
- 높은 context switch 오버헤드
- 공유 데이터에 대한 접근과 관련된 비용이 발생(프로세스 동기화)

S/W 오버헤드가 H/W 구동시간보다 훨씬 크다

CPU burst & I/O Burst

프로그램은 CPU 실행 주기와 I/O 대기 시간을 번갈아 사용
- 프로그램은 일반적으로 일정 시간 동안 CPU를 사용한 다음 I/O를 실행한 다음 CPU를 다시 사용.

CPU burst time: CPU 실행의 사이클

CPU가 프로세스를 실행하는데 걸리는 시간

I/O burst time: I/O 대기 사이클

프로세스가 I/O operation을 수행하는데 걸리는 시간

CPU burst, I/o burst 시간의 분배는 적절한 스케줄링 알고리즘 선택하는데에 중요하다

CPU burst 시간 분배는 보통 지수로 표현됨

I/O bound process
- 많은, 짧은 CPU burst를 지님
  - 프로세스 실행 도중 I/O 요청이 많음을 뜻함
CPU bound process
- 적은, 긴 CPU burst를 가짐
  - CPU 권한을 오래 들고 있어야한다.

스케줄링: introduction

스케줄링을 위해서
- 무엇을 가정해야하는가?
- 어떤 기준으로 평가를 해야하는가?
- 초기에는 어떤게 사용되었는가?

프로세스가 동작하는 일련의 행위를 워크로드라고 한다.
적절한 워크로드는 스케줄링 개발에 매우 중요하다.

작업 == 프로세스 라고 치겠다

Workload

지정된 기간 동안 프로세서에서 실행 중인 프로세스 수 ??? 맞냐??

workload 가정

모든 작업은 같은 시간 동안 실행된다(CPU burst time이 같다)
모든 작업은 동시에 도착
작업은 시작하면 종료될때까지 실행됨(non-preemptive)
모든 작업은 CPU만 사용(즉, 입출력 사용 안함)
각 작업의 실행시간은 사전에 알려짐

일단 스케줄링 조건을 쉽게 만들기 위해 가정을 하자
모두 비현실적인 조건들

스케줄링 평가 항목

평가 기준: Turnaround time(TAT)
- 작업이 완료된 시각에서 작업이 도착한 시각을 뺀 시간
- 작업을 요청하고나서 완료되는 시간

TAT = 완료된 시각 - 도착한 시각

fairness
- 성능과 공정성은 상충함
  - ex) 전체 시스템 성능 극대화를 위해 몇몇 작업에 기회를 안 줄 수 있음

FIFO first in first out 선입 선출

FCFS(first come first served)라고도 불림
- Non-preemptive
- 개발하기 매우 쉽고 간편함
짧은 프로세스보다 긴 프로세스의 대한 성능이 훨씬 우수
I/O-bound 프로세스보다 cpu-bound 프로세스를 선호
- non-preemtive하니깐
-> 낮은 CPU, device 이용 시스템에서 사용됨

Ex

A,B,C,가 거의 동시에 도착 (도착시간 = 0)
간발의 차이로 A,B,C 순서로 도착
각 작업은 10초간 진행 그렇다면 이 작업들의 평균 TAT시간은??

실행 순서
A->B->C

A TAT = 10 - 0 = 10sec
B TAT = 20 - 0 = 20sec
C TAT = 30 - 0 = 30sed

ave = (10+20+30)/3 = 20 sec

가정 1번을 풀자, => 작업시간이 모두 같지 않다(CPU burst time이 다르다)
그럼 FIFO는 좋은가..

Ex

A,B,C,가 거의 동시에 도착 (도착시간 = 0)
간발의 차이로 A,B,C 순서로 도착
A 실행시간 = 100sec
B,C 실행시간 = 10sec
평균 TAT?

실행 순서
A->B->C

A TAT = 100 - 0 = 100sec
B TAT = 110 - 0 = 110sec
C TAT = 120 - 0 = 120sec

ave = (100+110+120)/3 = 110sec

엥 TAT 급 증가!! B C가 짧은데 A때매 기다리네!!

Convoy effect

CPU를 많이 필요하지 않는 프로세스들이 CPU를 오래 사용하는 프로세스가 끝나기를 기다리는 현상

짧은 프로세스가 긴 프로세스 뒤에서 기다린다

B,C가 A보다 먼저 끝나면 TAT는 줄텐데...
어떠캐 해결??

SJF(shortest job first) 최단 작업 우선

가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다
- Non-preemptive이다
- 짧은 프로세스가 큐의 맨 앞으로 온다

아까의 Ex에 SJF를 적용해보자

실행 순서
B->C->A

A TAT = 120 - 0 = 120sec
B TAT = 10 - 0 = 10sec
C TAT = 20 - 0 = 20sec

ave = (10+20+120)/3 = 50sec

=> SJF는 TAT를 110sec에서 50sec로 향상시켰다.

모든 작업이 동시에 도착한다면 SJF가 최적의 스케줄링 기법일 것이다.
그럼 가정 2번을 풀자
작업은 모두 동시에 오지 않고 임의의 시간에 도착할 수 있다

이렇게 되면, 실행시간이 100초인 A가 실행 중 일때 실행시간이 10초 걸리는 B,C가 도착한다면..?
SJF는 Non-preemptive하기때문에 A가 다 끝나고 B,C가 실행된다.

=> 또다시 convoy effect가 발생!!

STCF(shortest time to completion first) 최소 잔여시간 우선

위의 문제를 해결하기 위해 가정 3을 풀자, 작업은 실행 도중 멈출 수 있다.
여기에 타이머 인터럽트와 context switch가 가능하다면!!
그렇다면 B,C가 도착했을 떄 실행 중이던 A를 멈추고 B나 C를 실행할 수 있다.
그리고 A는 나중에 다시 실행될 것이다.

SJF에 preemptive를 추가한 기법이다 STCf
PSJF(preemptive shortest job first)라고도 불린다.
새로운 프로세스가 도착하면 현재 실행중인 프로세스와 새 프로세스의 잔여 실행시간(CPU burst)을 비교해, 가장 작은 프로세스를 스케줄한다.

새 작업 추가
남아있는 작업과 현재 작업을 비교
더 적게 남은 작업을 스케줄

EX

A는 0초에 도착 100초의 실행시간
B,C는 10초에 도착, 10초의 실행시간

실행 순서
A->B->C->A

A TAT = 120 - 0 = 120sec
B TAT = 20 - 10 = 10sec
C TAT = 30 - 10 = 20sec

ave = (10+20+120)/3 = 50sec

더 긴 프로세스에 대한 starvation 가능성
이 방법을 하려면 각 프로세스의 실행시간을 알아야한다, 적어도 예측해야함!!
- 과거로 예측

새로운 평가기준 Response time(응답시간)

작업의 길이를 미리 알고, 작업(프로세스)가 CPU만 사용하고 평가기준이 TAT 뿐이라면 STCF는 훌륭함.

그러나 time slice 기법이 나오고 나서 그렇지 않게됨

response time 이라는 척도가 생겼다

STCF는 좋은 response time을 줄 수 없다
- TAT는 좋아도 response time, 상호작용 에는 안좋음

Response time

response time = 처음 프로세스가 시작한 시간 - 도착한 시간

이제 어떻게 response time을 줄일까??

Round Robin(RR) 라운드로빈 스케줄링

작업이 끝날때까지 기다리지 않는다.
대신 일정시간(time slice, scheduling quantum) 동안 실행 후 Run 큐의 다음 작업으로 전환한다.
타임 슬라이싱이라고도 볼림

time slice에 맞춰 작업을 수행하며 run queue에 있는 다음 작업과 스위치한다
- time slice는 time quantum이라고 불리운다
일이 끝날때까지 반복한다
time slice의 길이는 timer-interrupt 주기의 배수여야 한다
- 10msec마다 인터럽트를 발생시키면 타임슬라이스는 10msec의 배수여야한다

Ex response time, TAT

A,B,C가 같은 시간에 도착
5초씩 실행시간(CPU burst)

SJF에선

실행 순서
A->B->C

response

A  = 0 sec
B  = 5 sec
C  = 10 sec

ave response = (0 + 5 + 10)/3 = 5sec

TAT

A TAT = 5 - 0 = 5sec
B TAT = 10 - 0 = 10sec
C TAT = 15 - 0 = 15sec

ave TAT = (5+10+15)/3 = 10 sec


RR (time-slice 1sec)에선

실행순서

(A->B->C) 1sec씩 실행

A  = 0 sec
B  = 1 sec
C  = 2 sec

ave response = (0 + 1 + 2)/3 = 1sec

TAT

A TAT = 13 - 0 = 13sec
B TAT = 14 - 0 = 14sec
C TAT = 15 - 0 = 15sec

ave TAT = (13+14+15)/3 = 14sec

response 시간에서 좋다

RR은 공정하다, 그러나 TAT와 같은 기준에는 좋지 않다

RR은 가능한 작업을 늘리는 것이 목표 TAT는 작업 완료 시간만 고려하기때문에 좋지 않음
RR과 같은 공정한 기법들은 response time과 같은 평가 기준에서 나쁨

공정성이 좋으면, response time 좋음, TAT 나쁨
공정상 낮음, response time 낮음, TAT 좋음

time slice가 짧을수록 여러 프로세스를 더 빠르게 접근 가능하니 response time 기준 성능이 더 좋아진다.
하지만.. 과연 time slice를 무턱대고 짧게 하는 것이 좋을까??

짧은 Time slice는 문제를 일으킨다!

너무 짧으면 context switch가 전체 성능에 큰 영향을 끼친다
레지스터에 저장/ 복원과 함께 CPU 캐시 ,TLB 등 하드웨어에도 프로세스와 관련된 다양한 정보들이 있다.
이 갱신 작업이 큰 비용을 유발한다..

그래서 너무 context switch 비용을 상쇄할 수 있을 만큼 길어야 하지만 너무 길면 좀...

Time slice 길이의 중요성

짧은 Time slice
- 좋은 response time
- context switching이 전체 성능을 좌우
긴 Time slice
- switching 비용을 줄인다
- 낮은 response time

response time과 context switching으로 인한 성능 하락등의 trade off를 잘 계산해야한다

Incorporating I/O 입출력 연산의 고려

이제 가정 3도 풀어보자. 모든 프로그램은 입출력 작업을 수행할 것이다. 당연하다.
현재 실행중인 프로세스가  입출력 작업을 요청하면
스케줄러는 다음에 어떤 프로세스를 실행해야할지 고려해야한다.
 왜냐면 입출력 요청을 한 프로세스는 입출력이 완료될때까지
  CPU를 사용하지 않을 것이기 때문이다.

입출력 요청을 한 프로세스는 입출력 완료를 기다리며 wait status로 가고,
 입출력이 하드디스크로 간 뒤 프로세스는
  현재 입출력 워크로드에 따라 좀 더 block될 것이다.
그럼 이 시간동안 CPU를 이용할 다른 프로세스를 스케줄러가 골라야한다.

스케줄러는 입출력이 끝나면 또 결정을 해야한다.
입출력이 완료되면, 인터럽트가 발생되고
OS가 입출력을 요청한 프로세스를 wait status에서 ready state로 옮긴다.
 이제 어떤 프로세스를 실행할지 스케줄러가 골라야한다.

EX

A와 B는 50msec의 CPU 시간(CPU burst)을 필요로 한다.
A는 10msec 실행 후 입출력을 요청하고 입출력은 10msec이 걸린다.
B는 입출력을 하지 않는다.
스케줄러는 A를 먼저 실행한다.

STCF 방식

A->B

A가 끝나기전에 B를 실행하지 않는다. 그래서 A 입출력 시간에 CPU가 놀게 된다 비효율적이다
RR 방식

A->B(A입출력)

하지만 RR방식은 A가 입출력 중일 때 B가 CPU를 사용할 수 있다. CPU가 더 효율적으로 동작한다

작업이 입출력을 요청할 때
- 작업은 입출력이 끝날때 까지 블락 된다
- 스케줄러는 다른 작업을 CPU에 할당한다
입출력이 끝났을 때
- 인터럽트 발생
- IS는 프로세스를 ready state로 만들고(레디큐로감) 프로세스는 OS에 의해 스케줄링될 때까지 기다림

zh025700

정리

이전 포스트

운영체제 6)

다음 포스트

운영체제 07

운영체제

운영체제

7) 스케줄링: 개요

프로세스 스케줄링이란?

어떤 스케줄링이 좋은 것인가?

스케줄링 기준

CPU utilization - 최대화

Throughput - 최대화

Turnaround time - 최소화

Waiting time - 최소화

Response time - 최소화

Fairness

QOS

Process Scheduling

스케줄링 용어

Non preemptive 비선점 스케줄링

Preemptive 선점 스케줄링

CPU burst & I/O Burst

CPU burst time: CPU 실행의 사이클

I/O burst time: I/O 대기 사이클

스케줄링: introduction

Workload

workload 가정

스케줄링 평가 항목

FIFO first in first out 선입 선출

Convoy effect

SJF(shortest job first) 최단 작업 우선

STCF(shortest time to completion first) 최소 잔여시간 우선

새로운 평가기준 Response time(응답시간)

Round Robin(RR) 라운드로빈 스케줄링

Time slice 길이의 중요성

Incorporating I/O 입출력 연산의 고려

운영체제 6)

운영체제 09

0개의 댓글

관련 채용 정보