알고리즘 문제 복습을 위한 블로그

Outline

① File concepts

② File System Implementation

③ Allocation Methods

④ Examples

① File concepts

● 정의

보조 기억장치에 기록된 관련 정보의 명명된 모음

(A named collection of related information that is recorded on secondary storage)

● 속성

1. 이름

2. 식별자 (inode)

3. 타입

4. 위치

5. 크기

6. protection

7. time, date, user identification

● 연산 (파일 접근을 위한 API)

1. create

2. write

3. read

4. reposition within file (fseek)

5. delete

6. truncate (파일 내용 삭제)

● Open files

파일에 대한 정보를 읽어서 table 형태로 관리

entry를 메모리에 불러오고 keep함

Open-file table

  -> 열려있는 모든 파일의 정보를 포함

  -> 파일의 위치, 속성 등을 메모리에 keep

open()

  -> File Control Block을 Open-file table에 저장

  -> FCB를 메모리에 저장함으로써 read, write, seek를 효과적으로 수행

  -> FCB가 메모리에 없으면 FCB 읽기 위해 disk I/O 계속 수행

  -> open file table의 pointer를 반환 (file descriptor)

close()

  -> File Control Block을 Open-file table에서 제거

● File Control Block

해당 파일에 대한 모든 것 제어 가능

1. File pointer                  : 현재 파일의 offset (seek으로 변경가능)

2. File-open count            : 해당 파일을 open한 프로세스 수

3. Disk location of the file : 파일이 저장된 disk의 위치

4. Access right                 : 접근 권한

② File System Implementation

1. Information on disk

  1) Boot Control Block

    -> 시스템이 OS를 부팅하기 위해 필요한 정보를 저장

    -> 각 볼륨(파티션)의 첫 번째 block

  2) Volume Control Block

    -> 파일 시스템 자체에 대한 정보 

    -> 각파티션마다 별도의 파일 시스템 설치됨

  3) Directory structure

    -> directory file들의 meta-data (file name, inode number)

    ※ meta-data       : 파일을 관리하기 위한 정보

    ※ inode number  : File Control Block number

  4) FCB (File Control Block)

    -> 파일에 대한 자세한 정보 포함

• file permission
• file dates (create, access, write)
• file owner
• file size
• file location

2. Information in memory

  1) in-memory mount table

    -> mount된 각각의 volume 정보

    -> 현재 mount된 file system의 정보

    -> 파일 시스템 사용 위해 필수

    -> 부팅 시 자동으로 mount

  2) in-memory directory structure

    -> 최근에 접근한 directory structure를 메모리에 keep (빠른 접근 가능)

  3) system-wide open-file table

    -> 열려있는 파일들의 FCB 사본과 기타 정보 포함

  4) per-process open file table

    -> system-wide open-file table에 있는 entry에 대한 포인터와 기타 정보 포함

    -> 하나의 파일을 여러 프로세스가 별도로 open 가능

File Open

기존에 다른 프로세스가 해당 파일을 open 했는지 확인하기 위해서 system-wide open-file table 탐색.

다른 프로세스에서 해당 파일을 open했을 경우

  -> file control block을 디스크로부터 가져올 필요 없으므로

  -> per-process open-file table이 이미 존재하는 system-wide open-file table을 가리키고,  

  -> offset과 protection은 별도로 저장.

다른 프로세스에서 해당 파일을 open하지 않았을 경우,

  -> file control block을 디스크로부터 가져와서 system-wide open-file table에 추가 해야함.

  -> File control block을 가져오기 위해서 directory structure를 탐색.

  -> Directory structure에서 inode number를 찾고,

  -> inode table에서 해당 inode number에 해당하는 file control block 찾음.

  -> 해당 file control block을 system-wide open-file table에 복사함.

File R/W

  -> Per-process open-file table을 탐색해서 해당 파일의 offset, protection mode에 대한 정보 확인

  -> file의 위치 정보가 있는 file control block을 찾기 위해서 system-wide open-file table 탐색.

File Close

  -> per-process open-file table 제거

  -> system-wide open-file table의 open count 감소

3. Virtual file systems

여러 개의 file system 사용할 때 하나의 API로 여러 개의 file system 접근

R/W/Open 할 때 실제 file system API를 사용하지 않고, VFS interface 사용

file system에 맞춰 자동으로 변환됨

v node: virtual system에서 관리하는 inode

③ Allocation Methods

하나의 파일을 구성하고 있는 일련의 disk block들을 어떻게 저장/관리할 지

1. Contiguous allocation

하나의 파일을 구성하고 있는 block들을 연속적으로 저장

장점

  -> 구현이 간단함. 파일의 시작위치와 길이(블록 개수)만 알면 된다.

  -> 파일을 읽을 때 head movement가 필요 없다.

단점

  -> external fragmentation 발생

  -> file이 일정 크기 이상으로 커질 수 없음

구현

  -> Sequential access : 이전에 읽은 disk address에서부터 읽기

  -> Direct access       : 파일의 시작주소 + i에서 읽음

개선방안

  -> extent-based allocation

2. Linked allocation

이전 block의 끝에 다음 block의 주소 기록. 포인터 저장

장점

  -> 파일을 연속적으로 저장하지 않기 때문에 contiguous allocation의 문제점인 externam fragmentation 해결 가능

단점

  -> direct access 불가능.

  -> i번째 block을 찾기 위해서 파일의 시작지점부터 탐색해야함

  -> Pointer information을 저장하는 overhead

  -> 중간에 block이 사용 불가할 경우, 그 다음 block 접근 불가능.

해결책

  -> 단위를 block이 아닌 여러 개의 block으로 구성된 cluster 단위로 저장

개선 방안

  -> FAT(file allocation table)

3. Indexed allocation

각 파일마다 존재하는 Index block에 해당 파일을 구성하고 있는 block number 기록.

Index block 위치만 각 파일별로 가지고 있으면 그 파일을 구성하고 있는 block number들 확인 가능.

문제점

  -> 파일의 block 개수가 index block에 저장할 수 있는 block number 개수보다 많으면?

  1) Linked scheme

    -> 하나의 index block만 사용.

  2) Multilevel index

    -> index를 여러 level로 구성.

    -> Outer index에는 file  block number가 아닌 index block number 기록

    -> index block을 두 번 읽어야 하는 문제 발생(outer index, inner index)

    -> caching으로 해결 가능. Index block을 메모리에 keep

  3) Combined scheme

    -> 여러 개의 인덱스 기법을 혼합해서 사용.

    -> I-node에는 12개의 direct block과 3개의 indirect block 존재.

Direct block      : 파일을 구성하고 있는 block number를 저장(4KB x 12 = 48KB)

Single indirect   : linked scheme(4byte x 1024 = 4MB)

Double indirect : 2-level index(4mb  x 1024 = 4GB)

Triple indirect   : 3-level index(4gb x 1024 = 4TB)

④ Examples

Outline

① Disk Structure

② Solid-state disk (SSD) Characteristics

③ Disk Attachment

④ Disk Scheduling

⑤ Disk Management

⑥ RAID Structure

① Disk Structure

Spindle: 디스크의 중심. 데이터를 읽고 쓰기 위해서 spindle이 반드시 회전 해야함

Track: 여러 개의 sector로 구성

Sector: 데이터가 저장되는 최소 단위

Cylinder: spindle로부터 동일한 거리에 있는 track들의 집합

Platter: 데이터가 저장되는 공간. 여러 개의 track으로 구성

Arm assembly: 여러 개의 arm으로 구성됨

Read-write head: arm의 끝 부분. 특정 데이터를 읽고 쓰기 위해서 read-write head가 해당 track으로 가야함(seek).                              Read-write head가 서로 다른 cylinder를 가리킬 수 없음

Seek time: read-write head가 요청한 sector가 위치한 track으로 이동하는데 걸리는 시간

Rotational latency: 해당 sector가 read-write head의 밑으로 회전하는데 걸리는 시간

Transfer time: 데이터를 읽고 전송하는데 걸리는 시간

access time = seek time (트랙 찾기) + rotational latency (섹터 찾기) + transfer time (전송)

② Solid-state disk (SSD) Characteristics

● SSD 특징

1. HDD보다 비쌈

2. HDD보다 안정적

3. 수명 짧음

-> write 횟수 제한있기 때문에 wear-leveling을 통해 골고루 write 해야 함

4. 용량 작음

5. 더 빠름

6. 안움직임

-> seek time, rotational delay 없음

overwrite 안됨  : erase before write

R/W page 단위

erase block 단위 : 특정 page만 지울 수 없음

● Garbage collection

블록을 실제로 삭제하지 않고, 표기 후 적절한 시점에 일괄 삭제 처리하는 기술

● Flash Translation Layer

특정 content가 동일한 page에 계속 존재하지 않음 -> 특정 위치에 overwrite (X)

OS에서 보는 page 위치 계속 바뀜 -> mapping layer 하나 더 존재

③ Disk Attachment

https://youtu.be/Go8dQkaTaCQ

1. DAS (Direct Attached Storage), Host-attached

-> I/O bus 통해서 storage 접근

2. NAS (Network Attached Storage)

-> local connection이 아닌 network protocol로 storage 접근

-> RPC (Remote Procedure Call) 사용

-> 네트워크 통해서 남는 공간을 공유

-> 유일하게 OS 탑재

3. SAN (Storage Area Network)

-> network protocol이 아닌 storage protocol 사용

-> FC-AL (Fiber Channel Arbitrated Loop) 사용

-> 네트워크 통해서 남는 공간 할당

NAS: 파일 단위 전송 (느림)

DAS, SAN: 블록 단위 전송 (빠름)

④ Disk Scheduling

1. FCFS

-> 순서대로 진행

2. SSTF (Shortest Seek Time First)

-> 현재 head 위치에서 가장 가까운 것 기준

-> starvation 발생

-> optimal 아님

3. SCAN (elevator)

-> head가 끝에서 끝으로 이동하면서 처리

4. C-SCAN (Circular-SCAN)

-> 한 방향으로만 이동

-> 한쪽 끝에 도착하면 방향전환이 아닌 처음 위치로 되돌아감

5. LOOK

-> 끝까지 가지 않고 해당 방향에 request가 있는지 확인

-> 없으면 방향 전환

6. C-LOOK

-> 끝까지 안감 + 한 방향으로만 이동

⑤ Disk Management

● Disk formatting

1. physical formatting (low-level formatting)

-> disk를 sector 단위로 분할

2. logical formatting (Making a file system)

-> 흔히 말하는 포맷

-> file system 생성하려면 데이터를 다 지워야함 (file system 초기화)

-> file system 자료구조를 disk에 저장

● Boot block

-> 부팅 시 필요한 정보들이 저장됨

-> boot block이 시스템을 초기화

-> bootstrap이 ROM에 저장됨

-> bootstrap loader가 메모리에 boot block을 load하고 제어권을 넘겨줌

● Swap space

-> swap-out 된 페이지가 저장된 disk 공간 (backing store)

-> 일반적인 file system에서 사용될 수도 있고

-> 별도의 raw disk partition에서 사용될 수도 있음

● Swap map

-> swap out된 page를 사용하고 있는 process 개수

⑥ RAID Structure

● 목적

1. throughput 향상

  -> striping: 하나의 file을 여러 disk에 나눠서 저장

  1) bit-level striping    : 한 번 R/W 할 때 모든 디스크 동시 사용. 동기화 필요

  2) block-level striping : 특정 disk에서만 R/W 될 수 있음

2. fault-tolerance

-> disk 여러 개 사용하면 고장 확률 높아짐

-> MTTF (Mean Time To Failure)

    1 disk    -> 100,000시간

    100 disk -> 100,000시간 / 100 = 1,000시간 ≒ 41일

-> MTTR (Mean Time To Repair)

    (MTTF)² / 2 * MTTR = (100,000)² / 2 * 10 ≒ 57,000년

해결책

  1) mirroring : disk 복제, storage 용량 2배 필요

  2) parity      : parity block 사용 (XOR)

    A    B    C    (A⊕B⊕C) 

    A,B,C 중 하나 날라가도 복구 가능

    -> A ⊕ B ⊕ (A⊕B⊕C)

    -> A ⊕ C ⊕ (A⊕B⊕C)

    -> B ⊕ C ⊕ (A⊕B⊕C)

● 추가 개념

1. Hot spare  : 디스크 고장났을 때 대체

2. Rebuilding : 고장난 데이터를 복구하는 과정

● RAID (Redundant Array of Inexpensive (Independent) Disks)

1. RAID 0

-> non-redundant striping

-> 복구 불가

2. RAID 1

-> mirrored disks

-> storage 2배

3. RAID 3

-> bit-interleaved parity

-> parity + bit striping

4. RAID 4

-> block-interleaved parity

-> parity + block striping

-> 디스크 고장 안나면 낭비

5. RAID 5

-> block-interleaved distributed parity

-> parity 분산 + block striping

6. RAID 6

-> P+Q redundancy

-> 2개 동시에 고장나도 복구 가능

이전다음

01

Outline

① Demand Paging

② Page Replacement

③ Thrashing

④ Allocating Kernel Memory

① Demand Paging

● 가상메모리

프로세스 전체가 메모리 내에 올라오지 않더라도 실행 가능

사용자 프로그램이 physical memory보다 커져도 됨

● Demand paging

page가 필요할때만 메모리에 load

swapper : 전체 프로세스 조작

pager    : 개별 페이지 조작 (lazy swapper)

lazy swapper

-> 필요없는 page는 절대 swap 안됨

요청한 page가 physical memory에 없으면

disk에서 해당 page를 읽어서 load

● valid/invalid bit

page가 메모리에 있는지 없는지 확인

● Page fault

메모리에 없는 page를 요청하면 빈 frame 찾아서 해당 page를 memory에 load

Trap 형태로 처리. 해당 page가 invalid 상태

1)    Invalid 상태가 잘못된 참조 때문인지, 메모리에 없기 때문인지 확인하기 위해서 another table lookup

2)    빈 frame 확보

3)    해당 page를 빈 frame에 swap in (해당 process를 waiting state로 전환. Disk 접근하기 때문)

4)    page table 갱신

5)    Validation bit를 valid로 바꿈

6)    Page fault가 발생한 지점부터 instruction 재수행

● Pure paging

참조되기 전까지 절대 swap-in 안되므로 시작할 때는 page 없음

page fault 유발

● Locality of Reference

1. spatial: 특정 page 집중적으로 참조

2. temporal: 특정 시간에 일부 page만 참조

● EAT (Effective Access Time)

if p = 0, page faults 발생 안함

if p = 1, 모든 참조가 page fault

EAT = p*(page fault overhead) + (1-p)*(memory access)

② Page Replacement

page fault 발생했는데 빈 frame 없으면 교체해야 함

● 빈 프레임 있을 때

1. 디스크에서 필요한 page 위치 찾기

2. 빈 frame 찾기

3. 빈 frame에 page 삽입

4. 프로세스 재시작

● 빈 프레임 없을 때

1. 변경할 page swap out

2. bit를 valid에서 invalid로 변경

3. 요청한 page swap in 

4. page table에 추가, bit를 valid로 변경

1. FIFO

-> 순서대로 수행

-> Belady's Anomaly: frame이 많을수록 page fault가 많이 발생하는 기현상

2. Optimal

-> 가장 오래동안 사용되지 않을 페이지 교체

-> 예측 불가, 실용성 (x)

-> 다른 알고리즘의 효율성 비교, 평가용

3. LRU

-> 사용한 지 가장 오래된 페이지 교체

  1) Counter implementation: page 참조될 때마다 counter에 시간기록

  2) Stack implementation: page 참조되면 top으로 이동시킴

4. LRU-approximation 

-> LRU의 구현 복잡도를 낮추지만 유사한 성능

-> reference bit 사용

    -> 0으로 초기화, 참조되면 1로 변경

    -> 0이면 교체대상

  1) Additional Reference Bit Algorithm

    -> 각 페이지에 8 bit씩 할당

    -> 매 시간마다 bit를 오른쪽으로 shift

  2) Second chance (clock) Algorithm

    -> reference bit가 0인 page를 만날 때까지 1을 0으로 변경

    -> reference bit가 0이면 swap out

    -> swap in 하고 reference bit를 1로 변경

    -> clock hand (포인터) 다음 칸으로 이동

5. Enhanced Second Chance Algorithm

reference bit와 modify bit 사용

6. Couter-Based Algorithm (잘 안쓰임)

각 page마다 reference 횟수 기록

  1) LFU

    -> 참조횟수 작은 page 교체

    -> 활발하게 사용되는 page는 큰 참조횟수 갖게 될 것

    -> 초기에만 집중적으로 사용되고 이후에 사용 안될 경우 문제 발생

  2) MFU

    -> 참조횟수 큰 page 교체

③ Thrashing

프로세스가 충분한 frame을 할당받지 못해서 page fault 매우 높아짐

-> CPU utilization 감소

Low CPU utilization을 해결하기 위해 multiprogramming의 정도를 높임

-> swap in/out은 disk access이므로 waiting 상태로 전환, CPU가 놀고 있다고 판단

-> 다른 프로세스가 추가됨

-> 과도한 paging 작업 유발

● Thrashing 예방 (Working set model 사용)

-> frame을 필요한 만큼만 제공

-> 어떻게 각 프로세스가 필요로 하는 최소한의 프레임 수를 알 수 있는가? "Locality Model"

Locality Model

-> 프로세스가 실행될 때 항상 특정 지역에서만 메모리를 집중적으로 참조

프로세스는 demand paging에 의해 전체 메모리가 활성화되는 것이 아니라, 일부 set of pages만 활성화된다.

활성화된 set of pages를 locality라고 하는데, 프로세스는 하나의 locality에서 다른 locality로 이동하게 된다.

Locality의 합이 전체 메모리 크기보다 클 경우 thrashing이 발생한다.

● Working Set Model

n번 만큼의 page reference 관찰

  -> if n 작음 : 전체 locality 포함 못함

  -> if n 큼    : 여러 개의 locality 과도하게 포함됨

  -> if n 무한 : 전체 프로그램 포함

WSSi (Working set of Process Pi): 최근 n번 동안 참조된 page의 총 개수

∑WSSi (total demand for frames) > physical memory size 이면 thrashing 발생

④ Allocating Kernel Memory

kernel memory는 user memory와는 다르게 취급

user mode process에 할당하는 page list와는 다른 별도의 메모리 풀에서 할당 받음

이유

1. 커널은 다양한 크기의 자료구조를 위해 메모리를 할당 받음

2. 일부 커널 메모리는 연속적이어야 함

● 커널 프로세스에 할당되는 메모리 관리

1. Buddy system

2. Slab Allocator

● Buddy system

물리적으로 인접한 페이지로 구성된 고정 크기 세그먼트에서 메모리 할당

1. 할당

이전다음

012

2. 병합 (Coaleascing)

이전다음

01

● Slab

하나 또는 그 이상의 연속적인 메모리 공간을 slab이라고 한다.

이 slab을 kernel object마다 미리 할당한다.

Cache는 하나 또는 그 이상의 slab으로 구성된다.

Slab을 미리 할당하기 때문에 fast memory request가 가능하다.

예를 들어, 7kb의 semaphore를 할당하기 위해서 8kb의 page가 필요하므로

모든 semaphore마다 1kb씩 공간이 낭비되는데,

slab allocation을 사용할 경우 연속적인 page로 할당해놓고

semaphore 크기에 딱 맞춰서 할당하기 때문에

internal fragmentation을 방지할 수 있다.

Outline

① Overview

② Background

③ Swapping

④ Contiguous Memory Allocation

⑤ Paging

⑥ Structure of the Page Table

⑦ Segmentation

① Overview

● 기법

1. Contiguous allocation

2. Paging

3. Segmentation

● 해야할 작업

1. address translation

2. memory protection

프로세스들의 address space의 합이 physical memory보다 클 수 있음

디스크 접근 시간 >> 메모리 접근시간

  -> 메모리 hit ratio 높여야 함

② Background

● Basic hardware

base 레지스터, limit 레지스터

-> 합법적인 logical address space 정의

-> 프로세스 바꿀 때마다 base, limit 레지스터 업데이트

MMU (Memory Management Unit)

virtual address를 physical address로 변환하는 hardware device

1. register

2. TLB (Translation Lookaside Buffer)

모든 logical address에 relocation register의 값을 더함

346 (logical) + 14000 (relocation) = 14346 (physical)

● Address Binding

프로그램을 디스크에서 메모리로 올릴 때, 메모리의 어느 위치로 이동시킬 것인가?

Binding 되는 시점

1. compile time

-> 시작주소 바뀌면 컴파일 다시 해야함

2. load time

-> 메모리에 다시 로딩되면 주소 바뀜

3. execution time

-> runtime binding

-> binding을 실행 시점까지 지연시킴

-> MMU 도움 필요

Compile, load time -> logical == physical

Execution time       -> logical != physical

● Logical Address

Logical Address

-> CPU에 의해 생성된 주소

Physical Address

-> 실제 메모리 주소

● Process address space

● Dynamic loading, linking, shared library

Dynamic loading

-> 각 루틴은 호출되기 전까지 load되지 않음

-> 코드 많지만 자주 호출 안되는 경우 효과적

-> OS 지원 필요없음, library에서 제공됨

Dynamic linking

-> Linking을 execution time 직전까지 지연시킴.

-> stub이라고 하는 코드에 어떻게 memory-resident library routine을 적절히 위치시킬 지에 대한 정보를 저장.

-> stub은 해당 라이브러리의 주소로 대체되어 해당 routine을 수행함.

-> linking하고자 하는 routine의 주소는 다른 address space에 저장되므로, 다른 프로세서의 메모리에 접근하기 위해서는 operating system의 도움이 필요함.

Shared library

-> 각각의 프로그램에 library를 포함시키지 않으므로 메모리를 효율적으로 사용 가능.

-> Library가 업데이트 될 경우 static library는 linking을 다시 해야 하는데 shared library는 library만 업데이트 하면 됨

③ Swapping

프로세스가 일시적으로 메모리 밖으로 나감.

계속 수행하기 위해 다시 메모리 안으로 들어옴

swap in, out 시간 오래 걸림

④ Contiguous Memory Allocation

프로세스를 연속적으로 할당

● 레지스터

1. Relocation registers

-> base address

2. Limit registers

-> process 크기

● 연산

1. Address translation

-> offset (logical address) + base address

2. Memory protection

-> logical address < limit register

● Dynamic storage allocation

1. First fit: 제일 첫 번째 남은 공간

2. Best fit: 제일 작은 남은 공간

3. Worst fit:제일 큰 남은 공간

● Fragmentation

1. External fragmentation

  -> contiguous allocation에서 주로 발생.

  -> ∑(홀 크기)는 프로세스 크기 보다 크지만, 각각의 홀 크기는 process 보다 작아서 process 할당 불가

  -> Compaction을 해서 빈 hole들을 합쳐서 process 크기 보다 큰 hole을 만들면 해결 가능.

2. Internal fragmentation

  -> paging에서 주로 발생.

  -> Process를 할당하고 남은 공간이 절대 사용되지 않음.

  -> 메모리 할당 단위 때문에 발생함. 

⑤ Paging

-> Process가 연속적일 필요가 없으므로(non-contiguous) 하나의 process가 분산되어서 저장될 수 있음. 

-> physical memory를 고정된 크기의 block 으로 나눔 (frame)

-> logical memory를 같은 크기의 block으로 나눔 (page)

-> frame 크기 == page 크기

-> 내부 단편화 (O), 외부 단편화 (X)

1. page num 찾기

-> logical address를 page size로 나누기

2. page table 탐색

-> frame num 찾기

3. physical address 계산

-> frame num + page size (시작 주소) + offset

● paging 기본 방법

page number

-> page table 인덱스

page offset

-> page 시작 지점에서 얼마나 떨어져 있는가?

ex. logical address space = 2^m, page size = 2^n 일 때

상위 m-n비트 -> page num

하위 n비트      -> offset

● page number 찾기

● Address translation

page size를 줄이면 내부 단편화 감소하지만

page table entry 관리하는 overhead 증가 (trade-off)

page size 보통 4KB 또는 8KB

● Frame table

-> 각 프레임 당 하나의 항목을 가짐

-> 해당 프레임이 할당됐는지 아닌지에 대한 정보 저장

● 하드웨어 지원

1. 레지스터

  1) PTBR (Page Table Base Register): page table의 위치 가리킴

  2) PTLR (Page Table Length Register): page table의 크기 저장

  -> 메모리 접근 두 번 해야함 (page table 찾기, 실제 데이터 접근)

2. TLB (Translation Look-aside Buffer)

  -> 레지스터에서 메모리 접근 두 번 해야하는 문제 해결

  -> page table의 일부를 저장 (캐시 역할)

  -> TLB에서 주소 찾으면 메모리 접근 안함, 못찾으면 메모리 접근 수행

※ ASID (Address-space Identifier)

  -> 프로세스마다 다른 페이지 테이블을 가지므로, 전역에 있는 TLB는 전체 프로세스에 대한 캐시를 다뤄야 함.

  -> 전역에 있는 TLB 는 테이블에는 단순히 페이지 넘버뿐 아니라, 프로세스 아이디도 가지고 있어야 함. (ASID)

  -> context switch 할 때 page table을 교체할 필요 없음

● Associative memory

-> parallel search

● TLB가 장착된 페이징 하드웨어

● Memory Protection

-> page table에 valid/invalid bit 추가

1. valid    : page가 process의 logical address space에 있고 유효한 상태

2. invalid : page가 process의 logical address space에 속하지 않음

valid bit이지만 process 영역이 아닐 수도 있으므로 PTLR 확인 필요

⑥ Structure of the Page Table

1. Hierarchical Paging

2. Hashed Page Tables

3. Inverted Page Tables

● Hierarchical paging

-> 32비트 논리 주소 공간에서 페이지 크기가 4KB (2^12)일 경우 페이지 테이블은 2^20개의 entry를 가진다.

-> 각 entry가 4B일 때 각 프로세스는 4MB (4 * 2^20)의 page table을 가진다. 따라서 page를 여러 개로 나눈다.

1) Two-level page table

논리 주소 공간을 3개로 나눈다.

일반 page table의 경우 32비트 논리 주소 공간을 20비트 page number와 12비트 offset으로 나누는데,

two-level page table은 상위 20비트를 다시 10비트씩 나눠서

상위 10비트는 첫번째 레벨 page table의 인덱스를,

하위 10비트는 두번째 레벨 page table의 인덱스를 가리킨다.

두번째 레벨 page table에서는 frame number를 가리킨다.

Page table이 두개이므로 메모리 공간이 더 필요할 것으로 보이지만,

대부분 invalid bit가 가리키고 있는 2-level page table은 메모리에 저장되지 않으므로 메모리 공간을 적게 사용한다.

두 개의 page table을 탐색해야 하므로 lookup time이 증가한다.

2) Three-level page table

논리 주소 공간을 4개로 나눈다.

64비트 논리 주소 공간의 경우, two-level page table을 사용하면

논리 주소 공간이 각각 42비트, 10비트, 12비트로 나눠진다.

상위 42비트는 여전히 크므로 이를 각각 32비트, 10비트로 나눈다.

결과적으로 64비트의 논리 주소 공간은 32비트, 10비트, 10비트, 12비트로 나눠진다.

Page table의 개수가 3개이므로 lookup time이 증가한다.

● Hashed Page Table

페이지 테이블을 사용하지 않고, 해쉬 태이블 사용

● Inverted page table

Page table을 frame number, page number, pid로 구성한다.

동일한 page number이지만 서로 다른 frame number에 할당될 수 있으므로 이를 구분하기 위해서 pid를 추가한다.

보통의 page table의 경우 각각의 프로세스가 별도의 page table을 가지고 있으므로

page table을 유지하는데 많은 메모리가 필요한데,

inverted page table은 system-wide하게 단 하나의 page table을 가진다.

Page table은 frame index로 정렬한다.

원하는 pid를 찾기 위해서 전체 테이블을 search해야하는 단점이 있다.

⑦ Segmentation

Contiguous allocation

-> 연속적으로 저장되는 단위 = 전체 프로세스

Segmentation

-> 연속적으로 저장되는 단위 = segment

프로그램을 segment 단위(function, stack, code 영역 등)로 나눈다. (Segment는 contiguous하게 저장함.)

프로그래머가 인지하는 메모리의 모습을 실제 물리 메모리의 모습으로 변환하는 메모리 기법

세그먼트의 길이는 다양하며, 각 세그먼트의 길이는 프로그램 목적에 따라 자동적으로 결정

1. Address translation

base                : segment의 시작지점

limit                : segment의 길이

logical address   : <segment num, offset>

physical address : base + offset

2. Memory protection

offset과 segment table의 limit을 비교.

offset이 limit보다 크면 protection 위배

Segment-table base register(STBR): segment table이 저장된 메모리 상의 주소 저장

Segment-table length register(STLR): segment table의 개수 저장

Outline

① The Deadlock Problem

② System Model

③ Deadlock Characterization

④ Resource Allocation Graph

⑤ Methods for Handling Deadlocks

⑥ Deadlock Prevention

⑦ Deadlock Avoidance

⑧ Deadlock Detection

⑨ Recovery from Deadlock

① The Deadlock Problem

● Bridge Crossing Example

1. 자동차를 강에 던지기

  -> kill the process

2. 차를 후진하기

  -> preempt the resource and rollback

3. 1차선 도로에 이미 자동차가 존재할 경우 데드락 발생이 예상되므로 safe state까지 진입하지 않고 대기

  -> deadlock avoidance

4. 1차선 도로에 자동차 두대가 진입했을 경우 데드락이 탐지됨

  -> deadlock detection

● 방지 및 대처

1. Deadlock detection

2. Deadlock avoidance

3. Deadlock recovery

4. Deadlock prevention

② System Model

③ Deadlock Characterization

● 데드락의 필요 조건

1. Mutual exclusion

  -> 한 번에 하나의 프로세스만 리소스 사용 가능.

  -> 리소스를 여러 프로세스가 동시에 접근 가능하면 데드락 발생하지 않음.

2. Hold and wait

  -> 리소스를 가지고 있는 프로세스가 리소스 추가 요청

3. No preemption 

  -> 리소스가 사용 중일 때 다른 프로세스가 리소스를 가로채서 사용하는 것(preemption)을 허용 안함.

  -> Preemption이 된다면 두 개의 프로세스가 리소스를 번갈아가면서 사용할 수 있으므로 데드락 발생하지 않음.

4. Circular wait

  -> p1 → p2

  -> p2 → p3

  -> ...

  -> pn → p1

※ 4가지 필요조건이 모두 만족하더라도 데드락이 무조건 발생하는 것은 아님.

④ Resource Allocation Graph

리소스가 프로세스에게 어떻게 할당되는지를 그래프 형태로 나타냄

Deadlock Detection

1. request edge

  -> 프로세스 → 리소스

  -> Pi → Rj

2. assignment edge

  -> 리소스 → 프로세스

  -> Ri → Pj

● 예시

● 데드락 발생하는경우

1. 사이클 (x)

  -> 발생 (x)

2. 사이클 (o)

  1) resource의 instance 1개: 발생 (o)

  2) resource의 instance 여러 개: 발생 가능성 있음

● 사이클 (O) 데드락 (O)

● 사이클 (O) 데드락 (X)

이전다음

012

⑤ Methods for Handling Deadlocks

● 교착상태 처리방법

1. 시스템이 deadlock 되지 않도록 보장하기

  -> prevention, avoidance

2. 시스템이 deadlock 상태가 되는 것을 허용하되 원상복구하기

  -> detection, recovery

3. deadlock이 발생하지 않은 것처럼 무시하기

  -> 대부분 OS에서 이 방식 사용 (UNIX 포함)

⑥ Deadlock Prevention

● 발생조건 4가지 중 하나 제거

-> infeasible 또는 side effect

1. Mutual exclusion -> "infeasible"

근본적으로 공유 불가능한 resource 존재 (ex. 프린터, mutex 등)

2. Hold and wait -> "side effect"

프로세스가 자원을 요청할 때 다른 자원을 가지고 있으면 안됨

  1) 실행하기 전에 모든 자원을 할당 받을 경우

    -> Low resource utilization, starvation

  2) 리소스를 소유하지 않았을 때만 request를 허용: resource 효율이 저하됨 

    -> Low resource utilization

3. No preemption -> "almost infeasible"

CPU는 preemption 가능하지만 printer 같은 대부분의 resource은 preemption 불가

4. Circular wait -> "side effect"

모든 resource type에 Total ordering 설정

  -> 리소스 효율이 저하됨 (동시에 리소스를 활용할 수 없음)

⑦ Deadlock Avoidance

1. single instance

-> resource allocation graph

2. multiple instance

-> 그래프 만으로는 확인 불가

-> banker's algorithm

● Single instance

이전다음

01

● Multiple instance

목표

시스템이 절대 unsafe state가 되지 않도록 보장

sate state = allocated + demand ≤ available

● Banker's Algorithm

각 프로세스는 최대 자원 요구량을 선언해야 함

1. Available   : 길이 m인 vector  (사용 가능한 instance 수)

2. Max         :  n x m 행렬        (최대 요구 instance 수)

3. Allocation :  n x m 행렬        (최대 요구 instance 수)

4. Need       :  n x m 행렬        (최대 요구 instance 수)

⑧ Deadlock Detection

Deadlock avoidance와 유사

1. single instance

-> corresponding wait-for graph

-> 리소스 제거, 프로세스만 표시

2. multiple instance

-> banker's algorithm 변형

-> need를 current real request로 바꿈

⑨ Recovery from Deadlock

deadlock 발생 시 후속조치

1. Process Termination (kill processes)

  1) deadlock 된 프로세스 모두 종료

  2) cycle 제거될 때까지 한 번에 하나씩 종료

2. Check point & Roll back 

  1) selecting a victim

  2) Roll back

    -> 가장 근접한 check point로 이동

    -> safe state로 돌아가서 재시작 (Process Control Block의 Program Counter 정보 이용)

요약

1. prevention

4개 중 하나 제거

  - mutual exclusion

  - no preemption

  - hold & wait

  - circular wait

2. avoidance

  - single: Resource Allocation graph

  - multiple: Banker's Algorithm

3. detection

  - single: corresponding wait-for graph

  - multiple: Banker's Algorithm 변형

4. recovery

  - kill processes

  - roll back

Outline

① Background

② The Critical-Section Problem

③ Peterson's Solution

④ Hardware support for synchronization

⑤ Semaphores

⑥ Monitors

⑦ Liveness

⑧ Synchronization examples

① Background

● Too much milk problem

공유 자원: 냉장고

● Race Condition

  -> 여러 개의 프로세스가 동일한 자료를 접근/조작

  -> 실행결과가 접근 순서에 따라 바뀜

  -> data consistency를 유지하려면 cooperating processes를 순서에 맞게 실행하도록 보장해야 함

② The Critical-Section Problem

● 임계 구역 (Critical section)

공유 데이터가 접근되는 영역

1. 진입 구역 (entry section)

2. 퇴출 구역 (exit section)

3. 나머지 구역 (remainder section)

요구조건

1. Mutual exclusion

  -> 어떤 프로세스가 임계구역에서 실행 중이면

  -> 다른 프로세스들은 진입하면 안됨

2. Progress

  -> 임계구역에 실행 중인 프로세스가 없으면

  -> entry section의 프로세스 중 하나 임계구역으로 진입

3. Bounded waiting

  -> 일정 시간 후에 임계구역 진입을 보장해야 함

③ Peterson's Solution

두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결함.

int turn;            -> 임계구역으로 진입할 순번

boolean flag[2];  -> 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냄

1. Mutual exclusion

  -> While loop에서 flag[i], flag[j]는 항상 true값이고 turn에 의해서 실행이 결정됨.

  -> turn값은 한번에 한 개의 값만 가질 수 있으므로(i or j) 한번에 하나의 프로세스만 critical section으로 진입.

2. Progress

  -> turn == i이면 Pi 가 임계구역 진입

  -> turn == j이면 Pj 가 임계구역 진입

  -> 만약 Pi가 먼저 실행되고 임계구역에서 빠져나오면 flag[i] == FALSE로 바꾸므로

  -> Pj는 while loop에서 벗어나서 임계구역으로 진입할 수 있음.

3. Bounded waiting

  -> exit section에서 특정 flag 값을 false로 바꿔주어서 while loop를 벗어날 수 있게 보장

  ->  Pi 프로세스가 끝나면 Pj 프로세스가 다음에 실행되는 것이 보장됨.

※ Mutex 만으로는 bounded waiting 보장 안됨

   Waiting array와 같은 추가적인 자료구조 필요

④ Hardware support for synchronization

● Peterson's solution 문제점

1. busy waiting

2. 구현 어려움

● 다중 처리기

특별한 하드웨어 명령어 제공

1. test_and_set()

2. compare_and_swap()

※ 둘 다 bounded waiting 보장 안함

   waiting array 있어야 함

⑤ Semaphores

semaphore S: 정수 변수

wait(), signal()로 접근 가능

1. counting semaphore

  -> domain 범위 제한 (x)

  -> mutual exclusion 보장 (x)

2. binary semaphore

  -> domain 범위 0 또는 1

  -> mutex lock

● Spin lock, busy waiting

  -> while 사용할 경우 process running 상태

  -> CPU 계속 사용 중

● Semaphores without busy waiting

  -> 프로세스를 waiting 상태로 전환

  -> busy waiting 대신 waiting queue 사용

1. block()

  -> 특정 프로세스를 waiting 상태로 전환하고 waiting queue에 넣음

  -> 제어권 넘김

2. wakeup()

  -> waiting queue에 있는 프로세스 중 하나를 제거하고 ready queue에 넣음

● 비교

1. 임계구역 짧음

  -> spin lock이 더 나음

  -> 상태 전환 시간이 waiting 시간보다 더 걸림

2. 임계구역 긺

  -> without busy waiting이 더 나음

⑥ Monitors

데이터와 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어서 보호

● Semaphore의 문제점

1. Difficult to code

2. Difficult to prove correctness

3. Requirs voluntary cooperation

4. Single misuse affects entire system

● 특징

1. 추상화된 데이터 형 (ADT)

2. 모니터 안에 항상 하나의 프로세스만이 활성화

● 조건

  -> 특정 시점에 오직 하나의 프로세스만이 모니터에서 활성화 되어야함. (mutual exclusion property)

  -> 다른 프로세스들은 큐에 넣고 기다리게 함

● 구현

1. shared data

  -> monitor 내의 operation들이 공유하는 데이터

2. operation

  -> monitor 내에서 접근하는 함수

3. initialization code

  -> 초기화 코드

  -> entry queue에서 다른 프로세스들이 기다리게 하기 위해서 추가적인 요소 필요

4. condition variable: 활성화되지 않은 프로세스들을 기다리게 하도록 지원하는 변수

  1) x.wait(): 해당 operation을 호출한 프로세스는 일시정지됨(entry queue에 추가)

  2) x.signal(): x.wait()를 호출했던 프로세스들 중 하나를 다시시작함(entry queue에서 제거)

⑦ Liveness

● Liveness

시스템은 반드시 프로세스들의 실행 생명 주기 동안 진행되는 것을 보장해야 한다

(A system must satisfy to ensure that processes make progress during their execution life cycle)

● Deadlock

두 개 이상의 프로세스가 waiting process 중 하나에 의해서만 발생할 수 있는 사건을 무한정 기다리는 상황

● Bounded-Buffer Problem

1. Binary semaphore

  -> Mutex semaphore: critical section 진입 가능 여부 확인. (초기값: 1)

2. Counting semaphore

  -> Full semaphore: buffer에 들어있는 item의 개수. (초기값: 0)

  -> Empty semaphore: buffer의 빈 공간의 개수. (초기값: n)

● Dining-Philosophers Problem

shared-data: 밥 (data set)

semaphore: 젓가락[5] (초기화: 1)

해결방안

1. 한 번에 4명만 앉도록

2. 젓가락 2개 집는 걸 atomic 하게

3. asymmetric solution

  -> 짝수: 왼쪽 젓가락 먼저, 오른쪽 젓가락 나중에

  -> 홀수: 오른쪽 젓가락 먼저, 왼쪽 젓가락 나중에

⑧ Synchronization examples

● POSIX mutex

● POSIX semaphore

Outline

① Examples

② Basic Concepts

③ Scheduling Criteria

④ Scheduling Algorithms

⑤ Multiple-Processor Scheduling

⑥ Thread Scheduling

⑦ Linux Scheduling

⑧ Algorithm Evaluation

① Examples

TV 스케줄링

가족이 TV 보는 시간을 어떻게 할당할 것인가?

CPU 스케줄링

프로세스가 CPU를 사용하는 시간을 어떻게 할당할 것인가?

② Basic Concepts

● 스케줄링 기본 규칙

I/O Bound 프로세스에 더 높은 우선순위 부여

=> 프로세스가 ready 큐에서 기다리는 평균 waiting time을 최소화함

● CPU 스케줄러

CPU가 유휴상태가 될 때마다 운영체제는 ready 큐에 있는 프로세스들 중 하나를 CPU에 할당

● CPU 스케줄링이 결정되는 상황

1. running -> waiting      (비선점)

2. running -> ready        (선점)

3. waiting -> ready         (선점)

4. terminates                 (비선점)

● 커널에서의 Preemption

1. system call

우선순위 B > A일 때

  1) Preemptive kernel

     -> Preemption을 허용해서 A 프로세스의 SYSTEM CALL을 중단시키고 B 프로세스 우선 수행

  2) Non-preemptive kernel

    -> A 프로세스의 SYSTEM CALL이 끝나길 기다리고 B 프로세스 수행

2. HW Interrupt handler

-> 빠르게 무조건적으로 수행되어야 하므로 preemption 허용 안함

● 디스패처 (Dispatcher)

CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 넘겨주는 모듈

1) context switch

2) 사용자 모드로 전환

3) 프로그램을 다시 시작하기 위해 user program의 적절한 위치로 이동

● Dispatcher Latency

디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간

③ Scheduling Criteria

● 스케줄링 기준 (Scheduling Criteria)

1. CPU 이용률 (Utilization)

  -> CPU 최대한 바쁘게 유지

2. 처리량 (Throughput)

  -> 단위 시간 당 완료된 프로세스 개수

3. 총 처리시간 (Turnaround time)

  -> 프로세스 완료 시간 - 요청 시간

4. 대기 시간 (Waiting time)

  -> ready 큐에서 기다린 시간

5. 응답 시간 (Response time)

  -> 하나의 요구를 제출한 후 첫 번째 응답이 시작되는데까지 걸리는 시간

● 최적화 기준

1. 최대화

  -> CPU 이용률, 처리량

2. 최소화

  -> 총 처리시간 (Turnaround time), 대기 시간 (waiting time), 응답 시간 (response time)

④ Scheduling Algorithms

● FCFS (First-Come, First-Served)

-> 먼저 들어온 프로세스에게 더 높은 우선순위 부여.

-> 프로세스가 들어온 순서에 따라서 average waiting time이 달라짐.

-> 전체 프로세스 수행 시간은 동일.

-> 짧은 프로세스가 긴 프로세스 뒤에서 기다리는 현상인 convoy effect가 발생할 수 있음.

-> CPU burst가 짧은 i/o bound process에게 우선순위를 높게 주어서 convoy effect 제거 가능.

Ex) CPU Burst time: P1 = 24, P2 = 3, P3 = 3일때,

1) P1, P2, P3 순서 : Average waiting time = (0 + 24 + 27) / 3 = 17

2) P2, P3, P1 순서 : Average waiting time = (6 + 0 + 3) / 3 = 3

● SJF (Shortest-Job-First)

가장 짧은 Cpu burst length를 갖는 프로세스에게 높은 우선순위 부여.

1. Non-preemptive

  -> 새로 도착한 task의 cpu burst length가 먼저 수행된 tsak의 cpu burst length보다 짧아도

  -> 먼저 수행된 task가 끝나기를 기다림.

2. Preemptive

  -> 새로 도착한 task의 cpu burst length가 먼저 수행된 task의 “남은 시간”보다 짧을 경우

  -> 새로운 task로 context switch. Average waiting time을 최소화 할 수 있음.

Ex) CPU Burst time: P1 = 7, P2 = 4, P3 = 1, P4 = 4,

     Arrival time: P1 = 0, P2 = 2, P3 = 4, P4 = 5일때

1) Average waiting time of Non-preemptive: (0 + (8-2) + (7-4) + (12-5)) / 4 = 4

2) Average waiting time of Preemptive: ((11-2) + (5-4) + 0 + (7-5)) / 4 = 3

문제점

기아 (starvation): 높은 우선순위를 가진 프로세스들이 꾸준히 들어와서 낮은 우선순위 프로세스들이 CPU를 얻지 못함

해결

노화 (aging): 오래동안 대기한 프로세스들의 우선순위를 점진적으로 증가시킴

CPU 버스트 길이 예측

Exponential Averaging

  -> 오래된 작업일수록 낮은 가중치 부여, 최신 작업일수록 높은 가중치를 부여하여 다음 CPU burst의 길이를 예측한다.

● Round-Robin

시간 할당량 (time quantum)만큼 실행 후 프로세스 변경

SJF에 비해서

turnaround time : 더 긺

response time    : 더 짧음

q 크면

  -> FIFO (프로세스 잘 안바뀜)

q 작으면

  -> context switch 자주 발생해서 overhead 증가 (프로세스 자주 바뀜)

  -> context switch overhead와 response time의 trade-off

※ 각 프로세스는 (n-1) * q 시간 이상 대기하지 않음

● Multilevel Queue

포그라운드, 백그라운드 프로세스로 구분

ready 큐를 다수의 별도의 큐로 분류

각 큐는 자신의 스케줄링 알고리즘을 가짐

큐 간 스케줄링 알고리즘 존재

Fixed priority preemptive scheduling

batch process 실행 중에 interactive editing process가 ready 큐에 들어가면 batch process 선점됨

● Multilevel Feedback Queue

다단계 큐: 프로세스 이동 (x)

다단계 피드백 큐: 프로세스 이동 (o)

프로세스들을 CPU 버스트 성격에 따라 구분

CPU 시간 많이 사용   -> 낮은 우선순위 큐로 이동

오래 대기한 프로세스 -> 높은 우선순위 큐로 이동

quantum = 8에서

CPU burst 8 이하 -> 끝

CPU burst 8 초과 -> 다음으로 이동

quantum = 16에서

CPU burst 16 이하 -> 끝

CPU burst 16 초과 -> 다음으로 이동

⑤ Multiple-Processor Scheduling

1. Symmetric multiprocessing

  -> 각각의 프로세서는 자신만의 스케줄링 결정을 내림

  -> Master-slave relationship 없음

2. Asymmetric multiprocessing

  -> 하나의 프로세서만이 시스템 자료구조에 접근, data 공유의 의무를 완화시킴

  -> Master-slave relationship 있음

● Process affinity

1. Soft affinity

  -> operating system이 프로세스를 affinity 관계에 있는 CPU에 할당하려고 하지만 보장은 되지 않음

2. Hard affinity

  -> operating system이 프로세스를 affinity 관계에 있는 CPU에 할당하는 것을 보장함.

  -> 프로그래머가 특정 CPU에 할당되도록 operating system에 system call 요청.

● Load balancing

특정 CPU에 일이 몰리지 않도록 적절히 분배

1. Push migration

  -> specific한 task가 프로세서들을 확인, 불균형이 발견됐을 경우 다른 CPU에게 작업을 나눠 줌(push)

2. Pull migration

  -> idle한 CPU가 바쁜 CPU의 일을 가져옴(pull)

⑥ Thread Scheduling

user thread는 별도로 스케줄링 되는 개체

LWP (Light Weight Process)를 통해 간접적으로 kernel thread와 연결

1. Local Scheduling

  -> 쓰레드 라이브러리가 어떤 쓰레드를 이용 가능한 LWP에 넣을 것인지 결정

  -> 프로세스 경쟁 범위 (Process-contention Scope): 동일한 프로세스에 속한 쓰레드들 사이에서 CPU 경쟁

2. Global Scheduling

  -> 커널이 어떤 커널 쓰레드를 다음에 실행시킬 지 결정

  -> 시스템 경쟁 범위 (System-contention Scope): CPU 상에 어느 커널 쓰레드를 스케줄링 할 것인지 결정

⑦ Linux Scheduling

리눅스

각 클래스별로 특정 우선순위 부여받는 스케줄링 클래스 기반

1. real-time class

  -> 우선순위: 0 ~ 99

  -> 항상 높은 우선순위 프로세스 선호

2. conventional class

  -> 우선순위: 100 ~ 139

  -> CFS (Completely Fair Sharing)

● CFS (Completely Faire Sharing)

-> 임의의 한 시점에서 봤을 때 프로세스 진행률은 항상 일정한 비율 유지

-> CPU는 하나이므로 특정 시간에서 실행할 수 있는 task는 오직 하나

-> 불가능

● virtual time mechanism

다음 수행할 작업으로 가장 낮은 vruntime값을 가지는 작업을 선택.

⑧ Algorithm Evaluation

1. 결정론적 모델링 (Deterministic Modeling)

  -> 사전에 정의된 특정한 work load를 받아들임

  -> work load에 대한 각 알고리즘의 성능 정의

  -> 간트 차트 사용

※ Predetermined work load 예시

2. 큐잉 모델 (Queueing Models)

  -> 상황에 따라 실행되는 프로세스들 매번 바뀜

  -> 수학적으로 분석

  -> 복잡한 알고리즘, 분포와 관련된 수학적 분석 어려움

  -> 실제 시스템의 근사치이며, 연산 결과의 정확성에 의심의 여지가 있음

3. 모의실험 (Simulation)

-> 실제 시스템의 연속적 사건들 사이 관계 때문에 부정확할 수 있음

4. 구현 (Implementation)

  -> 가장 정확함

  -> 비용이 많이 듦

Outline

① Motivation

② Overview

③ Multicore programming

④ Multithreading models

⑤ Thread libraries

⑥ Threading issues

⑦ Thread programming API

① Motivation

새 요청 받을 때마다 프로세스 생성 (fork() 호출) 하면 리소스, 시간 많이 필요

쓰레드 사용 시 overhead 줄일 수 있음

② Overview

● Thread

  - CPU 이용의 기본 단위

  - 같은 프로세스에 속한 다른 쓰레드와 운영체제 자원 공유 (콛, 데이터 섹션, 열린 파일, 신호 등)

● 장점

1. 응답성

  - 특정 쓰레드가 block 되어도 나머지 쓰레드 실행 가능

2. 자원 공유

  - 프로세스: IPC 통해서 공유

  - 쓰레드: 자동적으로 프로세스의 자원, 메모리 공유 (code, data, file)

3. 경제성

  - 프로세스 생성을 위해 메모리와 자원 할당 하는 것은 비용 많이 듦

  - 쓰레드는 자신이 속한 프로세스의 자원 공유. 쓰레드 생성, 문맥 교환이 더 경제적

4. 규모 적응성

  - 다중 처리기 구조이므로 각 쓰레드가 다른 처리기에서 병렬로 수행 (multi processor 활용 가능)

③ Multicore programming

여러 개의 쓰레드 동시에 실행 가능

코어가 여러 CPU 칩 형태를 띠거나, 칩 안에 여러 개의 코어가 존재

1. 병행성 (Concurrent)

  - 모든 태스크가 진행되게끔 함으로써 하나 이상의 태스크 지원

  - 동시에 수행되는 것처럼 보임

2. 병렬성 (Parallelism)

  - 하나 이상의 태스크를 동시에 수행

  - 실제 병렬적으로 수행

  1) 데이터 병렬 (Data parallelism)

  - 동일한 데이터의 부분 집합을 다수의 계산 코어에 분배한 뒤, 각 코어에서 동일한 연산 실행

  - 하나의 일을 여러 개로 쪼개서 처리

  2) 태스크 병렬 (Task parallelism)

  - 태스크를 다수의 코어에 분배. 각 쓰레드는 고유의 연산 실행

  - 여러 개의 일을 처리

● 멀티코어 프로그래밍이 어려운 이유

1. 태스크 인식

  - 응용 프로그램을 분석하여 독립된 병행가능 태스크로 나눌 수 있는 영역 찾아야 함

  - 태스크는 독립적이고 개별코어에서 병렬실행 가능해야 함

2. 밸런싱

  - 찾아진 부분들이 균등한 기여도를 가지도록 태스크를 나누어야 함 (전체 성능 저하될 수 있음)

3. 데이터 분리

  - 응용 프로그램이 독립된 태스크로 나눠지는 것처럼, 태스크가 접근하고 조작하는 데이터 또한 개별 코어에서 사용가능하도록 나눠져야 함

4. 데이터 종속성

  - 태스크가 접근하는 데이터는 둘 이상의 태스크 사이에 종속성이 없는지 검토해야 함

5. 시험 및 디버깅

  - 다양한 실행경로 존재

=> 이 때문에 Multi Threading 사용

④ Multithreading models

● 종류

1. 사용자 쓰레드 (user thread)

  - 커널 위에서 수행됨. 커널과 관련 없음

2. 커널 쓰레드 (kernel thread)

  - 커널 내부에서 생성, 파괴됨.

  - 운영체제에 의해서 관리됨

● 모델

1. Many-to-One

  - user thread 여러 개

  - kernel thread 한 개

  - 장점: 쓰레드가 커널이 아닌 사용자 공간의 쓰레드 라이브러리에 의해 행해지므로 빠르고 오버헤드가 적음

  - 단점: blocking system call 호출하면 전체 프로세스가 block됨. 다중 코어 시스템에서 병렬로 실행 불가

2. One-to-One

  - user thread 한 개

  - kernel thread 한 개

  - 장점: blocking system call 호출해도 다른 작업 가능. 다중 코어 시스템에서 병렬로 실행 가능

  - 단점: 커널 쓰레드 많이 생성하므로 오버헤드 증가

3. Many-to-Many

  - user thread 한 개

  - kernel thread 한 개

  - 다대일, 일대일 모델의 장점 모두 가짐

  - 개발자는 필요한 만큼 user thread 생성

  - kernel thread는 멀티 프로세서에서 병렬 실행 가능

  - blocking system call 호출하면 커널이 다른 쓰레드의 수행을 스케줄링 가능

4. Two-Level

  - 다대다, 일대일 둘 다 사용

  - Bound thread: One-to-One 모델을 쓰고 있는 쓰레드

⑤ Thread libraries

프로그래머에게 쓰레드를 생성하고 관리하기 위한 API 제공

● 구현

1. 사용자 공간에서만 라이브러리 제공

  - 라이브러리 호출 시 사용자 공간의 지역함수 호출. 시스템 콜 호출 안함

2. 커널 수준 라이브러리 구현

  - 라이브러리 호출 시 커널 시스템 콜 호출

● 종류

1. POSIX Pthread

  - 사용자 / 커널

2. Win32 thread

  - 커널

3. Java thread

  - 호스트 시스템에 따라 다름

⑥ Threading issues

● 쓰레드가 fork() 호출 시 새 프로세스는 모든 쓰레드 복사? 한 개의 쓰레드만 복사?

1. fork() 호출 후 exec() 호출

  - fork()를 호출한 쓰레드만 복사

2. fork() 호출 후 exec() 호출 안함

  - 모든 쓰레드 복사

● 신호 처리

- 신호: 프로세스에게 어떤 사건이 일어났음을 알려줌

1. 동기식 신호

  - 실행 중인 프로세스에서 발생

  - 연산을 수행한 동일한 프로세스에게 전달됨

  - ex) 잘못된 메모리 접근, div by 0

2. 비동기식 신호

  - 실행중인 프로세스 외부에서 발생

  - 다른 프로세스에게 전달됨

  - ex) 타이머 만료, ctrl+c

※ 신호 전달: pthread_kill(pthread_t tid, int signal) (프로세스 kill 하는 것 아님!!)

● 쓰레드 취소

쓰레드가 끝나기 전에 그것을 강제종료 시킴

1. 비동기식 취소

  - 한 쓰레드가 목적 쓰레드를 즉시 강제종료

  - 모든 시스템 자원 다 회수 못하는 경우 있음

2. 지연 취소

  - 자신이 취소되어도 안전하다고 판단되는 시점에서 취소 여부 검사

  - 목적 쓰레드가 주기적으로 자신이 강제종료 되어야 할 지 점검

  - 목적 쓰레드 질서정연하게 강제종료 될 수 있음

● 쓰레드 풀

프로세스를 시작할 때 일정한 수의 쓰레드들을 미리 쓰레드 풀로 만들어 둠

CPU 시간, 메모리 공간 등 시스템 자원의 고갈을 막아줌

일 없으면 기다리다가 요청 들어오면 쓰레드 풀에서 한 쓰레드에 할당

장점: 새 쓰레드 생성하는 것보다 기존 쓰레드 할당하는 것이 더 빠름

쓰레드 개수 재한하면 많은 수의 쓰레드를 병렬처리 할 수 없는 시스템에 도움을 줌

● Thread specific data

  - Allows each thread to have its own copy of data

  - Most thread libraries provide some form of support for thread-specific data

⑦ Thread programming API

pthread_create: 새 쓰레드 생성

pthread_join: 특정 쓰레드의 종료를 기다림

pthread_exit: 쓰레드를 종료시키고 join 호출한 쓰레드에게 메시지를 전달