cs/운영체제

11강 - 2. File System Implementations 1

Tomato_Coffee 2023. 11. 15. 13:52

  • 디스크에 파일을 저장하는 방법은 크게 3가지가 있다.

연속 할당 방법

  • 디스크에 파일을 저장할 때는 동일한 크기의 섹터 단위로 나누어서 데이터를 저장하고 있다.
  • 파일 시스템, 디스크 외부에서 볼 때는 각각의 동일한 크기의 저장 단위를 논리적인 블록이라고 부른다.
  • 임의의 크기인 파일을 동일 크기의 블록 단위로 나누어서 저장하고 있다. (메모리 관리에서 페이징 기법과 유사)
  • Contiguous Allocation
    • 하나의 파일이 디스크상에 연속적으로 저장이 되는 방식이다.

디렉토리 안에 파일이 5개가 있다.

  • 디렉터리란 파일은 디렉터리 밑에 있는 파일들의 메타데이터를 내용으로 한다.
  • Contiguous Allocation의 장단점
    • 장점
      • 빠른 접근 = Fast I/O
        • 디스크 헤드가 한번 이동해서 한꺼번에 많은 데이터를 가져올 수 있다.
          • 같은 트랙에 존재한다고 가정한다.
      • Realtime file, process의 swapping 용으로
      • Direct access(= random access) 가능
    • 단점
      • 외부 조각이 생길 수 있다.
        • 각각의 파일의 길이가 균일하지 않기 때문에 중간에 내용이 들어가 있지 않은 블록들이 있다.
      • 파일의 크기가 커질수있는데, 커지는데 제약이 있을 수 있다.
        • 그러면 미리 빈 공간을 확보해서 대비한다.
        • 그러나 이렇게 미리 할당을 하면 내부조각이 생긴다(낭비). 또한 미리 할당한 크기 이상은 파일이 커질 수 없다.

  • Linked Allocation
    • 빈 위치는 아무데나 들어가서 블록을 배치한다.
    • 장점 
      • 외부조각이 발생하지 않음.
    • 단점
      • Direct access 불가. 순차접근만 가능하다.
      • disk가 seek를 할 때 시간이 많이 걸린다.
  • disk에서 하나의 섹터는 512바이트
    • 컴퓨터에서 디스크를 접근할 때, 디스크의 저장하라는 단위가 512바이트의 배수로 구성이 된다.
    • 포인터에 4바이트 소모. 한 섹터에 저장할 수 있는 데이터의 양은 512 - 4 = 508바이트
      • 포인터 때문에 공간 효율성을 떨어뜨림
  • FAT (File Allocation Table) 
    • Linked allocation 약간 변형

  • 인덱스 블록에 해당 파일이 어디에 저장되어 있는지 정보를 저장한다.
    • 인덱스 블록안에다가 내용으로 적어둔다.
  • 장점
    • 직접 접근 가능
    • 외부 조각이 안생긴다
  • 단점
    • 아무리 작은 파일이라도 블록이 2개가 필요하다
      • 인덱스를 위한 블록 1개,  실제 데이터를 저장하기 위한 블록 1개
      • 파일이 작은 경우에 공간낭비가 있다.
        • 실제로 작은 파일들이 많다.
    • 굉장히 큰 파일일 경우에 하나의 인덱스 블록으로 표시할 수가 없다.
      • 그래서 linked scheme , multil - level index
        • linked scheme
          • 인덱스 블록에 실제 파일의 위치를 적다가 끝까지 채웠음에도 파일의 크기를 커버를 못했을 때, 마지막 인덱스에 또 다른 인덱스 블록을 가리키는 포인터를 넣는다.
        • multi level index
          • 하나의 인덱스 블록이 직접 파일의 위치를 가리키는 게 아니라 또 다른 인덱스를 가리키게 된다.
        • 위에 방법들은 인덱스를 위한 공간 낭비가 있다.

실제 file system에서 어떤 할당 방법을 쓰는가?

  • UNIX 파일시스템의 구조
    • Boot block
      • 어떤 파일 시스템이든 Boot block이 제일 앞에 나온다.
      • 이 파일 시스템에서 운영체제의 커널의 위치를 찾아서 메모리에 올리면 정상적인 부팅 완료
    • Super block
      • 이 파일 시스템에 관한 총체적인 정보를 담고 있다.
        • 어디가 빈 블록, 사용 중인 블록인지 정보
        • Inode list가 어디부터 어디까지 인지(범위 정보)
        • data block이 어디부터 어디까지 인지
    • Inode list(index node)
      • 파일의 메타데이터는 그 파일을 가지고 있는 디렉터리에 기록되어 있다
        • 그러나 실제로 파일 시스템 구현에서는 디렉터리가 메타데이터를 다 가지고 있지 않음
        • 특히 유닉스 파일시스템일 경우에는 디렉터리는 지극히 일부의 메타데이터를 가지고 있다.
        • 실제로 파일의 메타데이터들은 별도의 위치에다가 빼서 보관하고 있다.
        • 그 위치가 Inode list이다.
          • 파일 하나당 inode가 한 개씩 배당이 된다.
          • inode는 그 파일의 메타데이터를 가지고 있다.
          • 그러나 파일의 메타데이터를 전부 가지고 있는 건 아니다.
          • 딱 한 가지
            • 파일의 이름은 디렉터리가 직접 가지고 있다. 나머지는 inode에 저장되어 있다.
          • inode는 크기가 고정되어 있다.
            • 위치 정보를 나타내는 포인터 개수도 유한하다.
            • 그렇지만 가급적 작은 inode를 가지고 굉장히 큰 파일을 표현할 수 있어야 한다.
              • 파일 크기가 작을 때
                • direct block(direct index)만 가지고 그 파일의 위치를 표현할 수 있다.
              • 파일 크기가 클 때
                • indirect를 이용한다.
                  • single indirect
                    • 인덱스 블록을 한번 거쳐서 파일에 접근한다.
                    • 인덱스 블록에는 포인터 블록이 여러 개 들어갈 수 있다.
                      • 포인터 블록은 실제 파일의 내용을 가리킨다.
                    • 인덱스 블록은 data block에 있다.
                  • double indirect
                    • 인덱스 블록을 2번 거쳐서 파일에 접근한다
                  • triple
                    • 인덱스 블록을 3번 거쳐서 파일에 접근

  • FAT File System
    • MS Dos를 만들 때 만들었던 File system
    • 윈도나 모바일에서도 일부 사용되기도 함.
    • 파일의 메타데이터 일부를 FAT에 보관함.
      • 위치정보만 FAT에 저장함.
      • 그 외 모든 정보(해당 파일의 첫 번째 위치도 가지고 있다.)는 디렉터리가 가지고 있다.
    • 이전에 배운 Linked allocation에서는 첫 번째 블록이 끝날 때, 두 번째 블록의 위치를 저장하고 있다.
      • 그러므로 인해서 중간에 bad sector가 발생하면 뒤에 있는 데이터를 찾을 수가 없다.
      • 또한 약간의 크기가 줄어들면  512바이트 sector를 다 활용할 수 없다.
      • 그러면 FAT File System을 위에 문제를 어떻게 해결하나?
        • ex) 위에 그림에서 217번 블록의 다음 위치를 FAT의 별도의 배열에 담아둔다.
        • FAT이라는 테이블(배열)의 크기는 디스크가 관리하는 data block안에 있는 블록의 개수만큼이다.
          • FAT은 이미 메모리에 올라와 있는 상황이다.
        • FAT file system의 장점은 FAT에 배열이 있기 때문에 직접접근이 가능하다.
        • FAT은 중요한 정보이기 때문에 
          • 디스크에 2 copy 이상 복제해 두고 있다. = Reliability 개선
        • FAT은 Linked Allocation의 문제점을 전부 해결할 수 있다.

  • 비어 있는 블록은 어떻게 관리할 것인가?
    • Bit map = Bit vector
      • bit map의 크기는 data block에 있는 블록의 개수만큼 있다.
      • 파일 시스템이 bit map에서 비트를 바꿔주면서 파일을 관리한다.
      • bit map에서의 블록하나는 1bit가 필요하다.
      • 연속적인 빈 블록을 찾는데 효과적이다.

  • Linked list
    • 비어있는 블록들은 연결한다.
    • 비어있는 첫 번째 블록의 위치만 포인터로 가지고 있다.
    • 연속적인 빈 공간을 찾는 게 어렵다.
  • Grouping
    • 인덱스 형식으로 grouping을 해서 빈 블록을 가리킨다.
    • 연속적인 빈 공간을 찾는 게 어렵다
  • Counting
    • [빈 블록의 첫 번째 위치, 거기부터 몇 개가 비어있는지 ] 쌍으로 관리한다.
    • 연속적인 빈 공간을 찾는 게 쉽다.

  • Directory를 어떻게 구현하는가?
    • Directory : 그 디렉터리 밑에 있는 파일의 메타데이터를 관리하는 특별한 파일이다.
    • 그러면 디렉터리 파일의 내용을 어떻게 저장할 것인가?
      • Linear list
        • 파일의 이름, 파일의 메타데이터(크기 고정)
        • 구현은 간단
        • 파일 찾는데 시간이 오래 걸림
      • Hash table
        • 파일의 이름에 해시함수를 적용한다.
        • 효율적인 사용이 가능.

  • 메타 데이터를 보관하는 방법
  • 파일 이름이 길 때
    • 이름이 고정된 entry 보다 길어지는 경우에 포인터를 두어서, 디렉터리 파일의 맨 끝에서부터 파일 이름이 거꾸로 저장된다.

  • Virtual File System(VFS)
    • 사용자가 파일 시스템에 접근할 때는 개발 파일 시스템의 종류와 상관없이 VFS 인터페이스를 사용한다.
    • 사용자 입장에서는 동일한 시스템 콜 인터페이스(API)를 통해서 파일 시스템을 접근할 수 있도록 도와준다. 
  • Network File System (NFS)
    • 원격에 저장되어 있는 파일 시스템을 접근하기

  • Page cache
    • 물리적인 메모리에 있는 page frame을 page cache라고 부른다.
      • swap area(backing store) 보다 빠르다.
    • Virtual memory 시스템 관점에서 page cache라고 부른다.
    • 운영체제에게 주어지는 정보가 제한적이다.
      • cache hit가 나면, 즉 이미 메모리에 존재하는 데이터에 대해서는 하드웨어적인 주소 변환만 한다.
      • 따라서 운영체제는 정확한 접근 시간등 정보를 알 수가 없다.
      • 정보를 알 수 없기 때문에 clock 알고리즘을 사용.
  • Buffer Cache
    • 파일의 데이터를 사용자가 요청했을 때, 운영체제가 읽어놓은 내용을 자신(운영체제)의 영역 중 일부에다가 저장을 해 놓는다.
    • 똑같은 파일 데이터를 다른 친구(프로그램) or 같은 친구(프로그램)가 요청을 하면 디스크까지 가는 게 아니라 buffer cache에서 바로 읽어다 준다.
    • file 시스템 관점에서는 buffer cache라고 부른다.
    • file data가 메모리에 올라와 있든 디스크에 있든 간에 파일을 접근할 때는 시스템 콜을 해야 하기 때문에 cpu 제어권이 운영체제에게 넘어오고, 그 파일에 대한 요청이 언제 일어났는지 cache hit, cache miss가 일어났는지 운영체제가 알 수 있다. 이렇게 얻은 정보를 바탕으로 LRU, LFU 알고리즘을 사용할 수 있다.
  • Unified Buffer Cache
    • 최근에는 Page cache, Buffer Cache를 합쳐서 같이 관리를 하는 운영체제가 많다.
      • ex) 리눅스
    • Buffer cache를 page 단위로 관리를 한다.
    • 운영체제에서 물리적인 메모리를 관리하는 루틴에 page cache, buffer cache를 같이 관리를 한다.
  • Memory Mapped I/O
    • 파일 입출력을 하는 방법 중에서 Buffer cache를 이용하는 즉, read/write  system call를 이용해서 파일을 접근하는 방법과 Memory Mapped I/O를 통해서 파일을 접근하는 방법이 있다.
    • Memory Mapped I/O란?
      • 파일의 일정 부분을 해당 프로그램의  메모리 영역에다가 Mapping을 시킨다.
      • read/write system call를 하는 게 아니라 메모리에다 읽고 쓴다
        • 실제로는 파일에다가 읽고 쓰게 하는 효과가 있다.

  • page 크기 : 4KB
  • Block 크기 : 512B
  • 최근에는 page cache, buffer cache 가 합쳐짐
    • 버퍼 캐시에서도 페이지 크기(4KB)로 블록들을 관리한다.
  • 가상 메모리 기법에서 쓰는 swap 영역은 빠르게 데이터를 내려놓고, 올려야 하기 때문에 여러 개의 블록(4KB)들을 모아서 하나씩 메모리에 올리거나 내린다.
    • 여러개의 페이지를 한꺼번에 올리거나 내린다.(속도 효율성을 위해)
저작자표시 비영리 변경금지 (새창열림)