운영체제#5

LeeMir, 29 March 2021

2강 - Processes and Threads(이어서)

Monitor

Monitor라는 객체를 예로 들어 Producer-Consumer Problem을 해결
Monitor라는 객체에는 Producer라는 메쏘드와 Consumer라는 메쏘드가 존재
- 컴파일러는 각 메쏘드를 동시에 실행하지 않음
- 쓰레드가 병렬로 실행되더라도 각 쓰레드가 부르는 메쏘드는 병렬로 실행되지 않음
  - 따라서 Mutex를 이용해 상호 배제를 고려할 필요 없음

Producer-Consumer with Hoare

Producer가 먼저 실행되는데, 실행되자마자 Consumer를 깨우고 Consumer로 턴을 넘김
sleep(wait)에서 깨어날 때 if문으로 조건을 따짐
- if문이므로 깼을 때 if의 조건을 확인하지 않고 그냥 바로 다음 코드를 읽음(깨울 때 if문의 조건에서 탈출했으므로 깨운다는 생각)
- 단, 깨운 코드가 끝나자마자 깬 코드가 바로 실행되어야함

Producer-Consumer with Lampson & Redell

sleep(wait)에서 깨어날 때 while문으로 조건을 따짐
- 깼을 때 while의 조건을 한번 더 확인해야 while문을 나갈 수 있으므로 오류 예방

Producer-Consumer in Java

메쏘드에 synchronized를 사용
- 동시에 실행하지 않는다는 의미

Lock-Free Data Structure

CPU에서는 Atomic CAS(Compare-and-Swap) Operation을 지원
- Lock을 사용하면 코어가 많아질수록 병목 현상이 심해짐
- Lock 대신 CAS를 사용해 병목 현상을 해결
- CAS : Compare and Swap을 하는 함수
  - Swap에 성공하면 True, 실패하면 False를 반환함(실패하는 원인 : CAS하고자 하는 메모리를 다른 코어에서 접근해서 수정함)
  - while문의 조건으로 들어가서 될 때 까지 실행
ABA Problem
- 하나의 쓰레드가 CAS를 실행하는 도중에 다른 쓰레드가 실행되어 CAS를 먼저 함
- (스택을 예로 들음) 이 때 head는 변경되지 않아 CAS가 False를 반환하지 않으나, 다른 쓰레드에서 head를 제외한 다른 노드들의 연결 상태를 변경해버렸을 경우 처음 실행되고 있던 쓰레드가 이미 Free된 노드를 head가 가리키게 만들 수도 있음

Message Passing

가장 일반적인 경우 : Nonblocking send, Blocking receive
- 다만 이 때 Message들을 Queue에 저장해놔야함(유한함)
- 운영체제에서 해줌
Addressing
- Message를 보낼 때 목적지의 주소를 프로세스 ID로 하는 것은 프로그램을 작성할 때 동적으로 생성되는 프로세스 ID를 모르므로 불가능함
- Mailboxes라는 다수의 Queue를 만들어 이를 Sender의 목적지로 활용함
  - Receiver는 그 Queue에서 Message를 받으면 됨

Producer-Consumer with N Messages

Sender를 Producer로, Receiver를 Consumer로 생각
Sender와 Receiver에 각각 Message를 담아둘 수 있는 Queue가 존재
- Queue가 비어있으면 자동으로 Sleep
Message가 담겨있지 않은 데이터 껍데기를 Sender의 Queue에 저장
- Sender에서는 Message 내용을 적은 후 Receiver의 Queue로 전송
- Receiver에서는 Queue에 있는 Message를 읽은 후 다시 빈 껍데기로 만들어 Sender의 Queue로 보냄

Barrier

모든 쓰레드가 특정 순간에 끝나있어야하는 순간이 존재할 때 Barrier 연산을 사용해 먼저 끝난 쓰레드가 나중에 끝나는 쓰레드들을 기다리게 함

Scheduling

스케줄링 시점
- 프로세스가 생성될 때
- 프로세스가 종료할 때
- 프로세스가 I/O, 세마포어, 다른 무언가로 대기할 때
- I/O 인터럽트가 발생할 때
- 선점형(preemptive) 스케줄링 알고리즘의 경우 클럭 인터럽트가 발생할 때
스케줄링 오버헤드(문맥교환비용)
- 모드 변경비용(사용자->커널->사용자)
- 프로세스 문맥 저장, 복구
- 메모리 맵 저장 복구
- CPU 캐쉬 무효화
- 기타
- 스케쥴링을 할 때, 하나의 코어에서 여러 쓰레드를 실행하면 문맥교환비용때문에 오히려 손해일 수 있음
  - 따라서 하나의 코어에서 하나의 쓰레드만 실행하는 것이 가장 바람직함
CPU-Bound Process : 프로세스가 실행되는 시간의 대부분이 CPU가 계산하는 시간인 프로세스
I/O-Bound Process : 프로세스가 실행되는 시간의 대부분이 I/O인 프로세스(한글)
- I/O-Bound Process가 CPU-Bound Process보다 우선순위가 높음
- 이유 : I/O-Bound Process는 CPU가 계산하는 시간이 매우 짧고 I/O를 기다리는 시간이 길기 때문에 그 시간동안 CPU-Bound Process가 계산을 할 수 있어 자원을 사용하는 효율이 커짐
Type of Scheduling
- Long-term scheduling
  - 프로세스를 실행할지말지 딜레이를 줘서 결정
- Medium-term scheduling
  - 현재 실행되고 있는 프로세스가 너무 많으면 몇 개 프로세스를 지정해 Ready, Suspend / Blocked, Suspend 상태가 되게 함
  - UNIX에서는 이 과정을 Swapping이라고 부름
- Short-term scheduling
  - Ready 상태의 프로세스들 중에 하나를 골라서 실행하게 함

Scheduling Algorithm Goals

All systems
- Fairness
  - 각 프로세스들에게 CPU 시간(자원)을 공정하게 나눠야 함
  - 동일하게 배분하는 것이 아니라, 프로세스의 중요도에 맞게 나눠야 함을 의미
- Polucy enforcement
  - 정책을 만들어 집행할 수 있어야 함
- Balance
  - 어떤 시스템도 비지 않게 균형을 맞춰야 함
Batch systems
- Throughput
  - 시간당 몇 개의 작업을 끝냈는지
- Turnaround time
  - 작업을 제출하고 종료하는 사이의 시간을 얼마나 줄일 수 있는지
- CPU utilization
  - 얼마나 CPU를 안놀게 하는지
Interactive systems
- Response time
  - 입력에 대한 반응이 얼마나 빠른지
- Proportionality
  - 사용자의 기대치를 충족해야 함
Real-time systems
- Meeting deadlines
  - 프로세스마다 입력으로부터 계산 후 출력까지 얼마나 걸리는 지 시간(Deadline)이 정해져 있어 그것을 지켜야 함
- Predictability
  - multimedia system에서 1초에 몇 프레임을 실행하는지 예측이 가능해야 함

Scheduling in Batch Systems

Batch System은 과거에, 평소에 실행되기 때문에 시간이 얼마나 걸리는 지 통계를 낼 수 있어 예측도 가능함
First-come First-served
- 단순히 먼저 들어온 프로세스부터 처리
- Turnaround time과 Waiting time의 평균을 고려하면 비효율적인 방법임
  - Waiting time : 프로세스가 도착한 시간으로부터 프로세스가 실행하기 시작될 때까지 걸리는 시간
Shortest job first
- 프로세스의 Service Time이 작은 순서대로 처리
- non-preemptive 방식
  - 한번 실행 시작한 프로세스는 중단하지 않고 실행
Shortest remaining time next
- Shortest job first를 preemptive하게 바꾼 방식
  - 실행 중인 프로세스의 남은 시간보다 Service Time이 작은 프로세스가 있을 경우 현재 프로세스를 중단하고 그 프로세스부터 처리
- 평균 Turnaround time과 Waiting time이 앞 두 방식보다 효율적임
- Starvation 문제를 야기할 수 있음
  - Service Time이 매우 큰 프로세스의 경우 아무리 앞서 들어왔다해도 무한정 대기만 할 수 있음
  - HRRN으로 해결
Highest Response Ratio Next(HRRN)
- Response Ratio가 큰 프로세스를 먼저 처리
  - Response Ratio = (time spent waiting + expected service time) / expected service time

Scheduling in Interactive Systems

Round-Robin Scheduling
- 프로세스들을 Time Quantum에 따라 순서대로 번갈아가면서 처리함
- Interactive System에서는 사용자의 입력에 대해 빠른 반응이 필요함
- I/O-Bound Process의 경우 본인에게 할당된 Time Quantum을 다 쓰지 못하고 I/O로 넘어감
- Virtual Round-Robin
  - I/O-Bound Process가 I/O로 넘어갔다가 Ready Queue로 가지 않고 Auxiliary Queue로 이동함
  - Auxiliary Queue가 Ready Queue보다 우선순위가 무조건 높음
  - Auxiliary Queue에서 나온 프로세스는 그 이전에 본인이 다 사용하지 못한 Time Quantum을 사용함
  - 만약 Time Quantum을 다 썼을 경우에는 Ready Queue로 가게 함으로써 CPU-Bound Process와 I/O-Bound Process를 효율적으로 처리할 수 있음
Priority Scheduling
- 프로세스마다 우선 순위가 존재
- 우선 순위마다 Ready Queue가 각각 존재
- Processor는 우선 순위가 높은 Queue에서 프로세스를 가져와서 실행함
- 한 프로세스가 처음에는 우선 순위가 낮더라도 입출력을 요구하면 우선순위를 높게 함
- Starvation 문제가 발생할 수 있음
  - 우선순위가 매우 낮은 프로세스가 있을 경우 입출력 프로세스에 밀려 영원히 실행 안될 수 있음
  - Aging mechanism으로 방지
    - 오랫동안 실행이 안됐으면 우선순위를 하나씩 높여줌
Short Process Next
- 실행 시간이 짧은 프로세스를 먼저 실행
- 실행 시간은 과거 통계를 기준으로 예측
  - 통계는 실행 환경이 달라짐을 고려해 산술평균이 아닌 Exponential Averaging을 이용해 산출함
    - Exponential Averaging : 과거의 평균과 최근의 값에 각각 가중치를 따로 부여해 평균을 냄
Guaranteed Scheduling
- N개의 프로세스들에게 1/N의 Processor time을 부여
Lottery Scheduling
- 프로세스별로 당첨확률을 부여한 후, 추첨을 통해 뽑힌 프로세스가 실행
- 프로세스들의 비율을 조정할 수 있는 장점이 있음
Fair-share Scheduling
- 프로세스들을 Group으로 묶고 Group에 CPU를 배분
- 프로세스들에게 공식을 통해 우선순위 계산해 부여함
  - 우선순위 값이 작을 수록 순위가 높음

Scheduling Mechanism vs. Policy

Scheduling mechanism과 Scheduling Policy를 구분해야함
Kernel은 Scheduling mechanism을 제공함
Kernel algorithm / User process는 Scheduling policy를 결정
- 예를 들어, Multi-media는 Real-time Scheduling으로 처리
Thread Scheduling
- 예전에는 쓰레드라는 개념이 없어서 커널은 그냥 단지 프로세스를 번갈아 실행했음
  - A1 A2 A3 B1 B2 B3 형식으로 실행 가능
  - A1 B1 A2 B2는 불가능
- 현재에는 커널이 프로세스 단위가 아니라 쓰레드 단위로 실행해 여러 프로세스에 있는 쓰레드들을 번갈아 실행할 수 있음
  - A1 B1 A2 B2도 가능