운영체제 - 반효경 #5 CPU Scheduling & Process Synchronization

unknownomad 2023. 4. 10. 15:04

# 5-1 CPU Scheduling

CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스를 통해 이번에 CPU 쓸 프로세스 선택

Dispatcher

CPU Scheduler 에 의해 선택된 프로세스에게 CPU 제어권을 넘김
= Context switch
= 문맥 교환

CPU 스케줄링이 필요한 경우 = 프로세스에게 아래와 같은 상태 변화가 있는 경우

Running ➡️ Blocked (ex. I/O 요청하는 시스템콜)
Running ➡️ Ready (ex. 할당 시간 만료로 timer interrupt)
Blocked ➡️ Ready (ex. I/O 완료 후 interrupt)
Terminate

비선점형	선점형
nonpreemptive	preemptive
강제로 빼앗지 않음	강제로 빼앗음

Scheduling Algorithms

FCFS (First-Come First-Served)
SJF (Shortest-Job-First)
SRTF (Shortest-Remaining-Time-First)
Priority Scheduling
RR (Round Robin)
Multilevel Queue
Multilevel Feedback Queue

Scheduling Criteria

Performance Index = Performance Measure = 성능 척도
시스템 입장의 성능 척도 = 최대한 일 많이 시킬수록 좋음
프로세스 입장의 성능 척도 = 고객 입장, 내가 CPU 얻어서 빨리 끝낼수록 좋음
시간 관련 성능 척도 = CPU 기준, CPU burst 기준으로 봐야 함

CPU utilization (이용률)

Keep the CPU as busy as possible
최대한 일 많이 시켜서 전체 일한 비율 높임

Throughput (처리량)

# of processes that complete their execution per time unit
Throughput = 처리량, 산출량
주어진 시간 동안 몇 개의 작업을 완료했느냐

Turnaround time (소요시간, 반환시간)

Amount of time to execute a particular process
CPU burst 가 다 끝나고 나갈 때까지 걸리는 시간
프로세스가 CPU 쓰러 들어와서 CPU 쓰고, I/O 하러 나갈 때까지 걸리는 시간

Waiting time (대기 시간)

Amount of time a process has been waiting in the ready queue
CPU 를 쓰려 해도 하나뿐이니 ready queue 에서 대기해야 함
순수하게 줄 서서 기다리는 시간
CPU 를 쓰다 뺏겨서 맨 뒤에 가서 줄 서는 대기시간들을 합친 총 대기시간
Running 시간까지 전부 합친 시간이면 turnaround time 이겠지

Response time (응답 시간)

Amount of time it takes from when a request was submitted until the first response is produced, not output
For time-sharing environment
Ready queue 에 들어와 처음으로 CPU 쓸 때까지 걸리는 시간

FCFS (First-Come First-Served)

먼저 온 순서대로 처리
비선점형 스케줄링
CPU 얻으면 이 프로세스가 직접 내줄 때까지 빼앗지 않음
CPU 오래 쓰는 프로그램이 CPU 계속 쓰게 되기에, 그다지 효율적이진 않음

Convoy effect = 짧은 프로세스들이 CPU 점유할 때까지 오래 기다려야 하는 현상

SJF (Shortest-Job-First)

각 프로세스의 다음 CPU burst time 을 가지고 스케줄링에 활용
CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄링
Average waiting time 최소화
짧게 쓰는 친구들을 먼저 CPU 쓸 수 있게 해줌

Non-preemptive

일단 CPU 를 잡으면 이번 CPU burst 가 완료될 때까지 CPU 를 선점(preemptive) 당하지 않음

Preemptive

현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 빼앗김
이 방법을 Shortest-Remaining-Time-First (SRTF) 라고도 부름
CPU 를 줬더라도 더 짧은 시간을 쓸 수 있는 프로세스가 오면 CPU 빼앗아 넘겨줌

SJF is optimal

주어진 프로세스들에 대해 minimm average waiting time 을 보장

Example of Non-preemptive SJF / Preemptive SJF

각 예시의 Average waiting time 결과 = 이 결과보다 더 짧은 average waiting time 은 구할 수 없다는 의미

Non-preemptive

0초 시점에 누구에게 CPU 줄지 결정해야

Preemptive

짧은 burst time 인 프로세스에게 CPU 빼앗아 넘겨줌

Priority Scheduling

A priority number (integer) is associated with each process
우선순위가 높은 프로세스에게 CPU 를 주겠다
Highest priority 를 가진 프로세스에게 CPU 할당(smallest integer = highest priority)
- Preemptive = 우선순위 더 높은 프로세스가 오는 경우
- Non-preemptive = 더 높은 우선순위가 오더라도 이미 CPU 할당했으니 기다려주자
SJF 는 일종의 priority scheduling
- Priority = predictd next CPU burst time
- CPU 사용량 가장 적은 프로세스에게 먼저 주니까
Problem
- Starvation = low priority processes may never execute
- = CPU 사용이 긴 프로세스는 영원히 CPU 를 못 받을 수도 있음
Solution
- Aging = as time progresses increase the priority of the process
- = 오래 기다릴수록 우선순위를 높여줘서 starvation 을 막아주자

다음 CPU Burst Time의 예측

tn = 실제 CPU 사용 시간
r(n+1) = n+1 번째 CPU 를 사용하고자 할 때의 예측시간
예측시간 = n 번째 실제 CPU 사용 시간과 n 번째 예측했던 CPU 사용시간을 일정 비율 곱해 사용
a + (1 – a) = 1
a 와 (1 – a) 둘에 일정 비율 적용하겠다는 의미

Exponential Averaging

SJF가 가진 Starvation 문제와 보완책

CPU 사용이 긴 프로세스는 영원히 CPU 를 못 받을 수도 있음, 즉, Long process = starvation
CPU 사용시간을 미리 알 수 없음 ➡️ CPU 사용시간을 추정할 수는 있음
과거 CPU 사용 흔적을 통해 이번에 얼마나 쓸지 예측(정확하진 않음) = Exponential Averaging

마지막 공식

최근에 진행된 CPU 사용시간일수록 가중치 높게 적용
오래 전 CPU 사용시간은 가중치 더 낮게 적용

Round Robin (RR)

각 프로세스는 동일한 크기의 할당 시간(time quantum) 가짐(일반적으로 10 - 100 milliseconds)
할당 시간이 지나면 프로세스는 선점(preemted) 당하고, ready queue 의 제일 뒤에 가서 다시 줄을 섬
n 개의 프로세스가 ready queue 에 있고, 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n 을 얻음 ➡️ 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
Performance
- q large ➡️ FIFO
- q small ➡️ context switch 오버헤드 증가
현대 컴퓨터는 모두 round robin 기반
응답시간이 점점 빨라짐 – 모든 프로세스가 CPU를 정해진 시간 동안 쓰게 되면서, 짧은 프로세스는 한번에 끝날 수 있고, 오래 걸리는 프로세스는 정해진 시간만큼 응답시간이 계속 줄어들게 됨
누구나 CPU를 맛볼 확률 높아짐

Example of RR

CPU 사용시간이 각자 다르거나 사용시간을 모를 때 round robin 유용
모든 프로세스가 기다렸다가 CPU를 마지막까지 조금씩 쓰고 동시에 빠져나감
Heterogeneous ➡️ why?

Time quantum 짧게 잡으면 모든 프로세스가 CPU를 쬐금쬐금씩 씀
Time quantum 크게 잡으면 동일하게 긴 시간 동안 CPU 사용하는 프로세스들 처리할 때 유용

# 5-2 CPU Scheduling 2

CPU-burst Time 의 분포

CPU scheduling 필요 이유

컴퓨터 시스템 안에 있는 job 들이 homogeneous 않고
I/O 처럼, 사람과 인터렉션하는 job 이나 CPU 와만 작업하는 job 들이 섞여있기 때문에 스케줄링이 쉽지 않음
그래서 FCFS 스케줄링 또한 쉽지 않음

FCFS (First-Come First-Served)

화장실 스케줄링
변비인 사람이 칸을 차지하면 super villain!

Round Robin (RR)

FCFS 같이 오래 기다려야 하는 스케줄링은 곤란
RR 은 컴퓨터 시스템에서 heterogeneous한 프로세스 스케줄링에 있어, 효율적 / 공정한 방법
CPU 를 주고 나서 무작정 쓰게 하는 게 아니라, 할당된 시간 미리 세팅해서 사용하게 하고, 그 시간이 지나면 다른 프로세스에게 CPU 넘겨줌
CPU 를 썼다, 뺏겼다를 반복
CPU 를 쓰는 시간 = 본인이 CPU 를 사용하려는 시간과 어느 정도 비례한다는 측면에서 공정한 스케줄링이라 볼 수 있음

Time quantum

주어진 시간, 할당 시간

RR 이 좋은 이유

Context 를 save 하고, 다시 CPU 를 얻었을 때 그 지점부터 재개할 수 있는 매커니즘이 제공되기에

Multi-level Queue

Ready queue

지금까지는 한줄로 줄을 서서 프로세스들이 CPU 를 사용했었는데
앞으로의 개념들은 여러 줄로 CPU 를 기다리는 줄서기를 하게 됨

Multi-level queue 의 줄서기 방식

Ready queue
- Foreground = interactive
- Background = 사람과의 interaction 없이, batch 처럼 CPU 만 쓰는

줄마다 우선순위가 있음
맨 위일수록 우선순위가 높음
시스템 프로세스 ➡️ 인터렉티브 ➡️ 약간 인터렉티브 ➡️ 배치(CPU 만 사용하는) ➡️ …
이 우선순위는 완전 계급제 = 우선순위가 높은 애들이 먼저 CPU 를 쓸 수 있고, 낮은 우선순위들은 이를 극복할 수 없음

Foreground, background 두 줄을 각각 세운 후, 각 줄마다의 순서도 정해야 하는데,

Foreground 에 줄 선 프로세스

사람과 interaction 하는 애니까 RR 써서 응답시간 짧게

Background 에 줄 선 프로세스

CPU 만 사용하니, 응답시간(interaction)이 빠를 필요 없음
그래서 중간에 CPU 를 얻었다 뺐었다 하는 context switching 이 없는, FCFS 방식이 좋음

Fixed priority scheduling

어떤 queue 에게 CPU 를 줄 것이냐 고민 ➡️ 아예 우선순위를 지정해보자
Starvation 발생하는 문제 있음

Time slice

CPU 시간을 적절하게 할당해주는

Multi-level queue는 어쨌든 RR에 비해 차별적임, 그래서 나온 게 Multi-level feedback queue

Multi-level Feedback Queue

현대사회같은 체제
출신이 낮아도 중간에 승격이 되기도 하는, 줄을 왔다갔다 할 수 있는 스케줄링

Multi-level queue나 multi-level feedback queue처럼 줄은 여러 개인데 CPU는 하나인 경우 고려사항

프로세스를 어느 줄에 넣을지
그 줄에 들어가 있을 때 무조건 우선순위가 높은 게 비어있지 않으면 그 줄에만 우선권을 주느냐, 그럼 낮은 우선순위는 starvation을 겪는데 이에 대한 해결책은?

Multi-level Feedback Queue 운영 방법

처음 들어온 프로세스는 가장 우선순위 높은 프로세스에 넣고, time quantum 을 짧게 줌(늘 1번 프로세스는 시간을 짧게 주기에 별도로 예측할 필요도 없음)
밑의 큐로 갈수록 그 다음 프로세스들은 round robin 에서 점점 긴 time quantum 을 주고
CPU burst가 짧은 프로세스는 맨 위의 큐에서 바로 할당시간 받고 빠져나갈 수 있는 거임
위의 큐가 비었을 때만 밑의 큐를 처리하는 방식이지만, 할당시간이라는 제한을 기반으로 스케줄링이 되는 것
CPU 할당시간이 짧은 프로세스에게 우선순위를 주는 방식
RR 만으로도 할당시간 분배가 잘 안 이루어지기에 multi-level feedback queue 써서 짧은 사용시간의 프로세스에게 먼저 할당해주는 것

Example of Multilevel Feedback Queue

Queue

위에 있을수록 할당시간 짧고
밑일수록 FCFS

Multiple-Processor Scheduling

CPU 가 여러 개 있는 경우의 스케줄링
EX) 화장실 칸이 늘어나는 경우 / 은행에서 은행 창구가 늘어나는 경우 등

Homogeneous processor

CPU 가 여러 개 있는데 어떤 job 은 특정 CPU 가 반드시 실행해야 하는 경우

Load sharing

CPU 가 여러 개 있으면 load sharing 이 잘 되어야 함
특정 CPU 만 일하고, 나머지는 놀면 안 됨
부하를 적절히 조절할 수 있어야 함
CPU 마다 한줄서기만 해야 하는 건 아님
별도의 줄(큐)을 서게 할 수도 있음

Symmetric multi-processing

모든 CPU 가 대등
각 CPU 가 알아서 스케줄링

Asymmetric multi-processing

CPU 가 여러 개인데, 그 중 하나의 CPU 가 전체 컨트롤(데이터 접근 / 공유 등) 담당

Real-Time Scheduling

Real-time job

데드라인이 있는, 정해진 시간 안에 무조건 끝내야 하는 job
먼저 CPU를 주는 그런 문제가 아니라, 시간 안에 끝내는 걸 보장해줘야 한다는 것

Hard real-time systems

데드라인 절대 보장

Soft real-time computing

다른 task에 비해 우선순위만 높여주는
데드라인 꼭 보장 못해도 됨
EX) 영화보기

Thread Scheduling

Thread

프로세스 하나 안에 CPU 수행 단위가 여러 개 있는 것

Local scheduling

User level thread
사용자 프로세스가 직접 스레드 관리, 운영체제는 스레드의 존재를 모름
운영체제는 그 프로세스에게 CPU 를 줄지 말지만 정하면 됨
할당받은 CPU 를 그 프로세스 내의 어떤 스레드에게 줄지 결정하는 것, 즉 내부에서 일어나는 일

Global scheduling

Kernel level thread
운영체제가 스레드 존재를 이미 알고 있는 상태
프로세스 스케줄링 하듯 알고리즘에 근거해 운영체제가 어떤 스레드에게 CPU 를 줄지 결정

Algorithm Evaluation

어떤 알고리즘이 좋은지 평가하는 방법
그림 속 server = CPU
CPU 용량에 따라 service rate (CPU 의 처리율) 결정됨

Queueing models

아주 이론적인 접근
도착율과 처리율 통해 확률 계산
실제 시스템에서 직접 돌리는 걸 더 의미있기 보기에, 이 개념은 이론적인 개념으로만 이해하자

Implementation & measurement

실제 시스템에 구현 후 돌려봐서 성능 측정
CPU 스케줄링 알고리즘을 내가 새로 만들었다 ➡️ 이를 평가하려면 ➡️ 실제 시스템에 구현
기존에 있던 스케줄러와 내가 작성한 스케줄러를 실제 작업(workload) 에 돌려봐서 성능 테스트
이는 운영체제 레벨의 접근이기에 결코 단기간에 되지 않고 어려운 작업임
그래서 쉬운 작업 할 수 있는 다른 방식이 있는데 그게 simulation

Simulation

CPU burst 와 I/O 작업이 빈번하며, 프로세스들이 왔다갔다하면 simulation 으로 가정해, 주어진 조건으로 돌려보는 것
실제 CPU burst pattern 에 적용해 simulation 돌리면 신빙성 높아짐
실제 프로그램 통해 추출한 input 데이터 = trace = 실제 시뮬레이션에 들어가는 인풋 데이터(추출도 가능)

# 5-2 Process Synchronization 1

데이터의 접근

컴퓨터 시스템 안에서 데이터가 접근되는 패턴
컴퓨터 시스템의 어떤 위치에 있던 간에 그림의 경로를 지나게 됨
Storage 에서 가져와 execution 처리 후 다시 storage 에 저장
보통 데이터를 읽기만 하면 다른 애가 읽어도 상관 없는데,
내가 데이터를 가져와 연산 후 그 데이터를 변경하면, 다른 애가 데이터 조회 시 synchronization 문제 발생

Race Condition

각각의 execution 에서 count ++, count– 되어버리면 Storage 내에서의 결과는 그냥 count 가 됨
여러 주체가 하나의 데이터에 동시 접근 시 race condition (경쟁 상태)

프로세스는 자기 자신만의 주소공간에 접근할 수 있지만
각 프로세스의 일부를 공유해 접근하는 공간에서는 sync 문제 발생할 수 있음

더 큰 문제는 운영체제 커널 관련 sync 문제

프로세스들이 직접 실행 못하고, 운영체제에 요청할 때 시스템콜을 하는데,
그럼 커널의 코드가 그 프로세스를 대신해 실행됨 = 커널의 어떤 데이터에 접근
또 커널 코드 실행 중에도 인터럽트 발생할 수 있음
인터럽트 코드 자체도 커널 코드임
이전 운영체제 커널이 실행 중이면서 데이터 건드릴 때 인터럽트 걸리면 인터럽트 코드를 실행할 텐데, 인터럽트 또한 커널의 코드이기에 어쨌든 커널의 데이터를 계속 건드린다는 것
근데 커널의 데이터는 공유 데이터이기에 문제 발생

OS에서 race condition은 언제 발생하는가?

Race condition 1

운영체제 커널이 cpu 에서 실행되고 있는데 count 변수를 ++ 해주고 있는 상태
이런 count++ 시키는 문장 = cpu 내부에서는 여러 개의 인스트럭션으로 진행됨
Count 라는 메모리 변수값을 1 증가시킨다
1. 메모리의 변수를 cpu 안의 레지스터로 불러들이고 = load
2. 그 레지스터 값을 1 증가시키고 = inc
3. 레지스터 값을 메모리의 변수의 위치에서 갖다 쓰는 순서 = store

Cpu 안의 레지스터에 접근할 때(load) 인터럽트 들어오면 인터럽트 핸들러가 작업 진행 ➡️ Count– 진행
이후 count++ 작업으로 돌아와 마저 수행해야 하는데,
그럼 count-- ➡️ count++ 순서가 되는데, 근데 결과값은 어떻게 되느냐?
Count– 작업 들어가기 전, count++ 는 이미 count 변수를 가지고 있는 상태
그렇기에 count– 작업과 상관 없이, count++ 가 load 단계에서 가지고 있던 오리지널 count 값에 ++ 한 결과값을 도출
마이너스 작업과 상관 없이, 값이 1 증가한 값만 반영됨
이게 바로 sync 문제!

위처럼 데이터 건드리고 도중에 인터럽트 발생할 수 있는 상황이면
도중 인터럽트가 될 수 없게 막고
먼저 하던 일 다 끝내서 저장한 이후 나머지 진행할 수 있게 함
한 마디로 순서를 정해주는 것임, 이 순서가 비효율적일 수 있기에 효율적인 방식으로 순서를 정해주는 것

OS에서의 race condidtion (1/3)

OS에서의 race condition (2/3)

Race condition 2

User mode ➡️ kernel mode ➡️ user mode ➡️ kernel mode ➡️ …
작업이 이런 식으로 왔다갔다 할 수 있는데
이때 cpu 를 독점 사용하지 않고, 할당 시간 만료되면 cpu 를 반납

문제

A가 본인 코드 실행하다 시스템콜로 커널에 요청해서 커널이 count ++ 작업 진행하던 도중, 이 프로세스에 할당된 시간이 끝남(count++ 가 끝나지 않은 것)
그럼 B가 자기 작업 진행하다 시스템콜로 커널에 요청했고, 그때 count ++ 실행
그럼 A는 아까 변수값 + 1 하려 CPU로 읽어들인 부분 그 다음의 인스트럭션을 실행하게 되는데, B에서 증가된 값은 반영 안 됨
B 들어가기 전 A에서 count 증가 작업이 시작됐기에, B 작업에서 증가한 건 반영되지 않음
Sync 문제 발생!

해결책