12장. 파일 시스템 구현

12.1 파일 시스템 구조 파일 구조 물리적 보조기억 장치에 논리적 파일 시스템을 사상시키기 위한 알고리즘 필요 논리적 저장 단위 관련 정보의 집합 물리적 보조기억 장치에 논리적 파일 시스템을 사상시키기 위한 알고리즘 필요 계층적 구조 사용 파일 제어 블록 파일에 대한 정보를 구성하는 저장 구조

디스트의 물리적 블록을 읽거나 쓰기 위해 적절한 장치 구동기 명령 사용 계층적 파일 시스템 파일의 논리 블록 주소를 물리 주소로 변환 디렉토리 구조 사용 보호/보안 문제 디스트의 물리적 블록을 읽거나 쓰기 위해 적절한 장치 구동기 명령 사용 수행 동작이 무엇인지 동작하는 장치의 위치를 제어기에 알려줌

12.2 파일 시스템 구현 디스크 구조 부트 제어 블록 파티션 제어 블록 디렉토리 구조 파일 제어 블록(FCB) 시스템 부팅에 필요한 정보 UFS – 부트 블록, NTFS – 파티션 부트 섹터 파티션 제어 블록 파티션 블록 수, 크기, 자유 블록 수와 포인터 등의 파티션 정보 UFS – 수퍼 블록, NTFS – 마스터 파일 테이블 디렉토리 구조 파일 제어 블록(FCB) 파일 허가, 소유, 크기 등 자세한 파일 정보 UFS – inode, NTFS – 마스터 파일 테이블 안에 저장

파일 제어 블록

메모리 안의 파일 시스템 구조

가상 파일 시스템 여러 종류의 파일 시스템에 대하여 같은 시스템 호출 인터페이스 (API) 사용 연산과 구현의 분리 유일선 보장(vnode)

12.3 디렉토리 구현 선형 리스트 해시 테이블 파일 이름을 가진 선형 리스트 (데이터 블록에 대한 포인터 포함). 프로그램 용이 실행하는 데 시간이 걸림 해시 테이블 해시 자료 구조를 가진 선형 리스트. 디렉토리 탐색 시간 감소 충돌(collisions) 발생 가능 두 개의 파일 이름이 같은 위치로 해시하는 상황 고정 크기

12.4.1 연속 할당 각 파일들은 디스크의 선형적으로 연속된 기억 공간을 할당 간단함 랜덤 접근 빈 공간의 낭비 블록들의 시작 주소와 개수만 필요 랜덤 접근 빈 공간의 낭비 외부 단편화 파일에 필요한 공간의 확장이 어렵다

연속 할당

연속 할당 많은 새로운 파일 시스템(예, Veritas File System) 이 수정된 연속 할당 방식 사용. Extent-기반 파일 시스템은 디스크 블록을 extents 에 할당. Extent - 연속된 디스크 블록들. 파일 할당을 위해 할당. 파일은 하나 이상의 extent 로 구성.

11.4.2 연결 할당 각 파일은 디스크 블록의 연결 리스트 간단함 – 시작 주소만 필요 순차 접근 파일에만 효과적 포인터들을 위한 공간 필요 신뢰성 문제

연결 할당

연결 할당 파일 할당 테이블 (FAT) MS-DOS, OS/2 에서 사용 각 디스크 블록 내의 블록 번호와 관련 포인터의 항목 테이블을 가지고 블록 번호에 의해 참조

FAT 를 사용한 연결 할당

11.4.3 색인 할당 색인 블록에 파일 포인터들을 관리 랜덤 접근 - 외부 단편화 없이 동적 접근 가능 색인의 I 번째 항목이 파일의 I번째 블록으로 연결 랜덤 접근 - 외부 단편화 없이 동적 접근 가능 색인 블록에 대한 메모리 낭비 해결 방법 연결 기법 - 색인 블록들을 연결 다중 단계 색인 - 여러 단계의 직/간접 색인 블록 사용 결합 기법 – 직접/단일 간접/이중 간접/삼중 간접 블록 등 다양한 색인 블록 사용, UNIX 등에서 사용

색인 할당

결합 기법 : UNIX (블록 당 4KB)

12.5 빈 공간 관리 빈 공간 관리 비어 있는 모드 디스크 블록들을 등록 비트 벡터 (bit vector) 연결 리스트 블록이 비어 있으면 0, 할당되어 있으면 1 빈 블록이 2,3,4,5,8,10,11,12,13,17,18,25,26,27  1100001101000011100111111000 연결 리스트 모든 빈 공간을 포인터로 연결 다음 빈 공간 탐색 또는 새 빈 공간 추가 시 오버헤드 그룹핑 첫번째 빈 공간 내에 n 개의 빈 공간의 주소 저장 계수 첫번째 빈 공간 주소와 연속된 빈 공간들의 계수 보존

디스크 상에 연결된 빈 공간 리스트

12.6 효율과 성능 효율이 의존하는 것 성능 디스크 할당과 디렉토리 알고리즘 파일의 디렉토리 항목에 유지되는 데이터 종류 디스크 캐시 – 자주 사용되는 블록을 위한 주 메모리의 분리된 부분 free-behind 와 read-ahead – 순차 접근을 최적화하는 기법들 메모리의 일부분을 가상 디스크 또는 RAM 디스크 로 전용함으로써 PC 성능 개선

여러 디스크 캐싱 지점들

페이지 캐시 Memory-mapped I/O 는 페이지 캐시 사용 파일 시스템을 통한 I/O 루틴은 버퍼 (디스크) 캐시 사용 페이지 캐시 (page cache) 는 가상 메모리 기법을 사용하여 디스크 블록 대신 페이지를 캐시 파일 시스템을 통한 I/O 루틴은 버퍼 (디스크) 캐시 사용 통합 버퍼 캐시가 없는 경우 이중 캐싱 발생 메모리 낭비 상당한 CPU 와 I/O 사이클 소비 버퍼(디스크)캐시 : 0번 블록가틍ㄴ 디스크의 접근 속도가 빠른 곳에 페이지 캐시를 만듬

통합 버퍼 캐시 없는 I/O

통합 버퍼 캐시 memory-mapped pages 와 보통 파일 시스템 I/O 는 같은 페이지 캐시 사용

12.7 복구 일관성 점검 (Consistency checking) 백업과 복구 디렉토리 구조의 데이터와 디스크 상의 데이터 블록간 비교한 후, 비일관성 수정. 백업과 복구 디스크로부터 다른 저장 장치 (플로피 디스크, 자기 테이프) 로 데이터를 주기적으로 백업하는 시스템 프로그램 사용 백업으로부터 데이터를 복구함으로써 잃어버린 파일 또는 디스크 복구

로그 구조(log structured) 또는 저널링 (journaling) 파일 시스템 파일 시스템의 매 갱신을 트랜잭션(transaction) 으로 기록 시스템의 일관성 유지 및 복구 문제 해결. 모든 트랜잭션은 로그(log) 에 쓰여지면, 승인된(committed) 것으로 간주하지만, 파일 시스템은 아직 갱신되지 않았을 수도 있다. 로그 내의 트랜잭션들은 비동기적으로 파일 시스템에 쓰여지고, 파일 시스템이 수정될 때 트랜잭션은 로그로부터 제거. 파일 시스템이 파손되면, 로그 내의 모든 남은 트랜잭션들은 수행되어야 한다. NTFS, VFS, JFS, ReiserFS, XFS, ext3, ext4 (Linux)

NFS LAN (또는 WAN) 을 통해 원격 파일에 접근하기 위한 소프트웨어 시스템의 구현과 사양. 데이터그램 프로토콜(UDP)/IP 프로토콜과 이더넷을 사용하여 Solaris 와 SunOS 운영체제의 일부분으로 구현.

NFS 서로 연결된 워크스테이션의 집합을 독립적인 파일 시스템을 가진 독립적인 기계들의 집합으로 본다. 파일 시스템들 사이에서 일정 수준의 공유를 투명하게 허용. 원격 디렉토리가 지역 파일 시스템 디렉토리로 마운트된다. 마운트된 디렉토리는 지역 파일 시스템의 서브디렉토리로 보임. 마운트 연산에 대한 원격 디렉토리 지정은 투명하지 않음 원격 디렉토리의 호스트 이름이 제공되어야 한다. 원격 디렉토리 내의 파일들은 투명하게 접근 가능. 접근 권한만 허용하면 어떤 파일 시스템 또는 파일 시스템 내의 디렉토리든지 어떠한 지역 디렉토리 위에도 마운트 가능.

세 가지 독립적인 파일 시스템

NFS 에서의 마운팅 Mounts Cascading mounts

NFS 의 사양 NFS 는 서로 다른 기계, 운영체제, 네트워크 구조로 구성된 이질적 환경에서 동작하도록 설계. 독립성은 두 개의 구현 독립적 인터페이스간에 사용되는 eXternal Data Representation (XDR) 프로토콜 위에 구축한 RPC 프리미티브의 사용을 통해 달성. NFS 사양에서의 두 가지 구분 마운트 기법에 의해 제공되는 서비스 – 마운트 프로토콜 실제 원격 파일 접근(remote-file-access) 서비스 – NFS 프로토콜

NFS Mount Protocol 서버와 클라이언트 사이에 초기 논리 연결 수립. 클라이언트는 마운트 연산으로 마운트 요청 수행 Mount 연산은 마운트할 원격 디렉토리 이름과 이를 저장하고 있는 서버 기계의 이름을 포함. Mount 요청은 해당하는 RPC 로 매핑되고 서버 기계 상에서 수행하는 마운트 서버로 전달. 서버는 Export list 유지 마운트를 허용하는 기계 이름과 마운팅을 위한 지역 파일 시스템 지정. Export list 에 일치하는 마운트 요청에 따라, 파일 핸들(미래의 접근을 위한 키) 반환. 파일 핸들 – 파일-시스템 식별자(identifier) 와 수출된 파일 시스템 내의 마운트된 디렉토리를 가리키는 inode 번호로 구성.

NFS Protocol 원격 파일 연산에 대하여 원격 프로시져 호출 집합 제공. NFS 서버는 무상태성(stateless) 디렉토리 내의 파일 검색 디렉토리 항목 집합의 읽기 링크와 디렉토리들의 조작 파일 속성의 접근 파일 읽기와 쓰기 NFS 서버는 무상태성(stateless) 각 요청은 매개변수들의 완전한 집합을 제공해야 함. 수정된 자료는 결과들이 클라이언트로 반환되기 전에 서버의 디스크에 기록되어야 한다. The NFS 프로토콜은 병행성-제어 기법(concurrency-control mechanism) 을 제공하지 않음.

NFS 구조의 세 계층 UNIX 파일-시스템 인터페이스 (open, read, write, close 호출과 파일 디스크립터에 기반). Virtual File System (VFS) 계층 지역 파일을 원격 파일과 구분하며, 지역 파일은 파일-시스템 종류에 따라 세분됨. 지역 요청을 처리하기 위해 파일 시스템 종류에 따라 적절한 연산 실행. 원격 요청을 위해 NFS protocol 프로시져 호출. NFS 서비스 계층 가장 하위 계층이며 NFS 프로토콜을 구현.

NFS 구조의 개략도

NFS 경로-이름 변환 경로를 요소 이름으로 분리하고, 요소 이름과 디렉토리 vnode 의 모든 쌍에 대한 별도의 NFS 룩업(lookup) 호출 수행. 룩업을 빠르게 하기 위해, 클라이언트 측의 디렉토리 이름 룩업 캐시는 원격 디렉토리 이름들에 대한 vnode 를 가짐.

NFS 원격 연산 정규적인 UNIX 시스템 호출과 NFS 프로토콜 RPC 사이에는 거의 1 대 1 대응 관계 (파일 open 과 close 제외). NFS 는 원격-서비스 패러다임을 따르지만, 실제로는 성능 향상을 위해 버퍼링과 캐싱 기술을 사용. 파일 블록 캐시 파일이 개방될 때, 커널은 캐시된 속성들을 다시 가져올지 이전 것을 사용할지 결정하기 위해 원격 서버를 검사. 캐시된 파일 블록들은 대응되는 캐시된 속성들이 최신일 때에만 사용. 파일 속성 캐시 새로운 속성이 서버로부터 도착할 때마다 속성 캐시를 갱신. 클라이언트는 서버가 자료를 디스크에 기록한 것을 확인하기 전에는 지연 쓰기 블록을 해제하지 않음.