fileSystem.md

📌파일 시스템(File System)

💡사전 지식

1. File

• 관련된 정보의 모음
• 일반적으로 보조기억장치에 저장
• File에 행할 수 있는 연산
  • create, delete, open, close, read, write, reposition(=lseek)
  • reposition 연산은 파일 내의 포인터 위치를 변경할 때 사용한다.

2. File attribute

• 메타 데이터(meta data)라고도 부른다.
• 파일을 관리하기 위한 각 종 정보가 이에 해당된다.
  • 접근 권한, 소유자, 생성 또는 수정 시간

3. File System

• 운영체제에서 파일을 관리하는 부분

4. root directory의 메타 데이터는 운영체제가 미리 알고 있다.

5. 디스크 블로 하나의 크기는 보통 512byte이다.

✔️디렉터리(Directory)

• 디렉터리도 일종의 파일이다.
• 디렉터리 파일의 내용(정보)는 디렉터리에 포함된 파일들의 메타 데이터이다.
  • 디렉터리에 포함된 파일 정보를 저장한다.
• 디렉터리에 행할 수 있는 연산
  • search for file, create a file, delete a file
  • list a directory, rename a file, traverse the file system

✔️파티션(Partition) 또는 Logical Disk

• 하나의 물리적 디스크를 여러 개의 파티션으로 나눌 수 있다.
• 반대로 여러 물리적 디스크를 하나의 파티션으로 구성할 수 있다.
• 하나의 물리적 디스크를 여러 파티션으로 나누고 각 파티션 별로 역할을 부여할 수 있다.
  • 하나의 파티션에는 파일 시스템을 적용하고 나머지 하나는 swap area로 사용할 수 있다.

✔️open 연산

• open 명령어는 I/O를 하는 시스템 콜이다.
• open 명령어를 사용하면 타깃이 되는 파일의 메타 데이터가 메모리(Open file table)로 올라오게된다.
• 프로세스에서 open('/a/b') 명령어를 수행
  1. 루트 디렉터리의 내용에서 a 디렉터리를 찾는다.
  2. 찾은 a 디렉터리의 메타 데이터를 메모리(Open file table)에 적재한다.
  3. a 디렉터리 내용에서 파일 b를 찾는다.
  4. 파일 b의 메타 데이터를 메모리(Open file table)에 적재한다.
  5. 메모리에 적재한 파일 b의 메타 데이터 위치를 PCB의 file descriptor table에 저장하고, 저장된 위치를 반환한다.
     • file dscriptor는 open 명령어의 반환값이 된다.
     • 향후 해당 프로세스에서 파일 b에 접근할 때 file dscriptor를 이용해서 접근할 수 있다.

❗️file table 종류

1. system wide Open file table

   • 시스템 전체에서 오픈된 파일을 관리하는 테이블
   • 열린 파일에 대한 메타 데이터 정보가 저장된다.

2. per-process file descriptor table

   • 프로세스 별로 오픈된 파일을 관리하는 테이블
   • 프로세스에서 사용 중인 파일들이 open file table 내부에서 저장된 주소를 저장한다.
   • 파일에 대해 프로세스 별로 관리해야 하는 추가 적인 정보를 저장
     • 파일 내부에서 현재까지 읽은 위치 등

✔️File Protection

• 각 파일에 접근을 어떤 사용자에게 허용하는 것과 관련된 문제
• Access control Matrix
  • 행은 각각의 사용자, 열은 각각의 파일을 의미하며 2차원 배열 형태로 접근 권한을 표현하는 방식
  • sparse matrix가 될 가능성이 높다.
  • overhead가 크다.
  • 보는 관점에 따라 두 가지 종류가 있다.
    • Access control list
      • 파일 별로 어떤 사용자에게 어떤 접근 권한을 허용했는지 표시
      • 파일을 중심으로 바라보는 관점
      • 2차원 배열에서 하나의 열을 중심으로 본다고 생각!
    • Capability
      • 사용자 별로 어떤 파일들에 대한 접근 권한이 허용됐는지 표시
      • 사용자를 중심으로 바라보는 관점
      • 2차원 배열에서 하나의 행을 중심으로 본다고 생각!
• Grouping 방법
  • 전체 사용자를 3가지 그룹으로 나눠서 권한을 부여한다.
    • 사용자는 owner, group, public 그룹 중 하나에 속한다.
    • 파일 별로 bit 9개로 접근 권한을 관리 할 수있다.
  • UNIX에서 사용하는 방법
    • 일반적으로 사용하는 방법
• Password 방법
  • 파일마다 비밀번호를 설정하는 방법
  • 접근 권한 별로 비밀 번호를 설정할 수 있고 또는 모든 접근 권한에 대해서 하나의 비밀 번호를 설정할 수 있다.

✔️Mounting

• 분리된 각각에 논리 디스크(파티션)에 파일 시스템을 설치할 수 있다.
• 만약 하나의 파티션에서 다른 파티션으로 접근이 필요할 때, Mount 방법을 이용한다.
  • A 파일 시스템의 디렉터리 b에 B 파일 시스템을 마운트 시킨다.
  • A 파일 시스템에서 디렉터리 b에 접근하는 것은 B 파일 시스템의 루트 디렉터리에 접근하는 것과 동일하다.
  • 즉, 마운트한 디렉터리를 통해 다른 파일 시스템으로 접근이 가능하다.

✔️접근 방법(Access Method)

• 순차 접근(sequential access)
  • 읽기 또는 쓰기 연산을 하몀ㄴ offset이 자동으로 증가
  • 정보가 A -> B -> C 순서로 저장되어 있다면 C 정보에 접근하기 위해서는 A와 B를 순차적으로 먼저 접근해야한다.
• 직접 접근(direct access)
  • 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있는 방법
  • 정보가 A -> B -> C 순서로 저장되어 있더라도 C 정보에 바로 접근할 수 있다.

✔️디스크 할당

• 세 가지 방법이 있다.
  • 연속 할당(Contiguous Allocation)
  • 연결 할당(Linked Allocation)
  • 색인 할당(Indexed Allocation)

연속 할당(Contiguous Allocation)

• 파일 데이터를 디스크의 연속적인 공간에 할당하는 방법
• 장점
  • 빠른 I/O가 가능하다.
    • 하드 디스크 동작 시간 중 디스크 헤더를 이동시키는 시간이 많은 부분을 차지하는데, 연속할당의 하면 디스크 헤더가 이동되는 시간을 줄일 수 있다.
    • swap area에 적합하다.
    • 공간 효율성 보다 시간 효율성이 우선시되는 경우에 적합하다.
  • 직접 접근이 가능하다.
• 단점
  • 외부 단편화 발생
  • 파일의 크기를 증가시키기 어려움
    • 파일 크기 증가를 대비해서 여유로운 공간에 할당하는 것은 낭비가 될 수 있다.(내부 단편화)

연결 할당(Linked Allocation)

• 파일 데이터를 디스크에 링크드 리스트처럼 저장한다.
  • 연속적인 공간에 할당하는 것이 아닌, 디스크의 여러 공간에 각각의 파일 데이터를 저장한다.
• 장점
  • 외부 단편화 문제가 해결된다.
• 단점
  • 직접 접근이 불가능하다.
  • 하나의 섹터가 유실되면 다음 위치에 접근할 수 없다.(Reliability 문제)
  • block 마다 다음 pointer를 저장하기 위한 공간이 필요하다.
• 연결 할당의 문제점을 보완한 방법으로 File-allocation table(FAT) 이 있다.
  • FAT은 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제를 해결한다.

색인 할당(Indexed Allocation)

• 파일 데이터가 저장된 블로 정보를 인덱스 블록에 순차적으로 저장한다.
• 장점
  • 외부 단편화 해결
  • 직접 접근이 가능
• 단점
  • 크기가 작은 파일도 블로이 두개가 필요하다
    • 데이터를 저장하는 블록과 인덱스를 저장하는 블록
  • 크기가 너무 큰 파일은 인덱스 블록이 하나 이상 필요하다.

✔️UNIX 파일 시스템의 구조

• 파티션의 구조
  • Boot block
    • 부팅에 필요한 정보가 저장(bootstrap loader)
    • 모든 파일 시스템의 첫번째 블록은 Boot block이다.
  • Super block
    • 파일 시스템에 관한 총체적인 정보를 저장한다.
  • Inode list
    • 파일 이름을 제외한 파일들의 메타 데이터는 Inode list에 저장된다.
      • Inode list에는 파일 이름을 제외한 모든 메타 데이터가 저장된다.
      • 파일 이름은 디렉터리 파일에 저장된다.
      • 파일에서 나머지 메타 데이터에 접근하기 위해서는 inode id를 이용해서 Inode list에서 조회한다.
      • 파일의 위치 정보는 색인 할당 방법을 이용한다.
        • 파일 크기에 따라 4가지 방법이 존재한다.
        • direct blocks
          • 파일 정보가 저장된 위치를 바로 저장하고 있다.
        • single indirect
          • 파일 정보가 저장된 위치에 접근하기 위해 하나의 인덱스 블록을 이용한다.
        • double indirect
          • 파일 정보가 저장된 위치에 접근하기 위해 인덱스 블록을 두 번 거친다.
        • triple indirect
          • 파일 정보가 저장된 위치에 접근하기 위해 인덱스 블록을 세 번 거친다.
  • Data block
    • 파일 데이터가 저장되는 공간

✔️FAT 파일 시스템의 구조

• 파티션 구조

  • Boot block

  • FAT

    • 파일의 위치 정보를 저장한다.
    • 테이블 구조
      • 현재 블록의 다음 위치를 저장한다.
      • 따라서 연결 할당처럼 접근이 가능하다.
    • 메모리에 적재된다.
      • 직접 접근이 가능하다.
      • 메모리에 올라와 있기 때문에 디스크의 블록을 순차적으로 확인하지 않아도 중간에 있는 블록 위치를 알 수 있다.
      • 섹션이 유실되도 메모리에 적재된 연결 정보를 통해 연결 할당에 비해서 데이터 유실을 최소화할 수 있다.
    • FAT은 중요한 정보이므로 디스크에 복사본을 따로 저장해둔다.

  • Root directory

  • Data block

    • 디렉터리에 파일의 이름과 파일의 시작 위치를 저장한다.

✔️자유 공간 관리(Free Space Management)

• Bit map(또는 bit vector) 방식
  • 디스크의 블록 하나당 하나의 bit를 이용해서 현재 블록의 사용 여부를 표시
    • 0이면 가용 블록이고 1이면 사용중인 블록이다.
  • 연속적인 자유 블록(가용 블록)을 찾기 적합하다.
  • 블록의 이용 여부를 저장 할 추가적인 공간이 필요하다.
• Linked-List
  • 비어있는 블록의 위치를 연결 리스트(free list)로 관리하는 방법
  • 연속적인 공간을 찾는 것은 쉽지않다.
  • 공간 낭비가 적다.
    • 연결 리스트의 첫번째 포인터만 저장하면 다음 위치에는 순차적으로 접근이 가능하다.
• Grouping
  • 연결 리스트의 변형된 방법
  • 하나의 자유 블록이 n개의 포인터를 가지며, 각 포인터는 자유 블록의 위치를 저장한다.
    • 마지막 포인터가 가리키는 블록은 또 다시 n개의 포인터를 가진며 이 포인터들 역시 다른 자유 블록의 위치를 가리킨다.
    • 색인 할당과 비슷한 느낌..!
  • 연속적인 빈 블록을 찾기에는 효과적이지 않다.
• Counting
  • 자유 블록의 시작위치와 그 위치로부터 연속적인 자유블록의 위치를 같이 저장한다.

✔️디렉터리 구현(Directory Implementation)

• 디렉터리 구현 방법
  • 선형 리스트(Linear List) 방법
    • 리스트의 각 요소는 <파일 이름, 파일 메타 데이터> 형식이다.
    • 구현이 간단하다.
    • 디렉터리 내의 특정 파일을 찾기 위해서 선형 탐색이 필요하다.
  • 해시 태이블 방법(Hash Table) 방법
    • 파일의 이름을 key로 사용하고, 파일의 메타 데이터를 value로 사용한다.
    • 디렉터리 안에 있는 파일을 탐색할 때, 선형 탐색을 하지 않아도 된다.
    • 해시 함수를 이용하기 때문에 해시 충돌(Collision)이 발생할 수 있다.
• 메타 데이터 보관 위치
  • 디렉터리 내에 보관 저장
  • 디렉터리에는 포인터만 저장하고 다른 고셍 보관
    • inode, FAT 등
• 파일 이름이 긴 경우 처리하는 방식
  • 파일 이름이 긴 경우, 잘리는 부분은 디렉터리 파일 내부에 저장한다.
    • 잘린 파일 이름이 저장된 위치(포인터)는 기존에 파일 이름이 저장된 위치의 마지막에 저장한다.
    • 포인터로 잘린 파일 이름에 접근할 수 있도록!

✔️VFS(Virtual File System)

• OS에서 제공하는 하나의 계층
• 동일한 시스템 콜 API를 이용해서 다양한 종류의 file system에 접근이 가능하게 해준다.

✔️NFS(Network File System)

• 분산 시스템에서 네트워크를 통해 파일이 공유될 수 있도록 가능하게 해준다.
  • 클라이언트에서 서버에 있는 파일시스템에 접근이 가능하게 해준다.

Cache 종류

• Page Cache
• Memory-Mapped I/O
• Buffer Cache
• Unified Buffer Cache
  • 최근에 사용하는 방식
  • Buffer cache와 Page cache를 따로 구분하지 않는다.

📚참고 자료

• KOCW 운영체제 Ch.File System - 반효경 교수님