[운영체제] 5장 Process Scheduling

(어떠한 프로세스 먼저 수행시킬지 정하는 것, 기준필요)

-> 본격적 운영체제를 배움

기준 – 언제까지 해야 하나, 빨리 끝나는 것 먼저 수행, 포기한 과목은 뒤로 미룸...등등

 

프로그램, 프로세스 수행과정을 보여줌

I/O관련 이벤트 들어올 때 wait(현 프로세스)을 하는 이유

CPU에서 명령어 수행 I/O수행이 반복되면서 프로세스 수행

CPU burst – CPU가 명령어를 수행하는 구간(running 상태)

I/O burst – wait 상태에서 I/O가 끝날 때까지 기다리는 것(wait 상태)

프로그램이 수행될 때 위에 두 개를 번갈아감

 

 

CPU burst vs. I/O burst

CPU-bound Process - 프로세스에서 CPU burst가 길다.

I/O-bound process - 프로세스에서 I/O burst가 길다.

문서작성 프로그램, 영상재생 프로그램 -> I/O-bound process(우리가 사용하는 것의 대부분)

CPU-bound Process -> 슈퍼컴퓨터(기상예측 프로그램 – 자료를 불러오는 과정보다 계산과정이 더 김, 화학분석 프로그램, 알집과 같은 프로그램 – 살짝 애매하긴 함)

 

우리가 사용하는 프로그램의 burst시간을 측정해봄

대부분의 프로그램이 I/O-bound process라는 것을 보여줌

 

 

CPU Scheduler

각각의 프로세스방법에 따라 다른 Scheduling이 필요함

ready상태의 프로세스 중 어떤 것을 먼저 처리하는 게 좋을까? (기준이 뭘까?)

>I/O-bound process(우선권을 가짐) 사용자와 즉각적인 반응하기 때문에(일반적으로 우선권을 줌)

Time-Sharing에서 위와 같은 우선권을 부여함

 

Scheduling의 2가지 종류

두 가지 중 Short-term Scheduling을 대부분 사용 -> VM이 생겼기 때문

ready queue에 있는 프로세스 중 어떤 것을 먼저 사용할지 정함

CPU Scheduling – ready 상태의 프로세스 중 어떤 것을 CPU에 올려 수행을 시킬지 정하는 것

 

Dispatcher(행동) – CPU에 프로세스를 올리는 것

Scheduling(계획을 세우는 것) - CPU가 어떠한 프로세스를 수행할지를 정하는 것(정렬)

요즘엔 둘 다 합쳐서 Scheduling이라고 하기도 함

 

 

Preemptive(유명인에게 우선권을, 선점함) vs Non-preemptive(모두 평등하게, 구분x)

->사람 기준으로 하면 도덕적 문제가 있다고 생각함

->프로세스로 생각하면

어떤 프로세스가 CPU에서 수행되고 있을 때

중요한 프로세스가 ready상태로 올라왔다면 -> 더 중요한 프로세스를 진행함(Preemptive)

-> 현재 수행중인 프로세스를 계속 수행(Non-preemptive) - 현재 진행 중인 프로세스를 모두 수행하고 다음 프로세스를 수행함

결론적으로 Scheduling에서는 Preemptive가 훨씬 더 효율적임

 

 

Scheduling을 할 때 고려사항(고려하여 알고리즘을 만들어야 함)

• CPU utilization - CPU 사용률을 가능한 높이게 스케줄링을 해야 함
• Throughput – 단위 시간당 처리량(단위시간 당 많은 명령어를 수행하도록 스케줄링을 해야 함)
• Turnaround time – 어떤 프로세스가 모두 실행되고 돌아오는데 걸리는 시간(총 수행시간)
• Waiting time(wait queue에 들어가 있는 시간은 포함x) - ready queue에서 기다리는 시간
• Response time – 중간 중간 사용자에게 응답을 해주는 시간

이러한 시간관련 요소는 I/O Bound Process에서 더 중요함(time관련 요소들을 작게 해야 함)

CPU관련 Scheduling은 CPU utilization, Throughput를 고려해야함 (context switching을 최대한 적게 해야 함)

but I/O관련 프로세스에서는 context switching(오버헤드가 큼)을 많이 해야 시간이 줄어 듬

모두 만족시키는 것은 현재는 없음

하나가 좋아지면 하나가 나빠짐 -> 트레이드오프

 

시간과 관련된 것은 작게 해서 최적화시킴

 

스케줄링 원칙

- 공평분배가 필요

- 균형 있게 분배 필요

 

Batch system 고려사항 – 한 프로세스를 처리하는 것에만 집중(옛날 운영체제에 사용)

-> Throughput, Turnaround time, CPU utilization 이런 것들만 고려함

 

Interactive systems(ex. AI스피커, Desktop, 노트북) - 사용자와 어떤 것들을 주고받음

성능적인 능력보다는 사용자 기대를 충족하는 것이 스케줄링에 더 좋은 요소로 사용됨

->Response time, Waiting time, Proportionality

• Response time: minimize average time spent on wait queue
• Waiting time: minimize average time spent on ready queue
• Proportionality: meet users’ expectations

Real-time systems(특정 시간까지 수행을 완료해야하는 시스템)

->Meeting deadlines, Predictability

 

 

Scheduling Non-goals

스케줄링을 할 때 일어나서는 안 되는 것(ex. 어미 새(CPU)가 자식 새(ready queue에 있는 프로세스)에게 먹이를 물어다 주는 것)

Starvation(굶주림) - 스케줄링을 공평하게하지 못해서 생기는 문제(발생하지 않는 것이 좋음)

 

 

프로세스 스케줄링 알고리즘

프로세스 구분 2가지

CPU burst process – 연산위주 프로세스(기상청, 슈퍼컴퓨터와 같은 계산위주의 프로세스)

I/O burst process – I/O 작업 위주(대부분의 프로세스)

(12page)

프로세스 처리방식 2가지

preemptive – 선점형, 중요한 프로세스가 들어오면 하던 일을 멈추고 중요한 프로세스 먼저 수행함

non-preemptive – 비선점형, 현재하고 있는 작업을 마치고 이후작업 수행

이러한 프로세스 작업 시 고려사항들이 존재

공평분배가 필요함

균형있게 사용

 

오늘 배울 알고리즘은 위에 배운 사항들을 고려하여 어떻게 스케줄링을 하는지 결정하는 방식

 

ex) 데이터베이스 – 트랜잭션(하나의 작업을 수행하기 위해 필요한 데이터베이스 연산들을 모아둔 것)에 스케줄링가능

네트워크 – 패킷 스케줄링가능

-> 스케줄링자체는 여러 분야에 비슷하게 적용 됨

 

FCFS(First-Come, First-Served)

FIFO – 처음 들어온 것을 가장먼저 나간다.(Queue)

FCFS(First-Come, First-Served) – FIFO와 유사하게 가장 먼저 들어온 서비스를 가장먼저 수행함.

장점 – 가장 공평한 알고리즘임, non-preemptive -> starvation문제가 없음

단점 – waiting time을 가장 적게 하는 것이 좋은데 이 측면에서 좋지 못함. (앞 사람의 수행시간을 알 수 없음)

알고리즘 그림 예시1

Average waiting time 구하기

 

알고리즘 그림 예시2

Average waiting time 구하기

FCFS가 waiting time 측면에서 비효율적인

이러한 문제를 Convoy effect라고 함

 

 

SJF(Shortest Job First)

I/O burst process에서 유용하게 하려면 waiting time을 줄여야 쌍방향 소통이 원할 함.

SJF(Shortest Job First) - waiting time이 짧은 것을 가장 먼저 수행시키는 것(수행을 해야하는 것들 중 가장 짧은 것 우선 수행)

단점 - 공평하지 못함 -> 다음 process를 예측하기 어려움

>Non-preemptive – 양보 없이 현재진행중인 프로세스 수행(도착해서 기다리는 것 중에 짧은 것을 우선수행 but 이후에 이것보다 burst time이 짧은 프로세스가 와도 현재 진행 중인 프로세스를 수행함)

>Preemptive – 짧은 것을 먼저 양보하여 먼저 수행시킴(이후에 burst time이 짧은 프로세스가 온다면 교체를 해줌) -> SRTF

=> 도착시간을 기준으로 burst time을 비교해줌

 

SJF optimal(최적) - waiting time을 가장 작게 만들 수 있음

 

Non-preemptive-SJF 예시

 

Preemptive-SJF 예시

 

SJF방식을 실제 컴퓨터에 적용하기가 매우 어려움 - Burst(사용시간) 파악이 어렵다

따라서 실제 운영체제에 적용되어 사용x

무조건 optimal이라고 해서 사용되는 건 아님

 

위에가 실제 CPU burst time 밑이 예측 값

실제와 예측의 차이가 크다

 

Priority Scheduling

Priority Scheduling – 우선순위를 부여하여 수행하는 방식

-> 우선순위를 어떻게 줄 것인가?

사실 전부 우선순위 스케줄링이긴 함 -> 우선순위를 부여하는 방식이 다름

조건에 따라 우선순위의 중요도를 다르게 부여하여 처리함(ex. 백화점 VIP 대우)

-> but fair하지 못함...(우선순위가 낮은 프로세스들은 starvation이 발생함)

-> 해결방안 Aging방법 – 시간이 지날수록 프로세스에 나이를 먹이는 가중치를 두어 후순위로 밀리는 것을 방지시키는 방법

Priority queues -> 운영체제에서 합당한 방법이긴 하나 어떤 방식으로 적용될지를 알아야함

priority가 같은 것끼리 줄을 세우고 priority가 높은 것을 다 처리하고 그 밑에 있는 것들을 처리함

->같은 priority에 있는 프로세스들끼리는 time quantum을 두고 처리 -> 그러면 같은 priority안에서는 fair한 처리가 가능해짐 -> waiting time과 response time을 줄여주는 효과가 있음

 

 

Round Robin(RR)

Round Robin(RR) - time quantum을 두고 계속해서 다음 작업을 수행하게 넘어가게 하는 방식 -> time quantum을 다 사용하기 전에 I/O요청이 들어오면 다음 프로세스로 넘어감

I/O요청이 들어오지 않는다면 time quantum에 따라 다음 프로세스로 넘어감 -> 아주 공평

time quantum에 따라 성능이 변함 -> 프로세스를 전체 수행하는데 SJF보단 시간이 오래 걸리지만 반응속도는 빠름(RR이 SJF보다 turnaround time이 더 걸리는 이유는 프로세스가 변경됨에 따라 context switch 시간이 추가되기 때문임

 

RR(Round Robin) 방식 예시 -> time quantum = 20

 

RR예시

time quantum에 따른 context switches 발생 횟수 확인

time quantum 크게 하면 context switches에 따른 오버헤드가 줄어듬 -> CPU bound process에 유리

time quantum 작게 하면 context switches에 따른 오버헤드가 큼 -> I/O bound process에 유리(waiting time과 response time에서 매우 좋음)

장단점 동시 발생 -> Trade off -> 적절한 접점 찾기 필요

-> 해결을 위해서 중간정도의 절충안이 필요 -> CPU burst time평균보다 조금 더 크게 설정하는게 좋음

우리가 사용하는 프로세스에서 CPU burst가 60ms보다 조금 작음 따라서 time quantum을 60ms정도로 설정함

 

Problems of RR

RR은 time quantum에 영향을 받음

time quantum을 무한대로 하면 FIFO과 같아짐

time quantum을 0으로 하면 Processor sharing

A rule of thumb -> time quantum보다 CPU burst가 80%정도로 작아야함(이렇게 하는 것이 가장 효율적이었음)

time quantum을 적절히 조절하여 trade off 발생을 줄여줘야 함.

 

Combining Algorithms - 여러 가지 스케줄링 알고리즘을 섞어서 사용

 

 

Multilevel Queue 

Multilevel Queue – 큐를 하나가 아닌 여러 개를 두고 각각의 특성에 맞춰서 사용하는 것

-> 여러 개의 레벨의 그룹으로 나눔

운용체제에서는 사람들과 상호작용하는 앞부분 프로세스들을 백그라운드 프로세스부분보다 중요하다고 생각함

-foreground – RR -> 전면에서 작용하는 것을 담는 큐, interactive

-background – FCFS -> 백그라운드에서 작용하는 것을 담는 큐, batch

워드프로세스는 foreground queue에 속함 -> 사용자와 인터렉티브하게 상호작용하는 부분이 큼 -> RR이 적절함

background는 처리량을 극대화하는 FCFS를 사용하는 것이 적절함

위 두 개의 큐 사이에서는 어떻게 스케줄링 해야 하나?

반반 나눠서 하는 것이 있고 둘 중 우선순위를 두어서 하는 것이 있음(foreground 80%, background 20%)

 

Multilevel Queue Scheduling를 그림으로 보여줌

시스템에서 -> 각각의 프로세스에게 맞는 알고리즘을 부여해줌

프로세스별로 우선순위도 다름

 

 

Multilevel Feedback Queue

Multilevel Queue 단점

하나의 큐로 들어가게 되면 변경이 어려움(하나의 큐로 분류가 되면 다른 프로세스가 불가능)

스케줄링 오버헤드가 낮은 대신 유연하지 못함

Multilevel Feedback Queue – 위 문제를 해결하기 위해 나옴

-큐 사이에 이동이 가능

-다섯 개의 변수에 의해서 결정이 됨

• number of queues – 여러 개의 큐로 구성
• scheduling algorithms for each queue – 각 큐별로 스케줄링 알고리즘을 다양하게 사용가능

위에 두 개는 앞과 비슷함

• method used to determine when to upgrade a process(프로세스에서 위에 있는 우선순위로 격상가능)
• method used to determine when to demote a process(프로세스에서 아래 있는 우선순위로 이동가능)
• method used to determine which queue a process will enter when that process

needs service(프로세스가 어느 큐에 들어갈지를 결정)

starvation 문제가 발생할 수 있는 부분도 생김 -> aging방법으로 해결

 

Multilevel Feedback Queue 예시

모든 프로세스들이 우선 제일 우선순위가 높은 큐로 들어감

 

Multilevel Feedback Queue 그림 예시

 

 

UNIX Scheduler

canonical UNIX　scheduler

유닉스 역시 Multilevel Queue를 사용함

같은 priority에서는 RR로 동작을 함 -> 전 세계 모든 운영체제라고 봐도 무방함

 

 

 

Multiple-Processor Scheduling

FCFS부터 Multilevel Queue까지 알고리즘들의 특성과 예시적용이 가능하게 공부할 것

RR – fair하게 운영됨, time quantum 조절이 중요

싱글프로세스(CPU하나)에서 멀티프로세스(CPU 여러 개)로 넘어가면서 생기는 이슈 -> 수행을 하지 않고 놀고 있는 CPU가 등장하면 안 됨 -> load balance유지가 중요함

 

Multiple-Processor Scheduling

-> Symmetric multithreading (SMT) - 여러 개의 코어를 두어서 프로세스에 load balancing하는 방법

물리적으로 CPU가 하나인 것을 여러 개의 Logical CPU코어를 둠

-> load balancing이 중요함

 

 

Real-Time Scheduling

Real-Time – 제한시간 안에 반드시 수행을 완료해야하는 시스템(deadline을 지키는 것이 중요함)

Hard real-time systems (deadline을 만족시키지 못했을 때 컴퓨터에 큰 영향을 미치는 시스템)

• required to complete a critical task within a guaranteed amount of time

Soft real-time systems (deadline을 만족시키지 못했을 때 컴퓨터에 큰 영향을 미치지 않는 시스템)

• requires that critical processes receive priority over less fortunate ones

-> deadline을 잘 조정하는 것이 핵심

Static vs. Dynamic priority scheduling

• Static: Rate-Monotonic algorithm
• Dynamic: EDF (Earliest Deadline First) algorithm -> Deadline이 가장 빠른 것부터 처리하는 것 -> optimal한 방법임(가장 좋은 알고리즘)

 

 

Algorithm Evaluation

처음 만들어낸 알고리즘이 기존의 알고리즘보다 어떻게 좋은지를 평가 할 수 있어야함

평가방법 4가지

Deterministic modeling

• Takes a particular predetermined workload and defines the performance of each algorithm for that workload 

Queueing models

• Mathematical models used to compute expected system parameters

위 두 가지 방법은 수학적 방법임

Simulation -> 보통 일반적으로 많이 적용(시뮬레이터 – 어떠한 프로그램이 정해진 상황 속에서 어떻게 동작하는지 검증해주는 프로그램, 평가의 유용성, 경제적 이점, 문제 발생에 대한 피드백을 빠르게 진행할 수 있음)

• Algorithmic models which simulate a simplified version of a system using statistical input
• Trace tape (or trace data)
• Cf) Emulation

Implementation

• Direct implementation of the system under test, with appropriate benchmarks

 

시뮬레이션 검증 화면예시

시뮬레이션에서 사용되는 프로세스 -> 실제 프로그램을 수행시키고 trace tape(기록된 데이터)를 분석함

이미 수집된 데이터를 사용하여 여러 알고리즘에 적용해서 비교해봄

 

스케줄링 알고리즘 보충

FCFS(First-Come, First-Served) Scheduling – 프로세스가 들어온 순서대로 스케줄링이 됨

성능 분석 시 waiting time을 통해 측정을 함

SJF(Shortest-Job-First) Scheduling – 수행시간(burst time)이 가장 짧은 것부터 스케줄링이 됨

->선별적 수행(Shortest-remaining-time-first) - 우선순위가 더 높은 것이 들어온다면 그것을 우선순위로 수행시켜줌(이상적인 방법이지만 남은 프로세스 시간을 알 수 없기 때문에 구현하여 사용하기 어려움)

->비선별적 수행 – 중요한 프로그램이 들오면 현재 프로그램을 우선적으로 끝내고 다음으로 수행함

 

RR(Round Robin) Scheduling – 타임 퀀텀을 두어 프로세스들을 순환시켜줌(변경 시 context switch 시간이 추가되어 전체 수행시간이 길어짐)

Priority Scheduling – 각각의 프로세스에 우선순위를 부여하여 우선순위가 높은 것 높은 것을 우선적으로 수행함

 

real-time scheduling – 반드시 제한시간 내에 수행을 완료해야함 -> 그림참고

ex. 미사일 발사 시 목표물을 발견하여 시간 내에 폭발을 함

-> EDF – deadline을 살펴보고 가장 가까운 주기가 있는 프로세스 먼저 수행함

->그림예제참고