DEVELOPyo

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의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생

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