운영체제 디스크 공간 할당(Disk Space Allocation) 알고리즘과 효과적 알고리즘의 판단 기준은?

2019. 5. 13. 22:13

안녕하세요? 허니입니다. 운영체제에서 디스크 공간 할당(Disk Space Allocation)의 알고리즘과 효과적 알고리즘의 판단 기준에 대해 포스팅 하도록 하겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

disk space allocation의 알고리즘

contiguous

linked list allocation

index

indexed allocation

효과적 알고리즘의 판단 기준

순차 접근(sequential access)

임의 접근(random access)

디스크 공간 할당(Disk space allocation)

파일 시스템을 학습하면서 이 시점에서 생각해야 할 것은 연속된 바이트의 연속으로 구성된 파일을 디스크 블록에 어떤 형식으로 저장시킬 것인가 하는 점이다. 이것을 바꿔 말하면 사용자가 하나의 파일을 불러올 때 디스크 이곳저곳에 블록단위로 흩어져있는 파일을 보다 신속하게 찾아내고 신속하게 저장하기 위해서 그 동안 어떤 방법들이 사용되었는지를 알아보는 것이다. 그 동안 디스크 공간에 파일을 할당하는데는 다음과 같은 방법들이 있다.

연속적 할당 (contiguous allocation)
하나의 파일을 디스크에 할당할 때 인접한 섹터들을 할당하여 최소의 시간으로 데이터를 읽어들일 수 있도록 하는 것이다. 이 방법이 활용되기 위해선 파일의 크기를 할당할 때에 알고 있어야 한다. 만약 현재 사용할 파일이 1Mbyte라면 디스크는 1Mbyte를 연속된 섹터들을 할당해 놓는 것이다.

그림 61 Contiguous Allocation

linked list allocation
연속할당 방법의 단점은 하나의 파일을 인접한 섹터을 할당하여 채움으로서 그만큼 디스크가 효율적으로 사용되지 못하다는 것 이었다. 디스크 곳곳에 사용되지 않은 블록이 있다 하더라도 그 블록이 현재 저장해야하는 파일의 크기보다 작다면 사용될 수 없기 때문이다. 디스크 공간을 보다 효율적으로 운영하는 방법을 고심하던 시스템 설계자들은 블록을 리스트로 연결해 블록이 디스크상에 떨어져 있어도 하나의 파일을 할당할 수 있는 linked list allocation을 구상하기 시작했다. 여러 개의 디스크블록이 필요한 파일을 저장할 때 인접한 섹터가 아니더라도 저장이 가능한데 이 이유는 파일의 가장 앞부분을 저장한 블록이 그 다음 저장 블록이 어느 곳에 위치해 있는지 포인터를 통해 알려주기 때문이다. 만약 10개의 떨어진 블록이 사용되었다면 각자 다음 순서의 블록이 어디 위치해있는지에 관한 정보를 갖고 있는 것이다. 시스템 사용 중 데이터를 삽입하거나 삭제하는 등의 행동은 바로 파일 크기의 변화를 가져온다. 이렇게 파일의 크기가 동적일 때 즉, 디스크 블록이 더 필요한 경우가 발생했을 때 필요한 블록이 디스크상에 어느 위치에 있다하더라도 포인터를 통해 연결이 가능하므로 편리하다.

그림 62 Linked List Allocation

보통의 경우 블록하나씩 포인터로 연결되는 경우는 적고 여유가 있는 인접한 블록에 파일을 저장한 다음 인접블록이 없을 경우 또 다른 블록에 포인터가 연결되게 된다.

index
앞서 우리는 파일의 논리적 블럭이 디스크의 물리적 블록으로 변화되는 원리를 공부해 보았다. 그렇다면 논리적 블록과 물리적 블록간에 연결사항을 알고 있다면 보다 쉽게 디스크에 저장되어 있는 파일을 찾을 수 있지 않을까. 바로 이런 생각에서 만들어진 것이 인덱스이다. 책에서 어느 한가지 내용을 찾고자 할 때 우리는 맨 첫 장부터 페이지를 한 장 한 장 넘기며 찾지 않는다. 보다 간편하게 원하는 내용을 찾기 위해 책 앞부분에 인덱스를 참고하게 되는 것이다. 그와 같이 내가 현재 필요로 하는 파일이 디스크 내부에 어떤 실린더 주소와 블록 주소를 갖고 있는지에 대해 도표를 만들게 되는 것이다. 이 방법은 linked list allocation처럼 파일 크기가 동적일 때 편리하다. 어떠한 내용 삽입으로 인해 기존 파일보다 크기가 커져 별도의 디스크블록에 삽입된 내용이 저장되었다면 인덱스 항목을 통해 늘어난 파일이 디스크 어느 블록에 저장되어 있는지 표시하면 되기 때문에 파일 크기 변화에 대한 대처가 발빠르게 진행된다.

논리적 블록	물리적 블록
0	(24,37)
1	(18,29)
2	(34,52)
3	(21,7)
4	(8,3)

그러나 이러한 인덱스를 통한 할당방법 역시 완벽한 것은 아니었다. 어떠한 문제점을 갖고 있는지 한번 살펴보자. 디스크블록포인터가 32bit, 디스크의 I/O 블록은 4Kbyte를 갖게 된다고 한다면 이러한 32bit(4byte)의 디스크 블럭 포인터는 실린더번호와 섹터 번호를 표기하게 된다. 또한 하나의 인덱스 블록에는 1024개의 포인터 항목들이 존재하고 하나의 인덱스 블록이 가르킬 수 있는 파일의 크기는 4Mbyte(1024포인터X4kbyte)인 것이다. 만약 파일의 크기가 8Mbyte라면 두 개의 인덱스 블록이 필요하게 되고 16Mbyte이면 4개의 인덱스 블록이 필요하게 된다. 파일의 크기가 1Gbyte라면 인덱스블록은 250개나 필요하다. 계속해서 파일의 크기가 커질수록 인덱스 블록의 갯수 또한 늘어나게 되는 것이다.

인덱스 블록이 증가한다는 것은 어떤 문제를 발생시킬까? 임의에 블록을 읽기 위해 인덱스 블록을 검색하기 위해서는 맨 처음 인덱스 블록부터 차례대로 접근해야 한다. 불행하게도 내가 찾는 인덱스 항목이 인덱스블록 가장 끝에 존재한다면....바로 파일이 클수록 인덱스블록의 수는 늘어나고 인덱스 항목을 검사하는데는 그 만큼 긴 시간이 걸리게 되는 것은 너무도 당연한 노릇이다. 그렇기에 멀티레벨페이지테이블과 같이 인덱스 블록을 하나 더 추가하는 것을 고려하게 되었다. 그러나 인덱스 블록이 하나 더 추가되어 사용되었지만 이 또한 100% 만족을 가져오지는 못했다. 인덱스 블록이 하나일 경우 헤드가 2번의 접근을 시도함으로서 디스크에 저장되어 있는 파일을 불러올 수 있었다. 인덱스블록을 한번 읽고 데이터 블록을 찾아가 저장된 파일을 읽어오면 되었지만 2레벨 인덱스 블록의 경우 3번의 접근을 시도해야 했다.

그림 63 2레벨 인텍스 블록

또한 파일의 크기가 4Mbyte 이하일 경우를 한번 생각해 보자. 이럴 경우 인덱스 블록 하나로도 4Mbyte 파일의 물리적 블록과 디스크에 논리적 블록간에 표시가 가능하므로 2레벨 인덱스블록은 낭비를 가져오게 된다. 결론적으로 파일이 클 경우 2레벨 인덱스 블록이 보다 효과적이지만 파일이 작을 경우 하나의 인덱스 블록이 효과적인 것이다. 그렇다면 이 두 가지의 방법을 적절히 섞어 사용하게 되면 어떨까.

Hybrid allocation
이 방법은 바로 블록 전체를 인덱스로 채우는 것이 아니라 파일의 크기가 4Mbyte 이하일 경우와 그 이상일 경우 또한 매우 클 경우 등 3가지의 경우를 염두에 두고 다이렉트 블록 포인터를 연결하는 것이다. 다음 그림과 같이 1레벨은 하나의 인덱스 블록을 통해 직접 데이터 블록에 연결시키고 2레벨은 두 개의 인덱스 블록에 또한 3레벨은 3개의 인덱스 블록에 접근을 시도함으로서 데이터블록을 찾아가는 것이다.

알고리즘이 가장 효율적으로 판단하는 기준

어떤 알고리즘이 가장 효율적이냐를 판단하기 위해선 어떤 하나의 잣대가 필요한 것이다. 다음의 순차접근(sequential access)과 임의 접근(random access)의 두 가지 기준의 내용을 알아보고 앞서 말한 4가지의 디스크 공간 할당 방법의 장단점을 구분해 보자.

순차접근(sequential access)
순차접근은 데이터가 저장되어 있는 파일을 앞에서 뒤로 순차적으로 접근하는 방식을 말한다. 자기테입의 경우 테이터에 접근하기 위해 테입을 앞뒤로 감아야 하기 때문에 테이터가 저장되어 있는 위치에 따라 순차적으로 접근하게 되는 것이다.

임의접근(random access)
임의접근은 데이터가 저장되어 있는 위치에 상관없이 접근하는 방식을 말한다. 자기디스크에 데이터가 저장되어 있을 경우 앞 뒤 구분없이 임의의 데이터에 접근하게 되는 것이다.

자, 그럼 이제부터 앞서 공부한 디스크 할당 방식을 비교해보자.

contiguous의 디스크공간 할당은 데이터의 첫 위치만 알면 헤드가 연속적으로 데이터를 읽게 되므로 순차접근을 기준으로 보았을 때 좋은 방법이다. 임의 접근을 기준으로 보았을 때도 연속적 할당은 별다른 문제가 존재하지 않는다.

linked list allocation의 경우는 순차접근을 할 경우 연결된 포인터만 쫓아가면 되므로 효율적인 방법이 된다. 그러나 임의 접근을 시도할 경우 내가 찾고자 하는 데이터가 리스트로 연결된 블록 가운데 마지막에 있다 하더라도 처음 블록부터 찾아야 하므로 비효율적인 방법이다.

index는 물리적 블록에 파일들이 흩어져 있으므로 순차접근과 임의접근 두 가지 모두 비슷한 성능을 보인다.

요점정리

disk space allocation
1) 연속적 할당 (contiguous allocation)
하나의 파일을 디스크에 할당할 때 인접한 섹터들을 할당하여 최소의 시간으로 데이터를 읽어들일 수 있도록 하는 것이다.
2) linked list allocation
여러개의 디스크블록이 필요한 경우 파일을 저장할 때 인접한 섹터가 아니더라도 포인터를 통해 연결된 파일이 저장된 블록을 알려주게 되는 할당방법이다.
3) index
파일과 디스크간에 로지컬블럭과 피지컬블록의 연결사항을 도표로 만들어 표시하는 할당방법이다.
4) Hybrid allocation
이 방법은 바로 블록 전체를 인덱스로 채우는 것이 아니라 파일의 크기가 4Mbyte 이하일 경우와 그 이상일 경우 또한 매우 클 경우등 3가지의 레벨를 염두에 둔 것으로 1레벨은 하나의 인덱스 블록을 통해 직접 데이터 블록에 연결시키고 2레벨은 두 개의 인덱스 블록에 또한 3레벨은 3개의 인덱스 블록에 접근을 시도함으로서 데이터블록을 찾아가는 것이다.

순차접근(sequential access)과 임의 접근(random access)
1) 순차접근(sequential access)
순차접근은 데이터가 저장되어 있는 파일을 앞에서 뒤로 순차적으로 접근하는 방식을 말한다.
2) 임의 접근(random access)
임의접근은 데이터가 저장되어 있는 위치에 상관없이 접근하는 방식을 말한다.

퀴즈

퀴즈1) 디스크공간 할당 방법 중 연속적 할당 (contiguous allocation)의 방법과 장점을 설명하시오.

퀴즈2) linked list allocation은 파일 크기가 동적일 때 유용하다. 그 이유를 설명해 보시오.

퀴즈3) 인덱스 블록이 증가한다는 것은 어떤 문제를 발생시킬까.

퀴즈4) Hybrid allocation은 인덱스 방법을 보다 효율적으로 설계한 것이다. 그 특성을 설명해 보시오.

퀴즈5) linked list allocation를 순차접근과 임의접근을 기준으로 효율성을 비교해 보시오.

정답1) 하나의 파일을 디스크에 할당할 때 인접한 섹터들을 할당하는 방법으로 최소의 시간으로 데이터를 읽어들일 수 있는 장점을 갖고 있다.

정답2) 시스템 사용 중 데이터를 삽입하거나 삭제하는 등의 행동은 바로 파일 크기의 변화를 가져온다. 이렇게 파일의 크기가 동적일 때 즉, 디스크 블록이 더 필요한 경우가 발생했을 때 필요한 블록이 디스크상에 어느 위치에 있다하더라도 포인터를 통해 연결이 가능하므로 편리하다.

정답3) 임의에 블록을 읽기 위해 인덱스 블록을 검색하기 위해서는 맨 처음 인덱스 블록부터 차례대로 접근해야 하기 때문에 인덱스블록이 증가한다는 것은 인덱스 항목을 검사하는데 그 만큼 긴 시간이 걸리는 문제가 발생된다.

정답4) 이 방법은 바로 블록 전체를 인덱스로 채우는 것이 아니라 파일의 크기가 4Mbyte 이하일 경우와 그 이상일 경우 또한 매우 클 경우등 3가지의 레벨을 염두에 둔 것으로 1레벨은 하나의 인덱스 블록을 통해 직접 데이터 블록에 연결시키고 2레벨은 두 개의 인덱스 블록에 또한 3레벨은 3개의 인덱스 블록에 접근을 시도함으로서 데이터블록을 찾아가는 것이다.

목 차

운영체제를 시작하는 분들을 위해

운영체제의 역사와 구체적으로 어떤 일들을 수행하나요?

운영체제의 목표와 역할이 미래에도 계속 증대될까요?

운영체제를 이해하기 위해 필요한 기본 개념들은 무엇인가요?

운영체제 프로세스 생애주기(Process Lifecycle)는 무엇인가요?

운영체제 프로세스 관리(Process Management)는 어떻게 하나요?

운영체제 프로세스(Process)의 처리 속도는 어떻게 높일까?

운영체제 스레드(Thread)는 무엇인가요?

운영체제 스케줄링 (Scheduling)은 어떻게 하나요?

운영체제 스케줄링 알고리즘의 비교 기준이 있나요?

운영체제 프로세스 동기화가 무엇인가요?

운영체제에서 세마포어(Semaphore)란?

운영체제 메모리 관리(Memory Management)는 어떻게 하나요?

운영체제 메모리 분할 방법은 어떻게 하나요?

운영체제 가상메모리(Virtual Memory)는 무엇인가요?