OS-12-Disk Management and Scheduling

Aug 03, 2021 in Computer Science, OS

Disk Structure

logical block
- 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
- 주소를 가진 1차원 배열처럼 취급
- 정보를 전송하는 최소 단위
Sector
- Logical block이 물리적인 디스크에 매핑된 위치
- Sector 0은 최외각 실린더의 첫 트랙에 있는 첫 번째 섹터이다

Disk Scheduling

Access time의 구성
- Seek time
  - 헤드를 해당 실린더로 움직이는데 걸리는 시간
- Rotational latency
  - 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
- Transfer time
  - 실제 데이터의 전송 시간
Disk bandwidth
- 단위 시간 당 전송된 바이트의 수
Disk Scheduling
- seek time을 최소화하는 것이 목표
- Seek time := seek distance

Disk Management

physical formatting (Low-level formatting)
- 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
- 각 섹터는 header + 실제 data(보통 512 bytes) + trailer로 구성
- header와 trailer는 sector number, ECC (Error-Correcting Code) 등의 정보가 저장되며 controller가 직접 접근 및 운영
Partitioning
- 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
- OS는 이것을 독립적 disk로 취급 (logical disk)
Logical formatting
- 파일 시스템을 만드는 것
- FAT, inode, free space 등의 구조 포함
Booting
- ROM에 있는 “small bootstrap loader”의 실행
- sector 0 (boot block)을 load하여 실행
- sector 0은 “full Bootstrap loader program”
- OS를 디스크에서 load하여 실행

Disk Scheduling Algorithm

큐에 다음과 같은 실린더 위치의 요청이 존재하는 경우 디스크 헤드 53번에서 시작한 각 알고리즘의 수행 결과는? (실린더 위치는 0-199)
- 98, 183, 37, 122, 14, 124, 65, 67
FCFS
SSTF
SCAN
C-SCAN
N-SCAN
LOOK
C-LOOK

FCFS (First Come First Service)

SSTF (Shortest Seek Time First)

SCAN

disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다
다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동한다
문제점: 실린더 위치에 따라 대기시간이 다르다 (중앙에 위치한 것이 2배 더 많이 실행된다)

C-SCAN

헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리
다른쪽 긑에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동
SCAN보다 균일한 대기 시간을 제공한다

Other Algorithms

N-SCAN
- SCAN의 변형 알고리즘
- 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service
LOOK and C-LOOK
- SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
- LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동한다

C-LOOK

Disk-Scheduling Algorithm의 결정

SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK, C-LOOK 등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음
File의 할당 방법에 따라 디스크 요청이 영향을 받음
디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직하다

Swap-Space Management

Disk를 사용하는 두 가지 이유
- memory의 volatile한 특성 -> file system
- 프로그램 실행을 위한 memory 공간 부족 -> swap space (swap area)
Swap-space
- Virtual memory system에서는 디스크를 memory의 연장 공간으로 사용
- 파일 시스템 내부에 둘 수도 있으나 별도 patition 사용이 일반적
  - 공간 효율성보다는 속도 효율성이 우선
  - 일반 파일보다 휠씬 짧은 시간만 존재하고 자주 참조됨
  - 따라서, block의 크기 및 저장 방식이 일반 파일시스템과 다름

RAID

RAID (Redundant Array of Independent Disks)
- 여러 개의 디스크를 묶어서 사용
RAID의 사용 목적
- 디스크 처리 속도 향상
  - 여러 디스크에 block의 내용을 분산 저장
  - 병렬적으로 읽어 옴 (interleaving, striping)
- 신뢰성(reliability) 향상
  - 동일 정보를 여러 디스크에 중복 저장
  - 하나의 디스크가 고장시 다른 디스크에서 읽어옴 (Mirroring, shadowing)
  - 단순히 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다

Comment and share

OS-11-File Systems

Jul 30, 2021 in Computer Science, OS

File and File System

File
- “A named collection of related information”
- 일반적으로 비휘발성의 보조 기억 장치에 저장
- 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해 줌
- Operation
  - create, read, write, reposition (lseek), delete, open, close 등
File attribute (혹은 파일 metadata)
- 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들
  - 파일 이름, 유형, 저장된 위치, 파일 사이즈
  - 접근 권한 (읽기/쓰기/실행), 시간 (생성/변경/사용), 소유자 등
File system
- 운영체제에서 파일을 관리하는 부분
- 파일 및 파일의 메타 데이터, 디렉토리 정보 등을 관리
- 파일의 저장 방법 결정
- 파일 보호 등

open()

open(“/a/b/c)
- 디스크로부터 파일 c의 메타 데이터를 메모리로 가지고 옴
- 이를 위하여 directory path를 search
  - 루트 디렉토리 “/“를 open하고 그 안에서 파일 “a”의 위치 획득
  - 파일 “a”를 open한 후 read하여 그 안에서 파일 “b”의 위치 획득
  - 파일 “b”를 open한 후 read하여 그 안에서 파일 “c”의 위치 획득
  - 파일 “c”를 open한다
- Directory path의 search에 너무 많은 시간 소요
  - Open을 read/write와 별도로 두는 이유임
  - 한 번 open한 파일은 read/ write 시 directory search 불필요
- Open file table
  - 현재 open된 파일들의 메타데이터 보관소 (in memory)
  - 디스크의 메타데이터보다 몇 가지 정보가 추가
    - Open한 프로세스 수
    - 한 번 open한 파일은 read/ write 시 directory search 불필요
- File descriptor (file handle, file control block)
  - Open file table에 대한 위치 정보 (프로세스 별)
- /a/b/c search 및 파일 읽기 과정
  1. OS가 hard disk의 root metadata의 저장 위치를 알기 때문에 Open file table에 root metadata 정보를 저장한다
  2. root metadata에서 a의 metadata 위치정보를 통해 metadata 정보를 불러온다
  3. 앞의 과정을 반복한다
  4. file descripter를 통해서 fd에 b의 metadata 정보를 읽는다
  5. b의 metadata 정보로 file b의 내용을 OS의 메모리에 올린다
  6. OS 메모리에 올라간 정보를 Process A의 메모리에 올린다

File Protection

각 파일에 대해 누구에게 어떤 유형의 접근(read/write/execution)을 허락할 것인가?
Access Control 방법
- Access Control Matrix
  - Access control list: 파일별로 누구에게 어떤 접근 권한이 있는지 표시 - Capability: 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시
- Grouping
  - 전체 user를 owner, group, public의 세 그룹으로 구분
  - 각 파일에 대해 세 그룹의 접근 권한 (rwx)을 3비트씩으로 구분
- Password
  - 파일마다 password를 두는 방법
  - 모든 접근 권한에 대해 하나의 password: all or noting
  - 접근 권한별 password: 암기 문제, 관리 문제

File System의 Mounting

물리적 디스크로 논리적 디스크 disk1 disk2, disk3으로 파티셔닝
이후에 disk1의 root 디렉토리의 하위 디렉토리 중 하나로 disk1, disk2를 위치시킴 (= Mounting)

Access Methods

시스템이 제공하는 파일 정보의 접근 방식
- 순차 접근 (sequential access)
  - 카세트 테이프를 상요하는 방식처럼 접근
  - 읽거나 쓰면 offset은 자동적으로 증가
- 직접 접근 (direct access, random access)
  - LP 레코드 판과 같이 접근하도록 함
  - 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있음

Allocation of File Data in Disk

Contiguous Allocation
Linked Allocation
Indexed Allocation

Contiguous Allocation

단점
- external fragmentation
- File grow가 어려움
  - file 생성시 얼마나 큰 hole을 할당할 것인가?
  - grow 가능 vs 낭비 (internal fragmentation)
장점
- Fast I/O
  - 한 번의 seek/rotation으로 많은 바이트 transfer
  - Realtime file 용으로, 또는 이미 run중이던 process의 swapping 용
  - swap area의 저장 데이터는 영구저장용이 아니기 때문에 공간 효율성을 중요하게 여기지 않는다
- Direct access(=random access)가능

Linked Allocation

장점
- External fragmentation 발생 안 함
단점
- No random access
- Reliability 문제
  - 한 sector가 고장나면 pointer가 유실되면 많은 부분을 잃음
- Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
  - 512 bytes/sector, 4 bytes/pointer
변형
- File-allocation table (FAT) 파일 시스템
  - 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결

Indexed Allocation

장점
- External fragmentation이 발생하지 않음
- Direct access 가능
단점
- Small file의 경우 공간 낭비 (실제로 많은 file들이 small)
- Too Large file의 경우 하나의 block으로 index를 저장하기에 부족
  - linked scheme
  - multi-level index

UNIX 파일 시스템의 구조

inode에서 index allocation 사용하며 파일 사이즈에 따라 multi level index의 수가 달라집니다

FAT File System

Linked Allocation 방식으로 파일을 저장합니다

사용하면 파일에 파일 시작 주소값 217을 저장하고 다음 데이터가 저장된 주소값은 FAT에 217번지에 저장되어있는 주소값을 제공하는 방식으로 파일 데이터의 저장 위치를 제공합니다

VFS and NFS

Virtual File System (VFS)
- 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스 (API)를 통해 접근할 수 있게 해주는 OS의 layer
Network File System (NFS)
- 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다
- NFS는 분산 환경에서의 대표적인 파일 공유 방법이다

Page Cache and Buffer Cache

Page Cache
- Vitrual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
- Memory-Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용
Memory-Mapped I/O
- File의 일부를 virtual memory에 mapping 시킴
- 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
- OS를 거치지 않고 File에 접근 할 수 있다.
  
  Process의 code, data, stack 영역중 code 영역은 read-only 파일이 때문에
  
  swap area에 존재하지 않으며 memory-mapped I/O 빙식을 사용할 수 있다.
Buffer Cache
- 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
- File 사용의 locality 활용
  - 한 번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달
- 모든 프로세스가 공용으로 사용
- Replacement algorithm 필요 (LRU, LFU 등)
Unified Buffer Cache
- 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨

참고

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

Comment and share

OS-10-Virtual Memory

Jul 28, 2021 in Computer Science, OS

Demand Paging

실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소 -> 많은 프로세스가 메모리에 올라올 수 있기 때문에
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid / Invalid bit의 사용
- Invalid의 의미
  - 사용되지 않은 주소 영역인 경우
  - 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- address translation 시에 invalid bit이 set되어 있으면
- -> page fault

Page Fault

invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
Kernel mode로 들어가서 page fault handler가 invoke됨
다음과 같은 순서로 page fault를 처리한다
1. Invalid reference? (e.g. bad address, protection violation) => abort process
2. Get an empty page frame. (없으면 뺏어온다: replace)
3. 해당 페이지를 disk에서 memory로 읽어온다
  1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
  2. Disk read 가 끝나면 page tables entry 기록, valid/invalid bit = “valid”
  3. ready queue에 process를 insert -> dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running
5. 아까 중단되었던 instruction을 재개

Demand Paging의 성능

Page Fault Rate 0 <= p <= 1.0
- if p = 0, no page faults
- if p = 1, every reference is a fault

Effective Acess Time

= (1 - p) * (memory access) 
    + p * (OS & HW page fault overhead
            + [swap page out if needed]
            + swap page in
            + OS & HW restart overhead)

Free frame이 없는 경우

Page replacement
- 어떤 frame을 빼앗아올지 결정해야 함
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에 쫓겨났다가 다시 들어올 수 있음
Replacement Algorithm
- page-fault을 최소화하는 것이 목표
- 알고리즘의 평가
  - 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

Page Replacement Algorithm

Optimal Algorithm

MIN(OPT): 가장 먼 미래에 참조되는 page를 replace
4 frames example
미래에 참조를 어떻게 아는가?
- Offline algorithm
다른 알고리즘의 성능에 대한 upper bound 제공
- Belady’s optiaml algorithm, MIN, OPT 등으로 불림

FIFO (First In First Out) Algorithm

FIFO: 먼저 들어온 것을 먼저 내쫓음

FIFO Algorithm은 Page frame을 늘렸을 때 Page fault가 더 발생할 수 있다

LRU (Least Recently Used) Algorithm

LRU: 가장 오래 전에 참조된 것을 지움

LFU (Least Frequently Used) Algorithm

LFU: 참조 횟수(reference count)가 가장 적은 페이지를 지움
- 최저 참조 횟수인 page가 여럿 잇는 경우
  - LFU 알고리즘 자체에서는 여러 page 중 임으로 선정한다
  - 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
- 장단점
  - LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
  - 참조 시점의 최근성을 반영하지 못함
  - LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 비교

다양한 캐슁 환경

캐슁 기법
- 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
- paging system 외에도 cache memroy, buffer caching, Web caching등 다양한 분야에서 사용
캐쉬 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer caching이나 Web caching의 경우
  - O(1)에서 O(log n) 정도까지 허용
- Paging system인 경우
  - page fault인 경우에만 OS가 관여함
  - 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  - 그 때문에 O(1)인 LRU의 list 조작조차 불가능

Clock Algorithm

Clock algorithm
- LRU의 근사(approximation) 알고리즘
- 여러 명칭으로 불림
  - Second chance algorithm
  - NUR (Not Used Recently) 또는 NRU (Not Recently Used)
- Reference bit을 사용해서 교체 대항 페이지 선정 (circular list)
- reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
- 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈
- Reference bit이 0인 것을 찾으면 그 페이지를 교체
- 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함
- 자주 사용되는 페이지라면 second chance가 올 때 1
Clock algorithm의 개선
- reference bit과 modified bit (dirty bit)을 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지 (swap area에 변경된 정보를 반영하는 I/O 작업이 동반된다)

Page Frame의 Allocation

Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?
Allocation의 필요성
- 메모리 참조 명령어 수행시 명령어, 데이터등 여러 페이지 동시 참조
  - 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
- Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
  - 최소한의 allocation이 없으면 매 loop마다 page fault
Allocation Scheme
- Equal allocation: 모든 프로세스에 똑같은 갯수 할당
- Proportional allocation: 프로세스 크기에 비례하여 할당
- Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

Global replacement
- Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다
- Process별 할당량을 조절하는 또 다른 방법임
- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당 Working set, PFF 알고리즘 사용
Local replacement
- 자신에게 할당된 frame 내에서만 replacement
- FIFO, LRU, LFU등의 알고리즘을 process 별로 운영시

Thrashing

프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
Page fault rate이 매우 높아짐
CPU utilization이 낮아짐
OS는 MPD (multiprogramming degree)룰 높여야 한다고 판단 (I/O 작업때문에 CPU이 이용률이 낮아지기 때문에)
또 다른 프로세스가 시스템에 추가됨 (higher MPD)
프로세스 당 할당된 frame의 수가 더욱 감소
프로세스는 page는 swap in/ swap out으로 바쁨
대부분의 시간에 CPU는 한가함
low throughput

Working-Set Model

Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
- 집중적을 참조되는 해당 page들의 집합을 locality set이라 함
Working-set Model
- Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 page들의 집합을 Working Set이라 정의함
- Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반남한 후 swap out (suspend)
- Thrashing을 방지함
- Multiprogramming degree를 결정함

PFF (Page-Fault Frequency) Scheme

page-fault rate의 상한값과 하한값을 둔다
- page fault rate이 상하값을 넘으면 frame을 더 할당한다
- page fault rate이 하한값 이하이면 할당 frame 수를 줄인다
빈 frame이 없으면 일부 프로세스를 swap out

Page Size의 결정

Page size를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- internal fragmentation 감소
- Disk transfer의 효율성 감소
  - Seek/rotation vs transfer
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  - Locality의 활용 측면에서 좋지 않음
Trend
- Larger page size

참고

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

Comment and share

OS-9 Memoery Management

Jul 26, 2021 in Computer Science, OS

Logical vs Physical Address

Logical address (=virtual address)
- 프로세스마다 독립적으로 가지는 주소 공간
- 각 프로세스마다 0번지부터 시작
- CPU가 보는 주소는 logical address다
Physical address
- 메모리에 실제 올라가는 위치
주소 바인딩: 주소를 결정하는 것
- Symbolic Address -> Logical Address -> Physical address

주소 바인딩

Compile time binding
- 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
- 시작 위치 변경 시 재컴파일
- 컴파일러는 절대 코드(absolute code) 생성
Load time binding
- Loader의 책임하에 물리적 메모리 주소 부여
- 프로그램이 메모리에 올라갈 때 물리적 메모리 주소가 정해짐
- 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
Execution time binding(= Run time binding)
- 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
- CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
- 실행중에 메모리에 쫓겨나고 다시 메모리에 올라갈 때 (Swapping)
- 하드웨어 지원이 필요하다 (e.g., base and limit registers, MMU)

Memory-Management Unit (MMU)

MMU (Memory-Management Unit)
- logical address를 physical address로 매핑해 주는 Hardware device
MMU scheme
- 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (= relocation register)의 값을 더한다
user program
- logical address만을 다룬다
- 실제 physical address를 볼 수 없으며 알 필요가 없다

Hardware Support For Address Translation

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터
Relocation register(= base register) : 접근할 수 있는 물리적 메모리 주소의 최소값
Limit register: 논리적 주소의 범위

용어 정리

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
memory utilization의 향상
가끔식 사용되는 많은 양의 코드의 경우 유용 (ex. 오류 처리 루틴)
운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)
Loading: 메모리로 올리는 것

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
프로세스의 크기가 메모리보다 클 때 유용
운영체제의 지원없이 사용자에 의해 구현
작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
- Manual Overlay
- 프로그래밍이 매우 복잡

Swapping

Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
Backing store(=swap area)
- 디스크
  - 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
Swap in/ Swap out
- 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
- priority-based CPU scheduling algorithm
  - priority가 낮은 프로세스를 swapped out 시킴
  - priority가 높은 프로세스를 메모리에 올려 놓음
- Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함
- Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
- swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

Dynamic Linking

Linking을 실행 시간(execution time)까지 미루는 기법
Static linking
- 라이브러리가 프로그램의 실행 파일 코드에 포함됨
- 실행 파일의 크기가 커짐
- 동일한 라이브러리를 각각의 프로스가 메모리에 올리므로 메모리 낭비 (ex. printf 함수의 라이브러리 코드)
Dynamic linking
- 라이브러리가 실행 시 연결(link)됨
- 라이브러리 호출부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
- 운영체제의 도움이 필요

Allocation Of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용
- OS 상주 영역
  - interrupt vector와 함께 낮은 주소 영역 사용
- 사용자 프로세스 영역
  - 높은 주소 영역 사용
사용자 프로세스 영역의 할당 방법
- Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
  - Fixed partiion allocation
  - Variable partition allocation
- Noncontigous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
  - Paging : 논리 메모리를 같은 크기로 자른다
  - Segment : 논리 메모리를 의미있는 단위로 자른다 (code, data, stack)
  - Paged Segmentation

Contiguous Allocation

고정 분할(Fixed partition) 방식
- 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
- 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
- 분할당 하나의 프로그램 적재
- 융통성이 없음
  - 동시에 메모리에 load되는 프로그램의 수가 고정됨
  - 최대 수행 가능 프로그램 크기 제한
- 가변 분할(Variable partition) 방식
  - 프로그램의 크기를 고려해서 할당
  - 분할의 크기, 개수가 동적으로 변함
  - 기술적 관리 기법 필요
  - External fragmentation 발생

Fragmentation
- External fragmentation(외부 조각)
  - 프로그램 크기보다 분할의 크기가 작은 경우
  - 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
- Internal fragmentation(내부 조각)
  - 프로그램 크기보다 분할의 크기가 큰 경우
  - 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  - 특정 프로그램에 배정되었지만 사용되지 않는 공간
Hole
- 가용 메모리 공간
- 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
- 프로세스가 도착하면 수용가능한 hole을 할당
- 운영체제는 다음의 정보를 유지
  - 할당 공간
  - 가용 공간 (hole)

Dynamic Storage-Allocation Problem
- 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
- 방식 종류
  1. First-fit
    - Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
  2. Best-fit
    - Size가 n 이상인 가장 작은 hole을 찾아서 할당
    - Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
    - 많은 수의 아주 작은 hole들이 생성됨
  3. Worst-fit
    - 가장 큰 hole에 할당
    - 역시 모든 리스트를 탐색해야 함
    - 상대적으로 아주 큰 hole들이 생성됨
  First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐(실험적인 결과) -> Worst-fit은 탐색 + 더 큰 프로그램의 메모리 hole을 차지하기 때문이다
Compaction
- external fragmentation 문제를 해결하는 한 가지 방법
- 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
- 매우 비용이 많이 드는 방법임
- 최소한의 메모리 이동으로 compaction하는 방법 (매우 복잡한 문제)
- Compaction은 프로세스의 주소가 실행 시간에 동적을 재배치가 가능한 경우에만 수행될 수 있다

Paging

Paging
- Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
- Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
- 일부는 backing storage에, 일부는 physical memory에 저장
Basic Method
- physical memory를 동일한 크기의 frame으로 나눔
- logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
- 모든 가용 frame들을 관리
- page table을 사용하여 logical address를 physical address로 변환
- External fragmentation 발생 안함
- Internal fragmentation 발생 가능 (마지막으로 나눠진 Page의 크기가 작기 때문)

Implemntation Of Page Table

Page table은 main memory에 상주
Page-table base register (PTBR)가 page table을 가리킴
Page-table length register (PTLR)가 테이블 크기를 보관
모든 메모리 접근 연산에는 2번의 memory access필요
- page table 접근 1번, 실제 data/instruction 접근 1번

속도 향상을 위해

associatve register 혹은 translation look-aside buffer(TLB)라 불리는

고속의 lookup hardware cache 사용

TLB

Associative registers (TLB): parallel search가 가능
- TLB에는 page table 중 일부만 존재
Address translation
- page table 중 일부가 associative register에 보관되어 있음
- 만약 해당 page #가 associative register에 있는 경우 곧바로 frame #를 얻음
- 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
- TLB는 context switch 때 flush (remove old entries)
Effective Access Time

Two-Level Page Table

현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
- 32 bit address 사용시: 2^32(4G)의 주소 공간
  - page size가 4K시 1M개의 page table entry 필요
  - 각 page entry가 4B시 프로세스 당 4M의 page table 필요
  - 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
    
    -> page table 자체를 page로 구성
    
    -> 사용하지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응하는 inner page table이 없음

Example
- logical address (on 32-bit machine with 4K page size) 구성
  - 20bit의 page number
  - 12bit의 page offset
- page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다 (각 page table entry가 4B)
  - 10-bit의 outer page number
  - 10-bit의 inner page number
  - 12bit의 page offset
- 따라서, logical address는 다음과 같다
- P1은 outer page table의 index이고
- P2는 outer page table의 page에서의 변위(displacement)
2단계 페이징에서 Address-translation scheme
## Multilevel Paging and Performance
Address space가 더 커지면 다단계 페에지 테이블 필요
각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
TLB를 통해 메모리 접근 시간을 줄일 수 있음
4단계 페이지 테이블 을 사용하는 경우
- 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
- TLB hit ratio가 98%인 경우
  - effective memory access time = 0.98 * 120 + 0.02 * 520 = 128 nanoseconds
- 결과적으로 주소변환을 위해 28ns만 소요

Memory Protection

Page table의 각 entry마다 아래의 bit를 둔다
- Protection bit
  - page에 대한 접근 권한 (read/wrtie/read-only)
- Valid-invalid bit
  - “valid”는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
  - “invalid”는 해당 주소의 frame에 유효한 내용이 없음을 뜻함 (접근 불허)
    - 프로세스가 그 주소 부분을 사용하지 않는 경우
    - 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

Inverted Page table

page table이 매우 큰 이유
- 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
- 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
Inverted page table
- Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)
- 모든 프로세스에 대해서 한 개의 페이지 테이블로 관리
- 단점
  - 테이블 전체를 탐색해야한다
- 조치
  - associative register 사용 (expensive)

Shared Page

Shared code
- Re-entrant Code (=Pure code)
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (eg. text editors, compilers, window systems)
- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무 곳에 와도 무방

Segmentation

프로그램은 의미 단위인 여러 개의 segment로 구성
- 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
- 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
- 일반적으로 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
Segment는 다음과 같은 logical unit 들임
- main()
- function
- global variables
- stack
- symbol table, arrays

Segmentation Architecture

Logical address는 다음의 두 가지로 구성
- < segment-number, offset >
Segment table
- each table entry has:
  - base : starting physical address of the segment
  - limit : length of the segment
- Page 보다 테이블 크기가 작아서 메모리 낭비가 적다
Segment-table base register (STBR)
- 물리적 메모리에서의 segment table의 위치
Segment-table length register (STLR)
- 프로그램이 사용하는 segment의 수
  - segment number s is legal if s < STLR

Protection
- 각 세그먼트 별로 protection bit가 있음
- Each entry:
  - Valid bit = 0 -> illegal segment
  - Read/Write/Execution 권한 bit
Sharing
- shared segment
- same segment number
- segment는 의미 단위이기 때문에 공유와 보안에 있어서 paging보다 훨씬 효과적이다
Allocation
- first fit/ best fit
- external fragmentation 발생
- segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점이 발생한다

Segmentation with Paging

pure segmentation과의 차이점
- segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음

사용 이유는 Segmentation의 의미 단위로 묶였을 때 Protection과 Sharing등의 장점과

Paging를 통해 외부 단편화를 없애는 장점을 같이 사용하기 위해서 이다

참고

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

Comment and share

OS-8-Dead Lock

Jul 24, 2021 in Computer Science, OS

길을 점유하면서 상대방의 길을 점유하길 원한다

The Deadlock Problem

Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource (자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- (예) I/O device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차 : Request -> Allocate -> Use -> Release
Deadlock Example 1
- 시스템에 2개의 tape drive가 있다
- 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
Deadlock Example 2
- Binary semaphores A and B
  
  P0가 A 자원을 점유한 후 인터럽트가 걸려서 context switching하여 P1이 B 자원을 점유 이후에서로의 자원을 할당받기 위해서 대기한다

Deadlock 발생의 4가지 조건

Mutual exclusion (상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
No preemption (비선점)
- 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
Hold and wait (보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 까지고 있음
Circular wait (순환 대기)
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- 프로세스 P0, P1, …, Pn이 있을 때
- P0은 P1이 가진 자원을 기다림
- P1은 P2이 가진 자원을 기다림
- Pn-1은 Pn이 가진 자원을 기다림
- Pn은 P0이 가진 자원을 기다림

Resource-Allocation Graph

그래프에 cycle이 없으면 deadlock이 아니다
그래프에 cycle이 있으면
- if only one instace per resource type, then deadlock
- if several instances per resource type, possibility of deadlock

2번째 그림에서 P4가 사용후 자원 R2를 반납하고, P2가 자원 R1을 반납하기 때문에 때문에 deadlock은 없다

Deadlock의 처리 방법

Deadlock Prevention
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
Deadlock Ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
- 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
No Preemption
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 저원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memeory)
Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당
- 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야한다

-> Utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

Deadlock avoidance
- 자원 요청에 대한 부가 정보를 이요해서 자원 할당이 deadlock으로 부터 안전한지 동적으로 조사해서 안전한 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요하는 각 자원별 최대 사용랴을 미리 선언하도록 하는 방법임
- 평생 쓸 자원들을 선언함으로써 자원에 Deadlock 가능성이 있을 경우를 피한다
safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
safe sequence
- 프로세스 sequence<P1, P2, …, Pn>이 safe하려면 Pi(1 <= i <= n)의 자원 요청이 “가용 자원 + 모든 Pj(j < i)의 보유 자원”에 의해 충족되어야 함
- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
  - Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다
  - Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다
시스템이 safe state에 있으면 no deadlock, 시스템이 unsafe state에 있으면 possibility of deadlock
Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다
2가지 경우의 avoidance 알고리즘
- Single instance per resource types -> Resource Allocation Graph algorithm
- Multi instance per resource types -> Banker's Algorithm

Resource Allocation Graph algorithm

Banker’s Algorithm

가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시
- 프로세스가 요청 자원을 모두 할당 받은 경우 유한 시간 안에 이들 자원을 다시 반납한다
방법
- 기본 개념: 자원 요청시 safe 상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)
- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정을 반복

Deadlock Detection and Recovery

Deadlock Detection
- Resource type 당 single instance인 경우
  - 자원 할당 그래프에서 cycle이 곧 deadlock을 의미
- Resource type 당 multiple instance인 경우
  - Banker’s algorithm과 유사한 방법 활용
Wait-for graph 알고리즘
- Resource type ekd single instance인 경우
- Wait-for graph
  - Resource type당 single instance인 경우
  - Wait-for graph
    - 자원 할당 그래프의 변형
    - 프로세스만으로 node 구성
    - Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
  - Algorithm
    - Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    - O(n^2)
Recovery
- Process termination
  - Abort all deadlocked processes
  - Abort one process at a time until the deadlock cycle is eliminated
- Resource Preemption
  - 비용을 최소화할 victim을 선정
  - safe state로 rollback하여 process를 restart
  - Starvation 문제
    - 동일한 프로세스가 계속해서 victim으로 선정되는 경우
    - cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
- Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다
- 만야그 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 직점 느낀 후 직접 process를 죽이는 등의 방법으로 대처
- UNIX, Windows등 대부분의 범용 OS가 채택

참고

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

Comment and share

OS-7-Process Synchronization

Jul 23, 2021 in Computer Science, OS

Race Condition

S-box(Memory Address Space)를 공유하는 E-box(CPU Process)가 여럿 있는 경우 Race Condition의 가능성이 있음
Multiprocessor system에서 공유 메모리를 사용하는 프로세스들이 커널 내부 데이터를 접근하는 루틴들 간에 발생할 수 있음

OS에서 Race Conditoin이 발생하는 경우

kernel 수행 중 인터럽트 발생 시
Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
Multiprocessor에서 shared memory 내의 kernel data

Case1. interrupt handler v.s kernel

커널 모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행

양쪽 다 커널 코드이므로 kernel address space를 공유하기 때문에 Race Condition이 발생할 수 있다

커널 모드 running중에는 interrupt가 걸리는 것을 막아서 Race Condition을 피할 수 있다

Case2. Preempt a process running in kernel?

두 프로세스의 address space 간에는 data sharing이 없음
그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨(share)
커널 작업 중간에 CPU를 preempt하면 Race Condition 발생
해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt하지않고, 커널 모드에서 사용자 모드로 돌아갈 때 preempt한다

Case3. Multiprocessor

여러 CPU가 한 자원에 동시 접근한다 -> Race Condition
Multi Processor인 경우 서로 다른 CPU가 접근하기 때문에 interrupt를 enable/disable로 해결되지 않는다
해결 방법
1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
2. 커널 내부에 있는 각 공유 데이터를 접근할 때마다 그 데이터에 대한 lock/unlock하는 방법

Process Synchronization 문제

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다
일관성(consistency) 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다
Race Condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  
  race condition을 막기 위해서는 concurrent process는 동기화(synchronize) 되어야 한다

The Critical-Section Problem

n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
하나의 프로세스가 critical section에 있을때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다

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

Mutual Exclusion : 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
Progress : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다
Bounded Waiting(유한 대기) : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다

해결 알고리즘 Case 1

Synchronization variable
- int turn;
- initially turn = 0;
mutual exclusion은 만족하나, progress를 만족하지 못함

반드시 한번씩 교대로 들어가야만 한다. 임계 구역에 작업하는 프로세스가 없어도, 한 프로세스가 연속해서 들어가지 못한다

해결 알고리즘 Case 2

Synchronization variable
- boolean flag[2];
- initially flag[] = false;
mutual exclusion은 만족하나, progress를 만족하지 못함

프로세스 둘 다 2행까지 수행 후에 끊임없이 서로에게 양보하는 상황 발생 가능

해결 알고리즘 Case 3 (Peterson’s Algorithm)

algorithm 1 2 번을 조합함
두 프로세스의 임계영역 문제 해결조건을 모두 만족한다

하지만 Busy Waiting!이다 (계속 CPU와 memroy를 쓰면서 wait)

Synchronization Hardware

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

Semaphores

앞의 방식들을 추상화 시킴
Semaphores S
- integer variable
- S는 자원의 갯수
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
세마포어의 두가지 종류
1. Counting Semaphore
  - 도메인이 0 이상인 임의의 정수값
  - 주로 resource counting에 사용
2. Binary Semaphore (=mutex)
  - 0 또는 1 값만 가질 수 있는 semaphore
  - 주로 mutual exclusion (lock/unlock)에 사용

Critical Section Of n Processes

위의 방식은 busy-wait 방식으로 임계구역이 오래걸리는 작업일 경우 효율적이지 못하다 따라서 Block & Wake up 방식을 사용하는 방법도 있다

Block And Wake Up 구현

Semaphore를 다음과 같이 정의한다

<img width=”400” alt=”스크린샷 2021-07-23 오후 10 02 04” src=”https://user-images.githubusercontent.com/12459864/126785511-2912b40c-b763-4646-a1ea-
block과 wakeup을 다음과 같이 가정
- block : 커널은 block을 호춝한 프로세스를 suspend시키고, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
- wakeup(P) : block된 프로세스 P를 wakeup 시킴, 이 프로세스의 PCB를 ready queue로
Semaphore 연산

value는 block과 wake up의 기준

Busy-wait vs Block/wakeup

Critical section의 길이가 긴 경우 Block/wakeup이 적당
Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
일반적으로는 Block/wakeup 방식이 더 좋음

Deadlock and Starvation

Deadlock : 둘 이상의 프로세스가 서로 상대방에 의행 충족될 수 있는 event를 무한히 기다리는 현상
Starvation : indefinite blocking, 프로세스가 suspend된 이후에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

대표적인 Race Condition 문제

Bounded-Buffer Problem

shared data
- buffer 자체
- buffer 조작 변수 (empty/full buffer의 시작 위치)
Synchronization variables
- mutual exclusion -> Need binary semaphore (Buffer의 사용 여부)
- resource count -> Need integer semaphore (남은 empty/full buffer의 수 표시)

Readers-Writers Problem

한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨
read는 동시에 여럿이 해도 됨
solution
- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
- Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
- 일단 Wrtier가 DB에 접근 중이면 Reader들은 접근이 금지된다
- Wrtier가 DB에서 빠져나가야만 Reader의 접근이 허용된다
shared data
- DB 자체
- readcount; -> 현재 DB에 접근 중인 Reader의 수
Synchronization variables
- mutex -> 공유 변수 readcount의 mutual exclusion을 보장
- db -> reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

Dining-Philosophers Problem

위의 solution의 문제점
- Deadlock 가능성이 있다
- 모든 철학자가 동시에 배가 고파져서 왼쪽 젓가락만 집을 경우
해결 방안
- 4명의 철학자만이 동시에 테이블에 앉을 수 있도록 한다
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집도록한다
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록한다

Monitor

Semaphore의 문제점
- 코딩하기 힘들다
- 정확성의 입증이 어렵다
- 자발적 협력이 필요하다
- 한 번의 실수가 모든 시스템에 치명적인 영향을 미친다
모니터란?
- 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
- 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능하다
- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
- 프로세스가 모니터 안에서 대기할 수 있도록 하기 위해 conditional variable 사용
  - condition x, y;
- condition variable은 wait와 signal 연산에 의해서만 접근 가능
  - x.wait(); : x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지는 suspend된다
  - x.signal(); : x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다
    
    monitor에 프로세스가 작업중이면 외부 entry queue에서 대기한다
    
    monitor내부에서 condition x가 없으면 x에 관한 queue에서 대기한다
    
    내부에서 작업중인 프로세스가 없거나 작업중인 프로세스가 condition 대기 queue에서 sleep하고 있으면 외부 작업 큐에서 프로세스가 monitor를 작업한다

Monitor를 적용한 Bounded Buffer Problem

Monitor를 적용한 Dining-Philosophers Problem

참고

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

Comment and share

OS-6-CPU Scheduling

Jul 22, 2021 in Computer Science, OS

CPU and I/O Burst Time

CPU burst time: CPU 실행시간
I/O burst time: I/O 작업 대기 시간
프로세스 특성에 따른 분류
- I/O bound process
  - CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  - (many short CPU bursts)
- CPU bound process
  - 계산 위주의 job
  - (few very long CPU bursts)
여러 종류의 process이 섞여 있기 때문에 CPU 스케줄링이 필요하다
- Interactivce job에게 적절한 response 제공
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
Dispatcher
- CPU 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
- 이 과정을 context switching(문맥 교환)이라고 한다
CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다
1. Running -> Blocked (예: I/O 요청하는 시스템 콜)
2. Running -> Ready (예: 할당 시간 만료 timer interrupt)
3. Blocked -> Ready (예: I/O 완료 후 인터럽트)
4. Terminate
  
  1, 4에서 스케줄링은 nonpreemptive, 나머지는 preemptive

Scheduling Criteria

CPU utilization(이용률) : CPU가 놀지 않고 사용하는 비율
Throughput(처리량) : 주어진 시간안에 몇 개의 작업을 완료하였는가?
Turnaround time(소요시간) : CPU를 대기하고 다 쓰고 반환하는 시간
Waiting time(대기시간) : CPU를 대기하는 시간
Response time(응답시간) : CPU를 처음으로 얻기까지 걸린 시간

이용률, 처리량은 시스템 입장에서

소요시간, 대기 시간, 응답 시간 프로세스(사용자) 입장에서 기준이다

Scheduling Algorithm

CPU를 누구한테 줄 것 인가?
CPU를 오래 잡고있으면 뺐을 것인가?

FCFS(First-Come First-Served)

프로세스 도착 순서대로 스케줄링 한다
오래걸리는 프로세스가 먼저 도착하면 전체 평균 응답시간이 느리다
- 소요시간이 긴 프로세스가 먼저 도착할 경우
- 소요시간이 짧은 프로세스가 먼저 도착할 경우

SJF (Shortest-Job-First)

CPU burst time이 가장 짧은 프로세스를 먼저 스케줄링 한다
SJF 종류
- Nonpreemptive(비선점형)
  - CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
- Preemptive(선점형)
  - 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  - Shortest-Remaining Time-First(SRTF)이라고도 부른다
  SJF는 최적의 스케줄링 알고리즘으로 주어진 프로세스에게 minmum average waiting time을 보장한다
문제점
- starvation : CPU burst time이 긴 프로세스는 CPU를 얻기 힘들다.
- 실제 프로세스들의 CPU burst time 예측하기 어려움
  - 과거의 CPU burst time을 이용하여 추정만이 가능하다
    
    최근의 CPU burst time 측정값이 현재의 추정치에 영향을 더 미친다

Priority Scheduling

우선순위가 높은 것 먼저 스케줄링한다
선점형 비선점형 두가지 종류가 있다
SJF도 priority = predicted next CPU burst time인 일종의 priority scheduling이다
문제점으로 우선순위가 낮은 프로세스가 실행되지 않는 Starvation 문제가 있다
따라서 Aging 방식을 통해서 프로세스의 우선순위를 시간이 지남에 따라 증가시켜 주는 방식으로 해결한다

Round Robin (RR)

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다
할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에서 다시 줄 선다.
n개의 프로세스가 ready queue에 할당 시간이 q time unit인 경우
- 어떤 프로세스도 (n - 1)q time unit 이상을 기다리지 않는다
- 응답시간이 빨리진다

time quantum이 많이 길어지면 FCFS Scheduling 처럼 동작하고

time quantum이 짧아지면 짧아질수록 context switching 오버헤드가 커진다

Multilevel Queue

우선순위가 높은 큐의 작업을 우선시 한다
Ready queue를 여러 개로 분할
- foreground (interactive)
- background (batch - no human interactive)
각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- background - FCFS
큐간의 스케줄링이 필요
- Fixed priority scheduling
  - foreground에 작업을 우선으로 하고 foreground에 작업이 없으면 background 작업 시작
  - starvation의 가능성이 있다
- Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당한다
  - 80% foregound in RR, 20% to background in FCFS

Multilevel Feedback Queue

프로세스가 다른 큐로 이동가능하다
Scheduling
1. new job이 queue Q0로 들어감
2. CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
3. 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
4. Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
5. 16ms에서 끝내지 못한 경우 queue Q2로 쫓겨남

Multiple-Processor Scheduling

Homogeneous processor 인 경우
- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
Load sharding
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

Hard real-time systems : 정해진 시간 안에 반드시 스케줄링해야 함
Soft read-time systems : 정해진 시간에 반드시 스케줄링하지 않지만, 일반 프로세스에 비해 높은 prioty를 갖도록 해야함

Thread Scheduling

Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
Global Scheduling : Kernel level tthrea의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

참고

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

Comment and share

OS-5-Process Management

Jul 22, 2021 in Computer Science, OS

프로세스 생성 (Process Creation)

부모 프로세스가 자식 프로세스를 생성합니다 (복제 생성)
프로세스의 트리 형성
프로세스는 자원을 필요로 합니다
- 운영체제로 받는다
- 부모와 공유한다
자원의 공유
- 부모와 지식이 모든 자원을 공유하는 모델
- 일부를 공유하는 모델
- 전혀 공유하지 않는 모델
수행 (Execution)
- 부모와 자식은 공존하며 수행되는 모델
- 자식이 종료(terminate)될 때까지 부모가 기다리는(wait)모델
주소 공간 (Address space)
- 자식은 부모의 공간을 복사함 (binary and OS data)
- 자식은 그 공간에 새로운 프로그램을 올림
유닉스의 예
- fork() 시스템 콜이 새로운 프로세스를 생성
  - 부모를 그래로 복사 (OS data except PID + binary)
  - 주소 공간 할당
- fork 다음에 이어지는 exec() 시스템 콜을 통해 새로운 프로그램을 메모리에 올림

프로세스 종료 (Process Termination)

프로세스가 마지막 명령을 수행한 후 운영체제에게 이를 알려줌 (exit)
- 자식이 부모에게 output data를 보냄 (via wait)
- 프로세스의 각종자원들이 운영체제에게 반납됨
부모 프로세스가 자식의 수행을 종료시킴 (abort)
- 자식이 할당 자원의 한계치를 넘어섬
- 자식에게 할당된 태스크가 더 이상 필요하지 않음
- 부모가 종료(exit)하는 경우
  - 운영체제는 부모 프로세스가 종료하는 경우 자식이 더 이상 수행되도록 두지 않는다
  - 단계적인 종료

fork() 시스템 콜

자식 프로세스는 부모 프로세스에서 Program Counte도 복제해서 fork한 이후부터 실행

exec() 시스템 콜

프로세스에 새로운 프로그램을 덮어서 다른 프로그램으로 만들어 실행

wait() 시스템 콜

프로세스 A가 wait() 시스템 콜을 호출
- 커널은 child가 종료될 때까지 프로세스 A를 sleep시킨다 (block 상태)
- child process가 종료되면 커널은 프로세스 A를 깨운다 (ready 상태)

exit() 시스템 콜

프로세스 종료
- 자발적인 종료
  - 마지막 statement 수행 후 exit() 시스템 콜을 통해
  - 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 넣어줌
- 비자발적 종료
  - 부모 프로세스가 자식 프로세스를 강제 종료시킴
    - 자식 프로세스가 한계치를 넘어서 자원 요청
    - 자식에게 할당된 태스크가 더 이상 필요하지 않음
  - 키보드로 kill, break 등을 친 경우
  - 부모가 종료하는 경우
    - 부모 프로세스가 종료하기 전에 자식들이 먼전 종료됨

프로세스 간 협력

독립적 프로세스
- 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못합
협력 프로세스
- 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음
프로세스 간 협력 메커니즘 (IPC: Interprocess Communication)
- message passing : 커널을 통해서 메시지 전달됨
- shared memory
  - 프로세스간 메모리 공유 요청을 커널에게 요청한 후, 커널을 통해서 특정 물리 메모리 공간을 공유합니다

thread : 프로세스 간의 협력은 아니지만 동일한 process를 구성하는 thread간에는 주소공간을 공유하므로 협력이 가능하다

Message Passing

Message System : 프로세스 사이에 공유 변수를 일체 사용하지 않고 통신하는 시스템
Direct Communication
- 통신하려는 프로세스의 이름을 명시적으로 표시
Indirect Communication
- mailbox (또는 port)를 통해 메시지를 간접 전달
- 특정 대상이 아니라 임의의 대상들이 메시지를 확인하고 가져감

참고

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

Comment and share

OS-4.Thread

May 14, 2021 in Computer Science, OS

Thread란

A thread (or lightweight process) is a basic unit of CPU utilization

Thread의 구성
- program counter
- register set
- stack space
Thread가 동료 thread와 공유하는 부분(=task)
- code section
- data section
- OS resources
heavyweight process는 하나의 thread를 가지고 있는 task로 볼 수 있습니다

스크린샷 2021-05-14 오후 6 24 12

Thread의 장점

다중 스레드로 구성된 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리를 할 수 있습니다
- ex) 웹 브라우저가 웹 페이지를 불러올 때 html과 text를 먼저 불러오고 text만으로 사용자가 작업할 수 있게 한 다음, 다른 스레드가 image를 불러오는 작업을 할 수 있습니다
동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능 향상을 얻을 수 있습니다.
자원 낭비를 막는다 (프로세스 각각으로 돌리면 각 프로세스당 메모리가 필요하게 되서 더 많은 메모리를 차지합니다)
스레드를 사용하면 병렬성을 높일 수 있습니다(멀티 코어일 경우)

참고

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

Comment and share

OS-3.Process

May 14, 2021 in Computer Science, OS

Process Concept

Process is a program in execution
프로세스의 문맥 (context)
- CPU 수행 상태를 나타내는 하드웨어 문맥
  - Program Counter(PC)
  - 각종 register
- 프로세스의 주소 공간
  - code, data, stack
- 프로세스 관련 커널 자료 구조
  - PCB (Process Control Block)
  - Kernel stack

Process State

프로세스는 상태(state)가 변경되며 수행됩니다
Running : CPU를 잡고 instruction을 수행중인 상태
Ready : CPU를 기다리는 상태(CPU만 얻으면 실행할 수 있는 상태)
Blocked(wait, sleep)
- CPU를 주어도 당장 instruction을 실행할 수 없는 상태
- Process 자신이 요청한 event(I/O)가 즉시 만족되지 않아 이를 기다리는 상태
- 디스크에서 file을 읽어와야 하는 경우
New: 프로세스가 생성중인 상태
Terminated: 수행이 끝난 상태
각 작업의 큐는 Kernel의 Data영역에서 관리되어집니다

PCB

운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보
다음의 구성 요소를 가집니다 (구조체로 유지)
1. OS가 관리상 사용하는 정보
  - Process state, Process ID
  - scheduling information, priority
2. CPU 수행 관련 하드웨어 값
  - program counter(PC), registers
3. 메모리 관련
  - code, data, stack의 위치 정보
4. 파일 관련
  - Open file descriptiors…

문맥 교환 (Context Switching)

CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정
CPU가 다른 프로세스에게 넘어갈 때 운영체제는 운영체제는 다음을 수행합니다
- CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장
- CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴
System Call이나 Interrupt 발생시 반드시 Context switching이 일어나는 것은 아닙니다
- 1번의 경우에도 CPU 수행 정보 등 context의 일부를 PCB에 save해야 하지만 문맥교환을 하는 2번의 경우 cache memory flush가 발생하기 때문에 성능 부담이 훨씬 큽니다

프로세스를 스케줄링하기 위한 큐

Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합 (Process Queue + Device Queue)
Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
Device Queue: I/O device의 처리를 기다리는 프로세스의 집합

프로세스들은 각 큐를 오가며 수행됩니다

스케줄러

장기 스케줄러 (job scheduler)
- 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정합니다
- 프로세스에 memory(및 각종 자원)을 주는 문제
- degree of multiprogramming을 제어
- time sharing system에는 보통 장기 스케줄러 없이 무조건 ready 상태가 됩니다
단기 스케줄러 (cpu scheduler)
- 어떤 프로세스를 다음번에 running 시킬 지 결정합니다
- 프로세스에 CPU를 주는 문제
중기 스케줄러 (swapper)
- 여유 공간 마련을 위해 프로세스를 통째로 메모레에서 디스크로 쫓아냅니다
- 프로세스에게서 memory를 뺏는 문제
- degree of multiprogramming을 제어
- 현재 시스템은 프로그램을 무조건 메모리에 올리고 swapper를 이용해서 메모리에서 쫓아낸다 (장기 스케줄러대신 중기 스케줄러를 사용한다)
  
  중기 스케줄러로 인해서 Suspended라는 프로세스의 상태가 추가됩니다

새로운 프로세스 상태

Running
Ready
Blocked
Suspended (stopped)
- 외부적인 이유로 프로세스의 수행이 정지된 상태
- 프로세스는 통째로 디스크에서 swap out 됩니다
- (예) 메모리에 너무 많은 프로세스가 올라와서 성능이 저하되었을 때 사용자가 직접 process를 중단시거나 시스템이 중단시킵니다

Block은 자신이 요청한 event가 만족되면 Ready 상태가 되어집니다

Suspended는 외부에서 다시 resume해 주어야 Activce됩니다

참고

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

Comment and share

OLDER POSTS
page 1 of 2