DEVELOPyo

Allocation of File Data in Disk 

Contiguous Allocation

단점 :

- external fragmentation, hole이 발생

장점 : 

- Fast I/O (헤드가 이동하는 시간이 짧음)

- 한번의 seek/rotation 으로 많은 바이트 transfer

- Realtime file용, process의 swapping 용으로 사용

- Direct access(=random access) 가능

Linked Allocation

장점 :

- external fragmentation 발생 없음

단점 :

- No random access

- Reliability 문제

- 한 sector 가 고장나 pointer 유실시 많은 부분을 잃음

- Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림 (512bytes는 sector로, 4bytes는 pointer로 사용됨)

* FAT(File-allocation table) 파일 시스템 : 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

Indexed Allocation

장점 :

- external fragmentation 발생 없음

- Direct access 가능

단점 :

- Small file의 경우 공간 낭비

- 파일이 너무 큰 경우 하나의 block 으로 index 를 저장 할 수 없음

UNIX 파일시스템 구조

Boot block

- 모든 파일시스템은 boot block 이 제일 위에있음

- 컴퓨터 부팅시 0번블럭(붙 블럭)을 올려서 부팅시킴

Superblock

- 파일시스템에 관한 총체적인 정보를 담고 있다

Inode

- 파일 이름을 제외한 파일의 모든 메타 데이터 저장

Data block

- 파일 실제 내용 보관

FAT 파일 시스템

FAT

메타데이터의 일부를 보관 (위치정보)

FAT 배열의 크기는 data block 의 크기와 동일

FAT 은 복제본을 저장하여 신뢰도를 높임

Free Space Management : 비어있는 블락 관리방법

1. Bit map 

Bit map 을 위한 부가적인 공간을 필요로 함

연속적인 n개의 free block을 찾는데 효과적

2. Linked list 

모든 free block들을 링크로 연결(free list)

연속적인 가용공간을 찾는게 힘듦

공간낭비 없음

3. Grouping

linked list 방법의 변형

첫번째 free block이 n개의 pointer를 가짐

n-1 pointer는 free data block을 가리킴

마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

4. Counting

프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안

Directory Implementation : 디렉토리 저장 방법

1. Linear list

- <filename, file의 메타데이터>의 list

- 구현이 간단함

- 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요(time-consuming)

2. Hash Table

- linear list + hashing

- Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌

- search time을 없앰

- Collision 발생 가능

* F에 Hash 함수 적용시 F는 특정 범위로 한정지어짐.

* Hash 함수를 적용하여 조회

※ 이화여대 반효경 교수님의 운영체제 강의 정리

File

named collection (메모리는 주소를 통한 접근)

비휘발성의 보조기억장치에 저장

운영체제는 다양한 저장 장치를 file 이라는 동일한 논리적 단위로 볼 수 있게 해 줌

Operation 종류 : create, read, write, reposition, delete, open, close

File attribute (metadata)

파일 이름, 유형, 저장위치, 파일사이즈, 접근권한, 시간(생성/변경/사용), 소유자과 같은

파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들

File system

운영체제에서 파일을 관리하는 부분

파일 및 파일의 메타데이터, 디렉토리 정보

파일의 저장 방법 결정

파일 보호

Directory

파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일

그 디렉토리에 속한 파일 이름 및 파일 attribute들

Operation 종류 : search for a file, create a file, delete a file, list a directory, rename a file, traverse the file system

Partition(=Logical Disk)

하나의 물리적 디스크 안에 여러 파티션을 두는게 일반적

여러 개의 물리적인 디스크를 하나의 파티션으로 구성하기도 함

물리적 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 swapping 등 다른 용도로 사용 가능

open()

파일의 메타데이터를 메모리로 올린다.

1) fd = open("/a/b") : 프로그램이 b 메타데이터 정보를 요청

2) 시스템콜을 하여 CPU를 운영체제에 넘긴다.

3) CPU가 root 메타데이터를 먼저 메모리에 올린다(root 메타데이터의 디렉토리는 이미 알고 있음)

4) root 메타데이터를 연다

5) root 메타데이터에 존재하는 a 메타데이터의 파일시스템상 위치정보로 디스크에서 a의 메타데이터를 가져와 메모리에 올린다

6) a의 메타데이터를 연다

7) a의 메타데이터에 존재하는 a content의 파일시스템상 위치정보로 디스크에서 a의 content 안에 존재하는 b의 메타정보를 가져와 메모리에 올린다

8) b의 메타정보를 가리키는 포인터의 인덱스(파일 디스크립터) 값을 리턴

9) read(fd...) : 프로그램이 b content 정보 요청(읽기)

10) 읽은 내용을 사용자 프로그램(Process A)에 직접 주는게 아닌, 커널 메모리 영역(buffer cache)으로 가져온다

11) 사용자 메모리영역(Process A)엔 그 내용을 카피해서 준다.

※ 만약 다른 프로그램(Process B)에서 b의 content 를 요청한다면 운영체제가 buffer cache에서 전달해준다 

※ File System 의 Buffer cache 환경에선 운영체제가 모든 정보를 알고 있으므로(파일 시스템 접근시 시스템 콜을 통해 제어권이 CPU로 넘어오므로) LRU, LFU 알고리즘을 사용할 수 있다. 

※ per-process file descriptor table : 파일 디스크립터 테이블은 프로세스마다 따로 존재

※ system-wide open file table : system wide 로 전체 시스템에 한개로 관리되지만 각각의 프로그램들이 파일의 offset을 프로그램 별로 관리하기 위한 공간(table)은 따로 존재

File Protection

1. Access control matrix : linked list 형태로 권한 관리 (overhead가 큼)

Access control list : 파일별로 누구에게 어떤 접근 권한이 있는지 표시

Capability list: 사용자별 자신이 접근 권한을 가진 파일 및 해당 권한 표시

2. Grouping

전체 user를 owner, group, public의 세그룹으로 구분

각 파일에 대해 세그룹의 접근 권한(rwx)을 3비트씩 표시

UNIX를 포함한 대부분의 OS에서 사용

3. Password

파일마다 password를 두는 방법

rwx 마다 password를 하나씩 부여해야하므로 관리가 어려움

File System의 Mounting

파티션을 통해 여러개의 논리적 디스크로 분리된 하나의 물리적 디스크

각각의 논리적 디스크에 file system 존재

다른 파일시스템에 접근할 경우 mount 사용

disk3의 루트를 disk1의 usr 경로에 연결(mount)하여 타 파일시스템 접근이 가능

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Page Frame의 Allocation(할당)

: 각 Process에 얼마만큼의 Page Frame을 할당할 것인지의 문제

- 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조하므로 명령어 수행을 위해 최소한 할당되어야 하는 frame 의 수가 있다. (page fault 를 줄이기 위해)

Allocation Scheme

Equal allocation : 모든 프로세스에 똑같은 갯수 할당

Proportional allocation : 프로세스 크기에 비례하여 할당

Priority allocation : 프로세스의 priority에 따라 다르게 할당

Global replacement 와 Local replacement 의 차이

Global replacement

Replace시 다른 process에 할당된 page frame을 빼앗아 올 수 있다

FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용하는 경우

Working set, PFF 알고리즘 사용

Local replacement

자신에게 할당된 frame 내에서만 replacement

FIFO, LRU, LFU 등의 알고리즘을 local(process) 별로 운영시

Global replacement 에서의 문제

Thrashing

메모리에 올라와 있는 프로그램이 늘어날 수록 CPU 이용량은 올라가지만, 

메모리에 프로그램이 너무 많이 올라갈 경우 page frame 수 (메모리 할당 용량)가 너무 적어질 경우 page fault 가 매우 빈번하게 발생하게 되어 CPU utilization 은 낮아지고, 프로세스는 page의 페이지를 빼고 넣고를 (swap in/swap out) 반복하게 되어 실제 CPU는 놀게 되는 현상

Thrashing 현상을 방지하기 위한 방법들

1. Working-set Model

- Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page 들의 집합을 Working Set이라고 한다 (프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조, 이 장소들의 집합을 working set이라 함)

- Working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend) : 묶음으로 넣거나 아예 넣지 않거나

- Thrashing을 방지하고 Muliprogramming degree를 결정한다

Working-set Algorithm

- Process들의 working set size의 합이 page frame의 수보다 큰 경우 일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜준다

- Working set을 다 할당하고도 page frame이 남는 경우 Swap out 되었던 프로세스에게 working set을 할당

Window size 

Working size가 너무 작으면 locality set(필요한 페이지 묶음)을 모두 수용하지 못할 수 있다

Working size 동안 Working set에 속한 page는 메모리에 유지, 속하지 않는 것은 버린다

2. PFF(Page-Fault Frequency) Scheme

Page-fault rate의 상한값과 하한값을 두고, 

Page fault rate 상한값을 넘으면 frame을 더 할당

Page fault rate 하한값 이하면 할당 frame 수를 줄인다

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

※ Page size의 결정

Page size가 작다면 

필요한 정보만 메모리에 올라와 메모리 이용에 효율적(페이지 단위가 작으므로 작은 크기로 올릴 수 있음)인 장점 등이 있지만, 

Disk seek (디스크 헤드 이동) 시간 증가

Page size를 감소시킬 경우

페이지 수 증가,

페이지 주소를 관리하는 페이지 테이블 크기 증가와 같은 단점이 있다.

위와 같은 이유로 Page 크기를 키우는게 최근 트렌드

※ 이화여대 반효경 교수님의 운영체제 강의 정리

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 ? ( if bad address, protection violation ) abort process

2. get an empty page frame (없으면 뺏어온다)

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 재개

Page replacement

- Free Frame(비어있는 frame(physical memory 영역))이 없는 경우 수행됨

- 어떤 frame을 빼앗아올지 결정해야 한다 (곧바로 사용되지 않을 page를 쫓아내는 것이 좋다)

- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음

Page fault를 줄이기 위한 Replacement Algorithm의  종류

page-fault rate을 최소화 하는 것이 목표

알고리즘의 평가기준은 주어진 page reference string에 대해 page fault를 얼마나 내는지

1. Optimal Algorithm (=Min Algorithm)

- 가장 먼 미래에 참조되는 page를 replace (미래를 안다는 가정)

- 다른 알고리즘의 성능을 측정하는 기준점이 됨(실제 사용은 불가한 offline 알고리즘)

- Belady's optimal algoroithm MIN, OPT 등으로 불림

-> 7번째 수행에서 5를 참조 할 때, 미래에서 가장 나중에 참조되는 4(마지막에서 2번째)를 쫓아내고 대신 5를 넣음

2. FIFO Algorithm (first in first out)

먼저 들어온 것을 먼저 내쫓는다

FIFO Anomaly (Belady's Anomaly) : 페이지가 늘어남에도 불구하고 page faults는 증가하는 현상이 발생

3. LRU Algorithm (Least Recently Used)

가장 오래전에 참조된 것을 지운다

4. LFU Algorithm (Least Frequently Used)

참조 횟수(reference count)가 가장 적은 페이지를 지움

* 최저 참조 횟수인 page가 여럿인 경우

- LFU 알고리즘 자체에는 여러 page 중 임의로 선정

- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음

* 장단점

- LRU 처럼 직전 참조 시점만 보는게 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음

- 참조 시점의 최근성을 반영치 못함

- LRU 보다 구현이 복잡함

※ LRU, LFU 의 비교

LRU

위에 있을 수록 오래된 참조

- linked list 형태

- 참조될 때 맨 아래에 link시킴

- 쫓아낼 경우 맨 위의 페이지 쫓아냄

LFU

LRU 처럼 linked list 형태로 관리하기는 비효율적

: 새로 참조될 때마다 어디에 link 시킬지 판별하기 위해 참조횟수를 비교해야함 (시간 복잡도 O(N)))

linked list 형태 대신 heap 으로 구현, 2진트리로 구성

* 쫓아낼 경우 root를 쫓아내고 heap을 재구성

캐싱 기법

- 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스 하는 방식

- paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용

캐시 운영의 시간 제약

- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음

- Buffer caching이나 Web caching의 경우

  : O(1) 에서 O(long n) 정도까지 허용

- Paging system인 경우

  : Page fault인 경우에만 OS가 관여함

  : 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음

  : O(1)인 LRU의 list 조작조차 불가능

* Paging System에서 LRU, LFU는 사용이 불가하다

: page fault 발생시(CPU 제어권이 운영체제로 넘어오면)에만 디스크에서 메모리에 올라온 시간을 알 수 있으며

이미 메모리에 페이지가 있으면 알 수 없음

Clock Algorithm(=Second chance algorithm = NRU(Not Recently Used))

LRU의 근사 알고리즘, LRU/LFU 대신 실제 사용되는 알고리즘

reference bit : 참조여부를 의미(1:최근에 참조된 경우, 0:최근에참조되지 않은 경우)

modified bit(=dirty bit) : write(변경) 여부를 의미(1:write 된 페이지, 0:write 되지 않은 페이지) 

1) 최근에 참조된 경우 Reference bit은 1

2) 1인 경우 Reference bit 을 0으로 바꾸고 다음 페이지를 확인(최근에 참조된 페이지인 경우이므로 다음 페이지 확인)

3) 0인 경우를 발견하면 페이지를 내쫓는다

※ 이화여대 반효경 교수님의 운영체제 강의 정리

1. Contiguous allocation (연속 할당)

1-1) 고정분할

1-2) 가변분할

2. Noncontiguous allocation (불연속 할당)

1) Paging 기법

- 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번

- 속도 향상을 위해 자주 사용되는 주소값을 가지고 캐시와 같이 가지고 있는 TLB 사용

※ TLB

- TLB 조회시 fullscan이 이루어지므로, parellel search 가 가능한 associative registers 사용

- 주소값이 없으면(miss) page table 사용

- TLB는 context switch 시 flush 된다(process 마다 달라져야 하므로)

※ Two-Level Page Table : 2단계 페이지 테이블

32 bit address 사용시 2^32 (4G) 의 주소 공간

page size 가 4K 일 경우 1M개의 page(=page table entry) 가 필요 ( 4G / 4K = 1M )

각 page entry가 4B 일 경우 프로세스당 4M의 page table 필요 (프로세스 하나에 page table 1개)

사용되지 않는 주소 공간에 대한 outer page table 의 엔트리 값은 NULL (대응하는 inner page table 이 없음)

inner page table의 크기는 page 크기와 동일. inner page table 은 page 내에 존재

page 하나는 4KB(inner page table도 마찬가지),  entry 1개는 4Byte entry 는 총 1K 개

page offset : 4KB(페이지크기) = 2^12 

P2 : page entry 갯수 1K = 2^10

P1은 outer pager table 의 index

P2는 outer page table의 page에서의 변위(displacement)

※ Multi-Level Paging : 멀티 레벨 페이징

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

- 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address변환에 더 많은 메모리 접근 필요

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

Memory Protection

Page table의 각 entry 마다 아래의 bit를 둔다

1) Protection bit

 : page에 대한 read/write/read-only 권한

 ex) code영역은 read-only, data 및 stack 영역은 read/write

2) Valid-invalid bit (아래 그림 참고)

 : valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)

 : invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함

  (프로세스가 그 주소 부분을 사용하지 않거나 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우)

Inverted Page Table

- Page frame 하나당 page table에 하나의 entry 를 둔 것(system-wide:시스템에 하나만 존재)

- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address)

- 물리주소로 논리주소를 역으로 찾아야 하기 때문에(value 기준으로 key를 찾아야) 검색에 overhead가 큼(associative register 사용하여 해당 문제 해소)

- 기존의 테이블 페이지 구조와 정반대의 구조

1) 페이지 테이블 : 프로세스 페이지 번호를 기준으로 page table에서 logical address를 physical address 로 변환(정방향)

2) inverted 페이지 테이블 : page table의 entry에 physical memory 에 들어있는 logical address 주소가 들어 있음(역방향)

- 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재(배열과 비슷한 구조), 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재와 같은 page table 의 문제점을 inverted page table은 갖지 않음.

Shared Page

- Re-entrant Code(=Pure code) : 재진입가능한 코드

- read-only로 하여 프로세스 간 하나의 code만 메모리에 올린다 

- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다

Private code and data

- 각 프로세스들은 독자적으로 메모리에 올림

- private data는 logical address space의 아무곳에 와도 무방

2) Segmentation Architecture

- Logical address 는 segment-number(s), offset(d) 으로 구성

- 각각의 segment table 은 limit(segment의 길이), base(segment 의 시작 물리 주소) 를 가짐

- Segment-table base register(STBR) : 물리적 메모리에서의 segment table 위치

- Segment-table length register(STLR) : 프로그램이 사용하는 segment의 수

if (s > STLR) trap

if (limit < d)  trap

장점 : segment 는 의미 단위이기 때문에 Sharing과 protection에 있어 paging 보다 훨씬 효과적

단점 : segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Allocation of Physical Memory : 메모리 할당

메모리는 일반적으로 두 영역으로 나뉘어 사용

1) OS 상주 영역 : interrupt vector 와 함께 낮은 주소 영역 사용

2) 사용자 프로세스 영역 : 높은 주소 영역 사용

사용자 프로세스 영역의 할당 방법

1. Contiguous allocation (연속 할당)

: 각각의 프로세스가 메모리의 연속적인 공간에 적재

1) 고정 분할 방식

- 물리적 메모리를 몇 개의 영구적 분할로 나눈다

- 분할당 하나의 프로그램을 적재

- 내부/외부 조각이 발생

  * 외부조각 : 프로그램의 크기보다 분할의 크기가 작은 경우,

                 아무 프로그램에도 배정되지 않은 빈 공간이지만 프로그램이 올라갈 수 없는 작은 분할

  * 내부조각 : 프로그램 크기보다 분할의 크기가 큰 경우,

                 특정 프로그램에 배정되었지만 사용되지 않는 공간

2) 가변 분할 방식

- 프로그램 크기를 고려해서 할당

- 분할의 크기, 개수가 동적으로 변함

- 기술적 관리 기법 필요

  * 외부조각 발생 : B가 끝나서 비어있는 공간이 발생했지만 프로그램 D가 해당 빈 공간 보다 커서 사용할 수 없음

Hole

- 가용 메모리 공간

- 다양한 크기의 Hole 들이 메모리 여러 곳에 존재

- 프로세스가 도착하면 수용가능한 hole 을 할당

- 운영체제는 다음의 정보를 유지 

  할당 공간, 가용 공간(hole)

Hole 을 어떻게 관리 할 것인가?

: Dynamic Storage-Allocation Problem

: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

1) First-fit

- Size 가 n 이상인 것 중 최초로 찾아지는 hole 에 할당

2) Best-fit

- Size 가 n 이상인 가장 작은 hole을 찾아서 할당

- 많은 수의 아주 작은 hole들이 생성됨

3) Worst-fit (First-fit, Best-fit 보다 속도/공간 이용률이 비효율적)

- 가장 큰 hole에 할당

- 상대적으로 아주 큰 hole들이 생성됨

※ Compaction

- 외부 조각 문제를 해결하는 방법

- 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것

- 비용이 매우 많이 드는 방법

- 최소한의 메모리 이동으로 compaction 하는 방법

- 프로세스 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행 가능

2. Noncontiguous allocation (불연속 할당)

: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감

1) Paging 기법

2) Segmentation 기법

※ 이화여대 반효경 교수님의 운영체제 강의 정리

메모리의 주소를 크게 두가지로 나눌 수 있다

Logical address(=virtual address)

- 프로세스마다 독립적으로 가지는 주소 공간

- 각 프로세스마다 0번지부터 시작

- CPU가 보는 주소는 logical address

Physical address

- 메모리에 실제 올라가는 위치

주소 바인딩 : 프로그램이 실제로 메모리에 올라 갈 때 주소를 결정하는 것

Symbolic Address > Logical Address > Physical address

주소 바인딩(Address Binding) 방식의 종류

1) Compile time binding

- 물리적 메모리 주소가 컴파일시 알려짐

- 시작 위치 변경시 재컴파일

- 컴파일러는 절대 코드 생성

2) Load time binding

- loader의 책임하에 물리적 메모리 주소 부여

- 컴파일러가 재배치가능코드를 생성한 경우 가능

3) Runtime binding

- 수행이 시작된 이후에도 프로세스의 메모리상 위치를 옮길 수 있음

- CPU가 주소를 참조할 때마다 binding을 점검

- 하드웨어적인 지원이 필요(base and limit registers MMU)

Memory Management Unit (MMU)

logical address를 physical address로 매핑해 주는 Hardware device

※ MMU scheme

사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다

※ user program

logical address만을 다룬다

실제 physical address를 볼 수 없으며 알 필요가 없다

1) CPU가 현재 실행중인 process p1의 논리주소 346 요청

2) process p1 은 물리주소 14000번부터 올라가 있음

3) 프로그램(process p1)이 혹여 자신의 메모리 범위(3000)가 아닌 주소를 요청할 경우를 막기위해

    limit register 의 값과 비교를 해본다.

    limit register 보다 요청 주소가 크다면 trap interrupt 발생 후 운영체제로 제어권을 넘긴다

3) 그렇지 않다면, 시작위치 물리주소인 base register(relocation register)에 논리주소를 더해 돌려줌 (14000+346)

Dynamic Loading (동적 로딩)

- 프로세스 전체를 메모리에 미리 다 올리는게 아니라 해당 루틴이 불려질 때 메모리에 load 하는 것

- memory utilization 의 향상

- 가끔씩 사용되는 많은 양의 코드의 경우 유용 ex)오류 처리 루틴

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

Overlays

- 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다

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

- 운영체제의 지원없이 사용자에 의해 구현

- 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현(프로그래밍 매우 복잡)

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 binding 혹은 load time binding 을 사용하는 경우 swapping 후 원래 주소로 복귀(Swap in)해야 하므로 효율적이지 못하다

- Runtime binding 에서 효율적이다

- swap time 은 대부분 transfer time(swap되는 양에 비례하는 시간)

※ 페이징 시스템에서 일부 페이지가 메모리에서 쫓겨날 때도 swap out 이라고 표현하지만 원칙적으로 swap out은 프로그램을 구성하는 메모리 전부가 쫓겨남을 의미

Dynamic Linking

Linking을 실행 시간(execution time)까지 미루는 기법

1) Static linking

- 라이브러리가 프로그램의 실행 파일 코드에 포함됨

- 실행 파일의 크기가 커짐

- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비

2) Dynamic linking (=Shared library =DLL(dynamic linking library))

- 라이브러리가 실행시 연결(link)됨

- 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠

- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴

- 운영체제의 도움이 필요

※ 이화여대 반효경 교수님의 운영체제 강의 정리

교착상태 Deadlock

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

Resource (자원)

- 하드웨어, 소프트웨어 등을 포함하는 개념

  ex) 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

Deadlock 발생의 4가지 조건

1. Mutual exclusion (상호 배제)

  : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2. No preemption (비선점)

  : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3. Hold and wait (보유대기)

  : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

4. Circular wait (순환대기)

  : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

Resource-Allocation Graph

좌측은 deadlock 우측은 deadlock 아님

좌측 : P1에게 R2 자원 1개 가있고, P2에게 R2 자원 1개가 가있는 상황, P3가 R2자원 하나 더 요구

        P2 은 R3 자원 요청, R3은 P3 가 가지고 있고 P1 은 R1을 요청하나 이는 P2 가 가지고 있으므로

        모든 프로세스가 자원을 반납할 수 없는 상황 즉, deadlock 상태

우측 : P1에게 R2 자원 1개 가있고, P4에게 R2 자원 1개 가있는 상황, P3가 R2 자원 요구 

        P4가 자원 반납시 문제가 없음 

그래프에 cycle이 없으면 deadlock이 아니다

그래프에 cycle이 있으면

if only one instance per resource type, then deadlock

if several instances per resource type, possibility of deadlock

Deadlock 처리 방법

1. Deadlock prevention

: 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

ex)

비선점방식을 선점방식으로,

가지고 있으면서 대기하지 못하도록(자원 요청시 보유한 자원 반납),

자원 유형에 할당 순서를 정하여 정해진 순서대로만 할당 

2. Deadlock Avoidance

: 자원 요청에 대한 부가적인 정보(최대 요청 자원양)를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사하여 안전한 경우에만 할당

: 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

ex)

※ Banker's algorithm

현재 요청(Need)을 충족시킬 수 있는 자원상황(Available)이라 할 지라도 최대 요청(Max) 가능성을 염두하여 현재 자원상황을 초과할 가능성이 있다면 자원 할당하지 않음. 

3. Deadlock detection and recovery

: deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

1) Process termination

- 데드락과 관련된 모든 프로세스를 죽인다

- 데드락이 풀릴 때 까지 데드락과 관련된 프로세스를 한 개 씩 죽인다

2) Resource Preemption

- 비용을 최소화할 victim 선정

- safe state 로 rollback 하여 process를 restart

- 동일한 프로세스가 계속해서 victim으로 선정되는 경우 starvation 문제 (cost factor에 rollback 횟수도 같이 고려)

4. Deadlock ignorance

: deadlock 을 시스템이 책임지지 않음, 현대 대부분의 OS는 해당 처리방법을 채택

- Deadlock이 매우 드물게 발생하므로 데드락 조치 자체가 더 큰 overhead 일 수 있음

- deadlock 발생하여 시스템이 비정상적일 경우 유저가 직접 process를 죽이는 방법으로 대처

※ 이화여대 반효경 교수님의 운영체제 강의 정리

1. Bounded-Buffer Problem : 공유버퍼 문제 (Producer-Consumer Problem)

Producer : 데이터를 넣어주는 생산자

Comsumer : 데이터를 사용하는 소비자

발생하는 문제

1) 복수의 생산자 동시접근

2) 복수의 소비자 동시접근

3) 버퍼가 꽉 차있을 때 생산자의 접근

4) 버퍼가 비어있을 때 소비자의 접근

Shared data]

buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)

Synchronization variables]

mutual exclusion : need binary semaphore (공유데이터의 상호배제를 위해(자원 접근 넣고 빼기))

resource count : need integer semaphore (남은 full/empty buffer 수 표시를 위해(가용자원에 대한 문제))

Synchronization variables
semaphore full = 0, empty = n, mutex = 1; // lock을 거는용 mutex, 비어있는 변수 empty, 내용있는 버퍼 full

Producer
do {
   P(empty);    //빈 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);    //버퍼 획득시 lock 걸기
   add x to buffer
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(full);       //데이터 넣은 버퍼 갯수 증가
} while(1);

Consumer
do {
   P(full);       //데이터 있는 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);   //버퍼 획득시 lock 걸기
   remove an item from buffer to y
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(empty);   //비어있는 버퍼 갯수 증가
} while(1);

2. Readers-Writers Problem : 읽고 쓰기 문제

한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안된다

read는 동시에 여럿이 해도 된다

solution

- writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 DB에 접근하게 해준다

- writer는 대기 중인 reader가 하나도 없을 때 DB접근이 허용된다

- writer가 DB에 접근 중이면 reader들은 접근이 금지된다

- writer가 DB에서 빠져나가야만 reader의 접근이 허용된다

Shared data]

DB 자체

readcount (현재 DB에 접근 중인 reader 의 수)

Synchronization variables]

mutex : 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용

db : reader 와 writer 가 공유 DB 자체를 올바르게 접근하게 하는 역할

Shared data
int readcount = 0;
DB 자체;
Synchronization variables
semaphore mutex=1, db=1; //mutex 는 readcount 에 대한 lock 용, db는 DB lock 용

Writer
P(db);  // Starvation 발생 가능 (Reader 가 계속 들어와서 존재할 경우 Writer 순서가 오지 않음)
writing DB is performed
V(db);

Reader
P(mutex); // readcount 도 mutex 가 보장되어야 하므로 readcount lock시킨다
readcount++;
if(readcount==1) P(db); //block writer : 최초의 reader 접근시 writer lock시킨다
V(mutex); //readers follow
reading DB is performed
P(mutex);
readcount--;
if(readcount == 0) V(db);  //enable writer (writer lock을 푼다)
V(mutex);

3. Dining-Philosophers Problem

Dead lock 의 가능성

해결방안 :

1) 최대 4명만 동시에 테이블에 앉도록

2) 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다

3) 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

2번 해결방안에 대한 코드]

Semaphore의 문제점

- 코딩하기 힘들다

- 정확성(correctness)의 입증이 어렵다

- 자발적 협력(voluntary cooperation)이 필요하다

- 한번의 실수가 모든 시스템에 치명적 영향을 준다

실수의 예]

Monitor

: 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct (java 디자인 패턴에서 어댑터 패턴을 사용하여 세마포를 캡슐화한 어댑터와 비슷한 느낌)

- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음

- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

- Condition variable 은 wait과 signal 연산에 의해서만 접근 가능

x.wait()

: x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다

x.signal()

: x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다

Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다

monitor 를 사용한 bounded buffer 문제 해결 코드]

monitor bounded_buffer
{
   int buffer[N];
   condition full, empty;
   // condition var은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나
   // 큐에서 프로세스를 깨우는 역할만 함

   void produce(int x){
      empty.wait(); // if there is no empty buffer 
      full.signal(); // add x to an empty buffer
   }
   void consume(int x){
      full.wait(); // if there is no full buffer
      empty.signal(); // remove an item from buffer and store it top x
   }
}

monitor 를 사용한 dining philosopher 문제 해결 코드]

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Semaphores 

임계영역 문제를 해결하기 위한 알고리즘(참고)들을 추상화 시킴

[Semaphore S]

integer variable

아래 두가지 atomic 연산에 의해서만 접근 가능

P(S) 자원 있으면 가져감

while(S<=0) do no-op;  //wait : busy-wait
S--;

V(S) 반납

S++;

[세마포를 사용한 임계영역문제 해결 : busy-wait (=spin lock)]

Synchronization variable
semaphore mutex; // mutual exclusion

do {
   P(mutex);        // if positive, decrement & enter, otherwise, wait
   critical section
   V(mutex);        // Increment semaphore
   remainder section
} while(1);

[세마포를 사용한 임계영역문제 해결 : block-wakeup]

Semaphore 정의]
여기서 value는 상호배제를 위한 flag용도가 아닌 가용한 자원의 수

typedef struct
{
   int value;             // semaphore
   struct process *L;   // process wait queue
}

block 과 wakeup을 다음과 같이 가정]

block :

커널은 block을 호출한 프로세스를 suspend 시킨다

이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다

wakeup(P) :

block된 프로세스 P를 wakeup 시킨다

이 프로세스의 PCB를 ready queue로 옮긴다

P(S)

S.value--;
if(S.value < 0){
   add this process to S.L;
   block();
}

V(S)
부등호가 <= 인 이유는,
value가 0보다 작을 경우 자원을 기다리는 프로세스가 있음을 의미하므로 value가 0보가 작을 때 wake up 함

S.value++;
if(S.value <= 0){
   remove a process P from S.L;
   wakeup(P);
}

일반적으로 Busy-wait보단 Block/wakeup를 사용

Critical section 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수도 있다

[ 두가지 유형의 Semaphores ]

1) Counting semaphore 

도메인이 0 이상인 임의의 정수값

주로 resource counting(가용한 자원 수 카운트용)에 사용

2) Binary semaphore (=mutex)

0 또는 1 값만 가질 수 있는 semaphore

주로 mutual exclusion (lock/unlock)에 사용

※ Deadlock (교착상태)

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

※ Starvation (기아)

indefinite blocking.

세마포어 큐에서 빠져나갈 수 없는 현상

(deadlock 도 일종의 starvation)

[Deadlock, Starvation의 예 : Dining-Philosophers Problem]

한 사람이 양쪽의 젓가락 한짝씩 들어서 한 쌍을 만들어야 식사가 가능하다고 할 때,

Dead lock 은 모든 사람들이 자신의 자리에서 오른쪽(왼쪽) 젓가락을 사용하여 모두가 식사를 시작하지 못하는 상황

Starvation 은 사람 A의 좌우 사람이 젓가락을 가지고 식사를 하여 A 가 식사를 시작하지 못하는 상황

※ 이화여대 반효경 교수님의 운영체제 강의 정리