운영체제 ② (KOCW 반효경 교수님 강의)

OS 2022. 7. 14. 18:49

http://www.kocw.net/home/search/kemView.do?kemId=1046323

운영체제

운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각

www.kocw.net

이 글은 반효경 교수님의 강의를 듣고 잊지않고 공부하기 위해 작성되었다.

Ch5. CPU scheduling

프로그램 수행시 CPU burst와 I/O burst(오래 걸림)가 반복적으로 이루어진다.
프로세스의 특성
- I/O bound job : many short CPU bursts
  - I/O가 끼어드는 작업의 프로세스가 많으며 오고 가는 소통이 많은 interactive한 작업
  - CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- CPU bound job : few very long CPU bursts
  - CPU를 오래 사용하는 작업
  - 계산 위주의 job
CPU 스케줄러 : 운영체제 안의 코드로 Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 고른다
- 스케줄링이 필요한 경우
  - NonPreemptive(비 선점형 : 강제로 빼앗지 않고 자진 반납)
    - Running -> Blocked (ex) I/O 요청하는 시스템 콜)
    - Terminate
  - Preemptive(선점형 : 강제로 빼앗음)
    - Running -> Ready (ex) 할당시간 만료로 timer interrupt)
    - Blocked -> Ready (ex) I/O 완료 후 인터럽트)
- 기준
  - CPU, 시스템 입장
    - CPU utilization(이용률)
    - Thoroughput(처리량) : 주어진 시간내에 처리할 수 있는 양
  - 프로그램(프로세스) 입장
    - Turnaround time(소요시간 반환시간) : 쓰레드 들어와서 기다리고 다 쓰고 나갈 때까지의 걸린 시간 (총 I/O가 아닌 해당 요청 I/O에서)
    - Waiting time(대기시간) : CPU를 얻었다 뺏겼다를 반복하면서 기다린 시간의 총합
    - Response time(응답 시간) : Ready queue에서 처음으로 CPU 얻기 까지 걸린 시간
- 순서 선정 알고리즘
  - FCFS(First Come First Served) -> 비선점형
    - 프로세스의 도착 순서에 따라 처리 (선착순)
    - 누가 먼저 왔냐에 따라 총 대기시간, 소요시간이 달라지며 비효율적
    - Convoy effect 발생 가능 : 오래걸리는 프로세스 뒤에 도착한 짧은 프로세스가 Queue에서 기다리는 경우 -> 온 시간에 따라서 순서가 달라지고 오래 기다려야 하는 현상
  - SJF(Shortest Job First) -> 선점형, 비선점형
    - 각 프로세스의 다음번 CPU burst time을 가지고 가장 짧은 프로세스를 가장 먼저 할당
    - 다음번 CPU burst time은 과거의 CPU burst time을 이용해서 추정
    - 비선점형
      - 일단 CPU를 잡으면 이번 CPU burst가 끝날때까지 CPU를 유지(중간에 더 짧은 프로세스가 와도 이미 실행중이면 내어주지 않는다)
    - 선점형 : SRTF(Shortest-Remaining-Time-FIrst)
      - 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스 도착하면 CPU를 내어준다(빼앗김)
      - 주어진 프로세스에 대해 minimum average waiting time을 보장한다
  - Priority Scheduling -> 선점형, 비선점형
    - 가장 높은 우선순위를 가진 프로세스에게 CPU 할당
    - SJF는 일종의 priority scheduling
    - 기아현상 발생 가능성 : 계속해서 우선순위가 높은 프로세스가 추가되면 우선순위 낮은 프로세스는 수행되지 못하고 계속 기다림
      - Aging(노화)를 이용해서 해결 : 시간이 지남에 따라 프로세스의 우선순위를 높여줌
  - Round Robin(RR) -> 선점형 (현대 사용 많음)
    - 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지고 할당 시간이 지나면 프로세스는 선점 당하고 ready queue에 가서 다시 줄을 선다.
    - 총 프로세스가 n개 일때 할당시간이 q time unit이면 어떠한 프로세스도 (n-1)q time out 이상 기다리지 않음
    - 할당시간이 큰 경우 -> FCFS
    - 할당시간이 작은 경우 -> context switch 오버헤드가 커진다
    - 일반적으로 SJF보다 average turnaround time(waiting time 길어지는 경우)이 길지만 response time은 더 짧다
  - Multilevel Queue
    - ready queue가 여러 개로 분할 되며 등급에 따라서 나뉜다
      - foreground : interactive
      - background : batch - no human interaction
    - 각 큐는 독립적인 스케줄링 알고리즘을 가진다
      - foreground : RR (응답시간을 짧게)
      - background : FCFS (CPU 사용이 많기 때문에 context switch 비용을 줄이는 방법 선택)
    - 큐에 대한 스케줄링이 필요
      - Fixed priority scheduling -> 기아현상 발생 가능
      - Time slice -> 각 큐에 CPU time을 적절한 비율로 할당
  - Multilevel Feedback Queue
    - multilevel과 달리 프로세스가 다른 큐로 이동 가능
    - aging을 이와 같은 방식으로 구현 가능
    - 파라미터
      - Queue의 수
      - 각 큐의 scheduling algorithm
      - Process를 상위 큐로 보내는 기준
      - Process를 하위 큐로 내쫓는 기준
      - 프로세스가 CPU 서비스를 받으로 할 때 들어갈 큐를 결정하는 기준
- 알고리즘 평가 (이론적 방법)
  - Queueing models
    - 확률분포로 주어지는 arrival rate, service rate를 통해 각종 performance index 값 계산 (throughput, 얼마나 기다렸는지 등을 측정)
  - Implementation(구현) & Measurement(성능 측정)
    - 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정
    - 어려울 수 있다
  - Simulation(모의 실험)
    - 알고리즘을 모의 프로그램으로 작성하여 trace(실제 프로그램 등의 방법으로 얻어낸 burst time 등의 input 데이터, 신뢰성 높음)를 입력하여 결과 비교
Multiple Processor Scheduling
- CPU가 여러개인 경우 스케줄링은 더욱 복잡
  - Homogeneous processor : (ex) 특정 미용사한테 머리하고 싶은 경우 -> 특정프로세스 사용 원함)
    - Queue에 한줄로 새워서 각 프로세서가 알아서 꺼내가게 할 수 있음
    - 반드시 특정 프로세서에서 수행되어야 하는 경우 문제가 더 복잡
  - Load sharing
    - 일부 프로세서에 일이 몰리지 않도록 부하를 적절히 공유 하는 메커니즘 필요
    - 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  - Symmetric Multiprocessing(SMP)
    - 각 프로세서가 각자 알아서 스케줄링
  - Asymmetric multiprocessing
    - 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임(master)지고 나머지 프로세서는 거기에 따름
Real Time Scheduling
- Hard real-time systems : 정해진 시간 안에 반드시 끝내야함 (미리 계산해서 일 배치)
- Soft real-time computing : soft-real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 함
Thread Scheduling
- Local Scheduling : 사용자 레벨 스레드의 경우 사용자 수준의 Thread library에 의해 어떤 쓰레드를 스케줄할지 결정 (OS는 모른다)
- Global Scheduling : 커너 레벨 스레드의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄 할 지 결정
Dispatcher : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다 => 문맥 교환 (context switching)

Ch6. Process Synchronization(프로세스 동기화) = Concurrency Control(병행 제어)

출처 https://www.mcafee.com/blogs/enterprise/testing-race-conditions-web-applications/

임계구역(공유 자원)을 여러개의 CPU프로세스가 동시에 접근하려는 경우 경쟁 상태의 가능성이 존재한다
- ex) Multiprocessor system에서 공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴 간 (커널 모드 수행 중 인터럽트로 커널모드를 건드려 다른 루틴을 수행하는 경우)
Race Condition
- 공유 데이터의 동시접근(concurrent acccess)는 데이터 불일치 문제가 발생할 수 있음
- 일관성을 유지하기 위해서 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요
- 발생 시기
  - CPU 1개일 때
    - kernel 수행 중 인터럽트 발생 시 ( 양쪽 다 커널 모드 이므로 kernel address space를 공유한다 )
      - 커널모드에서 중요한 작업중에는 할당 시간이 끝나도 interrupt 받지 않도록 정해주는 것이 필요(비선점 되도록)
      - 커널모드에서 사용자 모드로 돌아갈 때 선점 가능
    - Process가 system call을 하여 kernal mode로 수행중인데 context switch가 일어나는 경우
  - CPU 여러개 일 때
    - Multiprocessor에서 shared memory 내의 kernel data
      - multiprocessor의 경우 interrupt enable/disable로 해결 되지 않음
      - 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있도록 설정 (비효율적)
      - 2) 커널 내부에 있는 각 공유 데이터에 접근할 때 마다 그 데이터에 대한 것만 lock/unlock을 하는 방법

프로그램적 해결법의 충족 조건
- Mutual Exclusion(상호배제) : 프로세스 A가 임계구역 부분을 수행중이면 다른 모든 프로세스는 그들의 임계구역에 접근 불가
- Progress : 아무도 임계구역에 있지 않은 상태에서 임계구역에 들어가고자 하는 프로세스 존재 시 들어갈 수 있다
- Bounded Waiting : 프로세스가 임계구역에 들어가려고 요청한 후에 허용될 때 까지 유한대기가 발생하지 않도록 다른 프로세스들이 임계구역에 들어가는 횟수에 한계가 있어야 한다 -> 기아상태 방지

해결 알고리즘 (Peterson's Algorithm)
- 들어가려고 하는 의지와 차례 표시를 모두 이용하여 상호배제, 진행, 기아상태 방지
- Busy waiting (Spin Lock) : 상대방이 lock 걸어서 못들어가는 경우에도 할당시간에 while문을 돌아 계속해서 CPU와 memory를 사용하면서 기다린다
- 하드웨어 적으로 Test & modify(읽으면서 쓰는 작업)를 atomic하게 수행할 수 있도록 지원하는 경우 lock 사용 편하게 가능

Semaphores (공유자원 획득, 반납의 추상 자료형)
- Semaphore S는 정수값을 이용하며 P(S): 공유 데이터 획득, V(S) 공유데이터 반납의 연산에 의해서만 접근 가능
- 타입
  - Counting semaphore
    - 여분의 자원 갯수 카운팅 (도메인이 0 이상인 임의의 정수 값)
    - 주로 resource counting에 사용
  - Binary semaphore(= mutex)
    - 0 또는 1 값만 가질 수 있는 semaphore
    - 주로 상호배제 (lock / unlock)에 사용
- 기존의 busy waiting 방식 -> 효율적이지 못하다
- Block / Wakeup Implementation
  - Semaphore에서 프로세스 대기열 처리
  - block
    - 커널은 block을 호출한 프로세스를 suspend 시킨다
    - 이 프로세스의 PCB를 세마포어에 대한 대기열에 넣는다
  - wakeup(P)
    - block 된 프로세스P를 wakeup 시킨다
    - 이 프로세스의 PCB를 대기열로 옯긴다
- Busy-waiting (critical section 길이) vs BLock/wakeup (overhead)
  - Critical section 길이가 긴 경우 Block/wakeup
  - Critical section 길이가 매우 짧은 경우 Block/Wakeup의 상태변경 오버헤드가 busy wait 오버헤드보다 많을 수 있다
  - 일반적으로는 Block/wakeup방식이 더 좋다
- Deadlock & Starvation
  - 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다림
  - 서로 한쪽의 데이터를 반대쪽에 복사하려는 경우 두개의 데이터가 다 필요 (하나씩 쥐고 반납 안하고 계속 기다림)
  - Indefinite blocking (Starvation) : 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
  - 식사하는 철학자 문제
    - 젓가락을 한짝씩 양쪽에 둔 5인 원형테이블에서 젓가락이 양쪽 다 있을 때 식사가 가능하다고 가정
    - 양쪽 중 누군가 젓가락을 내려놓길 기다리는데 한쪽이 내려놨지만 다른 한족이 다시 젓가락 들어올림
    - 다섯명이 동시에 젓가락 한쪽씩 집어듬 -> 무한 대기 발생
    - 해결방안
      - 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
      - 젓가락을 두개 모두 집을 수 있을 때에만 젓가락을 집을 수 있도록 설정
      - 비대칭을 이용하여 짝수(홀수)철학자는 왼쪽(오른쪽)젓가락부터 집도록 우선순위를 다르게 설정
  - Bounded Buffer Problem
    - 원형 구조의 공유메모리의 Buffer에서 Producer는 공유버퍼에 데이터를 넣고 Consumer는 공유 버퍼에 있는 데이터를 소비하는 역할
    - 크기가 유한한 버퍼가 채워진 상태인데 생산자가 도착하였을 때 생산자 입장에서 빈 버퍼가 없기 때문에 소바자가 나타날때가지 계속해서 대기
    - 공유 데이터
      - buffer 자체 및 buffe 조작 변수 (empty/ full buffer의 시작위치)
    - 동기화 변수
      - 상호배제(lock) : binary semaphore를 이용하여 lock을 이용해 서로 제어
      - resource count : integer semaphore(남은 full/empty 버퍼의 수 표시)
    - Counting Semaphore(빈 버퍼의 갯수, 채워진 버퍼의 갯수)를 이용한다
      - 생산자
        
        1) 빈 버퍼가 있는지 확인
        
        2) 빈 버퍼가 있으면 공유 데이터에 lock을 건다
        
        3) 빈 버퍼에 데이터 입력 및 버퍼 조작
        
        4) lock을 푼다
        
        5) full 버퍼의 카운트를 하나 증가
      - 소비자
        
        1) 채워진 버퍼가 있는지 확인
        
        2) 채워진 버퍼가 있으면 공유데이터에 lock
        
        3) 채워진 버퍼에서 데이터 꺼내고 버퍼 조작
        
        4) lock 해제
        
        5) 빈 버퍼의 카운트 하나 증가
  - Readers-Writers Problem
    - 한 프로세스가 DB에 write 중일 때 다른 process가 접근할 수 없지만 read는 동시에 여럿이 접근해도 된다
    - 공유 데이터
      - DB 자체
      - read count : 현재 DB에 접근중인 reader의 수
    - 동기화 변수
      - mutex : 공유변수(read count)를 접근하는 코드, 임계구역의 상호배제 보장
      - db : reader와 writer가 공유 DB자체를 올바르게 접근하게 하는 역할
    - 해결 방안
      - Writer가 DB에 접근 허가를 아직 얻지 못한 상태 -> 모든 대기중인 Reader가 DB에 접근하게 해줌
      - Writer는 DB에 접근중이 Reader가 하나도 없을 때 접근 허용
      - Writer가 DB 접근 중이면 Reader의 접근이 금지됨 (Reader들 기다림)
    - Writer가 대기하고 있는 동중에 Reader가 계속해서 오게 되면 Starvation의 가능성이 있다
  - Semaphore의 단점
    - 코딩하기 힘들고 정확성 입증이 어렵다
    - 자발적 협력이 필요
    - 한번의 실수가 모든 시스템에 치명적 영향

Monitor
- 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization contruction(추상구현) -> 동시접근 허용 X ex)객체지향 프로그래밍
- 하번에 하나의 프로세스만 활동하며 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 X
- lock을 걸 필요가 없다 (자체내의 버퍼를 사용하여 하나의 프로세스만 모니터하면서 활성화 됨)
  - wait(), signal()연산에 의해서만 접근
  - wait() : wait() 을 invoke한 프로세스는 다른 프로세스가 signla()을 invoke하기 전까지 suspend된다
  - signal() : 정확하게 하나의 suspend된 프로세스를 재게한다. (suspend된 프로세스가 없으면 아무일도 일어나지 않음)프로세스가 모니터 안에서 기다릴 수 있도록 condition variable 사용

Ch7. Deadlock

Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
- 발생조건
  - Mutual exclusion (상호배제)
    - 매 순간 하나의 프로세스 만이 자원을 사용할 수 있음
  - No preemption (비선점)
    - 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
  - Hold and wait (보유대기)
    - 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓치 않고 가지고 있음
  - Circular wait (순환 대기)
    - 자원을 기다리는 프로세스 간에 사이클이 형성 되어야 함
- 해결 방안
  - 방지
    - Deadlock Prevention
      - 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것 (자원 이용률(Utilization) 저하, 성능(Throughput) 감소, starvation 문제가 발생할 수 있음)
        
        Mutual exclusion (상호배제)
        
        공유해서는 안되는 자원의 경우 반드시 성립해야 하므로 없애기 어렵다
        
        No preemption (비선점)
        
        프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
        
        1) 프로세스 시작시 모든 필요한 자원을 할당받게 하는 방법(비효율)
        
        2) 자원이 필요할 경우 보유자원을 모두 놓고 다시 요청
        
        Hold and wait (보유대기)
        
        프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨(timer 설정 등)
        
        모든 필요한 자원을 얻을 수 있을 때 프로세스가 다시 시작
        
        State를 쉽게 저장하고 restore할 수 있는 자원에서 주로 사용(CPU, memory -> 아무때나 뺏어도 restore, start 가능)
        
        Circular wait (순환 대기)
        
        모든 자원 유형에 할당 순서를 정해 순서대로 자원 할당
    - Deadlock Avoidence
      - 자원 요청에 대한 부가정보를 통틀어 Deadlock의 가능성이 없는 경우(safe)에만 자원을 할당 (아주 안전하게)
      - 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
      - 가장 단순하고 일반적인 방법은 각 자원별 최대 사용량을 미리 선언하도록 하는 것
      - safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
      - safe sequence : Pi의 자원 요청이 가용자원 + 모든 Pj의 보유자원에 의해 충족되어야 함
      - 알고리즘
        
        Single instance
        
        Resource Allocation Graph algorithm
        
        미래에 가능한 요청까지 합쳐서 사이클을 계산
        
        Multiple Instance
        
        Banker's Algorithm
        
        모든 프로세스는 자원의 최대 사용량을 미리 명시
        
        자원을 모두 할당 받은 겨우 유한 시간 안에 이들 자원을 다시 반납
  - 탐지 및 회복
    - Deadlock Detection and Recovery
      - Deadlock발생은 허용하되 그에대한 detection 루틴을 만들어 탐지되면 회복
      - 탐지 알고리즘
        
        자원 타입당 single instance : 자원할당 그래프에서의 사이클이 곧 deadlock의미
        
        자원 타입당 multiple instance : Banker's Algorithm과 유사한 방법 사용
        
        Wait for graph algorithm
        
        리소스 타입당 single instance인 경우
        
        자원 할당 그래프의 변형으로 사이클이 존재하는지 주기적으로 조사(O(n^2))
      - Recovery
        
        Process termination(다 죽여서 종료)
        
        Resource Preemption(하나씩 죽여서 자원 빼앗기)
        
        비용을 최소화 할 victim을 선정하여 safe state로 rollback하여 프로세스를 재시작
        
        기아문제 발생 가능 (동일한 프로세스가 계속해서 victim으로 선정되는 경우) -> cost factor에 rollback횟수도 함께 고려 (비용 및 자원세는 패턴을 매번 다르게 설정)
  - 무시
    - Deadlock Ignorance (현대 사용 많음)
      - Deadlock을 시스템이 책임지지 않음
      - Deadlock이 매우 드물게 발생하므로 조치 자체가 더 큰 오버헤드일 수 있음
      - UNIX를 포함한 대부분의 OS가 사용 (관여하지 않으면 사람이 알아서 프로세스를 종료)
Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- 프로세스가 자원을 사용하는 절차 (Request, Allocate, Use, Release)

'OS' 카테고리의 다른 글

동기 / 비동기 / 블로킹 / 논블로킹 (0)	2022.07.15
운영체제 ③ (KOCW 반효경 교수님 강의) (0)	2022.07.14
운영체제 ① (KOCW 반효경 교수님 강의) (0)	2022.07.14

ABOUT ME

합니다, 개발공부📝 합니다, 개발공부📝

'OS' 카테고리의 다른 글

티스토리툴바

ABOUT ME

'OS' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바