[CS 기초 스터디] 3주차 회의록

정규 회의록

일시 : 2022.10.18 18:30

범위 : 운영체제 6~9강

강의 : 반효경 교수님 운영체제 강의

활동 : github에 올린 내용 정리본 읽고 공부한 내용에 대해 발표 및 질의응답

정리 : https://github.com/GDSC-Ewha-4th/Study-CS.git

---

6. 프로세스 동기화

데이터의 접근

데이터를 읽음 → 연산 수행 → 결과 내보냄

하나의 공유 데이터에 동시에 접근하려고 할 때 문제

Race Condition (경쟁 상태)

Process Synchronization 문제

공유 데이터 동시 접근 → 데이터의 불일치 문제

일관성 유지를 위해 협력 프로세스 간의 실행 순서를 정해야 함

The Critical-Section Problem

Critical Section: 각 프로세스의 코드에서 공유 데이터를 접근하는 코드

한 프로세스가 critical section에 있을 때 다른 프로세스는 접근할 수 없음

프로그램적 해결법의 충족 조건

• Mutual Exclusion (상호 배제)
  
  한 프로세스가 사용중이면 다른 프로세스는 사용할 수 없음
• Progress (진행)
  
  아무도 critical section에 있지 않으면 들어갈 수 있어야 함
• Bounded Waiting (유한 대기)
  
  프로세스가 요청하면 기다리는 시간이 유한해야 함

Synchronization Hardware

하드웨어적으로 Test & Set를 atomic하게 수행할 수 있도록 지원하는 경우 문제 간단히 해결

Semaphores

추상 자료형 - object, operation으로 구성

Semaphore S - integer variable

공유 자원 counting, 자원이 남아있는지 확인

Block / Wakeup Implementation

Semaphore를 구조체처럼 정의

• block
  
  커널이 block을 호출한 프로세스 suspend
  
  PCB를 semaphore에 대한 wait queue에 넣음
• wakeup(P)
  
  block된 프로세스 P를 wakeup 시킴
  
  PCB를 ready queue로 옮김

Two types of Semaphores

• Counting semaphore
  
  자원의 수를 세서 도메인을 0 이상으로 설정
  
  주로 recource counting에 사용
• Binary semaphore
  
  0 또는 1 값만 가질 수 있는 semaphore
  
  주로 mutual exclusion (lock/unlock)에 사용

Deadlock and Starvation

• Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상. 여러 프로세스가 얽혀서 더 이상 진행 X
• Starvation: Indefinite blocking

Bounded-Buffer Problem

Producer-Consumer Problem

Producer: data 생성해서 버퍼에 넣음

Consumer: data 꺼내감

Readers-Writers Problem

한 프로세스가 DB에 write 중일 때 다른 프로세스 접근 X

read는 동시에 여럿이 해도 됨

Monitor

Monitor

공유 데이터에 대한 동시접근을 모두 책임짐

모니터 안에 정의되어 있는 함수로만 접근 가능

7. 데드락

The Deadlock Problem

Deadlock - 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

프로세스가 자원을 사용하는 절차

Request, Allocate, Use, Release

Deadlock 발생의 4가지 조건

• Mutual Exclusion (상호 배제) - 하나의 프로세스만이 자원 사용 가능
• No Preemption (비선점) - 자원을 강제로 빼앗기지 않음
• Hold and Wait (보유 대기) - 보유 자원을 놓지 않고 계속 가지고 있음
• Circular Wait (환형 대기) - 자원을 기다리는 프로세스 간에 사이클 형성

4가지 조건을 모두 만족해야 Deadlock 발생

Resource-Allocation Graph (자원할당그래프)

Vertex (Process, Resource)

Edge (request edge, assignment edge)

• 그래프에 cycle이 없으면 deadlock 아님
• 그래프에 cycle이 있으면
  • 자원의 인스턴스가 1개 - deadlock
  • 자원의 인스턴스가 여러개 - deadlock 가능성 있음

Deadlock Prevention

Deadlock의 4가지 필요 조건 중 하나가 만족되지 않도록 하는 것

• Mutual Exclusion - 반드시 성립
• Hold and Wait
  • 프로세스 시작 시 모든 자원을 할당받게 하는 방법 (자원 낭비)
  • 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • 빼앗을 수 있는 자원 (CPU, Memory - state 쉽게 저장 가능) 한정되어 있음
• Circular Wait
  • 모든 자원에 할당 순서(우선순위)를 정해 순서대로만 자원 할당

→ utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock 가능성이 없는 경우에만 자원 할당

safe state - 자원 할당, unsafe state - deadlock 가능성 있음

시스템이 unsafe state에 들어가지 않는 것을 보장

safe sequence - 프로세스의 자원 요청이 가용 자원 + 작업이 완료된 모든 프로세스의 보유 자원에 의해 충족

• Resource Allocaion Graph algorithm
  
  Multiple instances per resource types프로세스 P가 자원 R을 미래에 요청할 수 있음 (점선)
  
  프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
  
  자원이 release 되면 assignment edge → claim edge
• 점선을 포함해서 cycle이 생기지 않는 경우에만 request edge → assignment edge 변경
• Claim edge P → R
• Banker’s Algorithm
  
  Multiple instances per resource types프로세스의 최대 자원 요청량을 미리 안다는 것을 전제
• 가용 자원 내에서 프로세스의 최대 요청을 처리할 수 있는 경우에만 할당
  
  → 프로세스 종료 후 자원 반납 → 가용 자원 늘어남

Deadlock Detection and Recovory

• Deadlock Detection
  • Single instance
    
    Resource Allocation Graph algorithm
    
    → Wait-for graph (프로세스만으로 노드 구성)
  • Multiple instance
    
    자원 요청이 없는 프로세스가 가진 자원을 내어놓는다고 가정
    
    → 현재 요청된 자원을 만족할 수 있는 Sequence가 존재
    
    → No deadlock (현재)
• Recovery
  • Process termination
    
    Abort All
    
    Abort one process at a time (데드락이 없어질 때 까지)
  • Resource Preemption
    
    비용을 최소화하는 victim 선정 → safe state로 restart
    
    Starvation - 동일한 프로세스가 계속 victim으로 선정
    
    → rollback 횟수도 같이 고려

Deadlock Ignorance

Deadlock이 매우 드물게 발생하므로 조치를 취하는 것이 더 큰 overhead가 될 수 있음 → 아무런 조치 X

대부분의 현대의 범용 운영체제가 채택

사람이 직접 프로세스를 죽이는 등의 방법으로 대처

8. 메모리 관리

Logical vs. Physical Address

• Logical address (= virtual address)
  
  프로세스마다 독립적으로 가지는 주소 공간, CPU가 보는 주소
• Physical address
  
  메모리에 실제 올라가는 위치
• 주소 바인딩 (주소 결정)
  
  Symbolic address → Logical address → Physical address

주소 바인딩 (Address Binding)

Logical address가 Physical address로 바뀌는 시점이 언제인지

• Compile time binding
  
  실행파일을 만들 때 주소 결정
  
  여러 프로그램이 multi-tasking 되는 환경에서는 비효율적
  
  절대 코드 (absolute code)
• Load time binding
  
  프로그램이 실행 시작되는 시점에 주소 결정
  
  재배치가능코드 (relocatable code)
• Execution time binding (= Run time binding)
  
  프로그램이 실행 시작되는 시점에 주소 결정, 실행중에도 메모리 상 위치를 옮길 수 있음
  
  주소가 계속 변환되기 때문에 CPU가 주소를 참조할 때마다 binding 점검
  하드웨어 지원이 필요

Memory-Management Unit (MMU)

logical address를 physical address로 매핑해 주는 하드웨어 디바이스

MMU scheme

• Relocation register (Base register): 프로그램의 시작 위치
• Limit register: 프로그램의 크기

CPU가 요청한 논리 주소가 Limit register보다 큰 경우(악의적인 시도) 차단

정상적인 접근인 경우 주소 변환(시작 위치 + 논리 주소)

User program - logical address 만을 다룬다

Dynamic Loading

해당 루틴이 불려질 때 프로세스를 메모리에 load

memory utilization 향상

운영체제의 지원 없이 프로그램 자체에서 구현 가능 (라이브러리를 통해 지원)

Dynamic Linking

Linking을 실행 시간까지 미루는 기법

• Static linking (Static Library)
  
  라이브러리가 실행 파일 코드에 포함
  
  동일한 라이브러리가 각각의 메모리에 올라오므로 메모리 낭비
• Dynamic linking (Shared library
  
  라이브러리가 실행시 연결(linking)됨
  
  이미 메모리에 있으면 그 주소로 가고 없으면 디스크에서 읽어옴
  운영체제의 도움이 필요

Overlays

프로세스에서 실제 필요한 정보만 메모리에 올림

프로세스의 크기가 메모리보다 클 때 유용

운영체제의 지원 없이 사용자에 의해 구현 (초창기 시스템 - 수작업으로 구현)

Swapping

프로세스를 일시적으로 메모리에서 backing store(=swap area)로 쫓아냄

중기 스케줄러에 의해 swap out될 프로세스 결정 - CPU 우선순위 낮은 프로세스

Run time binding이 지원되어야 함

swap time은 대부분 transfer time이다

Allocation of Physical Memory

• Contiguous allocation (연속 할당)
• Noncontiguous allocation (불연속 할당)

Contiguous allocation (연속 할당)

외부 조각 (External framgmentation)

프로그램 크기보다 분할의 크기가 작은 경우

내부 조각 (Internal fragmentation)

프로그램 크기보다 분할의 크기가 큰 경우

• 고정 분할 방식 (Fixed partition)
  
  물리적 메모리 영구적 분할(partition)
  
  분할 크기가 고정적이므로 내부 조각 / 외부 조각이 생길 수 있음 - 공간 낭비
• 가변 분할 방식 (Variable partition)
  
  프로그램의 크기를 고려해서 할당
  
  프로그램이 종료되면 외부 조각이 생길 수 있음

Hole

가용 메모리 공간 - 여러 hole이 메모리 여러 곳에 흩어져 있음

운영체제는 할당 공간과 가용 공간(hole)에 대한 정보를 유지

• Dynamic Storage-Allocation Problem
  
  가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole 찾기
  • First-Fit - 최초로 찾은 size n 이상인 hole에 할당
  • Best-fit - size n 이상인 가장 작은 hole을 찾아서 할당, 모든 리스트 탐색
  • Worst-fit - 가장 큰 hole에 할당
  • First-fit과 Best-fit이 Worst-fit보다 효율적
• Compaction
  
  external fragmentation 문제 해결 방법
  
  외부 조각을 하나로 모아서 큰 hole을 만드는 것
  
  최소한의 메모리 이동으로 compaction - 매우 복잡한 문제
  
  프로그램의 물리 주소가 동적으로 바뀌어야 하기 때문에 run time binding에서만 사용 가능

Noncontiguous allocation (불연속 할당)

• Paging
  
  프로세스의 logical memory를 동일한 사이즈의 page 단위로 나누어서 저장
  
  일부는 backing storage에, 일부는 physical memory에 저장
  
  physical memory → frame, logical memory → page (frame과 같은 크기)
  
  page table을 사용하여 주소 변환
  
  외부 조각 발생 X, 내부 조각 발생 가능
• Page table
  
  32bit 주소 체계 / page 크기 4K = 100만개 이상의 paging entry 필요
  
  main memory에 상주
  
  Page-table base register(PTBR) - page table 시작 위치 / Page-table
  length register(PTLR) - page table 크기
  
  page table 접근 1번, 실제 data 접근 1번 → 2번의 memory access
  
  Translation Look-aside Buffer(TLB) 고속의 캐시 메모리 - associative register(parallel search 가능한 하드웨어)를 통해 구성

Two-level Page Table

32 bit address 사용시 4G의 주소 공간

→ page size 4K 이면 1M개의 page table entry 필요

→ page entry 4B 이면 4M의 page table 필요

→ 일부만 사용되므로 공간 낭비가 심함

• page number: 20 bit
  • page number: 10 bit → P1 (outer page table의 index)
  • page offset: 10 bit → P2 (page of page table)
• page offset: 12 bit

Multilevel Paging and Performance

Address space 커지면 다단계 페이지 테이블 필요

각 단계 페이지 테이블이 존재 - 더 많은 메모리 접근 필요

TLB를 통해 메모리 접근 시간 줄일 수 있음

Memory Protection

Page table의 각 entry마다 아래의 bit 추가

• Protection bit
  
  page에 대한 접근 권한
• Valid-invalid bit
  
  valid - 해당 주소 frame에 프로세스를 구성하는 유효한 내용이 있음 (접근 허용)
  
  invalid - 해당 주소 frame에 유효한 내용이 없음 (접근 불허)
  
  프로세스가 그 주소 부분을 사용하지 않는 경우 / 해당 페이지가 메모리에 있지 않고 swap area에 있는 경우

Inverted Page Table

모든 프로세스 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재 → page table 매우 커짐

Inverted page table (역방향)

• Page frame 하나 당 page table에 하나의 entry를 둔 것
• 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, logical address)
• 테이블 전체를 탐색해야 하는 단점 → associative register 사용

Shared Page

동일한 프로그램이 여러 프로세스에 의해 실행되면 동일한 코드가 각 메모리에 중복으로 올라가게 됨

Shared code = Re-entrant code = Pure code

• read-only로 하여 하나의 코드만 메모리에 올림
• 모든 프로세스의 logical address space에서 동일한 위치 (같은 page 번호)

Segment

프로그램을 의미 단위인 여러개의 segment로 나눔

일반적으로 code, data, stack 부분이 하나의 segment

<segment-number, offset>

• Segment table
  • base - segment 시작 주소
  • limit - segment 길이
• Segment-table base register (STBR) - segment table 시작 주소
• Segment-table length register (STLR) - segment table 수(길이)

Segmentation Architecture

• Protection - 각 segment 별로 protection bit
• Sharing - shared segment, same segment number
• Allocation - first fit / best fit, external fragmentation 발생

Segment는 의미 단위이기 때문에 공유와 보안에 있어 paging 보다 효과적

Segment 길이가 제각각이므로 가변 분할 방식에서의 문제점 발생

Segmentation with Paging

한 segment 여러 개의 page로 구성 → page 단위로 메모리에 올림

segment-table entry가 segment를 구성하는 page table의 base address를 가지고 있음

공유/보안 segment 차원에서 관리, 할당 문제 없음

9. 가상 메모리

Demand Paging

실제로 필요할 때 page를 메모리에 올리는 것

I/O 양 감소, 메모리 사용량 감소, 빠른 응답 시간, 더 많은 사용자 수용

Valid / Invalid bit 사용

Invalid - 사용되지 않는 주소 영역 or 페이지가 물리적 메모리에 없는 경우

처음에는 모드 invalid로 초기화

page fault - 주소 변환 시 invalid bit이 set 되어 있음

Page Fault

invalid page에 접근하면 MMU가 trap 발생시킴

1. Invalid reference? → abort process
2. Get an empty page frame (없으면 뺏어옴)
3. page를 disk에서 memory로 이동
   1. disk I/O 끝날때까지 프로세스는 CPU 뺏김 (block)
   2. Disk read 끝나면 page tables entry 기록, valid
   3. ready queue에 프로세스 insert

Performance of Demand Paging

Page Fault Rate 0 ≤ p ≤ 1.0

page fault 없으면 메모리 접근 시간만 소요

page fault가 일어나면 disk에 접근해야 하기 때문에 시간이 오래 걸림

Free frame이 없는 경우

Page replacement

어떤 frame을 뺏어올지 결정

곧바로 사용되지 않을 page를 쫓아내는 것이 좋음

Page replacement Algorithm

page-fault rate를 최소화

주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

Page replacement Algorithm

• Optimal Algorithm
  
  page reference string을 미리 알고 있다고 가정 - offline algorithm (실제 사용 불가)
  
  MIN (OPT): 가장 먼 미래에 참조되는 page를 replace
  
  다른 알고리즘의 성능에 대한 upper bound 제공
• FIFO (First In First Out) Algorithm
  
  FIFO - 먼저 들어온 것을 먼저 지움
  
  FIFO Anomaly - frame 수가 늘어나면 더 많은 page fault 발생
• LRU (Least Recently Used) Algorithm
  
  LRU - 가장 오래 전에 참조된 것을 지움
• LFU (Least Frequently Used) Algorithm
  
  LFU - 참조 횟수(referenced count)가 가장 적은 페이지를 지움
  
  최저 참조 횟수인 page 여럿 있는 경우 - 임의로 지움 / 오래 전에 참조된 page 지움

LRU와 LFU 알고리즘의 구현

• LRU
  
  linked list로 구현 - 가장 최근에 참조된 것을 list 마지막에 추가 → O(1)
• LFU
  
  linked list로 구현 - 하나하나 비교해서 자리를 찾은 후 추가 → O(n)
  
  heap으로 구현 - 자식 노드 2개와 비교 → O(log n)

다양한 캐슁 방법

캐슁 기법

한정된 빠른 공간(=캐쉬)에 요청된 데이터 저장 → 나중에 요청시 캐쉬로부터 직접 서비스

cache memory, buffer caching, web caching 등

캐쉬 운영의 시간 제약

지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 X

• Buffer caching, Web caching
  
  O(1)에서 O(log n) 정도까지 허용
• Paging system
  
  LRU, LFU 사용 불가능

Clock Algorithm

Second chance algorithm

NUR / NRU (Not Recently Used)

Reference bit

최근에 사용된 페이지 = 1, 최근에 사용되지 않은 페이지 = 0

0인 것을 찾을 때까지 포인터 이동 - 1 → 0으로 교체

Clock Algorithm의 개선

→ Reference bit과 modified bit을 함께 사용

Page Frame Allocation

한 loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함

• Equal allocation: 모든 프로세스에 같은 개수
• Proportional allocation: 프로세스 크기에 비례
• Priority allocation: 프로세스의 priority에 따라

Global vs Local Replacement

• Global replacement
  
  다른 process에 할당된 frame 빼앗을 수 있음
• Local replacement
  
  자신에게 할당된 frame 내에서만 replacement, process 별로 운영

Thrashing

메모리에 너무 많은 프로그램을 동시에 올려 놓아서 계속 page fault가 일어나는 상황

CPU utilization 낮아짐 → 또 다른 프로세스 추가됨 → low throughput

Working-Set Model

Locality set - 집중적으로 참조되는 page들의 집합

Working set - 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합

Working-Set Algorithm
특정 window size 안에 있는 page들을 working set으로 간주

working set에 속하지 않은 page 버림

working set이 보장되는 프로세스만 메모리에 올림

PFF (Page-Fault Frequency) Scheme

page-fault의 상한값과 하한값 지정

• Page fault rate 상한값 넘으면 frame 더 할당
• Page fault rate 하한값 이하이면 할당 frame 수 줄임

빈 frame이 없으면 일부 프로세스 swap out

Page Size 결정

Page size 감소

• 페이지 수 증가, 페이지 테이블 크기 증가
• Internal fragmentation 감소
• Disk transfer 효율성 감소

Larger page size 사용하는 추세