디스크에 파일 데이터를 저장하는 방법

디스크에 파일을 저장할 때는 보통 동일한 크기의 섹터로 나누어 저장한다. 이런 섹터들을 논리적인 블록이라고 본다.

이를 할당해서 저장하는 방법이 세가지가 있다.

Contiguous Allocation

하나의 파일이 디스크 상에 연속해서 저장되는 방법이다. 예를 들어 블록 두개로 구성되는 파일은 0, 1 이렇게 연속해서 들어가게 된다.

(위 그림에서 list 란 파일은 28번부터 31번까지 저장된 길이가 4인 파일이다)

장점

• 빠른 I/O가 가능하다.
  • 특히 하드디스크의 대부분의 접근 시간은 디스크 헤드가 이동하는 시간이 차지한다. 실제로 데이터를 읽고 쓰는 시간은 미미하여 크게 영향을 미치지 못한다. 그런데 이 방법을 쓰면 한번의 seek/rotation으로 많은 양의 바이트를 transfer할 수 있다. (연속적으로 쭉 할당되어 있으니까)
  • File System 용도 말고 프로세스의 swap area로 디스크를 쓰는 경우에 좋다. file system은 영구적인 공간이지만 그러나 swap area는 임시로 저장해놓고 프로세스가 끝나면 없애버린다. 따라서 swapping 용도는 공간 효율성보다는 속도 효율성이 더 중요하다. (어차피 금방 지워질 것이기 때문이다.)
  • File 중에서 realtime file용으로 사용하면 좋다. 데드라인이 있고 빠른 I/O가 필요하기 때문이다.
  • 직접접근(=random access)이 가능하다. 파일의 특정 위치의 블록을 보고 싶은 경우 start에 보고 싶은 위치만큼 더해주면 바로 그 부분을 볼 수 있다.

단점

• external fragmentation이 생길 수 있다.
  • 내용이 들어 있지 않은 빈 블록들의 크기들이 균일하지 않다. 연속할당을 하고 있기 때문에 비어있음에도 활용될 수 없는 외부조각들이 발생한다.
• File grow가 어렵다.
  • 파일의 크기를 키우는 데에 어려움이 있다.
  • 파일이 커질 것을 대비해 미리 빈 공간을 확보해놓는 방법을 생각해 볼 수는 있다. 그러나 그 미리 할당된 크기만큼만 커질 수 있고 그 이상은 커지지 못한다. 또한 할당되었지만 당장 사용하지 않는 공간인 internal fragmentation이 생겨 공간의 낭비가 발생한다.

Linked Allocation

비연속적으로 저장되며 빈 위치 어디든지 들어갈 수 있다. 블록이 다음 블록의 위치를 알려주고, 마지막 블록인 경우 -1을 저장한다. start와 end 위치만 디렉토리에 따로 기록해둔다.

예를 들어 jeep 파일의 첫번째 블록이 9번에 있다. 9번에 데이터 블록과 두번째 블록 위치가 함께 들어 있다.

장점

• 외부조각이 발생하지 않는다.

단점

• 직접 접근이 불가능하다.
  디렉토리에는 첫번째 블록 위치만 들어 있기 때문에 특정 위치 블록을 보고 싶다면 그 앞의 블록들을 다 탐색하여 따라가야만 볼 수 있다. (Contiguous 와 대비)
• 순차 접근에 의한 시간이 많이 발생한다.
• Reliability 문제
  디스크의 sector들 중 bad sector가 발생하면 포인터가 유실되어 뒤에 이어지는 많은 부분을 잃는다.
• pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어 뜨린다.

  • 한 sector : 512bytes/sector

  • 한 포인터 : 4bytes/pointer

    ⇒ 내용을 저장하면 한 섹터에 저장될 데이터가 포인터를 저장하면 두 섹터에 저장되는 등의 일이 발생할 수 있다.

변형

• FAT(File-allocation table) Linked allocation을 변형해 효율적인 할당방법
  

Indexed Allocation

직접 접근을 가능하게 하기 위해 디렉토리에 index block 위치를 표시하고 그 블록에는 데이터가 저장된 위치정보들을 열거해둔다.

장점

• 중간 위치의 블록에 직접 접근도 가능하다. (앞에서부터 따라갈 필요없고 건너뛰어 갈 수 있다.)
• 외부조각도 해결

단점

• 아무리 작은 파일이더라도 인덱스 블록과 데이터를 저장할 블록까지 최소 2개가 필요하기 때문에 작은 파일일 경우 공간 낭비가 발생한다.
• 너무 큰 파일일 경우 하나의 블록으로 인덱스를 저장하기 부족하다.
  이를 해결하기 위한 방법으로
  • linked scheme
    인덱스 블록에 실제 파일의 위치를 적다가 마지막에 실제 파일 데이터의 위치가 아니라 또다른 인덱스의 위치를 적어둔다.
  • multi-level index
    하나의 인덱스 블록이 직접 파일의 위치를 가리키는 게 아니라 두번 거쳐야만 가리키게 한다.
    (⇒ 인덱스를 위한 공간 낭비가 있다는 것이 단점)
  가 있다.

실제 파일 시스템에서의 저장

UNIX 파일 시스템 구조

Partition에 파일 시스템을 설치해둔다. 저장되는 구조가 4가지가 있다.

Boot block

어떤 파일 시스템이든 가장 앞에 boot block이 나오는 것이 약속이다. 컴퓨터 전원을 켜면 부팅을 하게 되는데 어떤 파일 시스템을 쓰든 0번 블록을 올리면 이 파일시스템에서 운영체제 위치를 찾아 메모리에 올려 정상적인 부팅이 가능하게 한다.

부팅에 필요한 정보를 가지고 있다. (bootstrap loader)

Super block

파일 시스템에 관한 총체적인 정보를 담고 있다.
어디가 빈 블록이고, 어디가 사용중인 블록인지를 관리한다.
어디가에 Inode list 가 있고 어디부터 실제 data block이 있는지 관리한다.

Inode list

실제 파일 시스템에서는 전체 메타데이터가 디렉토리에 저장되어 있지는 않다. 특히 유닉스의 파일 시스템의 경우 디렉토리는 극히 일부분만 가지고 있고 실제 파일의 메타데이터는 별도의 위치에 빼서 저장해두는데, 그 위치가 Inode list이다. (Inode = Index Node)

파일 하나 당 Inode 하나가 할당된다. Inode는 그 파일의 메타데이터를 가지고 있는다.

단, 파일의 이름은 디렉토리에 저장되어 있다. 나머지 메타데이터들은 inode에 저장되어 있기 때문에 디렉토리는 inode의 번호를 가지고 있는다.

그럼 파일의 위치는 어떻게 저장하냐?

기본적으로 Indexed Allocation을 사용한다. inode의 크기는 고정되어 있다. 그래서 위치 정보를 나타내는 포인터 개수가 유한하지만, 큰 파일까지 나타낼 수 있어야 한다.

• direct blocks : 작은 파일은 이것만으로 다 나타낼 수 있다.
• single indirect : single indirect를 따라가면 인덱스 블록이 있다. 그 인덱스 블록에는 포인터가 여러 개 들어갈 수 있다.
• double indirect : 더 큰 파일을 표현하는 경우. 이단계 인덱스 구조
• triple indirect : 더 큰 파일을 표현하는 경우. 삼단계 인덱스 구조

⇒ 대부분의 파일은 크기가 매우 작기 때문에 direct block만으로 파일의 위치를 바로바로 알 수 있다. 가끔매우 큰 파일인 경우 추가적으로 접근해서 파일의 위치를 찾는다.

FAT File System

마이크로소프트에서 MS DOS를 만들었을 때 처음 만든 file system이다.
(아직도 모바일 기기나 일부 윈도우에서 사용하는 경우도 있다)

Boot Block

마찬가지로 부트 관련 정보

FAT

파일의 메타데이터의 일부를 담고 있다. 위치 정보만 FAT에 저장한다.
나머지 메타데이터는 디렉토리에 저장한다. (file 이름, 소유주, 첫 시작 블록 위치 등)

linked allocation에서 발생하는 문제(한 섹터가 깨지면 뒤에 이어지는 섹터도 사용 못함, 블록의 공간 낭비, 직접접근 불가)를 해결할 수 있다. 한 블록의 다음 블록이 무엇인지를 별도의 배열인 FAT이 저장하고 있는 것이다.

• 배열의 인덱스 위치 = 현 블록 위치
• 배열에 담긴 숫자 = index 블록의 다음 블록 위치

장점

• 직접 접근이 가능하다.
  FAT은 이미 메모리에 올라가 있고, 중간 위치더라도 배열에서 곧바로 위치를 파악할 수 있다.
• reliability 개선
  포인터가 유실되더라도 FAT에 내용이 있기 때문에(데이터 블록과 FAT이 분리) reliability가 개선된다. 또한 (파일 위치를 담고 있는 중요한 정보기 때문에) 보통 2개의 카피를 두기 때문에 reliability가 더 올라간다.
• 공간 활용도
  512bytes/sector를 모두 활용 가능

실제로는 이 두개 외에도 많은 파일 시스템이 사용되고 있고 더 많이 개선되어 있다.

Free Space Management

비어있는 블록들은 어떻게 관리할지에 대한 설명.

bit map or bit vector

각각의 블록별로 번호가 있다. 비트맵의 크기는 블록의 개수만큼이다.

• 값이 0이면 비어있는 블록
• 1이면 할당되어 있는 블록

비트맵은 약간의 부가적인 공간을 필요로한다.

이 방법의 장점은 연속적인 N개의 free block을 찾는 데 효과적이라는 것이다. contiguous allocation을 사용하지 않더라도 디스크 헤더의 이동량을 줄이기 위해 가능하다면 연속적으로 저장하면 좋다.

Linked List

모든 free 블록들을 링크로 연결해둔다. 비어 있는 블록의 첫번째 위치만 포인터로 가지고 있고, 그 다음의 빈 블록의 위치는 비어있는 블록들이 가지고 있어 연결리스트로 연결되어 있다.

연속적인 가용 공간을 찾는 것이 쉽지 않아 잘 사용되지는 않지만 공간의 낭비가 없다는 장점이 있다.

Grouping

인덱스 형식으로 그룹핑한 것.
비어있는 블록을 한번에 찾기에는 linked list보단 낫지만 연속적인 빈 블록을 찾기에는 효과적이진 않다.

Counting

연속적인 빈 블록들을 찾기 위해 (빈블록의 첫번째 위치, 거기서부터 몇개가 비어있는지)를 쌍으로 가지고 있는다.

Directory Implementation

디렉토리를 관리하는 방법.
디렉토리 파일의 내용을 어떻게 저장할까?

Linear list

단순하게 파일의 이름과 파일의 메타데이터의 리스트를 순차적으로 저장해둔다.

구현이 간단하지만 디렉토리 내에 파일이 있는지 찾기 위해서는 Linear search가 필요하기 때문에 time-consuming(비효율적)

hash Table

파일의 이름을 그냥 저장하지 않고 해시 함수를 적용해서 저장한다.

해시함수를 적용하면 특정 범위 안으로 값이 바뀐다. 해시함수 결과값에 해당하는 엔트리에 그 파일의 메타데이터를 저장한다.

파일을 찾을 때 파일 이름에 해시함수를 적용한 엔트리만 찾으면 되기 때문에 효율적으로 search 할 수 있다.

해시함수의 특성상 collision이 발생할 수 있다는 가능성이 있다.

file 의 metadata의 보관 위치

• 디렉토리 내에 직접 보관
• 디렉토리에는 포인터를 두고 다른 곳에 보관
  • inode, FAT 등

Long file name의 지원

<file name, file의 메타데이터>의 list에서 각 entry는 일반적으로 고정된 크기이다. file name이 고정 크기의 entry 길이보다 길어지는 경우에는 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법이 있다.

VFS and NFS

사용자가 파일 시스템에 접근하기 위해선 시스템 콜을 해야 한다. 파일 시스템 종류별로 서로 다른 시스템 콜 인터페이스를 써야 한다면 사용자가 혼란스러울 것이다. 따라서 이를 방지하기 위해 개별 파일 시스템 윗 계층에 VFS를 둔다.

VFS(Virtual File System)

다양한 파일 시스템에 대해 사용자 입장에서는 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 운영체제의 layer

NFS(Network File System)

파일 시스템이 로컬 스토리지에 저장될 수도 있지만 원격에 저장되는 경우도 있다. 그럴 경우 NFS를 사용해서 접근해야 한다.

위 그림에서 컴퓨터가 client 컴퓨터와 server 컴퓨터, 이렇게 두대가 있으며 두 컴퓨터가 네트워크로 연결되어 있다.
클라이언트 컴퓨터는 VFS 인터페이스를 써서 로컬 파일 시스템처럼 접근 요청을 하고 NFSclient와 NFS server를 통해 마치 로컬에서 일어난 요청처럼 처리해서 원격에 저장된 파일에 접근할 수 있다.

server와 client 쪽 모두에게 NFS 모듈이 있어야 한다.

Page Cache and Buffer Cache

Page Cache

페이징 시스템에서 사용하는 page frame을 caching 관점에서 말하는 용어이다.
swap area backing store 보다 빠르다.
운영체제에게 주어지는 정보가 지극히 제한적이기 때문에 정확한 접근 시간 등을 알 수 없어 clock alg 를 사용 했다.

Buffer Cache

파일의 데이터를 사용자가 요청 했을 때 디스크에서 운영체제가 읽어온 내용을 자기의 영역 중 일부에 저장해두고 똑같은 파일을 다른 프로세스가 요청하게 되면 다시 읽어오지 않고 운영체제가 저장해둔 걸 바로 전달한다.

이미 파일 데이터가 메모리에 올라와있든 디스크에 있든 간에 파일에 접근하기 위해선 시스템콜을 해야하기 때문에 cpu 제어권이 운영체제에게 넘어와 파일의 요청이 언제 일어났는지 알 수 있다. 그 정보를 이용해서 Replacement alg로 LRU나 LFU를 사용할 수 있다.

Unified Buffer Cache

최근에는 page cache와 buffer cache를 합쳐서 사용한다.

버퍼 캐시도 페이지 단위로 관리한다. 운영체제가 페이지 프레임(물리적 메모리) 관리하는 루틴에 페이지 캐시와 버퍼캐시를 같이 관리한다는 이야기.

합쳐졌다해서 관리 방법이 달라진다는 건 아니다.

memory-Mapped I/O

파일 입출력 방법 중 Read나 write 시스템 콜을 이용하는, 버퍼 캐시를 이용하는 방법이 있고, memory-mapped i/o를 이용해서 접근하는 방법이 있다. 원래는 파일을 오픈한 다음에 read나 write 시스템콜을 사용했다. 그러나 이 방법에서는 file의 일부를 virtual memory 에 mapping 시켜 놓는다. 매핑을 해놓고 나면 그 다음부턴 read, write 시스템 콜을 하는 게 아니라 메모리에 읽고 쓰는 것이다. 그런데 실제로는 파일에 데이터를 읽고 쓰는 효과가 난다.