반응형
교재 : Applied Operating System Concepts / Silberschatz, Galvin, Gagne / WILEY
교수 : 고건 교수님
학기 : 2003/봄
Chapter 9. Memory Management
Binding
- Compile time binding : M주소를 알아야함. absolute code generated. M주소가 바뀌면 리컴파일
- Load time binding : Loader책임하에 주소부여. relocatable code로 compile(즉, Base주소 + x 로 표기)
- Execution time binding : 수행중에도 주소 바뀜. CPU가 주소생성시 마다 binding check(Address mapping table). HW서포트 필요(MMU).
Dynamic Loading : Routine is not loaded until it is called.
Overlay : Keep in memory only those part when actually needed(같은 곳에 mapping).
Dynamic Storage-Allocation Problem
- First-fit : structure의 앞부분에 너무 작은 hole들이 많아지게 됨 -> move head-pointer
- Best-fit : must search entire list. many small holes.
- Worst-fit : must search entire list. large holes.
=> 이상 세 가지 : External fragmentation의 문제 -> Buddy system
- Buddy system : 2의 배수로만 allocate. Internal fragmentation의 문제.
Fragmentation
- External F : M는 충분하지만, contiguous하지 않음. = many small holes. -> compaction
- Internal F : 요구한것보다 좀더 많이 M를 allocate함으로써 쓰지 않는 메모리가 생김.
- Compaction : shuffle M conents - 빈공간을 모두 한데 모음. dynamic relocation일때만 가능.
IO를 수행중일 경우 다른 주소로 옮겨가지 못함. -> OS buffer를 통해서만 IO
Very expensive at peak load. 성능저하!!
Page Table
- TLB : Associative Register. Parallel Search가 요구됨 -> 비쌈. context switch때 flush!
- 하나의 정보를 여러 copy로 보관할 경우 valid/invalid bit이 항상 필요함.
- 테이블이 너무 크므로 한번에 한 페이지 크기만큼의 테이블만 로드.
- 최초엔 모든 frame이 invalid.
Inverted Page Table
- 1 entry per page가 아니라 1 entry per frame으로 구현
- frame#를 index로 하고, 각 entry에는 (PID, page#)가 존재함. 시스템 전체에 하나의 Table만 존재.
- 단점 : associative search. need to search entire table.
Shared Code
- aka. Re-entrant Code(여러 process가 enter), Non-self-modifying Code(code수정불가)
- instruction과 data를 구분하여 컴파일.
- code부분에 state를 남겨서는 안됨. 모든 state는 Base Addr. Relative하게 data부분에 표현해야함.
- 각 process는 Private code and data를 따로 갖고, Shared Code부분을 공유.
Segmentation Architecture
- Segment : a logical unit.
- Protection 용이. segment 단위로 protection bit(RWX)을 둠. -> 한 segment 안에 RWX가 섞여있을 경우엔?
- fault : 아직 M에 없거나, offset 볌위를 넘었거나 등의 다양한 경우에 발생.
- segment 크기가 크면 다시 page 단위로 나눔.
segment offset을 page/displacement로 나누어야하고, table을 두번 access 하는 단점.
Free Storage
- 순서 : LIFO(스택, 하나의 큰 hole), FIFO(큐, 두개의 작은 hole), 무순서(무수히 많은 hole, 검색에 O(n) 시간이 요구됨)
- 크기 : fixed(internal fragmentation), variable(external fragmentation).
Chapter 10. Virtual Memory
Page Fault
- Access to invalid page - page fault trap - trap handler
- Pure paging : Never swap-in until referenced. 프로그램은 M에 page가 없는 상태로 시작(cold start).
- Locality of reference : 근거 - Paging system이 성능이 좋다!
- Effective Access Time(EAT) = (1-p) x memory access
+ p x (OS&HW page fault overhead + [swap out(replace)] + swap in +OS&HW restart overhead)
... p : page fault rate
Page-Replacement Algorithms
- reference string을 유지함. sequence of page name
- FIFO : Belady's Anomaly : more frames -/-> less page faults (<-> Stack Algorithm)
- LRU Approximation : Reference bit 이용. Addtional R bit(R-bit이 8bit, OS가 주기적으로 shift),
Second chance, Enhanced SC(dirty bit도 고려).
- Counting Alg. : LFU, MFU - reference 횟수(frequency)에 기반.
Thrashing
- swapping pages in and out 하느라 많은 CPU time을 소모함.
- page fault rate↑ : 성능↓ : OS가 멀티프로그래밍 degree를 더 올림 -> Thrashing 발생!
Working-Set Model
- WS(t) : 일정 시간동안 ref된 페이지들.
- WSS : Working Set Size : ref돤 페이지의 갯수
- D : 씨그마 of WSS, m : 할당된 frame수
- D > m -> Thrashing! -> 그 프로세스를 Suspend
- LRU와 달리 replace/allocate를 같이 결정.
Page Management Policy
- Fetch policy : prefetch or on-demand
- Replacement policy : Recency based, Frequency based ...
- Allocation policy : Equal vs. Unequal, Fixed vs. Dynamic
Chapter 11. File-System Interface
File System = Disk (Data Structure + Operation)
- 일종의 Abstract Data Type
Acyclic-Graph Directories
- Symbolic link : pathname. 원래주인이 파일 삭제시 dangling reference?
- Hard link : metadata를 복사. consistency문제. delete를 위해 reference count 필요.
Mounting File-System
- Floppy Disk, Comact Disc 등은 어떻게 접근? -> mounting을 이용, 루트 아래 새 pathname을 부여
Allocation of File Data in Disk
- Contiguous : external fragmentation. File grow의 어려움. Fast I/O(한번에 많은량 전송), swapping용으로 사용.
- Linked : No Random Access
- FAT : pointer들을 한곳에 모아둠.
Chapter 13. Secondary-Storage
- Disk Scheduling : FCFS, SSTF, SCAN, C-SCAN
Chapter 18. Protection
Access Matrix : domain-object 간의 권한
- Switch right : 한 도메인에서 다른 도메인으로 스위치 가능
- Copy right : Asterisk(*)로 표시, 권한을 can copy un/down. 즉 이 오브젝트에 대한 권한을 다른 도메인에게 줄 수 있다.
- Limeted Copy right : 그렇지만 Asterisk(*)까지 copy할 수는 없다.
- Transfer right : Copy up/down then, Remove my right. so, Transfer!
- Owner right : 이 오브젝트에 대한 access matrix를 수정가능. 즉 현재 column 내에서.
- Control right : 이 도메인에 대한 access matrix를 수정가능. 즉 현재 row 내에서.
- Access-control list : Each column
- Capability list : Each row
Chapter 19. Security
Threats
- program에서 : Trojan Horse(예,가짜 login code), Trap Door(은행 잔고 유출)
- system에서 : Worm(spawn mechanism), Virus(싱글유저시스템에서만)
교수 : 고건 교수님
학기 : 2003/봄
Chapter 9. Memory Management
Binding
- Compile time binding : M주소를 알아야함. absolute code generated. M주소가 바뀌면 리컴파일
- Load time binding : Loader책임하에 주소부여. relocatable code로 compile(즉, Base주소 + x 로 표기)
- Execution time binding : 수행중에도 주소 바뀜. CPU가 주소생성시 마다 binding check(Address mapping table). HW서포트 필요(MMU).
Dynamic Loading : Routine is not loaded until it is called.
Overlay : Keep in memory only those part when actually needed(같은 곳에 mapping).
Dynamic Storage-Allocation Problem
- First-fit : structure의 앞부분에 너무 작은 hole들이 많아지게 됨 -> move head-pointer
- Best-fit : must search entire list. many small holes.
- Worst-fit : must search entire list. large holes.
=> 이상 세 가지 : External fragmentation의 문제 -> Buddy system
- Buddy system : 2의 배수로만 allocate. Internal fragmentation의 문제.
Fragmentation
- External F : M는 충분하지만, contiguous하지 않음. = many small holes. -> compaction
- Internal F : 요구한것보다 좀더 많이 M를 allocate함으로써 쓰지 않는 메모리가 생김.
- Compaction : shuffle M conents - 빈공간을 모두 한데 모음. dynamic relocation일때만 가능.
IO를 수행중일 경우 다른 주소로 옮겨가지 못함. -> OS buffer를 통해서만 IO
Very expensive at peak load. 성능저하!!
Page Table
- TLB : Associative Register. Parallel Search가 요구됨 -> 비쌈. context switch때 flush!
- 하나의 정보를 여러 copy로 보관할 경우 valid/invalid bit이 항상 필요함.
- 테이블이 너무 크므로 한번에 한 페이지 크기만큼의 테이블만 로드.
- 최초엔 모든 frame이 invalid.
Inverted Page Table
- 1 entry per page가 아니라 1 entry per frame으로 구현
- frame#를 index로 하고, 각 entry에는 (PID, page#)가 존재함. 시스템 전체에 하나의 Table만 존재.
- 단점 : associative search. need to search entire table.
Shared Code
- aka. Re-entrant Code(여러 process가 enter), Non-self-modifying Code(code수정불가)
- instruction과 data를 구분하여 컴파일.
- code부분에 state를 남겨서는 안됨. 모든 state는 Base Addr. Relative하게 data부분에 표현해야함.
- 각 process는 Private code and data를 따로 갖고, Shared Code부분을 공유.
Segmentation Architecture
- Segment : a logical unit.
- Protection 용이. segment 단위로 protection bit(RWX)을 둠. -> 한 segment 안에 RWX가 섞여있을 경우엔?
- fault : 아직 M에 없거나, offset 볌위를 넘었거나 등의 다양한 경우에 발생.
- segment 크기가 크면 다시 page 단위로 나눔.
segment offset을 page/displacement로 나누어야하고, table을 두번 access 하는 단점.
Free Storage
- 순서 : LIFO(스택, 하나의 큰 hole), FIFO(큐, 두개의 작은 hole), 무순서(무수히 많은 hole, 검색에 O(n) 시간이 요구됨)
- 크기 : fixed(internal fragmentation), variable(external fragmentation).
Chapter 10. Virtual Memory
Page Fault
- Access to invalid page - page fault trap - trap handler
- Pure paging : Never swap-in until referenced. 프로그램은 M에 page가 없는 상태로 시작(cold start).
- Locality of reference : 근거 - Paging system이 성능이 좋다!
- Effective Access Time(EAT) = (1-p) x memory access
+ p x (OS&HW page fault overhead + [swap out(replace)] + swap in +OS&HW restart overhead)
... p : page fault rate
Page-Replacement Algorithms
- reference string을 유지함. sequence of page name
- FIFO : Belady's Anomaly : more frames -/-> less page faults (<-> Stack Algorithm)
- LRU Approximation : Reference bit 이용. Addtional R bit(R-bit이 8bit, OS가 주기적으로 shift),
Second chance, Enhanced SC(dirty bit도 고려).
- Counting Alg. : LFU, MFU - reference 횟수(frequency)에 기반.
Thrashing
- swapping pages in and out 하느라 많은 CPU time을 소모함.
- page fault rate↑ : 성능↓ : OS가 멀티프로그래밍 degree를 더 올림 -> Thrashing 발생!
Working-Set Model
- WS(t) : 일정 시간동안 ref된 페이지들.
- WSS : Working Set Size : ref돤 페이지의 갯수
- D : 씨그마 of WSS, m : 할당된 frame수
- D > m -> Thrashing! -> 그 프로세스를 Suspend
- LRU와 달리 replace/allocate를 같이 결정.
Page Management Policy
- Fetch policy : prefetch or on-demand
- Replacement policy : Recency based, Frequency based ...
- Allocation policy : Equal vs. Unequal, Fixed vs. Dynamic
Chapter 11. File-System Interface
File System = Disk (Data Structure + Operation)
- 일종의 Abstract Data Type
Acyclic-Graph Directories
- Symbolic link : pathname. 원래주인이 파일 삭제시 dangling reference?
- Hard link : metadata를 복사. consistency문제. delete를 위해 reference count 필요.
Mounting File-System
- Floppy Disk, Comact Disc 등은 어떻게 접근? -> mounting을 이용, 루트 아래 새 pathname을 부여
Allocation of File Data in Disk
- Contiguous : external fragmentation. File grow의 어려움. Fast I/O(한번에 많은량 전송), swapping용으로 사용.
- Linked : No Random Access
- FAT : pointer들을 한곳에 모아둠.
Chapter 13. Secondary-Storage
- Disk Scheduling : FCFS, SSTF, SCAN, C-SCAN
Chapter 18. Protection
Access Matrix : domain-object 간의 권한
- Switch right : 한 도메인에서 다른 도메인으로 스위치 가능
- Copy right : Asterisk(*)로 표시, 권한을 can copy un/down. 즉 이 오브젝트에 대한 권한을 다른 도메인에게 줄 수 있다.
- Limeted Copy right : 그렇지만 Asterisk(*)까지 copy할 수는 없다.
- Transfer right : Copy up/down then, Remove my right. so, Transfer!
- Owner right : 이 오브젝트에 대한 access matrix를 수정가능. 즉 현재 column 내에서.
- Control right : 이 도메인에 대한 access matrix를 수정가능. 즉 현재 row 내에서.
- Access-control list : Each column
- Capability list : Each row
Chapter 19. Security
Threats
- program에서 : Trojan Horse(예,가짜 login code), Trap Door(은행 잔고 유출)
- system에서 : Worm(spawn mechanism), Virus(싱글유저시스템에서만)
반응형