반효경 운영체제 - 9. File System

File and File System

• file
  • 연관된 정보의 집합 - A named collection of related information
  • 일반적으로 비휘발성의 보조기억장치에 저장
  • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해줌
  • Operation
    • create, read, write, reposition(파일 포인터의 위치 변경), delete, open(파일의 메타데이터를 메모리에 올려놓는 작업), close
• File attribute(file metadata)
  • 파일 자체의 내용이 아닌 파일을 관리하기 위한 각종 정보들
    • 파일 이름, 유형, 저장된 위치, 파일 사이즈
    • 접근 권한 (읽기/쓰기/실행), 시간 (생성/변경/사용), 소유자 등
• File System
  • 운영체제에서 파일을 관리하는 부분
  • 파일 및 파일의 메타데이터, 디렉토리 정보 등을 관리
  • 파일의 저장 방법 결정
  • 파일 보호 등

Directory and Logical Disk

• 디렉토리
  • 파일의 메타데이터 중 일부를 보관하고 있는 특별한 파일
  • 그 디렉토리에 속한 파일 이름 및 파일 attribute들
  • operation
    • search for a file, create a file, delete a file
    • list a directory, rename a file, traverse the file system
• Partition
  • 하나의 디스크 안에 여러 파티션을 두는게 일반적
  • 여러 개의 물리적인 디스크를 하나의 파티션으로 구성하기도 함
  • 디스크를 파티션으로 구성한 뒤 각각 파티션에 file system 구성이나 swap area로 사용할 수 있다.

open()

• 파일의 메타데이터를 메모리에 로드하는 행위
  • 시스템에서 위치를 메모리에서(fd) 가지고 있어 수정이 가능하다는 의미
  • 운영체제는 buffer caching을 하여 다른 프로세스가 동일한 자료를 요청하면 디스크를 조회하지 않고 보내준다.
    • buffer cache에 있는 내용여도 시스템콜이므로 cpu제어권은 무조건 운영체제에게 넘어간다.
    • LRU 알고리즘, LFU 알고리즘을 사용할 수 있다.
• per-process file descriptor table -
• open file table - system wide open file table 시스템에서 공유하는 오픈 파일 테이블
• open(”/a/b/c”)
  • 디스크로부터 파일 c의 메타데이터를 메모리로 가지고 옴
  • 이를 위하여 directory path를 search
    • 루트 디렉토리 “/”를 open하고

File Protection

• 각 파일에 대해 누구(사용자/프로그램)에게 어떤 유형의 접근(read/write/execution)을 허락할 것인가?
• Access control 방법
  • Access control matrix : 파일별로 누구에게 어떤 접근권한이 있는지 표시
  • Capability : 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시
• Grouping
  • 전체 user를 owner, group, public의 세 그룹으로 구분
  • 각 파일에 대해 세 그룹의 접근 권한(rwx)을 3비트씩으로 표시
• Password
  • 파일마다 password를 두는 방법(디렉토리 파일에 두는 방법도 가능)
  • 모든 접근 권한에 대해 하나의 password: all-or-nothing
  • 접근 권한 별 password : 기억력 문제

파일 접근 방법

• 순차 접근
  • 카세트 테이프를 사용하는 방식처럼 접근
  • 읽거나 쓰면 offset은 자동적으로 증가
• 직접 접근
  • LP 레코드 판과 같이 접근하도록 함
  • 파일을 구성하는 레코드를 임의 순서로 접근할 수 있음.

 

 

File System Implementation

Contiguous Allocation

• 하나의 파일이 디스크 상에서 연속으로 저장된다.

단점

• 파일의 크기가 균일하지 않기 때문에 외부 디스크 조각이 생길 수 있다.
• 파일의 크기가 커질 수 있는데, 커지는 데에 제약이 있다.
  • 빈 공간을 미리 확보해 놓으면? → 당장 사용하지 않기 때문에 내부조각이 발생하게 된다.
• 외부 조각 : 할당되지 않아 낭비되는 공간
• 내부 조각 : 할당되었지만 사용하지 않는 공간

장점

• 빠른 I/O가 가능하다. → 대부분의 시간이 pin이 이동하는 시간을 차지하는데, 한번의 Seek로 많은 데이터를 가져올 수 있다.
• Process의 swapping용(임시로 저장하는 프로세스의 주소공간 - 빠르게 저장했다가 빠르게 올려야하는데, 공간 효율성보다 속도 효율성이 중요한 데이터에서 효과적이다.)
• 디스크를 많이 차지해도 금방 지워지는 데이터에 효과적이다.
• Realtime용
• Direct Access가 가능하다.

Linked Allocation

• 연속일 필요없이 남는 공간에 데이터가 저장된다.
• 파일의 시작위치와 끝위치만 디렉토리에 저장해두고, 파일 위치에 가보면 다음 위치를 알 수 있다

장점

• 외부조각 문제가 발생하지 않는다.(아무 곳이나 할당할 수 있으므로)

단점

• 직접 접근이 불가능하다. 4번째 블록을 보려면 3번째 블록까지 확인해야한다.
• 순차접근에 의한 시간이 많이 발생된다.
• Reliability 문제 - 디스크 섹터가 배트 섹터가 생길 때, 포인터가 유실되어 데이터의 일부를 잃게된다.
• Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어트림.

변형

• File-allocation table(FAT) 파일 시스템
  • 포인터를 별도 위치에 보관하여 reliability와 공간 효율성 문제를 해결

Indexed Allocation

• 디렉토리가 index 블록의 위치정보를 가지고 있다.
• index 블록은 전체 파일의 index 정보를 가진다.

장점

• 순차접근의 공간활용성 문제, 직접접근 문제를 해결할 수 있다.

단점

• 파일이 하나 별도로 필요하므로 small file의 경우 공간 낭비
• Too Large file의 경우 하나의 블록으로 index를 저장하기에 부족
  • linked scheme - index block 마지막에 또 다른 index block의 위치를 기입한다.
  • multi level

UNIX 파일 시스템의 구조

• Boot block
  • 부팅에 필요한 정보 (bootstrap loader)
  • 파일시스템에 대한 정보가 없기 때문에 0번 블록을 메모리에 올려서 동작시킨다.
• Super block
  • 파일 시스템에 대한 총체적인 정보를 담고 있다.
  • 어디가 빈 블록인지, 어디가 사용 중인 블록인지.
• Inode list
  • 디렉토리는 실제로 파일에 대한 모든 메타 데이터를 가지고 있지 않다.
    • 유닉스에서는 사실 파일의 이름과 Inode 번호만 디렉토리에서 저장한다.
  • 메타 데이터를 별도로 빼서 저장해 놓은 것이 Inode list
  • 파일 1개당 Inode가 하나씩 할당된다.
• Data block

유닉스 Inode는 파일의 위치를 표현하기 위해 Indexed Allocation를 변형한 형태로 저장한다. 파일의 크기에 따라 single indirect, double indirect, triple indirect 순서로 사용한다. (B+ tree와 비슷한듯?)

direct blocks - 실제로 파일 내용을 보관하는 pointer들을 저장.

single indirect - 인덱스를 가리키는 pointer를 저장

FAT File System

Linked Allocation을 활용한 시스템

• 실제 파일 시스템 접근이 아닌 FAT만 확인해서 다음 위치를 알 수 있다는 장점이 있다.
• 직접 접근이 가능하다. → 디스크에서 팁이 이동하는 것이 아닌, 메모리에 FAT을 띄워놓고 빠르게 위치를 확인할 수 있다.
• Reliability 개선 → 데이터 블록에서 bad sector가 나더라도 FAT에서 위치 정보를 보관하고 있음, 거기다가 중요하기 때문에 1 copy 이상을 저장한다.

• FAT
  • 파일의 위치에 대한 메타 데이터만 보유
  • 데이터 블록의 개수만큼 생성
  • 블록의 다음 블록을 저장한다.
• Root directory
• Data block
  • 위치를 제외한 모든 메타데이터를 디렉토리가 관리한다.

Free-space Management

1. Bit map

• Bit map or Bit Vector
• 비어있는지 아닌 지를 저장하는 자료 구조
• bit map은 부가적인 공간이 필요하다.
• 연속적인 n개의 free block을 찾는 데 효과적

2. Linked List

• 비어있는 블록을 Linked List로 연결해둔다.
• 연속적인 가용 공간을 찾기 어렵다.
• 첫 위치만 보관하므로 공간 낭비가 없다.

3. Grouping

• Linked list 방법의 변형
• 첫번째 free block이 n개의 pointer를 가짐
  • n-1 pointer는 free data block을 가리킴
  • 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

4. Counting - 연속적인 빈 블록을 찾기에 효과적인 방법

• 빈 블록의 첫번째 위치와, 몇 개가 연속으로 빈 블록인지를 함께 관리하는 방식.
• 프로그램은 종종 여러 개의 연속적인 block을 할당하는 성질에 착안.

Directory Implementation

• Linear list
  • <file name, file의 metadata> list 형태로 구현
  • 구현이 간단
  • 파일을 찾기 위해 linear search 필요(시간 복잡도 높다)
• Hash Table
  • linear list + hashing
  • Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
  • search time을 없앰
  • Collision 발생 가능
• File의 metadata 보관 위치
  • 디렉토리 내 직접 보관
  • 디렉토리에는 포인터를 두고 다른 곳에 보관
    • Inode, FAT
• Long file name의 지원
  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정
  • file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
  • 이름의 나머지 부분은 동일한 directory file의 일부에 존재.

VFS and NFS

• VFS(Virtual File System)
  • 사용자는 어떤 파일시스템을 사용하는지에 상관없이 동일한 시스템 콜 인터페이스로 파일 시스템에 접근할 수 있도록 VFS Interface를 사용한다.
• NFS(Network File System)
  • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • RPC(원격 접근 프로토콜), NFS client/server로 마치 사용자가 요청하는 것처럼 파일 시스템에 요청이 가능하다.
  • NFS는 분산 환경에서의 대표적인 파일 공유 방법

Page cache

• 자주 사용되는 페이지를 사용자 메모리 영역에 보관해두는 것
• swap area에 page가 존재하느냐, 메모리에 로딩되어있느냐를 일컫는 용어라고 함
• 단위 : 4kb page

Buffer Cache

• 잦은 I/O를 하는 데이터의 경우 입출력 데이터를 커널 메모리 영역에 복사해두고 사용자 프로그램에 copy해서 넘겨준다.
• 단위 : block 단위, 예전엔 512byte(페이지 대비 적음)
• 리눅스에서는 단위가 통합되어, 페이지 단위로 사용한다.

Memory Mapped IO

장점

• 한 번 매핑을 하면 시스템콜을 할 필요가 없다.
• 여러번 호출시마다 copy를 만들지 않고 물리 메모리에 mapping된 위치를 그대로 사용한다.

단점

• 여러 프로세스 간 share할 때 동시성 문제 발생 가능