Operating Systems: Three Easy Pieces의 chapter 35~40 / 최종무교수님 운영체제(SW) 강의노트 참고
Chap 35. A Dialogue on Persistence Chap 36. I/O Devices Chap 37. Hard Disk Drives Chap 39. Interlude: Files and Directories ( APIs for file, directory and file system ) Chap 40. File System Implementation ( Layout & Interface ) 자료들 출처 및 참고 : https://pages.cs.wisc.edu/~remzi/OSTEP/
[ Chap 36. I/O Devices ]
🍑 System Architecture
: CPU와 Memory, device들의 교류방식, 구조
(1) Hierarchical structure
Memory bus( system bus ) : CPU와 Memory를 연결 ⇒ 빠름, 고가, 짧음
I/O bus : SCSI, SATA, USB : CPU와 주변장치(peripheral)를 연결 ⇒ 느림, 저렴, 김
graphic cards는 별도의 고속 연결버스를 이용하여 연결됨
(2) Modern system
Special interconnect ( Memory interconnect ) : 다수의 CPU와 다수의 메모리가 상호연결 ( 근거리 작동방식에 따라 NUMA방식, UMA방식 )
Graphic interconnect
DMI : I/O chip과 CPU연결( 인텔표준 )
specialized chips : 서로다른 디바이스의 인터페이스를 관리, 디바이스를 표준화하여 관리
🍑 Canonical Device & Canonical Protocol
(1) Device의 구성
interface parts( 명령전달, 상태파악 기능 ) : 3개의 register( command, data, status )
OS-specific layer : OS과 연결하여 디바이스를 file처럼 다룸 → generic 시스템콜 지원( open, read, write, close … )
[ Chap 37. Hard Disk Drives ]
🍑 The interface & Basic Geometry fo HDD
기본단위 : sector( 512byte ) / sectors → track → platter( 양면, two surface ) → disk
cyliner : 각 트랙에서 같은 트랙의 집합 → seek time이 필요하지 않음( FS 중요개념 )
Head : 데이터를 감지( 섹터단위, 섹터내부 자성성질을 이용 ), 각 표면(surface)당 하나씩 존재하며 arm으로 연결
데이터 접근(data access) = seek time + rotation latency + transfer time
seek time : 헤더가 움직이는 시간 → 트랙을 찾음, 디스크 매뉴얼에 기술됨
rotation latency : 디스크가 회전하는 시간 → 섹터를 찾음
RPM(rotation per minute) → 60000(60*1000)으로 나누면 ms당 도는 바퀴계산가능 → 1바퀴소요 ms구하기
LBA (Logical Block Address for disk) : 디스크에서 논리적 블록단위(disk block)로 나누고 번호식별하는 방식 sector단위가 아닌 multi-sector( disk block : 4/8KB )단위( 디스크가 빨라지며 큰 단위 접근 )
🍑 I/O Time
(1) 성능지표(metrix)
I/O time( latency ) = seek time + rotation latency + transfer time
rotation time : RPM을 ms단위로 환산(1/60000) → 1바퀴당 소요된 ms
transfer time : Max transfer(MB/s)를 이용하여 주어진 데이터만큼 읽는데 걸리는 시간 비례식으로 구하기
I/O rate( bandwidth ) = transfer size / ( I/O time ) : 시간당 데이터 전송량( 단위 : MB/s = KB/ms )
(2) Workload의 특성
Random(임의적)인 작업 : 작은 크기, 분산적인 위치 → 임의위치에서 읽음
Sequential(순차적)인 작 : 큰 크기, 연속적인 위치 → 순차적으로 읽음
⇒ sequential한 작업이 random한 작업보다 빠르게 수행된다. 개발자는 프로그래밍시 sequential한 프로그램을 짤것!!
🍑 Disk Scheduling
: 한정된 자원(disk)에서 I/O요청들의 순서를 결정하는 정책
(1) FCFS(First Come First Serve) : 가장 간단하나 long seek time이 소요될 가능성 (2) SSTF(Shortest Seek Time First) : 현위치에서 seektime이 적은 요청 처리( 가까운 트랙번호) ⇒ seek time이 훨씬 줄어드나 형평성(unfair) 문제 : 가장자리(boundary)는 우선순위가 항상낮음 (3) SCAN(Elevator) : 한쪽으로 이동하며 요청을 모두 서비스 → 이후 반대로 이동하며 해당방향의 요청을 모두 서비스 ⇒ 성능이 향상되나 여전이 형평성(unfair)이 완벽하지 않음 (4) C-SCAN : SCAN방식 + 돌아올때는 서비스 하지 않음 ⇒ 완벽한 fairness (5) SPTF(Shortest Positioning Time First) : seek time + rotation latency도 함께 고려하여 가까운 것부터 수행 ( N seek + M/N rotation 모두 고려하여 합이 적은 것부터 서비스 ) (6) Anticipatory disk scheduling : 다음요청을 예상하여 대기하여 처리하고 이동**( merge requests )**
[ Chap 39. Files and Directories ]
🍑 Files and Directories
: Storage(HDD, SSD.. )장치는 비휘발성(Non-volatility)의 특성을 통해 영속성제공한다. 그러나 무결성, 공간효율성, 일관성, 고장복구, 접근제어, 보안에 대한 다양한 이슈가 제기됨 ⇒ File system 존재이유, 목적
(1) File : 연속적인 문자의 배열(byte)로, 영속적으로 저장되는 데이터 다양한 고유구조(data structure) 가지게된다. (txt, c, exe, o ..) 그러나 OS상에서는 모두 문자열로 처리된다. 절대경로(absolute path : /(root)부터 시작) & 상대경로(relative path : 현위치부터 시작) OS내의 자료구조(low-level name) inode로 관리 시스템의 다양한 개체들 파일로 관리가능( device, pipe, socket, and even process )
(2) Directory : 계층구조(file hierarchy)를 형성하는 특수한 형태의 파일 하위의 파일이름(filename) + inode 쌍(pair)으로 구성된 데이터를 가짐 root directory(/) ⇒ home directory ⇒ working directory홈 디렉토리 : 로그인후 처음으로 들어가는 디렉토리 워킹 디렉토리 : 현재 작업중인 디렉토리 루트 디렉토리 : 최상위 디렉토리
🍑 File System Interfaces
API = System calls( 유저가 이용가능 ) + internals( 내부적으로 호출되어 실행 ) ※ strace 툴 : 해당명령이 어떤 system call을 사용했는지 trace확인 가능
같은 파일을 2번 오픈 각각의 fd가 생성 in open file table entry( 별도의 offset ) → 하나의 inode를 포인트
위와는 반대대는 처리 ( 동일한 offset을 공유하는법 )
File table entry(fd)의 공유 ( file table entry의 refcnt=2 )
① fork case : 프로세스의 PCB가 복사 = fd테이블이 복사, 같은 fd값 공유
② duplicate : 다른 fd값을 복사해서 저장
(5) 동기화 작업 API : fsync(fd)
지연쓰기 실행된 dirty data를 즉시 disk에 반영 / 성공시0, 실패시-1 반환
지연쓰기(dirty write)란? DRAM과 Disk의 큰 속도차이로 인해 즉시 디스크 기록시 성능저하 발생 DRAM의 buffer(page cache)에 쓰기(dirty data) ⇒ 후에 주기적으로 디스크에 기록 추가적으로 write grouping(그룹화) & write reordering(순서조정) 등으로 성능강화
wirte()은 기본적으로 지연쓰기를 수행
지연쓰기의 문제점 : Asynchronous(비동기화) 작업으로 durability(신뢰성, 영속성) 상 약점, 휘발가능성 사용자가 제어를 원하는 시점에서 명확한 동기화가 필요!
(6) Metadata 조회 API : stat( filename, struct stat ); / fstat( fd, struct stat );
다양한 Metadata - indoe : 개별 file들 관련 메타데이터, superblock : 전체 file system 관련 메타데이터
stat명령이 반환하는 구조체의 형태
(7) Directory를 다루는 API
mkdir( name, permission ) = mkdir name
readdir(dp) : 파일+inode로 구성된 dir을 읽는다. command line상의 ls-l 명령 = readdir() + stat()
rmdir( name )
(8) Link API : 존재하는 파일에 다른 이름을 생성하는 작업
HardLink : 동일한 inode를 서로다른 이름으로 공유 ( connect name with an inode )
command line : ln 기존파일명 새로운파일명
API : link( oldname, newname ) +) rm 파일 명령시 이와 반대되는 unlink가 호출
Link count : stat file 확인시 Links갯수 확인가능, 0일 경우 데이터까지 자동으로 삭제처리
Symbol Link(Soft Link) : 서로다른 inode를 가짐, 그러나 데이터는 공유
⇒ imbalance tree형태 : 포인터를 사용하여 큰 파일을 저장가능 & 작은파일은 빠르게 직접접근( 성능 )
실제수행방식 : inode에서 location정보 참조 → 실제 datablock에 접근
(1) inode찾기 = root directory 찾기( 파일의 inode정보를 담고 있음 ) Directory entry( file name + i_number 의 쌍 ) 저장 ( 파일의 inode정보 )(*0부터 시작함 주의) i_number / ( inodes per block=16) = 몫은 iblock순번 + 나머지는 블럭내 인덱스
(2) datablock찾기 = inode내의 디스크포인터(offset정보) + location정보를 활용 offset(start=0) disk block size(4096) = 몫은 dblock순번(location값중) + 나머지는 블럭내 인덱스
[ 7KB의 hello.c 70KB의 a.out가 할당된 모습 ]
datablock[8]에는 /(root directory)가 저장
datablock[9~10]에는 hello.c가 direct로 저장
datablock[11~22]에는 a.out이 direct로 저장( 12개 )
datablock[23]에는 a.out이 indirect(pointer)로 저장 -> 이는 datablock[24~29]를 저장
🍑 Directory Organization / Free Space Mgmt
Directory
사용자 관점 : 연관된 파일들의 집합( 윈도우의 폴더 )
시스템 관점 : 파일명 + i_number 쌍의 집합
빠른 검색을 위해 byte단위의 name length, record length를 추가하여 관리
Free Space의 관리
Bitmap : block, inode의 공간당 하나의 비트로 그것이 사용중인지 여부를 표현 이후 값이 0인곳을 찾아 할당( 공간효율성 증가 )
Pre-allocation(선할당) : 배치방식으로 할당 = 요청보다 크게 할당 추후 데이터가 증가할경우 연속공간사용이 가능( contiguous ) & seektime줄임( overhead 감소 )
🍑 Access Paths: Reading and Writing ( 예제 )
[ CASE1 ] Reading a file(/foo/bar, 12KB) from disk
(1) open(bar) : bar의 inode를 읽어 정보를 확인하고 정상수행시fd를 리턴 : root inode read → root data read → foo inode read → foo data read → bar inode read ⇒ directory tree traverse 수행하여 총 5회의 디스크블럭 I/O발생
(2) read(bar) : bar의 데이터 블록을 읽음( 4KB*3회 ) & inode에 최근 접근시간(last accecss time)기록 in inode : bar inode read → bar data[1] read → bar inode write bar inode read → bar data[2] read → bar inode write bar inode read → bar data[0] read → bar inode write ⇒ 총 3*3회의 디스크블럭 I/O발생
(3) close(bar) : 디스크 작업X, 메모리상에서 처리
[ CASE2 ] Writing a file(/foo/bar, 12KB)
(1) create(bar) : 기존에 존재하는 foo경로에 도달 → 가용 inode블럭 할당(bitmap) → 상위 foo 디렉토리에 경로쌍추가(삽입), 생성된 bar inode에 정보작성 → 상위 foo 디렉토리에 최근접근시간 기록 : root inode read → root data read → foo inode read → foo data read → inode bitmap read → inode bitmap write → foo data wirte → bar inode read → bar inode write → foo inode write ⇒ 총 10회의 디스크블럭 I/O발생
(2) write() : bar의 정보읽음 → 가용 data블럭할당(bitmap) → 데이터 작성( 4KB씩 총 12회 ), inode에 최근접근시간 기록 : read bar inode → data bitmap read → data bitmap write → write bar data[0] → write bar inode … ⇒ 총 5*12회의 디스크블럭 I/O발생
🍑 Caching and Buffering ( 예제 )
간단한 open, read, write 작업이지만 파일시스템 내부적으로는 수많은 디스크 I/O가 발생한다는 것을 볼 수 있었다. 잦은 I/O작업 문제점은 디스크와 메모리간 속도차이로 인한 성능저하(overhead) ⇒ I/O의 횟수를 줄이는 것이 요구됨!!
(방법1) Caching : 디스크 데이터 일부(recently used file’s inodes and data)를 메모리에 올려두고 접근 ⇒ 시간적 지역성 활용, 한정된 공간을 LRU로 교체하며 이용
각 영역( bitmap, data )에서 처음 read만 수행하여 캐시에 저장
(방법2) Write buffering (Delayed write) : 몇번의 쓰기 작업을 한번에 수행, 수정여부만 기록
