[운영체제] 기말고사 Summary

 

 

 

 

9. main memory 

- memory management 목표 – provide a convenient abstraction for programming (인터페이스)

- Batch programming 

– program이 직접 physical address를 사용한다. 

- process 하나만 있던 시절에는 상관 없었음 -> multiple process – 메모리 관리의 필요성 발생

 

- 문제점 1) multiple process 2) 메인 메모리보다 큰 프로세스 (ex) 게임)

-> Virtual memory 등장
: process 내부에서는 virtual, logical address 사용, 실제 RAM의 주소는 physical address 

- secondary storage, memory를 main memory처럼 가져와서 사용함

- 실제 메모리는 무한하다고 가정하고 프로그램 개발, OS가 이러한 기능을 가능하게 하는 것

 

* 언제 logical address와 physical address를 binding 해야 할까? (address binding time)

- compile time / load time / execution time – 실행 시간에 binding

 

1) compile time – logical address를 실제 RAM 주소에 compile time에 연결 -> 고정적으로 해당 영역(물리적) 에서만 특정 process가 수행됨 – 나머지 영역은 낭비될 수 있다 – 특정 메모리에서만 프로세스가 돌아감

- batch system (아두이노) – 하나의 프로그램만 수행되는 환경은 okay

2) Load time – 로딩 시, 시간이 많이 걸림 – 오버헤드가 많아 사용 X

 

3) Execution time – 현재 사용하는 방법

- logical address가 그대로 올라간 뒤, 해당 프로세스의 명령어가 실행될 때, 그제서야 base address + a로 physical address가 계산됨 (binding)

 

Address mapping – MMU (memory management unit) 
– CPU 내에서 virtual(프로그램 내부에서 사용), physical address(실제 RAM 주소) 변환시키는 하드웨어 장치

- 둘 사이의 변환을 할 때, CPU내의 MMU라는 로직에서 translation을 해준다.

+ Swap – RAM에 존재하는 일부분을 secondary storage에 저장, 무한 메모리처럼 보일 수 있다. (10장)

 

- logical address space = 서로 다른 사용자가 동시에 application을 실행 -> 동일한 주소 값

: 다른 Physical address에 매핑 되더라도, 프로그램 내부의 logical address는 동일하다

 

1. Contiguous allocation – logically contiguous => physically contiguous (가장 단순하고 쉬운 방법, 사용X)

- physical address = logical address + base address (relocation register)

+ 메모리 보호: 내가 참조할 수 있는 영역이 아니라면 exception, fault -> OS (limit register보다 작은 값만)

* access time 측면에서 성능은 가장 좋다. 

 

-> 여러 process를 돌리며, hole이 발생 -> first fit(가능한 첫번째), best fit(가장 짜투리 작은 것에 배치) // 

Worst fit(가장 큰 hole이 남는 것에 배치)은 다른 두 방법에 비해 성능이 떨어짐 // 하지만 이렇게 해도 

* External Fragmentation – 단편화 (hole의 자투리 조각), 홀이 작아져서 더이상 사용되지 않음

- compaction으로 해결할 수 있지만, HDD로 옮기고 다시 copy하는 과정에서 I/O overhead가 매우 큼 

 

2. Paging – logically contiguous, but physically not contiguous

- logical memory를 page 단위로, physical memory를 frame 단위로 자름 (보통 4KB)

- 더이상 external fragmentation은 발생X, internal fragmentation은 O -> 그러나 비교적 매우 작음

 

* 주소 변환 - <page number + offset> (p, d) -> <frame number + offset> (f, d) 

- page table은 OS가 관리한다, (p, d) -> (f, d) // 이때 offset은 유지되는데, 이게 page 크기만큼 할당

(한 페이지 내부에서 어느 위치인지 결정하는 값이니까)

- page table은 page number -> frame number 로 mapping 시키는 역할 (offset은 동일)

- page table은 Process 별로 존재한다!

 

* page example – logical address – 32bit, physical address – 20bit, page size 4KB(12bit)

-> offset 12 bit, page number 20bit (32 – 12) // frame number = 8 bit

Page table entries = 2^20개 (page number 수 만큼) // 저 테이블 값이 Int -> 4MB(CPU 내의 MMU에 둘 수 X, 메인 메모리에 둔다. 메인 메모리에 2번 접근 -> 성능이 2배 나빠진 것)

- Free frame – 현재 할당되지 않은 frame 관리 

 

* Associative memory – parallel search == CAM(content addressable memory)

- TLB (translation look-aside buffer) -> 얘도 process 별 존재, MMU(즉 CPU)가 관리

- two memory accesses 문제를 해결하기 위해, TLB(캐쉬 메모리)를 사용한다.

- page number를 주면, parallel하게 쫙 서치, 바로 frame number가 튕겨져 나오는, 특별한 캐쉬 메모리 

* TLB = locality (temporal locality – 실행 시간 관점, code 영역, loop 구문 80% vs Spatial locality – 내가 참조한 주변 영역 메모리가 참조될 가능성이 높다, data array)

 

- TLB miss – 99%는 TLB hit, but 때때로 miss -> CPU(하드웨어)가 알아서 TLB miss 처리

: 0.99 * 1 + 0.01 * 2 -> 1.01 

- Effective access time (EAT) = (1 + e) * a + (2 + e)(1 – a) = 2 + e – a == 1

// TLB hit 확률 = 0.99 = a, TLB miss = 1 – a, e는 그냥 매우 작은 값 의미 

 

* paging의 memory protection (지금까지는 memory address 관리) -> 참조하지 못할 영역을 어떻게 보호? 

- process 별로 존재하는 page table -> frame number와 함께, valid – invalid 한 비트 필요 

- 내가 원하는 page의 frame number + invalid라면, access할 수 없다. 
-> Fault, exception: CPU가 스스로에게 인터럽트를 건다 – OS가 수행되어 해당 프로세스 종료시킴

 

* Page table entries (PTEs)

- valid bit (V) – 메모리 프로텍션 / reference bit (R) – 참조된 유무 확인 / modified bit (M) – 변경 유무 

Protection bit (prot) – 해당 페이지에 허용된 연산을 제어, 2bit ex) read, write, exec, ect 

-> page table에 frame number만 있는 것은 아니다. 이렇게, 다른 비트들도 더 있음

 

- managing page tables – 32bit address space, offset 12bit, 2^20개의 entries * 4KB pages -> 4MB, 100개의 프로세스 -> 400MB

- 작은 process의 경우, 1개 page만 valid, 나머지 싹 다 invalid -> 비효율

-> 따라서 page table 구조를 dynamically extensible하게! -> 1. Hierarchical paging (현재 사용하는 방식)

 

1. * Hierarchical paging – multiple page tables를 사용 – 원래 frame number를 저장한 위치에, 다른 page table의 주소가 있다. 

- outer page table – 2^10 entries, 4B(32bit int의미) * 2^10 = 4KB

- page table – 2^10 entries * 2 ^ 10 = 4B(int) * 2^10 * 2^10 = 4MB (전체 = 4KB + 4MB)

(If single level paging – 2^20 entries * 4B = 4MB) 줄인다면서 왜 늘어남? 최악의 경우인 것! 

 

- 필요할 때 마다 동적으로 하나씩 만드는 것

- only one page is used -> outer page table은 4KB다 존재, but outer에서 연결되는 inner가 2^10 entries 1개 

-> 2^10 * 4B = 4KB (따라서 총 4KB + 4KB = 8KB만 있으면 됨!) 

-> process 크기에 비례한 page table의 크기

 

2. Hashed page table – 오버헤드가 너무 커서 사용X 3. Inverted page table – frame과 page를 거꾸로 만들자 X

 

* paging의 장점 – shared memory를 구현하기 좋다. 

- 서로 다른 process가 code영역은 동일하고, data 영역만 다르다 -> page table의 마지막 page 요소만 다름

-> 동일한 physical memory를 매핑 

-> 유닉스-리눅스의 shared library 구현 시 활용, (윈도우는 dll – dynamically linked library)

 

- paging의 장점 – external fragmentation X, memory protection 용이

- 단점 – 2 reference per address lookup (page table -> memory) -> TLB (cache memory)로 해결!

+ 과한 page table 크기 -> hierarchical page tables로 해결!

 

3. Segmentation (contiguous allocation, paging 그리고 마지막 방법 – 얘도 현재 쓰이는 방법)

- 의미 있는 단위로 자르자. 내용을 고려하여 분리하자. Ex) 코드, 데이터, 힙(extra), 스택

+ segment 내에서 contiguous allocation -> 다시 external fragmentation 문제 발생! -> paging 사용

 

- segmentation의 장점 – memory protection 용이 (read, write, exec 등 protection 비트 활용)

- Share segment가 용이하다 (Code/data sharing이 segment level에서 가능, ex shared libraries)

-> paging의 장점과 혼합하여 hybrid 방식으로 사용, segment로 나누고, 그 내부에서 paging으로 자름

=> Hybrid approach: Paged segments // Segmentation with paging 이라고 부름 

 

+ multiple page size = 4KB보다 더 큰 페이지 사이즈도 지원 (특정 경우, 큰 4MB page 지원)

- ARM – mobile – segmentation X, multiple page size 활용

 

 

 

 

 

10. Virtual memory 

: virtual memory that is larger than physical memory (RAM) – 잘 안 쓰는 것은 secondary로

 

* Demand Paging – 필요한 시점에 이루어지는 paging

- paging system with page level swapping 

: page 단위의 swapping -> secondary storage <-> main memory (RAM)

- page가 필요한 시점에 main memory로 불러온다. 

-> Locality (cache memory, TLB, demand paging, Buffer cache 등등)

- temporal locality – 최근에 참조된 부분이 다시 참조될 가능성이 높다 – x 축으로 길게 표시됨

- spatial locality – 최근 참조된 부분의 근처가 곧 참조될 가능성이 높다 – y 축으로 길게 표시됨

 

- 왜 Demand Paging인가? // 이전까지는 해당 프로세스가 참조 가능 or 아닌지 표현하는 Invalid bit 

-> 일단 다 안 올림, 시작 시 모두 invalid bit 

- 그 페이지가 참조되는 시점에 valid로 올림 -> demand paging

 

* 새롭게 정의된 의미

1. valid bit (v) – 참조할 수 있는 영역, 지금 현재 physical memory에 있다 (in memory 의미)

2. invalid bit (i) – 내가 참조할 수 없는 영역 (protection fault) or 
              있긴 있는데, 지금 현재 메모리에 없다! (secondary storage에, 따라서 Page fault)

+ 처음에는 모두 invalid로 설정되어 있다. 

 

- CPU가 메모리 참조 명령어를 실행하는 시점에 (exec time) 

- virtual (logical) address <-> physical address mapping by MMU 

1. TLB hit (99%)  TLB miss -> 2. Page table -> 더이상 CPU(MMU)가 진행할 수 없음 -> fault

-> falut 걸렸으니, OS가 처리 -> secondary storage (backing store) – I/O 

-> free frame에 가져옴 -> 해당 frame number를 기입하고, invalid를 valid로 변경 

-> 명령어를 restart 시키면 main memory access 가능! 

 

+ protection fault – 참조할 수 없는 메모리 영역을 참조 – program bug

- page fault – main memory를 충분히 달았어야 함 

 

- Copy on write: fork 시 memory management // Unix

- 프로세스 fork 시 바로 copy 되는 것이 아니라, write하는 시점에 메모리 공간이 분리되는 것

 

* free frame이 없다면? -> main memory의 모든 frame이 다 사용 중이다. (여러 process 실행 중이라)

- 어떤 page가 메인 메모리에 올라오면서, 다른 Page는 backing store로 내려감 (i 중 하나를 내려서 처리)

-> page replacement (페이지 교체)

: 어떤 page를 내려 보낼 것? (page replacement algorithm) – 오래 사용되지 않은 것을 내리자. 

-> 앞으로도 사용되지 않을 확률이 높기 때문에 (locality) -> victim(희생양)을 정해 swap한다. 

 

* page replacement algorithm – 알고리즘의 목표 – Lowest page fault rate

- page faults vs Number of frames (main memory free frame 수와 page fault는 반비례 관계)

-> free frame 수가 많을수록, page faults가 덜 발생한다. 

 

1. FIFO – 가장 fair, but locality에 대한 이해가 없음. 성능이 낮다 – Bradly’s anomaly 

Process가 3개의 frame 할당 – 9 fault, 4개 frame 할당 받으면 10 fault가 발생

-> locality를 전혀 고려하지 않았기 때문에 

 

+ memory 4GB / frame 4KB -> frame이 1M개 (2^20, 백만) / process 100개 -> 1개 당 10,000 frame

 

2. Optimal algorithm – 나보다 더 좋은 성능을 가진 알고리즘은 없다

- replace page that will not be used for longest period of time (가장 오랫동안 안 쓰일 것을 교체)

- 처음 애들은 무조건 Fault가 남 -> demand paging 때문

- 곧 reference 될 애들은 내리지 않음 

- 하지만 순서를 미리 알 수 없다 -> 과거를 통해 미래를 예측해야 함 – 역시나 locality

 

3. LRU – Least Recently Used 알고리즘 – optimal에 근접한 성능

- 가장 오랫동안 사용되지 않은 page를 교체한다. (과거로부터 미래를 추측한다)

-> page가 언제 참조되었는지, 그 정보를 갖고 있어야 함. 2가지 방법 제시 

 

1) timestamp implementation – page 별 time stamp를 기록하겠다. 

2) Stack implementation – 메모리 참조될 때 마다 스택 구조 변경 – 오버헤드 너무 커서 불가능 

+ 타임 스탬프도 오버헤드 부담스러움 -> 작은 비트로 추정(approximation)하자 -> 1 bit로 확 줄임

 

* Reference bit -> 1 or 0 – 어떤 page가 참조될 때, reference bit를 1로 세팅한다. 

- 주기적으로 reference를 0으로 만듦 -> replace가 이루어질 때, 1과 0 중 0을 내리겠다. 

- 0이 여러 개라면? 랜덤으로 내림 

 

+ 실제 CPU가 사용하는 방법 – Second Chance (LRU lock) – 한 번 더 기회를 준다!

- circular queue of pages로 한 번 봐준다

 

4. NRU - Not Recently Used – 현재 CPU가 사용하는 방식

- R(reference), M(modified) bit를 활용한다. 

1. Class 0 – R = 0, M = 0, 최근에 참조도, 변경도 X -> 가장 우선적으로 쫓아냄

2. Class 1 – R = 0, M = 1, 최근에 참조X, 변경O -> 그 다음으로 쫓아냄

3. Class 2 – R = 1, M = 0, 얘가 그나마 더 자주 참조될 가능성 있다. 

4. Class 3 – R = 1, M = 1, 가장 낮은 쫓김 순위 

 

+ PTEs (page table entries) -> 여기서 나온 R, M bit! 

- Page table에서 지원한다 == CPU에서 지원한다 (하드웨어적으로)

 

5. LFU – Least Frequently Used – 아까는 시간, 이건 횟수 count 기준

- Counting based page replacement – 이것도 오버헤드 때문에 한 비트로 줄이면 (approximation), 결국 LRU나 LFU나 똑같이 됨 – 성능이 둘 다 optimal

 

* Allocation of frames – process에게 free 프레임을 얼마나 할당할 것인가?

- Proportional allocation – process의 크기에 비례하여 할당 

- Priority-based allocation 

 

+ Page replacement 

- global replacement

- local replacement – 현재 OS가 사용하는 방법: 해당 process 내에서 교체

 

- Page fault frequency scheme (free frame 수 대비, page fault 비율)

- Page fault가 자주 발생하는 process -> 얘는 frame이 부족하구나 – 더 할당해 줌

- Page fault 비율이 매우 낮은 process -> 얘는 여유가 있구나 – 다른 애에게 줄 수 있음

 

* Thrashing – process is busy swapping pages in and out 

- process의 수가 늘어나다 보면, CPU utilization이 확 줄어드는 지점 -> thrashing

- CPU가 Disk IO만 하는 것 // locality (자주 사용되는 메모리)의 합이 전체 메인 메모리 사이즈보다 클 때 

 

해결 방법 1. Main memory를 더 늘린다. 2. 실행 중인 Process의 수를 줄인다. 

- 메모리에 비해, 프로세스가 사용하는 메모리가 더 많은 것 

 

- Working-Set model

- working set size == locality의 크기 

- 해당 process가 최근 참조한 page들의 집합 // WSS가 작을수록 locality가 우수한 process

- 모든 process들의 working set size의 합 D > M – 메인메모리 크기 -> thrashing 발생

 

- Prepaging – 인근의 메모리를 미리 Disk에서 읽어오는 것 

-> Spatial locality

 

- Page size에 대한 특성들

- internal fragmentation -> 작을수록 좋다 

- Page table size – 큰 게 좋다. 

- I/O Overhead – 큰 게 좋다. 

- Locality – 큰 게 좋다. 

 

* TLB reach – TLB가 커버하는 메모리 영역 

–> 이 입장에서도 page size가 큰 것이 좋다. 

- TLB Reach = (TLB size) * (Page size)

 

+ index 연산, j -> i : A[i][j] -> 1024*1024 page faults 

- i -> j : A[i][j] -> 1024 page faults

+ 32bit integer 1024개 -> 4KB -> page size

 

+ DMA (direct memory access) – I/O가 직접 disk에 씀 

- main memory에 직접 접근 (CPU register에 담을 수 없기 때문에) 

- 이때 virtual memory management 고려X, lock을 걸고 I/O 장치만 사용한다. 

- virtual memory의 free frame 영역에 들어가서는 안됨

 

 

 

 

 

11. Mass-Storage Structure

- I/O 장치 관리, secondary storage, mass storage

- HDD – hard disk drive – 기계적 

- SDD – Solid State disk – 전기적

- RAM disk – 전원 껐다가 켜면, 다 날라가는 메모리 – iptime 

- Magnetic tape – data 백업 용도로 사용

 

- Disk attachment 

1) Host attached – 개인 PC

2) Network attached – 연구실 NAS

 

* Network Attached Storage – NAS

- IP 네트워크를 통해 접근 / file level access / 여러 사용자들이 공유하는 storage

 

* Storage Area Network – SAN 

- block level access / Use storage protocols SCSI or Fibre channel -> Non-IP networks

- 디스크들이 네트워크로 연결됨 ex) 데이터 센터 서버 

- SAN의 파일 단위와 달리, 하나의 큰 디스크, 블록으로 보는 것 

 

- HDD structure 

- 특정 rpm으로 계속 도는 축 spindle / 기둥 cylinder / platter 판 / platter의 한 면 surface / surface 위의 동심원 track / track의 일부분 sector / arm / head 

- 하드웨어적으로 cylinder, surface, track, sector 넘버 대신, logical block 단위로 읽음 

 

* 3단계로 이루어지는 disk performance 

1) Seek – 매우 느림, 디스크 arm을 원하는 실린더로 옮기는 것, 기계적 

2) Rotation – 원하는 sector가 head 밑으로 오도록 회전하는 것, 기계적

3) Transfer – surface에서 disk controller로 데이터를 읽는 것, 전기적 신호로 읽어 빠르다. 

-> Disk scheduling -> minimize seek time // seek time == seek distance 

 

1. FCFS – 가장 fair – 큐에 들어온 순서대로 읽는다. Seek time을 고려하지 않음

+ 큐의 숫자 – Cylinder, track number를 의미한다. 

 

2. SSTF – Shortest Seek Time First 

- 현재 head 위치에서 가장 가까운 것을 선택 – seek time 최소화

- 일종의 SJF(shortest job first) – 이건 미리 알 수 없었지만, 디스크는 순서를 미리 알 수 있음 

- starvation을 유발할 수 있다. 

 

3. SCAN – 헤드를 한쪽으로 쭉 스캔하여 처리 

- 왼쪽으로 쭉 -> 왼쪽 끝에 도달하면 방향 전환 -> 오른쪽으로 쭉 

 

* 결론 

- 일반적으로는 – SSTF 사용 

- disk 요청이 많다면 –> SCAN – 비디오 시청 같은 경우 // heavy load

 

+ C-SCAN: 한번에 쭉 오른쪽 끝까지 간 다음, 왼쪽 끝으로 헤드를 옮김 – 쓸모없는 오버헤드

+ C-LOOK: 뒤에 더 요청이 없다면, 반대쪽 끝으로 가라 -> C-SCAN + a 

 

- Disk controller (I/O controller)

- BUS와 연결되어, 실제 IO 장치들을 제어하는 작은 컴퓨터

- 예전에는 OS가 하던 일들을 똑똑해진 Disk controller가 하는 것

 

* Swap Space management 

- Swap space – backing store – virtual memory가 디스크의 공간을 메인 메모리의 연장선에서 사용함 

- 윈도우와 달리 리눅스는 별도의 partition을 잡음 / main memory의 2배를 swap space로 잡음 

 

* RAID – Redundant Array of Inexpensive Disks = 저렴한 디스크를 중복하여 매우 많이 배치 

1. reliability 중복하여 저장 -> 신뢰도가 올라간다. (mirroring, shadowing – 똑같이 저장, or Parity, error correcting codes – 손상되어도 복구할 수 있도록) 

2. parallelism을 통해 성능 향상 (data striping = bit level vs block level)

 

1) bit level striping – parallelism – 하나의 요청을 모든 디스크가 수행 / 디스크들을 관통하는 가로로 길게 

2) block level striping – concurrency – 4개 영역을 동시에 읽기 가능하다는 장점 / 각 디스크 별로 다른 블록 

-> HDD는 한 번에 많이 읽어야 성능이 올라감 -> 따라서 block level이 더 우수 

 

1. RAID 0

- 오직 concurrency만 / data가 날라가도 상관X, 성능이 중요하다 / OS가 동시에 4개의 request를 concurrent하게 읽는 것 

- non-redundant striping – no reliability (신뢰도는 무관)

 

2. RAID 1 

- 성능은 중요X, 신뢰도만 중요하다. Mirrored disks – 똑같이 복사본만 하나 더 만든 것 

 

3. RAID 2

- bit level (사실 안 쓰임) / error-correcting codes (ECC) – 3개로 4개 복구 가능 
/ 4개 중 3개 고장까지 복구 가능 

 

4. RAID 3

- bit level / Parity – 4개 중 하나가 고장나면 P를 통해 복구 가능, 4개중 2개 이상 고장 시 복구 X

 

5. RAID 4 

- block level striping / Parity가 동일한 줄에 있다 

- write 및 update 시 P도 함께 바뀌어야 한다 -> read 시에는 문제 X 

-> P가 있는 줄만 너무 바쁨 

 

6. RAID 5 * 가장 많이 쓰이는 configuration 

- block level / Parity도 striping (distributed parity) 

- 서로 다른 디스크들로 뿌림 / 고장 잘 안 난다면 RAID 5로 충분하다. 

 

7. RAID 6 

- 2개가 고장나더라도 복구하고 싶다 -> RAID 5에서 P를 2로 늘린 것

 

* 돈이 더 많다면 mirroring 

8. RAID 0 + 1

-RAID 0 – 블럭 레벨로 -> RAID 1 – 그 뒤, 통으로 복사 

- 이때, RAID 덩어리 중 하나만 고장나도 덩어리 채로 날라감 

 

9. RAID 10 (RAID 1 + 0) 

- RAID 1 -> 먼저 복사하고 -> 이후 RAID 0 – 블럭으로 처리

- 즉 줄 별로 복사된 형태 -> 고장된 줄만 복사본으로 대체되고, 나머지는 모두 사용 가능함

- RAID 0+1보다 성능이 더 우수하다. 

 

 

 

 

 

12. I/O systems

I/O operation 

– Direct I/O vs Memory Mapped I/O

- Communicate with registers in I/O controller – MCU (작은 컴퓨터) 

- IR (instruction register) & DR (data register)

 

I/O method

- Programmed I/O – 작은 단위라면 CPU에게 전달

- DMA (Direct Memory Access) – 큰 단위, 디스크에 직접 씀

- Interrupt – 하드웨어가 일을 끝내거나, I/O event 발생 시 CPU에게 알림

 

- Direct I/O – memory와 I/O 버스가 별도로 존재 separate address – intel CPU

- Memory Mapped I/O – integrated address – 더 간단한 구조 – ARM CPU

 

* I/O Device controller – 작은 컴퓨터를 의미한다. 

- Device controller (== Host adapter) ex) Disk controller, keyboard controller -> 더 똑똑해 짐 

 

+ I/O Performance 

- CPU Cache가 가장 성능이 좋다 / DRAM / SSD / HDD (뒤로 갈수록 latency 증가)

 

- Kernel I/O 구조 

- Device와 1:1 mapping 되는 device controller (I/O를 직접 컨트롤) // hardware 

- Device Driver –> device를 구동시키는 software, 그 위의 kernel // software

 

- Device – functionality Progression 

- 가장 software (flexibility 높음) application code / kernel code / device-driver code // device controller code (hardware, firm ware) / device code (찐 hardware) 

- hardware에 가까울수록, 개발 비용 증가, 효율성도 증가, 추상화 단계도 증가, 생성하는데 시간도 증가

-> (time, efficiency, development cost, abstraction vs flexibility) 

 

- interrupt handler – interrupt를 처리 

: 짧은, 중요한 interrupt를 처리하는 critical actions / non-critical action으로 나뉘고 / 이후 OS가 처리하는 부분으로 나뉨

 

- device drivers – device specific code to control each I/O device interacting with device independent I/O software and interrupt handler – 여하튼 이건 software다! 

 

+ Unix / linux에서 I/O software 개발 시, special files 형태로 개발한다. 

 

* Buffering – CPU는 빠르지만, I/O는 매우 느림 -> I/O data가 buffer에 저장되고, 이를 CPU가 꺼내서 사용

- 성능 측면에서는 application이 직접 하는 것이 좋지만, 일반적으로 커널이 I/O 디바이스를 관리한다. 

(커널을 거쳐서 user mode, application에게 전달되는 것) 

 

* Spooling – 프린터 예시

- 일반적으로 버퍼링을 사용하나, 프린터는 매우 느림, 데이터 내용도 많다. 따라서 application에서 프린터로 보낼 파일을 미리 만들어, 커널에 전달하고, 이를 프린터로 내보내는 방식 -> Spooling이라고 한다.

 

 

 

 

 

13. File System Interface 

- 사용자 입장에서의 파일 시스템

- long term information storage – 전원이 꺼지더라도 오래 유지되어야 한다. 

- 파일들을 logically 조직한다 – directory / Sharing과 protection 기능도 있어야 함 

 

* Text file vs binary file 

- Text file – 아스키 코드, .txt, .cpp -> 텍스트나 소스 코드 파일들처럼 데이터를 코드화 한 것

- binary file – 데이터 그 자체로 의미가 있는 파일 ex) 실행 파일, .hwp 한글 파일 (그림이 삽입된 경우). PPT, word 파일 등등 대부분 binary 파일 

 

- file operation system call 

Ex) int open, int close, size_t read, size_t write -> 가장 기본적인 file operation system call // OS에게 요청

 

- file type 

- 윈도우는 파일명 뒤에 붙는 확장자로 file type 지정 (.exe, .mp3 등)

- 유닉스는 확장자명이 별 의미 X, OS가 관리한다. 

 

* file access

1) sequential access – 순서대로 바이트들을 읽는 것 2) direct access – 내가 원하는 데이터 위치로 바로 이동, random access  3) record access 4) index access 

 

- 예시 index and relative files 

- 큰 파일에서 찾을 수 X -> 작은 index file에서 내가 얻고 싶은 정보를 찾은 뒤, 해당 정보의 위치로 접근 

- 작은 Index file / 원래 정보가 저장된 큰 파일 == relative file (data file) 

- 내가 원하는 위치로 단번에 이동 -> direct access, 레코드 단위로 접근 – record access, 효율적으로 접근하기 위한 index access (3가지 다 찾을 수 있는 것) 

 

- directory와 관련된 Unix operations – opendir, readdir, seekdir, closedir => 모두 system call

 

* file system mounting 

- window = drive letter 알파벳 사용 (C:\, D:\ 등등)

- 유닉스/리눅스 = 전부 root directory -> 빈 directory 밑에 새로운 directory를 붙인다. -> 산 같아서 마운팅

 

- file sharing – Remote File Sharing 

- NFS – network file system – 유닉스의 클라이언트-서버 파일 공유 표준 프로토콜 

- CIFS – windows에서 사용하는 표준 프로토콜

 

* Protection 

1. Access control list (ACLs) – file 별로, 사용자마다 가능한 여부를 표시한 리스트 (세로 방향) 

- 지금 사용하는 방식, 모든 사용자를 다 표시하지 않고, 사용자들을 grouping

2. Capabilities – 사용자 별로, 모든 파일에 대한 read, write 등등 가능성 여부를 리스트에 저장 

- 파일이 하나 새로 생길 때 마다, 모든 사용자에게 작업 -> 복잡도가 높아 사용하지 않는 방식 

 

* Access list in Unix/Linux

- 접근 모드 3가지 – read, write, execute

- 유저 class 3가지 – owner access -> file을 만든 자기 자신 / group access -> 자신이 속한 그룹의 사람들 / public access – 모든 사람들

 

owner access (RWX 111)  /  group access (RWX 110)  /  public access (RWX 001)  -> 파일 하나 당 9bit 필요

 

ex1) chmod 761 game // 7 – owner, 6 – group, 1 – public (8진수, 0~7까지 최대 7 표현)

== game이란 파일의 permission을 761로 바꾼다는 의미 

 

ex2) -rw-rw-r-- (owner, group, public)

    drwx------ (나만 read, write, execute 가능하고, 아무도 X)

 

 

 

 

 

14. File System Implementation

15. File System Internals 

- 개발자 입장에서의 file system 

 

1) in-memory structure

- OS가 수행되는 동안, 어떻게 file을 application에게 제공하는가? 

 

2) On-disk structure 

- 이게 더 중요! 컴퓨터 종료 후에도 유지되는 파일 시스템

2-1) Boot control block – 부팅 시 필요한 것 – Boot block (UFS) or Boot Sector (NTFS – 윈도우) 

2-2) Volume control block – file system에 대한 정보 저장 – super block (UFS) / master file table (NTFS)

2-3) Directory structure 

2-4) File control block (FCB) – attribute 관리 – i-nodes (UFS), in master file table (NTFS)

 

* in-memory structure 

- 전원이 켜져, application process가 OS에게 system call로 요청

- process 별 open file table 갖는다. (0 – standard input / 1 – standard output / 2 - standard error) 3번부터 file descripter -> process가 file open 할 때 마다, table의 entry가 증가한다. 

- file table – 커널이 관리하는, system wide open file table s

- memory에 존재하는 data structure 

–> Buffer cache (directory cache – 디렉토리 저장 + buffer cache – file data 저장) 

-> HDD 파일 중 자주 사용하는 파일을 main memory에 올려 사용 

 

Virtual File System (VFS) – 공통인 부분을 VFS로 관리

 

1) CD-ROM – read에 최적화 된 CD ROM의 파일 시스템 – ISO 9660 표준 – OS와 무관하게 정의됨

2) UNIX – UFS (유닉스 파일 시스템), FFS (fast file system) 

3) Windows – FAT – file allocation table, FAT32(USB), NTFS (현재 모든 윈도우 OS의 파일 시스템) 

4) Linux – ext2, 3, 4 – extended file system // 기존 운영체제와 호환을 위해 130개의 파일 시스템 존재 

+) ZFS – embedded system – flash memory file system / 분산 환경에서의 파일 시스템 

 

* On-Disk Structure – HDD or SSD 거의 변하지 X

- BIOS – MBR // UEFI (새로운 표준) – GPT // OS가 부팅될 수 있는 partition – active partition 

1) boot block – 부팅과 관련된 정보 저장 – 커널이 저장됨 

2) super block – 파일 시스템과 관련된 메타 데이터 저장 (총 파일 수 – 파일 시스템의 크기, 타입 등등) 

3) bitmaps – free space management 

4) i-nodes – file 하나하나에 대한 metadata (FCB – file control block) / index 의미

5) 이 뒤는 모두 data – 제일 첫번째 데이터가 root directory data // 이후 파일과 디렉토리 데이터들 저장 

 

* 윈도우의 format / UNIX – mkfs (make file system) -> 위와 같은 파일 시스템을 하나 만듦 

 

- Disk block – HDD의 cylinder, surface, track, sector 영역의 넘버 표현 -> disk block 넘버로 mapping 

-> OS에서는 다음과 같이 disk block 단위로 관리한다. (크기는 4KB)

- 이러한 매핑 관리는 disk controller가 한다. 운영체제는 0번부터 1M – 1 개의 디스크 block을 관리한다. 

- 4GB HDD가 있을 때, 4KB의 디스크 block이 1M개 (2^20개) 생긴다. 

 

* Free Space Management – bitmap block // 사용 중 1 or not 0 -> block 당 1 bit로 표현 가능 

- block size – 4KB (2^12 byte), disk size – 1GB (2^30 byte) -> 2^18 bit 개 (byte로 변환 시, 2^15 byte, 32KB)

-> 이러한 수의 disk block들을 어떻게 관리할 것?

 

- Linked list (free list) – HDD는 flash memory 기반의 SSD보다 더 깨지기 쉽다 (충격에 약함) 

-> 이 방법은 잘 사용하지 X / bit map 방식 활용 // 중간에 고장 나면, 그 뒤는 싹 날라감 

- ZFS – 빅데이터 처리를 위한 분산 파일 시스템 / space map과 같은 다른 자료 구조를 사용한다.

 

* File control block (FCB) – i-nodes – 파일이 하나 생성될 때 마다 아래의 메타 데이터를 저장 -> FCB

- 윈도우 OS의 경우 master file table // UNIX – i-nodes (UFS – Unix file system)

 

- directory implementation – 디렉토리는 어떤 데이터 저장? 1) file 이름 2) file의 metadata (FCB)

1) in the directory table – 파일 이름과 메타 데이터를 싹 다 저장하는 방식

2) in the separate data structure (i-nodes) // UNIX / LINUX에서 사용하는 방식 

- 파일 이름과, FCB(i-nodes)의 위치를 저장한다. -> 따라가면 메타 데이터가 나오는 것 

3) a hybrid approach – 윈도우 – 파일 이름과 + FCB 위치와 + 더불어 중요 정보까지 중복으로 저장 

Ex) 윈도우 탐색기에서 파일에 대한 간략한 정보를 띄울 때 – FCB와 겹치는 내용을 작게 저장하고 있음 

 

* Allocation methods – file data가 어떻게 관리되는가? 

- 가장 중요한 것은, 이 file data가 어디에 저장되었는 지 아는 것 

Ex) file size 40KB -> 4KB 크기의 disk block 10개가 필요한 것 -> 이게 어디에 어떻게 저장되는가? 

-> 4MB, MP3의 경우 1K 개가 필요하다. 

-> contiguous / linked / indexed allocation 방식이 존재한다. 

 

1) Contiguous allocation / 시작 위치와 길이만 있으면 찾을 수 있다 – 쉽고, simple 하다는 장점 

- file 이름 + FCB (file control block에 시작 위치와 길이 저장) 

- file에 data가 추가될 경우, 파일이 더 커지면 수정이 어려움 -> 연속으로 block들을 저장하다 보니, 더 큰 빈공간으로 옮겨야 함 – 파일이 생성되고, 사라지는 환경에서는 사용하기 어렵다. // dynamic allocation 단점

Ex) 읽기 전용 CD-ROM에 사용 

 

2) Linked Allocation / 연속적 배치를 불연속적으로 배치 

- block은 자신의 데이터와 함께 다음 block의 위치를 가리키는 포인터를 저장한다.

- 이 또한 파일 이름과 시작 block 위치만 저장하면 되어, 표기하기 쉽다는 장점이 있다. 

+ contiguous와 달리, dynamic한 파일에도 적용 가능한 장점

- 단점 – sequential하게 저장된 실행 파일은 OK -> data file, random access -> 앞부터 다 읽어야 하는 문제점 

+ 중간에 공간이 하나 날라가면 못쓴다. 신뢰도 측면에서 포인터가 손상될 경우, 신뢰도 측면에서 문제 

 

+ File Allocation Table (FAT)

- 이전 방식에서 block의 pointer 들을 모두 모아서, 별도의 테이블로 만들어 관리 // 2~3 중으로 관리 

- 작아서 메인 메모리에 테이블을 올리고 cache // linked allocation의 random access 문제도 해결 가능

- 하지만 여전히 신뢰도 문제 존재

 

+ FAT16 (DOS 시절, disk block을 표현하는 크기가 16 bit) 

vs FAT32 (32 bit로 늘린 것, USB에서 사용, 윈도우는 여기에서 NTFS로 넘어간 것) 

 

3) Indexed Allocation – i-nodes -> index node 

- 별도의 disk block에 쭉 저장 / 이 파일이 어디 있는지 / 날라가더라도 이 파일 하나만 날아감 

- random access 용이 // reliability 장점 

-> 영화처럼 큰 애들은 어떻게 저장? 

 

* Indexed allocation – combined scheme – UFS (block은 4KB, 주소는 32 bit – 4Byte)

1) direct blocks – data 위치가 어디에 있는지 직접 쓰는 것 / 12개, 즉 48KB까지 커버 가능) 

2) single indirect – 32bit integer – 4byte -> 4KB disk block 하나에, 1K개의 block address 표현 가능 (1024개)

-> 따라서 1K개 * 4KB (4MB) 커버 가능 

3) double indirect – single indirect 구조가 1K 개 -> 4B * 1K * 1K = 4GB

4) triple indirect – 4B * 1K * 1K * 1K = 4TB

 

* Unix file system (UFS) 구조 – 아주 많은 disk block을 읽어야 실행 가능 

i-node(0): root directory -> root data의 번지 수를 찾아 간다. -> directory 에서 /bin 을 찾아 읽는다 -> /bin의 i-node -> 해당 디렉토리의 data를 저장하는 directory에서 내가 읽어야 할 파일 a.out의 위치를 찾는다 -> a.out의 i-node -> 여기에 single direct block 12개 + double indirect block 등등 

- ls 명령어 -> 처음에는 HDD에서 읽음 -> 이후 메인 메모리에 cache -> 성능 향상 

 

* Block size performance vs efficiency 

- block size 크기가 클수록, HDD는 한번 움직여 많이 읽어야 하니까 성능이 증가한다. 

- 하지만 성능 측면에서, block size가 증가하면 internal fragmentation 증가 -> utilization 감소

- 성능과 utilization이 trade off가 있다 -> 현재 적절한 4KB로 disk block size가 정해짐 

+ SSD = 전기적 동작으로, 많이 읽는 것과 무관하다. 따라서 utilization만 고려하면 된다. 

 

* Read ahead – sequential하게 읽을 경우, 파일 시스템이 프로세스가 필요할 disk block들을 미리 읽어, cache

 

* Buffer Cache – HDD에서 자주 사용하는 것들을 main memory에 cache (SSD도 캐시 효과적) 

- 4MB만 캐시 하더라도, 매우 효과적이다. 

- Synchronous write – 변경 사항을 캐시에 쓰고, HDD에도 동시에 쓰면 – 성능 향상 X (write through)

- Asynchronous write – 모두 모아 한번에 HDD에 쓰면 성능 향상 O (Write behind, write back)

-> 하지만 unreliable – main memory만 바뀌고, HDD는 반영되지 않았는데, 정전 or 비정상적인 종료 발생 등 

 

* Reliability – 복구하는 것 – utility 프로그램이 파일 시스템의 일관성을 체크하는 것 

UNIX – fsck (file system check) // Window – scandisk -> 비정상적인 종료를 복구 

 

* Journaling file system (Log Structured File Systems) 

- Linux ext3 이후 // 윈도우 NTFS 등 – 현재 OS들이 사용하는 방식 

- 파일 변경에 대한 요약 정보만 journal이라는 곳에 저장 -> 이후 HDD에 쓰고, 저널은 삭제 

- 부팅 시 저널이 비어야 정상 / 저널이 차 있다면 -> HDD에는 쓰지 않은 상태인 것 -> 비정상적인 상황을 감지할 수 있다. 

 

* remote file system 

-> 네트워크로 연결된 컴퓨터의 파일 시스템을 마치 내 파일 시스템처럼 사용하는 것 

- VFS (virtual file system) – 공통인 것에 대한 interface 

- NFS (network file system) – 마운트하여 내 컴퓨터에서 로컬 파일 시스템처럼 사용 가능 

+ RPC – 다른 컴퓨터의 코드를 실행시키기 위한 C/Cpp 기술 의미 (remote procedure call)

 

 

 

 

 

16. Security 

- Security requirement triad (CIA triad)

1. Confidentiality – 기밀성, 암호화 / 2. Integrity – 무결성, 변조되지 않음 / 3. Availability – 가용성 (서비스 죽음X)

 

* 용어 정리 

- Vulnerability – 취약점 / Threat – 위협 / Attack – 공격 / Adversary – 적, attacker / Countermeasure – 대응책

- CIA + Authentication – 인증 / Access control – 접근 권한 / Nonrepudiation – 부인 방지 

 

* Cracker’s basic step 

1. gather information 2. Use port scanner 3. Get a login account – authentication을 통해 적법한 사용자가 됨 
4. Get root privilege – 루트 권한을 얻는 것은 어렵지 않다 5. Backdoor – 언제든지 접근할 수 있도록 백도어 

 

* Physical security 

1) Hardware security – 시스템, 하드웨어 사용에 대한 보안 – smart card / bio-metric access control 

2) BIOS security – 부팅 시 firmware 단계에서 비밀번호 – 아무도 이렇게 사용 X

3) Session security – 회사에서 자리 비울 때, screen saver 

 

* Account security 

1) Authentication – 인증 – password – CHAP (Challenge Handshake Authentication protocol) 
- 복잡한 비밀번호로 설정하여, brute force로 깰 수 없도록 최근에 사용

2) Authorization – 권한 – access control – Access Control List (ACLs) vs Capabilities (사용자 별) 

 

* File System Security – Unix, Linux 

– setuid, setgid – 보안에 취약한 프로그램으로 특별히 잘 관리해야 함 

- search path를 이용한 공격 등 다양한 공격이 있었다 -> 이에 대한 다양한 countermeasures (대응책) 존재 

 

* Network Security - File System Security보다 더 중요

1) application layer – https를 사용해라

2) transport layer – SSL (Secure socket layer) 

3) Network layer – IPSec Protocol – IPv6은 필수, 4는 optional – IPv4 세상 -> 제대로 사용되고 있지 X

 

- TCP Wrapper – 특정 IP/Port 에서만 들어올 수 있다. 다른 경로를 deny 가능 

- Firewall (방화벽) – 별도의 장비를 활용하여 network security – public internet에서 경희대로 오는 Packet 중 이상한 packet은 drop 거르고, 적합한 packet만 들여다 보낸다. 

+ DMZ – 외부 사용자에게 서비스 제공 시, 내부 인트라넷은 접근 불가능, DMZ를 통해 서비스 제공

 

- detection – 침입 감지 vs prevention 원천 봉쇄 

- IDS – Intrusion Detection System – 서버 및 방화벽에 수행 / 인공지능, 딥러닝 

- IPS – Intrusion Prevention System – WIPS – 특정 지역 LTE 끊김 

 

* Security Treats 

- Physical threats – 자연 재해 / Logical threats – 컴퓨터 소프트웨어 버그, 취약점 // 사라질 수 X 

- Operational threats – 관리자 실수 / Denial of service – 컴퓨터의 서비스 제공을 막는 것 (DOS) 

 

* Attacks 

- Virus – 혼자서 실행 X, 다른 프로그램에 기생 / Worm – 독립적인 프로그램으로 번식 가능 -> 둘 다 악성코드

- Trojan horses 트로이 목마 – 재미있는 다운로드 – 멀웨어 설치 / Logic bomb – 개발자 해고 시 시스템 날라감 

- Trap door – backdoor 몰래 들어갈 경로 뚫기 / Dictionary attack – brute force로 password 깨기

- Logic spoofing – 피싱 

 

- Malware – 악성코드 / Spyware – 중요 정보 빼가기 / Ransomware – 중요 문서 암호화, 돈 요구

- Keystroke logger – 사용자의 모든 입력 전달 / Code injection – 멀웨어를 시스템에 주입

- Dos / DDos – distributed denial of system – 분산적으로 dos 공격 

 

* the Morris Internet Worm – 세계 최초로 UNIX 멀웨어 개발 – 스스로 복제하는 worm 프로그램

- finger의 bug를 통해 worm 주입 (code injection) 

-> 현재 이 system에 로그인한 사용자들에 대한 정보를 보여주는 서비스 

 

* Buffer overflow – finger 서비스가 버퍼 오버플로우 취약점이 있었다. 

- 사용자가 입력한 커맨드가 argv[1]에 들어감 -> B라는 array에 입력을 copy하고, 화면에 출력

-> 1024보다 더 많은 바이트가 들어가면? 

 

* Code injection 과정 

- main 함수부터 stack에 쌓임 -> A라는 함수 호출 시, A의 local 변수들을 위한 공간도 스택에 쌓임

- Buffer B 공간도 (1024 byte) 스택에 잡힘 // Code segment의 어딘가로 return 될 return address 공간

- 사용자가 1024 이상의 입력을 넣으면 buffer가 더 위로 write 됨 -> return address 영역 침범

-> 잘 계산해서, 내가 입력한 곳으로 jump -> code 영역으로 return이 아니라 자기 자신으로 돌아가도록

-> hello world 자리에 악성 코드 실행 프로그램을, 즉 코드를 쭉 쓴 것 

* 그냥 돌아가는 코드가 아닌, 취약점이 없도록 Secure coding을 해야 한다!

 

* IP Spoofing – IP address를 속이는 것 

- cracker는 HOST B에 접속하고 싶으나, 바로 접속할 수 없음 

- HOST A는, cracker가 알고 있으며, HOST B에 접속 가능 

- Denial of Service attack으로 A를 무력화 -> A인 것 처럼 cracker가 B로 패킷을 보냄 

- A는 무력화되어 ack를 못 날림 -> cracker의 IP address도 B에 접속 가능하도록 조작 

 

* Denial of service attack – 서비스가 불가능하도록 막음 

1) internal attack – 무한히 Process 생성 – system 다운, 마비시키기 / fork, malloc으로 메모리를 엄청 많이 씀

2) external attack – packet을 보내는 것 – 방화벽으로 discard (IDS) 가능

-> DDos인 경우, 방화벽에서 감지할 수 없음. //

 

* Basic concept of Cryptography 

1. Shared Key cryptography – AES 알고리즘

- 동일한 shared key를 서로 나눠 갖고, 암호화 및 복호화를 한다. (키를 가진 사람만 원문을 볼 수 있다.) 

- 어떻게 shared key를 공유할 것인가? 가 이슈

- 상대적으로 오버헤드가 작아, 긴 장문의 text를 암호화할 때 사용한다. 

 

2. Public Key cryptography – RSA 알고리즘 

- 누구나 다 알 수 있는 public key와 자기 자신만 아는 private key

2-1) Confidentiality – A가 B의 공개키로 암호화 – B만 복호화 가능 (기밀성)

2-2) Authentication – A가 자신의 private key로 암호화 – 누구나 복호화 가능 – A가 만든 문서임을 증명 

- AES보다 RSA가 엄청나게 많은 계산량 – 오버헤드 크고, 시간도 오래 걸림 / 비교적 작은 data 암호화에 사용

 

* Network 암호화 (TLS/SSL) – 웹 브라우저(클라이언트)와 웹 서버 사이의 암호화

1. 키 교환

- 웹 브라우저가 AES 키 생성 – 웹 서버의 공개 키로 암호화 – 인터넷으로 패킷 전달 – 웹 서버의 private key로 복호화하여, 서로의 키를 공유한다. (오버헤드가 큰 RSA 방식이지만, 작은 key 값을 주고 받을 때 사용 O)

2. 데이터 교환 – 대용량, AES 방식

- 앞서 공개키 방식으로 shared 된 Key를 공유하여, 암호화, 복호화를 통해 데이터를 주고 받는다. 

 

* Digital signature – 디지털 서명 

- for authentication & integrity (변조되지 않음!) // not confidentiality (기밀성과 무관)

- ex) 공인 인증서에 private key가 저장됨 

- 웹 브라우저가 hash를 통해 data 양을 줄이고, 이를 자신의 private key로 암호화 한 뒤, 원문과 함께 보냄

- 웹 서버는 동일한 hash 알고리즘으로 계산한 값을, 브라우저 공개키로 복호화 한 값과 비교 

-> 서로 같으면 변조되지 않음 확인, 서로 다르면 원문이 변조됨을 알 수 있음 

 

*VPN - Virtual Private Network 

- 설캠 국캠 사이의 전용선 – 비용이 비싸다 – 중간에 public internet을 타야 함 
–> 이를 software로 virtual하게 private 암호화

- 암호화 한 트래픽은 중간에 볼 수 없다 – 복호화 하여 원문을 전달받을 수 있음