[OS(2)]File System Implementations 1

지난시간

storage 데이터에 접근하는 방법

• 순차적인 접근
• 임의적인 접근
  매체에 따라서 다름
• tape => 순차적 접근
• 하드디스크, 플래시메모리, cd => 임의적 접근

직접 접근이 가능한 매체라 하더라도, 데이터를 어떻게 관리하느냐에 따라서 순차적 접근만 허용되는 경우, 직접 접근이 가능한 경우가 있다.
=> 오늘, 그 이유에 대해 알아보자.

디스크에다가 파일을 저장하는 방법 3가지

• 파일은 크기가 균일하지 않다.
• 디스크에다가 파일을 저장할 때는 동일한 크키의 sector 단위로 나누어서 저장하고 있다.
  
• 파일 시스템이나, 디스크 외부에서 볼 때는 각각의 동일한 크기의 저장단위를 논리적인 block이라고 부른다.
  • 실제로 디스크 내부에는 각각이 sector 단위로 데이터를 저장하고 있음.
    • 어떤 임의의 크기의 파일을, 동일 크기의 block 단위로 나누고 있다는 뜻.
  • 메모리기법의 paging 기법과 유사함
    => 저장하는 방법이 아래 3가지
    1. Contiguous Allocation : 연속 할당 방법
    2. Linked Allocation : link를 둔 연결 할당 방법
    3. Indexed Allocation : index를 둔 할당 방법

Allocation of File Data in Disk

• 디스크에다가 파일을 저장할 때는 동일한 크키의 sector 단위로 나누어서 저장하고 있다.
  
• 파일 시스템이나, 디스크 외부에서 볼 때는 각각의 동일한 크기의 저장단위를 논리적인 block이라고 부른다.
  • 실제로 디스크 내부에는 각각이 sector 단위로 데이터를 저장하고 있음.
    • 어떤 임의의 크기의 파일을, 동일 크기의 block 단위로 나누고 있다는 뜻.
  • 메모리기법의 paging 기법과 유사함

1. Contiguous Allocation

하나의 파일이 디스크 상에 연속해서 저장이 되는 방법

전시간에)

• 디렉토리라는 파일은 그 디렉토리 밑에 있는 파일들의 meta data를 내용으로 한다.

장점

- 1. 빠른 i/o가 가능

• 특히 하드디스크 같은 매체는 대부분의 접근 시간이 head가 이동하는 시간이다. 바깥쪽 트랙 => 안쪽 트랙 이동 시간. 데이터를 읽거나 쓰는 크기는 별로 상관이 없음.
  어떤 파일을 통째로 읽고 싶을 때, 한번의 seek로 많은 데이터의 내용을 받아올 수 있다.
• 연속할당은 파일 시스템 용도 말고, 또 다른 용도로 쓰는데, process의 swap area로도 쓴다. (파일을 저장하는게 아니라 process 주소 공간 중 일부를 물리적인 메모리에서 쫓아내고 , 나중에 필요할 때 올려놓는 용도로 씀)
  => 파일 시스템은 연속적인 공간이다. 전원이 나가더라도 내용이 유지되어야 하는데, swap area는 그런게 아니다. process가 끝나면 의미가 없는 정보이기 때문에 임시로 저장하고 process의 주소 공간 많은 양의 크기를 빠르게 디스크로 쫓아냈다가, 다시 메모리에 올리고 처럼 swapping의 용도는 공간 효율성보다 속도 효율성이 중요한 데이터에 속한다. 빠른 i/o를 위해서 연속 할당을 해주는 것이 좋다. 특히, realtime file은 빠른 속도가 중요하기 때문에 contiguous 할당이 참 좋음 ~~

- 2. 직접 접근이 가능
ex) main 이름의 파일 데이터의 길이는 6인데, 이 파일의 5번째 block을 읽고 싶을 때,
=> 앞의 4개의 블록을 다 접근할 필요가 없다. (연속적으로 저장되어 있기 때문임)

단점

• 외부조각 발생

• 파일의 크기는 계속 바뀌는데, 파일의 크키를 키우는데 대해 제약이 생긴다.
  • 미리 더 할당하더라도 크기 제약이 있기도 하고, 당장 사용하지도 않으니 => 내부조각 발생

2. Linked Allocation

하드디스크임에도 불구하고 직접접근이 불가능하다.

• 파일의 데이터를 디스크에다가 연속적으로 배치하지 않고, 빈 위치면 아무데나 들어갈 수 있도록 배치한다.
  

장점

• 외부 조각 발생안함.

단점

• 직접접근이 안됨

  • 4번째 blcok 가려면 1block => 2block => 3block을 거쳐야함

• block 각각의 경우에 head가 이동해야함. (seek에 의한 시간이 오래걸림)

• Reliability 문제

  • 디스크의 sector들이 bad sector가 간혹남. (중간에 하나 bad sector가 나면 다음 위치는 다 접근 불가능) => pointer가 유실

• Pointer를 위한 공간이 block의 일부가 되는 문제 (디스크에서 하나의 sector는 512byte로 구성되어 있음. 그리고, 또 디스크의 바깥쪽, 컴퓨터에서 디스크에 접근할 때 디스크의 data를 저장하려는 단위가 512byte의 배수로 저장이 된다. 근데, 512byte 배수를 디스크에 저장하라고 하는데, 다음 위치를 가리키는 pointer를 위해서 4byte가 소요된다면, 하나의 데이터를 디스크에 저장하는데 두개 sector 사용되어야 함)

변형

Linked Alloctaion을 약간 변형해서 굉장히 효율적으로 바꾼 파일 시스템
=> FAT 파일 시스템 (File-allocation table)

3. Indexed Allocation

Indexed Allocation은 파일의 직접 접근을 가능하게 하기 위해 사용되는 파일 할당 방식입니다. 이 방식에서는 디렉토리에 파일의 위치 정보를 바로 저장하지 않고, 인덱스를 가리키게 합니다.

• 디렉토리 구조: 파일의 위치 정보 대신 인덱스 블록을 가리키도록 되어 있습니다.
• 인덱스 블록 (Index Block): 실제 파일의 데이터를 담고 있는 블록들의 주소를 열거해둔 블록입니다. 인덱스 블록 자체는 실제 데이터를 담고 있지 않지만, 해당 파일이 저장된 블록들의 위치 정보를 가지고 있습니다.

장점)

• 직접접근 가능하다.
• 중간중간 hole 생기는 문제도 해결

단점)

• 아무리 작은 파일이여도 block이 두개가 필요하다.
  • index block 하나, 데이터 저장하는 block 하나.
    => 파일이 아주 작은 경우에 공간낭비가 있다는 뜻.
• 너무 큰 파일도 index block 하나로 표시할 수 없음.
  • 한 block 크기가 512 byte이고, 포인터가 4byte라고 할 때, 이것도 제한적임.

linked scheme

• 이렇게 큰 파일 같은 경우에는 index block이 여러개가 된다.

multi-level index

• index가 데이터를 바로 가리키는게 아니라, 두번 거쳐서 가리키게 되는 등의 방식
  • 굉장히 큰 파일 표현 가능
  • index를 위한 공간 낭비

+ 지금까지.

디스크에 저장하는 파일의 기본적인 방법 3가지, 이론적으로 이런 할당이 가능하다고 설명.
앞으로는,
실제 파일 시스템에서 어떤 할당 방법을 어떻게 쓰고, 변형해서 쓰는가 알아보자

UNIX 파일시스템의 구조

• UNIX 는 역사가 오래된 운영체제이다.
• 지금 설명할 UNIX 파일 시스템 구조는 가장 기본적인 파일 시스템 구조임.
  • UNIX나 linux의 파일 시스템이 기본적인 파일 시스템에서 => Fast file system => EXT2,EXT3등 굉장히 많은 파일 시스템으로 발전해왔음.
    - 이 과정에서 기본 구조를 효율적으로 저장하고 ,시간을 줄이는 방법이 발전.
    하지만 이 수업에서는 기본적인 파일 시스템 구조로 이야기 할 것임.

• 논리적인 디스크에다가 UNIX 파일 시스템을 설치해둔 것임.

UNIX 파일 시스템은 저장되는 구조가 크게 4가지로 구성
1. Boot block

• unit 파일 시스템 뿐만 아니라 모든 파일 시스템이 첫번째로 Boot block이 나온다. : 0번 block에 저장.
  • 올려놓고, Boot block이 시키는대로 하면, 이 전체 파일 시스템에서 운영체제의 커널의 위치가 어디인지를 찾아서 메모리에 올려서 정상적인 부팅이 이뤄지게 됨.
• 부팅에 필요한 정보를 담고 있음 = (bootstrap loader)

2. Super block
:

• 파일 시스템의 관한 총체적인 정보를 담고 있다.
  • 어디가 빈 block이고, 어디가 파일이 저장된 사용중인 block인지 관리
  • 어디까지가 Inode list가 있고, 어디부터 실제 Data block이 있는지 총체적 관리

3. Inode list
파일의 메타데이터는
그 파일을 가지고 있는 디렉토리에 가면 있다.
근데, 실제 파일 시스템 구현에서는 디렉토리가 메타데이터를 다 가지고 있진 않다.
특히, unix 파일시스템에서 디렉토리는 지극히 일부만 가지고 있고,
파일의 메타데이터들은 별도의 위치에다가 빼서 보관하고 있다.
그 위치가 Inode list라는 부분이다.

• Inode라는게 index node 인 것임.
• Inode라는 것들이 빨간색으로 표시된 것처럼 하나씩 저장될 수 있는 위치가 있음.
• 빨간색으로 표시된 이 inode 하나가, 파일 하나당 할당 되는 것임.
• 그리고 그 inode는 그 파일의 메타데이터를 가지고 잇는 구조다.
  • 메타데이터: 파일 소유주, 접근권한, 최종 수정된 시각, 위치정보 등
    
• unix 파일 시스템에서 파일의 meta data를 전부 inode가 갖고 있는 건 아니고, 파일의 이름은 directory가 갖고 있다.
  
• 디렉토리에 가면, 디렉토리 파일의 메타데이터가 저장.
• 파일의 이름은 디렉토리가 가지고 있고, 나머지 메타데이터는 inode에 저장되어있기 때문에 inode 번호가 저장되어 있는 것임.
  • ex) inode 10번이다 하면 Inode list의 10번 째에 그 파일의 메타데이터가 저장되어 있는 것임.

그러면, 파일의 위치정보는 어떻게 저장하고 있는가?

• UNIX 파일 시스템은 기본적으로 Index Allocation을 변행해서 사용하고 있다.
  • 각 파일당 Inode 크기가 고정되어 있다.
  • 여기서 표시될 수 있는 위치정보를 나타내는 pointer 개수도 유한하다.
  • 그렇지만 가급적 작은 inode를 가지고 굉장히 큰 파일을 표현할 수 있어야 한다.

• unix는 indexed allocation 중에서 4가지로 그 파일의 위치 정보를 구성한다.

파일 크기가 굉장히 작으면 direct index 만 가지고 그 파일의 위치를 표현할 수 있다.
파일 크기가 커지면 indirect 사용

• single indirect
• double indirect
• triple indirect
  이게 왜 효율적인가?
• 대부분의 파일은 크기가 작다.
• 작은 파일들은 한번에 pointer 접근으로 파일의 위치를 바로바로 알 수 있다.
• 굉장히 큰 파일들은 indirect block을 이용해서 index를 디스크에서 추가적으로 접근해서 위치를 찾는다.
  => 굉장히 큰 파일을 이 한정된 크기의 inode로 지원할 수 있다.

FAT File System

• ms사가 ms-dos를 만들었을 때 처음 만든 파일 시스템
• 최근에도 윈도우즈 계열에서도 FAT File-system을 사용하는 경우가 있다.
• 모바일 기기 경우에도 사용하기도 함.

1. Boot block

• 어떤 파일 시스템이든 마찬가지로 부팅과 관련된 정보

2. FAT

• 파일의 메타데이터 중에 일부를 FAT에 보관하고 있다.
  • 지극히 제한적인 위치정보만 FAT에 !

• 나머지 메타데이터는 directory가 가지고 있다.
  • 파일의 이름
  • 접근권한
  • 소유주
  • 파일 사이즈
  • 그 파일의 첫번째 위치가 어딘지
    • 만약 217번 블록이다
      
    • 그러면, 217번 블록에 그 파일의 첫번째 내용이 있다.
    • 이 상황에서 Linked allocation을 생각해보면, 다음 문제가 있다. 첫번째로는 중간에 베젝스터? 가 나면 다음꺼를 다 찾지 못하고, 두번째로는 약간의 크기가 줄어듬으로써 512byte 를 다 활용할 수 없는 것.
      => FAT 파일 시스템은 217번 block의 다음 block이 뭔지를 FAT이라는 별도의 테이블에 담고 있다. (Data block이나 directory file에 안담고 있음.)
      
    • FAT이라는 배열의 크키는 디스크가 관리하는 Data block의 개수만큼 있다. 그 배열에는 숫자를 하나 담을 수 있는데 그 숫자는 그 블록의 다음 블록이 어딘지를 담고 있다.

예시 정리)

• 이 file의 경우에는 첫번째 block이 217번이였다.

• 217번 block은 Data block에 있고,

• 두번째 block은 FAT을 본다.

• 217번 entry를 가면 618이라고 써져있다.

• 그러면 이 파일의 두번째 block은 Data block의 618번에 있구나

• 그다음 파일은 FAT의 618번 entry에 가본다 339라고 써져있음.

• ...

• EOF는 이 파일이 끝났다는 약속의 숫자를 뜻함.

  개념 정리)

• Linked Allocation을 활용한 것.

• 하지만, 다음 위치를 찾기위해 block을 접근하는 것이 아님.

• FAT만 확인해보면, 그 다음 위치를 알 수 있음.

• FAT 파일 시스템은 직접 접근이 가능하다는 장점이 있다.

  • (linked allocation은 파일의 중간위치를 보려면 디스크 헤드를 이동해서 따라가야지만 가능했던 것과는 대조적이다.)

• FAT 파일 시스템은 linked allocation의 단점을 모조리 극복한다.

  • random access 가능하고,
  • reliability 해결한다.
    • pointer 하나가 유실되더라도 (bad sector가 나더라도) FAT에 내용이 있기 때문에 이 Data block의 내용하고 FAT의 내용하고는 분리가 되어있음.
  • FAT은 데이터의 위치를 담고 있는 대단히 중요한 정보이다.
    • FAT은 한 copy만 두지 않고, 디스크에 두 copy이상을 두고 있다.
  • 512 byte 공간을 다 사용가능하게 한다.
    • pointer의 역할을 FAT이 하니까.

Free-Space Management

• 그동안, 논리적인 디스크에서 파일에 할당된 데이터들을 어떻게 관리할까? 에 대해서 이야기 했음
• 이제, 비어있는 block들은 어떻게 관리할지 이야기해보자.

비어있는 block 관리하는 방법

• 1. Bit map을 두기(또는 bit vector)
• 2. Linked list로 관리
• 3. Grouping 하는 방법
• 4. Counting 하는 방법

1. Bit map or Bit vector

각각의 block 별로 번호가 있으면,
unix 같은 경우에는 Super block에다가 bit를 둬서
첫번째 block이 사용중이냐 , 비어있느냐를 0과 1 로 표시한다.

• bit map의 크기는 data block에 있는 block 개수만큼이다.

• 0 => 비어있는 block

• 1 => 파일에 할당된 block

• 파일 시스템이 어떤 파일이 새로 만들어지거나 , 파일 크기가 커지면 => 비어있는 block 중에 할당

• 파일이 삭제되면 1로 표시되어 있던 bit map을 0으로 바꾼다.

• Bit map은 부가적인 공간을 필요로 한다.

  • 그렇게 많은 공간을 차지하진 않음. block 하나당 1 bit 필요함.

• 연속적인 빈 block을 찾는데 효과적이다.

  • 파일이 여러개의 block으로 구성되니까, 가능하면 연속적인 빈 공간에 할당하면 좋긴 하겠음. 디스크 이동을 최소화해서 많은 양을 한꺼번에 읽어올 수 있기 때문임.

2. Linked list

• 비어있는 block을 연결한다.
• 어처피 비어있기 때문에, pointer로 다음 위치 저장한다.
• bit map에 비해서 추가적인 공간 낭비가 없음.
• 그렇지만 연속적인 빈 공간을 찾기 어려움.
  • 디스크 헤드가 seek 해서 다 찾아야 함.
• 이론적으론 가능하지만, 실제로는 비효율적이라 안씀

3. Grouping 하는 방법

• Indexed Allocation을 활용한 방법임.
  => Grouping 방법
• 비어있는 block을 한꺼번에 찾기에는 Linked list보단 효과적이지만, 연속적인 빈 block을 찾기에 썩 효과적이지 않음.

4. Counting 하는 방법

• 빈 block을 연속적으로 찾는데 효과적임.
• 빈 block을 가리키기만 하는게 아니라,
• 거기서부터 몇개가 비어있다~ 이런식으로 관리. # of contiguous free blocks
  • 연속적으로 free block이 몇개인지 써있는 것을 찾으면 됨

Directory Implementation

• 디렉토리를 어떻게 구현하는지에 대한 것을 이야기해보자.
• 디렉토리란? 디렉토리 밑에 있는 file의 metadata를 관리하는 특별한 파일.
• 디렉토리 파일의 내용을 어떻게 저장할 것이냐?

1. Linear list 방식

• file의 이름
• file의 metadata들 순차적 저장
  • : 접근권한, 사이즈, 소유주...
• 크기를 고정시켜서 관리 (몇비트, 몇바이트로 정보를 차지하기)
• 디렉토리에 대한 연산이 주어질 때 (ex. 그 디렉토리 밑에 어떤 file이 있는지 찾아라)
  • 파일 이름에 대한 필드가 어떤 단위로 구성됐는지 알기 때문에 파일 이름을 쭉 찾아보면 된다.
    => 구현은 간단하지만, 연산에 대해서 시간이 많이 필요함. 비효율적임.

2. Hash Table 방식

• 파일의 이름을 그냥 저장하는게 아니라 hash 함수를 적용한다.
  • hash 함수라는 것은 어떤 input 값을 넣더라도 결과괎이 특정 범위 안의 숫자로 한정된다.
  • F 함수를 적용했을 때 1부터 n 사이의 값이 나오도록 할 수 있다.
  • 파일의 해시 함수 결과값에 해당하는 entry에다가 그 파일의 meta data를 저장한다.
• 파일이 있는지 찾아라 ! 연산할 때,
  • 순차적으로 탐색하는 것이 아니라
  • 그 파일 이름을 해시함수로 적용하고 그 다음에 적용된 결과괎에 해당하는 entry만 확인해보면 된다.
    => 서로 다른 파일 이름에 대해서 해시함수 결과괎이 같은 entry로 mapping되는 Collision 발생 가능.

File의 metadata 보관위치 정리

디렉토리에다가 파일의 메타데이터를 직접 구현할 수 있지만,
메타데이터를 디렉토리가 전부 가지고 있는 것이 아니라

• 일부는 직접 가지고 있고,
• 일부는 파일 시스템에서 다른 곳에 별도로 저장
  • unix에서는 inode에 대부분의 metadate를 가지고 있었고,
  • Fat 파일 시스템에서는 FAT이라는 곳에 파일의 다음 위치 정보를 가지고 있었음.

Long file name의 지원

긴 파일 이름을 지원하는 방식에 대해 이야기해보자.

VFS and NFS

VFS (Virtual File System)

• 개별 파일 시스템 윗 계층에 VFS를 둔다.
• 사용자가 파일시스템에 접근할 때는 종류와 상관없이 VFS 인터페이스를 사용한다.
• 다양한 파일 시스템이 있지만, 사용자 입장에서는 동일한 API, 동일한 시스템콜을 이용해서 파일 시스템에 접근한다.

NFS (Networdk File System)

• 파일 시스템이 자기 스토리지, 즉, 로컬 스토리지에 저장될 수도 있지만, 원격에 저장되어있는 파일 시스템에 접근할 수도 있음
  => NFS 인터페이스를 활용해서 접근해야함.

• 두대의 컴퓨터가 Network로 연결되어 있는 상황

• client가 어떤 파일 시스템이든 상관없이 VFS를 통해서 접근하는데 그 파일 시스템 중에는 자기 로컬 컴퓨터에 있는 파일 시스템에도 접근이 가능하고, 원격의 다른 컴퓨터의 파일 시스템에 접근할 수 있는 인터페이스도 지원이 된다는 뜻.
  => NFS
• 마찬가지로 로컬 사용자가 원격의 파일 시스템에 접근하려면 VFS interface를 통해서 시스템 콜을 해서 접근하면 됨.
• NFS를 지원하려면 server 쪽에도 , client 쪽에도 NFS 모듈이 있어야 한다. 같은 약속을 가지고 접근을 하는 것임 !

Page Cache and Buffer Cache

Page Cache

page cache는 가상 메모리 관리 챕터에서 이야기 했었음.

• page들을 특히, 물리적인 메모리에 있는 page frame들을 page cache라고 부른다. 왜냐하면 swap area보다 물리적인 메모리 page frame이 빠르다.
• caching 관점에서 이야기해보자면, paging system에서의 page frame들을 page cache라고 부르는 것임.
• 운영체제한테 주어지는 정보가 지극히 제한적이였음.
  • cache hit가 나면, 즉, 이미 메모리에 존재하는 데이터에 대해서는 하드웨어적인 주소 변환만 하기 때문에 정확한 접근 시간을 알 수 없음. clock 알고리즘 사용햇음.

Buffer Cache

파일의 데이터를 사용자가 요청햇을 때,
그걸 디스크에 읽어서 운영체제가 그 내용을 자기 영역 일부에 저장하고, 똑같은 파일 데이터를 또 요청 받으면 디스크까지 안가고 바로 데이터를 주는 것임.

• file system 관점에서 Buffer Cache라고 한다.
• 이미 파일 데이터가 메모리에 올라와 있든, 디스크에 있든 간에 어처피 파일을 접근할 때는 시스템 콜을 해야 하기 때문에 cpu 제어권이 운영체제한테 넘어오고 , 그 파일에 대한 요청이 언제 일어났는지를 cache hit이든 cache miss가 나든. 그 정보를 이용해서 LRU 알고리즘을 사용할 수 있음.

Unified Buffer Cache

• 최근에는 Page Cache하고, Buffer Cache를 합쳐서 같이 관리하는 운영체제가 많다.
  • linux
• 합쳐져 있다는 거가 buffer cache도 page 단위로 관리를 한다는 뜻.
• 운영체제에서 page frame들, 물리적 메모리를 관리하는 루틴에 page cache, buffer cache를 같이 관리한다는 뜻인 것임.

Memory-Mapped I/O

파일 접근하는 방법

• read나 write를 이용한 즉 buffer cache 같은
• memory-mapped 이용
  • 파일을 접근할 때 원래는 파일 접근할 때 그 파일을 open 하고 read systemp call이나 wirte system call로 접근을 했다. 근데 그런 방법을 안쓰고,
  • 파일의 일정 부분을 그 프로세스의 메모리에다가 mapping 해놓고 쓰는 것임.
  • read나 write system call을 하는 것이 아니라 메모리에다가 읽고 쓰는 것처럼.

• 왼쪽그림은 물리적인 메모리다

• 커널 메모리 영역
  • 원래는 buffer cache가 존재했었음.
  • 파일의 내용을 읽어와라 => buffer cache에 먼저 가져오고 => 사용자한테 전달
  • block하나는 보통 512 byte 구성
    • 그런데 최근에는 page cache하고 buffer cache 랑 합쳐졌기 때문에 buffer cache에서도 4kbyte 즉, page 크기로 이 block들을 관리하고 있다. (Unified Buffer Cache 특징)
• 사용자 영역
  • page 단위로 필요한 데이터가 올라가고 내려가고 했엇음.
  • page는 보통 4kbyte 단위

• 빠르게 데이터를 내려놓고, 올려야 되기 때문에 여러개의 block을 모아서 4kbyte 단위로 올려놓거나 내려놓는것이 기본