File System Implementation

https://core.ewha.ac.kr/publicview/C0101020140520134614002164?vmode=f

반효경 [운영체제] 25. File System Implementations 1

 

디스크에 접근하는 방법 중 순차접근과 직접접근이 있다.

직접접근이 가능한 매체더라도 데이터를 어떻게 관리하느냐에 따라 순차접근만 허용할 수도 있다. 

 

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

Contiguous Allocation

파일의 크기는 동일하지 않다. 디스크에 파일을 저장할 때는 보통 동일한 크기의 섹터 단위로 나눠서 저장한다. 

이러한 동일한 크기의 단위를 논리적인 블록이라고 부른다. 

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

예를 들어 블록 6개로 이루어진 파일이면 19~24번으로 연속적으로 저장된다. 

디렉토리라는 파일은 디렉토리 하위의  파일들의 메타데이터를 내용으로 갖는다. 파일의 이름, 파일의 시작 위치, 파일의 길이 등을 갖고 있다. 

 

단점

• 각 파일들의 길이가 균일하지 않기 때문에 외부 조각이 생긴다. 
• 파일 grow가 어렵다. 
  • 파일은 수정되어 크기가 커질 수 있다. 뒤에 남은 공간을 넘어서서 파일을 키울 수 없다
  • 파일이 커질 것을 대비해서 미리 빈 공간을 확보해 놓을 수 있다. 
    • 이 방식은 내부조각이 발생한다. (할당되었는데 아직 사용되지 않은 공간

장점

• 빠른 IO가 가능하다.
  • 하드디스크 같은 매체는 대부분의 접근시간이 헤드가 이동하는 시간이다. 
  • 한번의 seek/rotation으로 많은 바이트 transfer
  • 파일시스템 용도 말고 스왑 에어리어로 사용할 때 유용하다. 공간효율성보다 속도효율성이 더 중요하기 때문이다. 
• 직접접근이 가능하다. 연속적으로 저장되어 있기 때문에 시작 주소로부터 보고싶은 위치만큼 더하면 된다. 

Linked Allocation

contigous allocation의 단점은 중간중간에 홀이 생기는 것이다. 

Linked Allocation에서는 블록을 연속적으로 저장하지 않고 빈 공간 아무데나 저장할 수 있다. 

각 블록에 다음 블록을 적어 놓는 방식으로 연결한다. 마지막에는 끝났다고 표시한다. 

파일의 시작 위치만 디렉토리가 가지고 있다. 다음 위치들은 실제 그 위치에 가야 확인할 수 있다. 

• 장점
  • 외부조각이 발생하지 않음 
• 단점 
  • 직접접근이 불가능하다. 앞의 블록을 먼저 접근해야 다음 블록의 위치를 알 수 있기 때문이다. 
  • 각 블록에 대해 디스크 헤드가 seek해서 이동해야 한다. 따라서 시간이 오래 걸린다. 
  • Reliability 문제 
    • 하나의 섹터가 bad sector면 그 다음 섹터들은 전부 접근이 불가능해진다. 
  • 블록(일반적으로 512바이트)에 포인터를 위한 공간(4바이트)가 필요하다. 공간 효율성이 떨어진다 
• 변형
  • FAT file allocation table 파일 시스템 
    • 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제를 해결한 것이다.

Indexed Allocation

인덱스 블록에 각 블록의 위치가 어딘지 열거해놓는다. 

인덱스 블록을 참고해서 직접 접근이 가능하다. 

장점

• 외부 조각이 발생하지 않는다. 비어있는 위치 어디든 활용가능하기 때문이다.
• 직접접근이 가능하다.

단점

• 아무리 작은 파일이더라도 블록이 2개 필요하다. 인덱스를 위한 블록 1개가 필요하기 때문이다. 공간 낭비가 발생한다.
• 너무 큰 파일은 하나의 인덱스 블록으로 모든 블록의 위치를 나타내지 못한다. 아래 두가지 방법으로 해결한다.  
  • Linked scheme : 인덱스 블록의 맨 끝에 또다른 인덱스 블록을 가리키게 한다. 
  • 멀티레벨인덱스 : 2단계 페이지 테이블처럼 두번 거쳐서 가리키게 한다던지.. 

지금까지 다룬 내용들은 이론적인 내용들이다. 실제 파일시스템에서는 어떻게 할당할까 ? 

 

유닉스 파일시스템 

유닉스 파일시스템 구조

가장 기본적인 파일시스템 구조이다. 

부트블록, 슈퍼블록, 아이노드리스트, 데이터블록 4가지로 구성된다.

부트블록

부팅에 필요한 정보, bootstrap loader, 어떤 파일 시스템이던 맨 앞에 위치하기로 약속

슈퍼블록

파일 시스템에 관한 총체적인 정보를 담고 있다. 

어디가 빈 블록이고, 어디가 실제로 파일이 저장된 사용중인 블록인지

어디가 아이노드 리스트고 어디가 데이터블록인지 등 ..

아이노드 리스트

파일의 메타데이터는 디렉토리에서는 일부만 갖고 있는다. 

아이노드 리스트에서 파일의 메타데이터를 갖고 있다. 아이노드는 인덱스노드다.

파일 하나당 아이노드가 하나씩 할당된다. 그 파일의 메타데이터를 가지고 있다. (소유주, 접근권한, 위치정보 등 .. )

아이노드는 파일 이름을 제외한 모든 메타데이터를 저장하고 있다. 

파일 이름은 디렉토리가 직접 가지고 있다. 그리고 아이노드 번호를 갖고 있어서 아이노드리스트에서 참조해서 나머지 메타데이터를 얻을 수 있다. 

 

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

인덱스 얼로케이션을 번형해서 사용한다. 아이노드는 크기가 고정되어 있다. 하지만 큰 파일의 위치정보도 표현할 수 있어야 한다. 

direct blocks, single indirect, double indirect, triple indirect 4가지를 사용해서 파일 위치정보를 표현한다. 

파일 크기가 작으면 direct blocks를 사용한다. 이것만으로 충분하기 때문이다. 

큰 파일은 indirect를 이용한다. single indirect의 경우 주소를 따라가면 인덱스 블록이 있고, 그 블록에 실제 파일의 내용을 가리키는 포인터들이 있다. 

더 큰 파일이면 더블 인다이렉트, 파일이 엄청 크면 트리플 인다이렉트를 사용한다. 

데이터블록

파일의 실제 데이터 보관

 

FAT 파일 시스템 

윈도우즈 계열에서 일부 사용

 부트블록

위와 동일

FAT

파일의 메타데이터중 위치정보만 FAT에 따로 빼놓는다.  나머지 메타디에터는 디렉토리가 가지고 있다. 

파일의 첫번째 위치가 어딘지도 디렉토리가 갖고 있다. 

블록에 다음 블록의 주소를 적어놓는 것이 아니라 FAT에 적는다.

즉 FAT[217]에 적혀있는 값은 217의 다음 블록이 어딘지 의미한다. 

EOF는 그 파일이 끝났다는 것을 의미한다. 

FAT만 확인하면 그 파일의 다음 위치를 알 수 있다. 즉 직접접근이 가능하다. 

FAT은 이미 메모리에 올라가 있고 FAT에서 n번째 블록을 보고 싶으면 그 횟수만큼 FAT에서 따라가며 확인하면 된다. 

즉 Linked allocation의 단점을 해결하는 방법이다. 포인터가 유실되더라도 FAT에서 나머지를 확인할 수 있고, 데이터랑 FAT은 완전히 분리되어있다. 

 

---

실제로는 훨씬 많은 종류의 파일 시스템이 있으며, 유닉스나 FAT 파일 시스템같은 기본적인 파일 시스템을 개선해서 사용한다. 

 

Free Space Management

메모리에 블록을 할당하면서 비어있는 블록들은 어떻게 관리할까? 4가지 방법이 있다. 

 

Bit Map or bit vector 

i번째 블록이 free인지 occupied인지 각각 0,1 비트값으로 표현한다. 

비트맵의 크기는 데이터 블록에 있는 블록의 개수가 되겠다. 

비트맵을 위한 부가적인 공간이 필요하다. 한 블록당 1비트만 있으면 되므로 그렇게 많은 공간이 필요한 것은 아니다.

장점으로는 연속적인 n개의 빈 블록을 찾는데 효과적이다. 

연속할당을 쓰지 않더라도 가능하면 연속적인 빈 공간에 할당을 하는 것이 좋다. 디스크 헤드의 이동을 최소화 할 수 있기 때문이다. 비트맵은 비트맵을 스캔하면서 연속적으로 0인 공간을 찾기가 좋아서 이런 작업에 적합하다.

 

LinkedList

링크드리스트로 free space 관리

모든 비어있는 블록들을 링크로 연결하는 것이다. 

어차피 비어있는 블록이므로 해당 블록에 포인터로 다음으로 비어있는 블록은 어딘지 표시할 수 있다. 

단점으로는 연속적으로 비어있는 공간을 찾는데는 부적합하다. 장점은 공간 낭비가 발생하지 않는다.

Grouping

첫번째 빈 블록에 비어있는 블록들의 포인터를 갖는다. 마지막 칸에는 빈 블록이 더 있다면 또 다른 포인터들을 갖고있는 블록을 가리킨다

링크드리스트 방법을 변형한것이다.  

빈 블록에 빈 블록들을 가리키는 포인터를 넣는다. 블록 하나로 부족하면 그 블록의 마지막에 또 다른 포인터를 넣어놓은 블록을 가리키도록 한다. 

역시 연속적인 빈 블록을 찾는데는 효과적이지 않다. 

 

Counting

이 방법은 연속적인 빈 블록을 찾는데 효과적이다. 

(빈 블록의 첫번쨰 위치, 위치로부터 연속적인 빈 블록의 개수)를 쌍으로 관리한다.

즉 빈 블록의 위치를 가리키고 거기서부터 몇개가 비어있는지를 관리한다. 그러면 연속적으로 n개가 비어있는 블록을 찾고 싶으면 두번째 갚이 n개 이상인 것을 서치하면 된다. 

 

디렉토리 구현 

디렉토리는 디렉토리 하위의 파일들의 메타데이터를 관리하는 특별한 파일이다. 

디렉토리 파일의 내용을 어떻게 저장할까?

 

Linear List

디렉토리 파일을 <파일 이름, 파일의 메타데이터> 로 순차적으로 저장한다

메타데이터를 고정 길이로 관리한다. 접근권한 9비트, 사이즈 몇바이트,..와 같이 고정시켜 관리한다는 뜻이다.

디렉토리에서 어떤 파일이 있는지 찾는 연산을 하면 각 필드의 길이가 몇인지 알기 때문에 원하는 메타데이터를 순차적으로 찾을 수 있다. 

구현이 간단하지만 디렉토리 내에서 파일을 찾기 위해서는 선형탐색을 해야 한다. 즉 시간 면에서 비효율적이다.

 

Hash Table

해시테이블 방식은 파일의 이름에 해시함수를 적용해서 저장하는 것이다. 

파일 이름에 대한 해시값이 특정 범위 안의 숫자로 한정이 된다. 

해시함수 결과값에 해당하는 엔트리에 그 파일의 메타데이터를 저장한다. 

파일을 찾을 때 순차적으로 찾을 필요 없이 해시함수를 적용하고 해시함수의 결과값에 해당하는 엔트리만 찾아보면 된다. 

따라서 search time이 감소해서 시간적으로 효율적이다. 

반면에 collision이 발생할 수 있다. 서로 다른 파일의 이름에 대해서 해시 값이 같은 결과가 될 수 있기 때문이다.

충돌에 대한 해결 방법은 자료구조 수업에서 배우시오.. (그 다음 엔트리에 넣는다던가 등)

 

메타데이터 보관 위치 

메타데이터는 일부는 디렉토리에 직접 보관하고 일부는 파일 시스템에서 다른 곳에 별도로 보관한다. 

유닉스에서는 inode가, FAT 파일 시스템에서는 FAT이 그 역할이다.

 

긴 파일 이름 지원

대부분의 메타데이터는 길이가 한정되어 있다. 접근권한 9비트, 이런 식으로 .. 

파일 이름이 문제다. 파일 이름 길이는 정해진 것이 아니기 때문이다. 

파일 이름을 제한하면 되지만 이것 또한 비효율적이다. 긴 파일 이름을 지원해야 한다. 하지만 엔트리의 크기는 제한되어 있다. 

해결방법

파일 이름을 다 저장하는 것이 아니라, 파일 이름이 길면 포인터를 둔다. 

포인터는 디렉토리 파일의 맨 끝을 가리키고 맨 끝에서부터 긴 파일 이름이 저장된다. 

4글자까지 저장이 가능한데 파일 이름이 aaabb라면, aaa까지 저장한다.  (공간 하나는 포인터로 쓰기 위해서)

포인터가 가리키는 곳을 가보면 bb가 있다. 

짧은 파일 이름인 경우는 그냥 저장하면 된다. 

 

VFS, NFS

VFS는 virtual file system

nfs와 vfs, 클라이언트 PC와 서버 PC가 있고 네트워크로 연결되어 있다

 

파일 시스템의 종류는 실제로 많다. 유닉스는 fast file system, ext 4, 어쩌구.. 

사용자가 파일 시스템에 접근할 때는 시스템 콜을 한다. OS에게 파일 시스템 접근을 위한 시스템 콜을 한다. 

파일 시스템 종류 별로 다른 파일 시스템 콜 인터페이스를 써야 하면 사용자가 혼란스러울 것이다. 

어떤 파일 시스템이 실제로 사용되는지 상관 없이 개별 파일 시스템 윗 계층에 VFS 인터페이스를 두는 것이다.

사용자가 파일 시스템에 접근할 때는 파일 시스템 종류에 상관 없이 VFS 인터페이스 API를 사용해 접근하는 것이다.

 

NFS는 network file system

원격의 파일 시스템에 접근할 때도 있다. 이때는 NFS를 사용한다. 

즉 원격 PC에 접근할 때는 NFS 인터페이스를 사용하는 것이다. 

클라이언트가 VFS로 서버의 파일시스템에 접근하려고 하면 NFS 클라이언트가 작동해서 원격으로 접근해서 네트워크를 통해서 접근한다. 서버에서도 이것을 받는 인터페이스와 NFS 서버가 있어서 작동한다.

서버 쪽 클라이언트 쪽에 각각 NFS 모듈이 있어야 한다. 

 

페이지 캐시와 버퍼 캐시

페이지 캐시

버츄얼메모리의 페이징 시스템에서 사용하는 물리적인 메모리의 페이지 프레임을 캐시의 관점에서 설명한 것이다.

swap area, backing store보다 빠르기 때문이다. 

OS에게 주어지는 정보가 제한적이다. 캐시 히트에 대해서는 HW만 작동하기 때문에 정확한 정보를 알 수 없다. 그래서 clock 알고리즘 등을 사용한다. 

 

버퍼 캐시 

파일의 데이터를 사용자가 요청했을 때 디스크에서 읽어서 사용자한테만 전달하고 끝나는 것이 아니라 OS의 영역 중 일부에 저장해놓고(캐시하고) 똑같은 요청에 대해 버퍼 캐시에서 바로 읽어다 주는 것이다. 

버퍼 캐시는 파일이 메모리에 올라와 있던 디스크에 있던 간에 시스템 콜로 인해 CPU가 OS에게 넘어가서 모든 경우에 대해 (캐시 히트던 미스던) OS가 정보를 알 수 있어 LRU 등의 알고리즘을 사용할 수 있다. 

 

Unified Buffer Cache

최근에는 페이지 캐시와 버퍼 캐시를 합쳐서 관리하는 추세다. 유닉스도 이렇게 한다. 

버퍼 캐시도 페이지 단위로 관리한다는 것이다. 그리고 OS에서 페이지 프레임을 관리하는 루틴에 페이지 캐시랑 버퍼 캐시를 같이 관리한다. 

 

Memory Mapped I/O

시스템콜을 이용해서 파일에 접근할 수도 있고 메모리 맵드 IO를 활용할 수도 있다. 

원래는 파일을 open하고 read나 wrtie 시스템 콜을 통해 접근한다. 

메모리 맵드 IO는 파일의 일정 부분을 프로세스의 메모리 영역에 매핑을 시켜놓고 쓰는 것이다.

매핑을 하고 나면 그 다음부터는 시스템 콜을 하지 않아도 되고, 메모리에 읽고 쓰는 것처럼 사용할 수 있다. 

커널 메모리 영역에 버퍼 캐시가 있어서 파일의 내용을 읽어와서 사용자에게 전달 

페이지는 보통 4KB이고 블록 하나는 512바이트로 구성된다. 

최근에는 버퍼 캐시- 페이지 캐시가 합쳐져서 버퍼 캐시에서도 4KB단위로 블록을 관리한다. 

 

가상 메모리 기법에서 사용하는 스왑 에리어는 빠르게 데이터를 올리고 내려야 하기 때문에 여러개의 블록을 모아서 4KB 단위로 올려놓거나 내려놓는다. 더 크게 여러개의 페이지를 한번에 올리고 내릴 수도 있다. (속도 효율성을 위함)

---

위 내용 다시 정리

페이지 캐시의 단위는 페이지 단위 4키로바이트, 버퍼 캐시의 단위는 블록 단위인데(섹터, 논리적인 블록) 512바이트이다.

 최근에는 버퍼캐시와 페이지캐시가 통합되면서 버퍼캐시에서 사용하는 단위도 작은 크기의 블록이 아닌 4키로바이트 단위의 페이지단위를 사용하도록 변경되었다. 

즉 버퍼 캐시와 페이지 캐시로 구분하지 않고 4KB의 페이지 단위로 관리한다. 

파일 입출력을 위한 공간이 필요하면 페이지 캐시를 버퍼 캐시 용도로 쓴다.  프로세스 주소 공간으로 필요하면 페이지 캐시로 쓴다. 필요할 때 용도에 맞게 할당해서 쓴다. 

 

메모리 맵드 IO는 파일의 일부를 버츄얼 메모리에 매핑시키는 것이다. 매핑하고 나면 시스템 콜로 파일에 접근할 필요 없이 메모리 접근으로 가져다 쓸 수 있다. 

 

 

파일에 IO는 두가지 방법으로 가능하다.

리드, 라이트 시스템 콜을 사용하면 캐시 히트하면 캐시에서 바로 가져다 주고, 캐시에 없으면 파일 시스템에서 읽어서 가져온다. 읽은 것을 먼저 OS의 캐시에 저장하고 프로세스에게 복제해준다. 

 

다른 방식은 메모리 맵드 IO이다. 처음에는 역시 메모리 맵드 IO를 하겠다는 시스템 콜을 해줘야 한다. 자신의 주소공간 중 일부를 파일에 매핑한다. 매핑을 하더라도 디스크에 있는 파일을 버퍼캐시로 읽어오는 것 까지는 똑같다. 읽어오고 그 내용을 페이지캐시에 카피한다. 페이지 캐시의 내용이 매핑 된 내용이 되는것이다. 

파일에 읽고 쓰는 요청을 하면 매핑된 곳에 메모리에 접근하듯이 요청하면 된다. 

즉 운영체제의 간섭 없이 내 메모리 영역에 접근하는 것 처럼 파일 입출력을 할 수 있다. 단 맵만 해놓고 읽어오지 않았으면 페이지 폴트가 발생한다. 

즉 시스템 콜을 이용한 방법은 내용이 버퍼캐시에 있던 없던 OS에 요청을 해서 받아와야 한다. 반면 메모리 맵드 방식을 사용하면 일단 페이지 캐시에 올라온 맵핑된 내용은 OS의 도움 없이 사용자 프로그램이 자신의 메모리 공간에 접근하는 것처럼 IO를 할 수 있다. 

메모리 매핑을 사용하는 이유는 이미 메모리에 올라온 내용에 대해 OS의 도움을 받지 않고 리드, 라이트가 가능하다는 것이 장점이다. 

기존의 버퍼 캐시를 사용하면(왼쪽그림) 파일 입출력을 하려면 버퍼 캐시를 거쳐가야 한다. 버퍼캐시의 내용을 페이지캐시에 복제해야 하는 오버헤드가 있다. 

유니파이드 버퍼 캐시를 사용하면(오른쪽 그림) 경로가 더 단순화된다. 리드 라이트 시스템 콜은 버퍼에 매핑이 되어있던 안되어 있던 OS에게 시스템 콜을 해야 한다. 메모리에 없는 내용은 디스크의 파일 시스템에서 읽어와서 버퍼로 복사 후 사용자 프로세스에게 복사해서 전달하고, 있는 내용은 캐시에서 복사해서 전달한다. 

메모리 맵드 IO를 하면 운영체제한테 주소영역 중 일부를 파일에 매핑하는 단계를 거치고 나면 사용자 프로그램의 주소 영역에 페이지 캐시가 매핑된 것이다. 매핑이 되고 나서는 페이지 캐시에 직접 읽고 쓰고 할 수 있게 된다. 

버퍼캐시가 별도로 존재하는 것이 아니라 통합되서 사용한다. 

 

과거에 배운 내용을 리마인드 해보자. 

실행파일을 실행시키면 프로세스가 된다. 프로세스의 독자적인 주소공간(버추얼메모리)가 만들어진다.

주소변환을 해주는 hw에 의해 당장 필요한 부분을 물리적인 메모리에 올리고, 쫓겨나는 내용들은 스왑 에어리어로 간다.

이 때 간과한 것이 코드 부분이다. 코드 부분은 쫓겨날 때 스왑 에어리어로 내려가지 않

는다.

코드는 리드 온리이다. 파일 시스템에 실행 파일 형태로 이미 저장이 되어 있다. 

메모리 맵드 IO가 이 코드 영역에 대해 사용된다. 파일시스템에 실행파일이 있고, 버츄얼메모리의 코드 부분에 매핑이 되어서 사용된다. 

실행파일도 파일시스템에 저장되어있지만 데이터파일도 저장되어 있다. 

메모리 맵드 IO로 접근할 수도 있다. 리드라이트 시스템콜이 아닌 메모리맵드 방식으로 접근하고 싶으면 프로세스가 OS에게 데이터 파일의 일부를 내 주소공간에 매핑해달라고 시스템 콜을 한다. 

OS가 데이터파 일의일부를 프로그램의 주소공간에 매핑을 한다. 

프로그램이 실행되면서 메모리 위치를 접근했을 때 그 내용이 메모리에 안 올라가 있으면 페이지 폴트가 난다. 

폴트가 나서 OS에 의해 페이지에 올리고 나면 그때부터는 매핑이 된다. OS의 도움을 받지 않고 리드라이트를 할 수 있다. 

나중에 스왑아웃 될 때는 역시 메모리맵드된 내용이므로 스왑에어리어로 내보내는 것이 아니라 파일시스템에 써줘야한다.

 

다른 프로세스에게 동시에 매핑을 해줄 수도 있다. 

시스템 콜을 해서 사용할 수도 있다. 그러면 OS는 그 내용을 자신의 버퍼 캐시에 먼저 읽어온다. 그런데 유니파이드 캐시를 사용하는 경우 다른 프로세스가 이미 해당 내용을 물리 메모리에 올려놓고 매핑해서 사용하고 있었을 수 있다.

그 경우 해당 페이지는 매핑됨과 동시에 버퍼 캐시의 역할도 수행하기 때문에 해당 캐시에서 복사해서 프로세스에게 제공해주면 된다. 

 

정리하자면 사용자가 파일에 접근하는 인터페이스는 r/w 시스템콜과 메모리 맵드 IO가 있다. 

리드라이트 시스템 콜을 이용하면 캐시의 내용을 복사해서 프로세스의 주소공간에 전달한다.

메모리맵드IO를 쓰면 물리 메모리의 내용을 버츄얼메모리에 매핑하버리는 것이다. 

메모리맵드 IO를 쓰면 일단 메모리에 올라온 파일은 시스템 콜을 하지 않고 자신이 CPU를 가지고 있으면서 직접 접근할 수 있어서 빠르다는 장점이 있다. 또한 캐시의 내용을 자신의 주소공간으로 카피하는 오버헤드도 없다. 

즉 한번의 메모리 copy가 줄어들고, 이미 메모리에 올라와 있는 내용은 OS의 도움을 받을 필요가 없다.

단점으로는 버퍼 캐시를 매핑하는 것이기 때문에 다른 프로세스도 share해서 사용하게 되면 일관성 문제가 발생할 수 있다. 리드라이트 시스템 콜을 쓰는 경우는 copy하는 것이기 때문에 이런 문제가 없다.