[운영체제] 디스크 공간할당

디스크 공간할당

• 프로그램 파일, 데이터 파일, 디렉토리 파일 모두 파일이며, 파일은 저장장치에 블록 단위로 산재되어 저장된다.
• 이를 최대한 효율적으로 저장해야 파일 입출력의 속도를 높일 수 있다.
• 이처럼 디스크에 파일을 저장할 때 파일의 블록들의 배치를 결정하는 것이 디스크 공간할당이다.
• 디스크 공간할당은 연속 할당과 불연속 할당으로 나누어진다.
• 연속 할당 : 임의의 한 파일을 위해 디스크 내에 선형적으로 연속된 블록을 할당.
• 불연속 할당 : 임의의 한 파일을 위해 디스크 내에 산재된 블록을 연결해 할당, 블록이 디스크 내 어디에 있어도 액세스 가능.
• 불연속 할당을 구현하는 방법으로는 연결 할당, 색인 할당, 간접 색인이 있다. 간접 색인도 멀티레벨 색인과 혹합 색인으로 나누어진다.

연속 할당

• 연속할당 시 한 작업에서 디스크에 접근한다고 가정했을 때 블록 b 다음에 블록 b+1에 접근하므로 일반적으로 헤드를 이동하지 않아도 된다. (하나의 트랙을 넘어서게 된다해도 하나의 트랙만 이동하면 된다.)
• 따라서 연속할당되는 파일을 접근하기 위해 필요한 디스크의 탐색횟수를 최소화할 수 있다. 만약 탐색이 필요해도 해당 시간을 최소화할 수 있다.
• 한 파일의 연속 할당은 디스크의 주소와 블록단위의 길이로 정의된다. 파일의 길이가 n블록이고, 블록 b에서 시작한다면 이 파일은 b+n-1까지 연속된 블록을 차지하게 된다. 각 파일을 위한 디렉토리는 해당 파일의 시작 블록 주소와 파일의 길이만 표시하면 된다.
• 이렇게 연속적으로 할당된 파일을 접근하려면 파일 시스템을 최근 참조되었던 주소를 가지고 있다가 필요할 때 다음 블록을 읽기만하면 된다. 블록 b에서 시작하는 파일의 i번째 블록은 블록 b+i로 즉시 접근할 수 있다. 즉, 연속할당 기법은 순차접근이면서 직접접근을 동시에 지원한다.
• 장점 : 연속하는 논리적 블록들이 물리적으로 인접해있어 빠른 액세스가 가능하고, 디렉토리가 단순히 시작블록 주소와 파일의 길이만 파악하고 있으면 되므로 디렉토리 구현의 단순화가 가능하다.
• 단점 : 새로운 파일을 생성할 때 필요 공간을 미리 명시하고, 그만큼 연속 공간이 확보되지 않으면 생성이 불가능하다. 일정 파일이 사용 중 할당된 공간보다 커지면 해당 파일이 들어갈 수 있는 새로운 영역을 찾아 옮겨야 한다. 이러한 과정에서 외부단편화와 내부단편화가 동시에 발생할 수도 있다. 디렉토리 구현이 단순해 보이기도 하지만 파일의 크기가 계속 변한다고 가정할 경우 구현이 복잡해진다.

연결 할당

• 리스트 혹은 인덱싱 방법을 이용한다.
• 리스트를 사용할 경우 하나의 블록은 디스크 상 섹터로 대응되지만 임의의 한 파일에 속해 있는 여러 섹터들이 포인터로 서로 연결된다.
• 예를 들어 디렉토리 파일에 jeep이라는 파일명, 그리고 해당 파일이 연결리스트의 시작이 9번 블록부터 이어지고 마지막은 25번이라는 정보만 존재한다. 리스트 형성은 각 블록이 리스트 상 다음 블록 번호를 지정함으로서 이루어진다. 예를 들면 9-16-1-10-25 순서로 연결될 수 있다. 각 블록은 다음 블록을 가리키는 포인터를 포함하기 때문에 해당 정보만큼은 사용자가 정보를 저장할 수 없게 된다. (ex. 512 - 4 = 508B만 사용)
• 빈 파일의 경우 start는 -1을 가지고, end는 0으로 설정된다.
• 파일 쓰기가 이루어지면 자유블록을 하나 할당받아 연결리스트 끝에 추가한다. 해당 블록이 최초의 블록이라면 이 블록 번호가 디렉토리의 start와 end필드에 똑같이 기록된다.
• 장점 : 파일을 확장할 때도 자유공간 리스트로부터 블록을 얻어 연결리스트에 추가하면 되고, 파일이 축소되면 사용하지 않게 되는 블록을 자유공간리스트로 반납하면 되므로 단편화가 발생하지 않고 압축도 불필요해진다.
• 단점 : 한 파일 내에서 논리적으로 연속된 블록들의 검색에 시간이 소요되고, 연결리스트 구조 유지를 위해 포인터를 할당하고 해제하는 등의 작업에서 시간 및 공간이 필요하다. 또한 오류나 하드웨어 고장으로 인해 하나의 포인터를 잃어버리거나 잘못된 포인터값을 가지게 되면 모든 데이터를 잃어버릴 수 있다. (이중 연결리스트를 사용하거나 각 블록마다 파일 이름 및 상대블록 번호를 저장하는 등의 방식으로 보완할 수도 있으나 이 역시 오버헤드가 발생할 수 있다.)

FAT(File Access Table)

• FAT : 파티션의 시작 부분에 위치해, FAT의 각 테이블 항목이 디스크의 각 블록에 하나씩 대응된다.
• 디렉토리 항목은 각 파일의 첫번째 블록 번호를 보유한다. 해당 블록번호를 FAT 테이블에 대응하면 다음 블록의 블록번호를 가리키게 된다. 이러한 사슬이 마지막 블록까지 이어진다. (마지막 블록은 파일의 끝을 나타내는 특수값을 보유한다.)
• 새로운 블록 할당 시엔 값이 0인 테이블 항을 찾아 이전 사슬의 끝 값을 해당 블록 주소로 대체하고, 해당 테이블 항에는 파일의 끝을 나타내는 특수 값을 넣어주면 된다.
• FAT가 캐시되지 않으면 상당 수의 디스크 탐색을 유발하기 때문에 주의해야 한다. FAT를 읽기 위해서는 디스크 헤드를 반드시 파티션 시작부분으로 움직여 찾고자하는 블록 주소를 알아내야 한다. 그리고 이어서 블록이 있는 곳으로 다시 이동한다. 최악의 경우 블록 탐색마다 두번의 이동이 발생하는 것이다.
• 물론 무작위 접근 시간이 개선되어 디스크 헤드가 FAT의 정보를 읽어 임의의 블록 위치를 알아낼 수 있다는 장점은 있다.

색인 할당

• 색인 블록에 디스크 블록 포인터(섹터 주소)를 모아둠으로써 포인터가 산재되어 비효율적 연결 할당의 단점을 해결한다.
• 색인 블록의 i번째 항목은 i번째 블록을 가리킨다. 따라서 i 번째 블록을 읽기 위해서는 색인블록의 i번쨰 항목에서 포인터를 얻어서 접근해야 한다.
• 각 파일은 해당 파일을 구성하는 디스크 섹터들의 주소로 이루어진 자신만의 색인 블록을 소유한다. 색인 블록의 기능은 메모리 경영에서 페이지 테이블의 기능과 유사하다.
• 디렉토리는 그 디렉토리에 속한 각 파일의 색인 블록에 대한 포인터를 소유한다.
• 예를 들어 디렉토리 파일이 jeep이라는 파일명과 색인 블록 19번의 정보를 보유한다고 하자. 그럼 색인블록에는 jeep 파일을 구성하는 섹터들의 주소, 예를 들면 9, 16, 1, 10, 25가 순서대로 기록되어 인덱싱해주고 있는 것이다. 파일이 생성될 때 색인 블록의 모든 포인터는 -1로 설정된다. i번째 블록이 처음 쓰여지면 자유공간 관리자로부터 한 블록을 받아 그 주소를 색인블록의 i번째 항을 기록한다.
• 장점 : 탐색이 색인 블록 자체에서 일어나 빠르다. (이러한 장점을 살리기 위해 색인 블록을 주기억 장치에 로딩시켜 놓는다.)
• 단점 : 블록을 삽입하려 할 때 색인 블록을 완전히 재구성해야 한다. 보통의 경우 색인 블록으로 한 섹터를 잡아주는데, 작은 파일의 경우 대부분 비워둔채 사용하므로 기억장치가 낭비된다. 또한 색인 블록이 색인할 수 있는 블록의 개수를 초과하는 큰 파일은 처리할 수 없다.

간접색인

• 색인 할당의 파일 크기 제한을 해결하는 방법 중 하나가 간접색인을 이용하는 것이다.
• 간접색인 : 상위 색인파일이 하위 색인파일을 인덱싱하는 것. 간접색인을 하지 않은 경우를 다이렉트 블록이라 하고, 간접색인을 한 단계만 할 경우 single indirect,두 단계 할 경우 double indirect, 세 단계 할 경우 triple indirect라고 한다. 간접 색인의 단계가 증가할수록 저장 파일의 크기가 커진다. 이처럼 다이렉트 블록과 간접 색인을 모두 사용하는 방식을 혼합색인 방식이라고 한다.
• 리눅스에서는 파일마다 inode라는 구조체를 둔다. 이 inode에는 해당 파일의 파일 모드, 소유자, 변경시점, 블록크기, 블록 개수 등 다양한 정보가 저장되어 있다. 또한 혼합색인을 위해 12개의 다이렉트 블록과 3개의 간접 색인 블록을 갖는다. 이 3개의 간접 색인 블록은 각각 ingle indirect, double indirect, triple indirect를 위한 블록들로 하위 간접블록들을 포인팅한다.
• 이렇게 구성할 경우 작은 파일 혹은 파일 중 자주 접근하는 블록은 다이렉트 블록에 할당하여 속도를 높이고, 아울러 용량이 커지면 간접색인의 단계를 높여 블록들을 할당함으로써 매우 큰 용량의 파일도 저장할 수 있게 된다.

빈 공간 관리

• 디스크 공간은 기본적으로 제한되어 있기 때문에 삭제된 파일들이 차지하던 공간을 새로운 파일들이 사용할 수 있도록 해야한다. 빈 공간 관리는 이렇게 디스크 상의 공간(블록)을 할당하고 회수하여 관리하는 작업이다.
• 빈 공간 관리는 주기억 장치에서 가변 분할 기법에 의한 기억 공간 할당 방법과 유사하다. 즉, 파일들이 디스크 공간을 할당받고 남은 공간을 비워둔채로 방치하면 작업공간의 단편화가 발생한다.
• 하지만 파일 입출력의 평균 속도를 높이려면 가급적 한 파일의 블록들은 인접해 있을수록 좋다. 만약 단편화가 너무 심해지다보면 어떤 파일의 블록들은 인접하게 배치할 수 없게 된다. 따라서 단편화된 공간을 주기적으로 압축할 필요가 있다.
• 이를 위해 빈공간의 리스트를 다루는 자료구조가 필요해진다.

빈 공간 관리 방법

• 연결 리스트 : 자유공간을 리스트로 유지하고 관리한다. free-space list head 라는 커널 내 변수를 통해 제일 처음 나오는 빈 공간에 대한 포인터를 보유한다. 그로부터 순차적으로 다음 빈 공간에 접근할 수 있게 된다. 하지만 해당 방법은 특정 위치의 빈공간을 찾아가기 위해 링크를 많이 따라가야 한다는 성능상의 한계점이 존재한다. (물론 빈공간에서 특정 위치를 탐색하는 일은 빈번하게 일어나지 않는다.)
• 그루핑 : 연결리스트의 단점을 보완한 방법이다. 맨 처음 빈블록에 n개의 블록에 대한 주소를 기입한다. 이 중 n-1개는 빈 공간의 블록주소이고, 마지막 하나는 다른 n개의 빈 공간에 대한 주소를 포함하는 블록의 주소를 기입해 연결한다. 즉, 연결리스트를 그룹화하는 것이다. 단순 연결 리스트 방법보다 빠르게 빈 공간을 찾을 수 있다.
• 비트맵(비트벡터) : 비트맵 상의 각 비트를 저장공간 상의 블록(섹터)에 맵핑해놓고 해당 섹터가 할당되면 1, 아니면 0으로 간단하게 표시해놓는다. 비트 연산을 이용할 수 있어 속도를 높일 수 있다. 이를 위해 비트맵은 메인메모리에 존재해야만 한다. 하지만 해당 방법은 비트맵을 위한 메모리 공간이 소모되어, 메모리 용량 소비 문제가 존재하게 된다.
• 계수(Counting) : 일반적으로 공간이 할당되거나 회수되는 작업은 연속성이 크다. 모든 사용 가능 블록에 대한 주소를 갖지 않고, 임의의 빈 블록이 있다고 했을 때 해당 블록에 대한 주소와 그로부터 연속해 할당될 수 있는 빈 블록의 개수만을 리스트에 기록해 관리하는 방법이다. 빈 공간에 대한 목록이 작아진다는 장점이 있다.
• 공간맵(Space Map) : 대규모의 파일, 디렉토리, 심지어 파일 시스템 자체를 저장할 수 있도록 설계되었다. 대용량 시스템에서는 비트맵같은 메타데이타의 입출력 성능이 큰 영향을 미친다. 이를 위해 대용량 공간을 관리가 가능한 크기의 덩어리로 나눈 메타슬랩을 생성한다. 한 볼륨은 수백개의 메타슬랩을 포함할 수 있다. 각 메타슬랩은 해당 영역에 대한 공간맵을 가진다. 각 공간맵은 모든 블록 할당과 변환 활동을 계수 포멧으로, 시간순서로 기록한다. 이는 오라클의 ZFS 파일 시스템에서 볼 수 있다. ZFS가 메타슬랩으로부터 공간을 할당하거나 반환하려고 할 때 효율적 연산을 위해 해당 공간맵을 균형 트리 형태로 메모리에 적재한다.