사용자와 파일 시스템 인터페이스에 대한 설명 다음, 가장 하위 단계인 저장장치의 구조에 대해 설명한다.

1. 대용량 저장장치 종류

1.1 자기 디스크

1.1.1 자기 디스크의 구성

자기 디스크는 현대의 컴퓨터 시스템을 위한 대량의 보조저장장치로 사용된다.

• 중심에는 스핀들(spindle)이 있어 시계방향으로 돌아간다. 용량이 큰 서버용 디스크는 면이 여러개이다. 여기서 면은 플래터(platter)라고 부른다. 이러한 플래터 상에는 섹터(sector)들이 모여 하나의 원을 형성하고, 이 원을 트랙(track)이라고 한다. 트랙이 안 쪽에 있든 바깥쪽에 있든 한 트랙의 섹터 수는 동일하다. 각 플래터 상의 동일한 트랙들을 통합해 실린더(cylinder)라고 부른다.
• 디스크가 입출력을 하는 단위는 섹터이다. 디스크에 읽기와 쓰기를 실행하는 헤드가 목표하는 섹터를 찾아가기 위해 디스크 암은 해당 트랙을 찾아가주고, 스핀들은 디스크를 회전시킨다. 일반적으로 하드디스크의 한 섹터 크기는 512바이트이다.
• 헤드를 움직여 특정 트랙의 특정 섹터를 찾아가 읽기 혹은 쓰기 작업을 한다. 이러한 움직임은 물리적 움직임을 포함하고 있기 때문에 매우 효율적으로 이루어져야 한다.
• 디스크에서 읽기 혹은 쓰기의 작업을 하기 위해서는 3가지 시간 지연 요소를 고려해야 한다.(탐색시간/회전지연시간/전송시간)
• 섹터의 위치에 따라 읽기의 순서를 변경하여 처리하기도 하는데, 이렇게 디스크 입출력 순서를 정하는 작업이 디스크 스케줄링이다.

1.1.2 자기 디스크의 용어

• 하드웨어 구조
  • 플래터 : CD처럼 생긴 원형 평판, 양쪽 표면이 자기 물질로 덮여있다.
  • 헤드 : 읽기 헤드/쓰기 헤드가 보통 함께 있다.
  • 암 : 헤드를 움직일 수 있도록 하는 모듈이다.
• 데이터를 나누는 단위(디스크가 입출력을 하는 단위)
  • 트랙 : 하나의 동심원
  • 섹터 : 트랙을 일정한 크기의 섹터로 나누고, 정보를 저장한다.
  • 실린더 : 동일한 암 위치에 있는 트랙의 집합을 말한다.
• 접근 시간/속도에 관한 용어
  • 전송률 : 드라이브와 컴퓨터 간의 데이터 흐름 비율 (보통 초당 수(십) 메가바이트)
  • 임의 접근 시간(Random Access time)
  • 위치 잡기 시간(Positioning time) : 탐색 시간 + 회전 지연 시간 (수밀리초)
    • 탐색 시간 : 디스크 암이 움직이는 시간
    • 회전 지연 시간 : 원하는 섹터가 디스크 헤드로 회전하는 데 걸리는 시간
• 하드 디스크나 플로피 디스크가 자기 디스크에 해당한다.
• 보통 디스크 드라이브는 입출력 버스라고 하는 회선들의 집합에 의해 컴퓨터에 부착되어 있다.
• EIDE, ATA, SATA, USB, FC, SCSI 등등
• 버스 상에서의 데이터 전송은 제어기(Controller)가 처리한다. 보통 각각의 디스크 드라이브에 내장되어 있다.
• 하드디스크가 캐시를 내장할 수도 있다.

1.2 자기 테이프

초기의 보조저장장치 매체로 사용되었다. 상대적으로 영구적, 대용량의 데이터가 보관 가능하지만 접근 시간이 느리다.
그래서 보조저장장치로는 부적합하여 백업용으로 사용한다.
테이프 형태의 구조는 앞뒤로 왔다갔다하며 정확하게 이동하는데 많은 시간이 걸린다.
한번 이동하면 자기 디스크와 비슷한 속도로 데이터를 읽고 쓸 수 있다.

2. 디스크 구조

• 현대의 디스크들은 크기가 일정한 논리 블록의 일차원 배열처럼 취급된다.

• 디스크의 정보 전송 단위는 항상 이 블록 구조로만 이루어진다.

• 논리 블록은 정보를 전송하는 최소 단위이다.

• 섹터 0은 가장 첫번째(가장 바깥쪽) 실린더의 첫번째 트랙의 첫번째 섹터가 된다. 차차 안쪽 실린더로 진행된다.

  • 고정 선형 속도 : 트랙당 비트의 밀도가 일정하다. 트랙이 디스크의 중심에서 더 멀어질수록 더 많은 섹터를 가질 수 있다. 따라서 현대의 디스크들은 실린더를 몇 개의 구역으로 나눈다. 바깥쪽으로 갈 수록 트랙당 섹터 수가 증가한다. 헤드가 바깥쪽에서 안쪽으로 이동할 때 데이터의 읽고 쓰는 양을 동일하게 하기 위해 회전 속도를 높인다. CD DVD 등에서 사용한다. 밀도가 같다.

  • 고정 각속도 : 디스크의 회전 속도를 일정하게 유지하고 안쪽 트랙에서 바깥쪽 트랙으로 갈수록 비트의 밀도를 줄여 데이터 전송률을 일정하게 유지한다. 하드디스크에서 사용한다. 밀도가 다르다.

3. 디스크 부착

디스크를 I/O 포트에 붙이거나 디스크를 네트워크에 붙이거나 둘 중 한가지의 형태를 가진다.

3.1 호스트 부착 저장장치

로컬 입출력 포트를 이용하여 접근하는 방법이다. IDE, ATA라고 하는 입출력 버스 아키텍처를 사용한다. 입출력은 버스마다 최대 2개의 드라이브를 지원한다.

• SCSI : 보통 50 또는 68개의 핀으로 이루어진 커넥터를 쓰고 1버스당 16대의 디바이스를 지원한다.
• FC : 높은 속도를 지원하는 직렬 아키텍처이다. SAN의 기본이 된다.

3.2 네트워크에 부착된 저장장치 (Network-Attached Storage)

네트워크를 통해 원격으로 접근되는 전용 저장장치이다. 클라이언트는 NFS 또는 CIFS 등의 원격 프로시저 호출을 통해 NAS에 접근한다.
NAS는 디바이스가 가지고 있는 전용 프로토콜(SCSI IDE등)이 아닌 TCP/IP 상에서 RPC를 사용하여 호출한다.

3.3 SAN(Storage-Area-Network)

NAS의 경우 입출력 연산시 TCP/IP 네트워크 프로토콜을 사용한다. 따라서 통신의 지연을 증가시키게 된다. 이는 대규모 클라이언트/서버 구축 시 통신 대역폭을 놓고 서버-클라이언트와 경쟁하게 된다.

SAN은 서버들과 저장장치 유닛들을 연결하는 사유 네트워크이다. 따라서 네트워크 프로토콜이 아닌 저장장치 프로토콜을 사용한다.
여러 호스트와 저장장치가 같은 SAN에 부착될 수 있고, 저장장치는 동적으로 호스트에 할당이 가능해 융통성 있게 사용할 수 있다.

4. 디스크 공간할당

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

4.1 연속 할당

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

4.2 연결 할당

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

4.3 FAT(File Access Table)

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

4.4 색인 할당

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

4.5 간접색인

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

4.6 빈 공간 관리

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

4.7 빈 공간 관리 방법

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

5. 디스크 스케줄링

• 운영체제의 역할 중 하나는 효율적인 하드웨어 사용이다. 디스크 드라이브의 경우에는 빠른 디스크 접근 시간과 높은 전송량을 제공해야함을 의미한다. 효율적인 스케줄링은 접근시간과 대역폭을 모두 향상시킬 수 있다.
• 디스크 공간할당 기법을 생각해보면, 일반적으로 한 파일의 블록들에 해당하는 섹터는 디스크 상에 물리적으로 순차적이게 저장되지 않는다.
• 시분할 시스템에서 동시에 수행중인 프로세스들에 의해 발생되는 요청이 수시로 디스크 입출력 요청 큐에 도착하기 때문에, 이를 순서화할 필요가 있다.
• 요청을 순서화 시키는데 있어 가장 중요한 것은 처리율의 극대화이다.
  평균 반응시간과 반응시간의 분산을 줄이는 작업이 되어야 한다. 평균 반응시간을 줄이는 것은 각 요청이 디스크 구동기에 전달되어진 순간부터 그 결과가 나올 때까지 걸리는 시간의 평균값을 최소화하는 것이고, 반응시간의 분산을 줄이는 것은 어느 곳에 위치한 섹터이든 각 섹터에 대한 반응시간에 편차를 최소화하여 반응의 예측성을 높이도록 한다는 것이다.

다시 말해, 일반적으로 컴퓨터는 데이터를 저장할 때 순차적으로 하드웨어 디스크에 저장하지 않는다. 그래서 데이터를 찾기 위해선 산재되어 저장된 데이터를 찾아와야 한다. 이때, 어떻게 효율적으로 산재된 데이터를 액세스할 것인가에 대한 고민과 방법을 디스크 스케줄링이라 한다. 즉, 운영체제가 어떻게 하면 효율적으로 디스크를 제어할 수 있는가에 대한 논의이다.

프로세스가 입출력을 필요로 할 때마다 운영체제에 시스템 호출(System call)을 하는데, 시스템이 디스크에 입출력을 요청할 때에는 다음과 같은 인자들을 같이 전달한다.

• 입력/출력 여부
• 디스크 주소
• 메모리 주소
• 전송될 섹터의 수
  디스크 드라이브의 제어기가 쉬고 있다면 요청이 바로 시작되지만, 바쁜 경우라면 드라이브의 큐(Queue)에 들어가 기다려야 한다. 다중 프로그래밍 시스템에서는 많은 프로세스들이 디스크를 공유한다. 따라서 큐가 길어질 가능성이 크다. 디스크 스케줄링 알고리즘은 큐에 대기하고 있는 입출력 요청들을 어떤 순서로 처리할 지에 대한 연구이다.

디스크 드라이브가 유휴 상태라면 이 요청은 즉시 처리되고 아니면 큐에 들어가 기다려야 한다. 멀티프로그래밍에서는 많은 프로세스들이 디스크를 공유하므로 이 큐에는 여러 디스크 입/출력 요청들이 함께 대기하고 있을 수 있다.

용어

• 디스크 접근 시간 : 탐색 시간 + 회전 지연
  • 탐색 시간(Seek time) : 디스크 암이 헤드를 해당 실린더로 움직이는 데 걸리는 시간
  • 회전 지연(rotational delay) : 디스크 헤드가 원하는 섹터에 도달하기까지 걸리는 회전에 소요되는 추가적인 시간
• 디스크 대역폭 : 단위 시간당 전송되는 총 바이트 수
  = 전송 시간(transfer time) : 디스크와 메인메모리 간 실제 데이터가 이동하는데 소요되는 시간

주어진 실린더 번호가 다음과 같을 때의 처리 순서에 대한 설명
98 183 37 122 14 124 65 67

5.1 선입 선처리 스케줄링 (FCFS)

먼저 요청이 들어오는 것부터 처리한다. 가장 단순한 형태의 알고리즘이다.

5.2 최소 탐색시간 우선 스케줄링(SSTF)

헤드가 다른 곳으로 이동하기 전에, 현재 헤드로부터 가장 가까운 곳에 있는 요구를 먼저 처리해주고 이동하는 알고리즘이다.
최소 작업 우선(Shortest-Job-First) 스케줄링과 유사하나, 몇 개의 디스크 요청들이 매우 오래 기다리는 기아 현상(Starvation)이 발생할 수 있다. 큐의 길이가 길어질수록 기아 현상이 심해질 수 있다.

5.3 SCAN 스케줄링

디스크 암이 디스크의 한쪽 끝에서 시작하여 다른쪽 끝으로 이동하며 가는 길에 있는 요청을 모두 처리한다. 한쪽 끝에 도달하게 되면 역방향으로 이동하며 오는 길에 있는 요청을 다 처리한다. 따라서 헤드는 양쪽을 계속해서 가로지르며 왕복한다. 엘리베이터의 동작과 비슷하다고 해서 엘리베이터 알고리즘이라고도 부른다.

5.4 C-SCAN 스케줄링

각 요청에 걸리는 시간을 좀 더 균등하게 하기 위한 SCAN의 변경 알고리즘이다. 한쪽 끝에 다다르면 헤드를 이동하면서 서비스하는 것이 아니라 헤드를 원위치 시킨 뒤 다시 서비스를 시작한다.

5.5 LOOK 스케줄링

SCAN 및 C-SCAN 알고리즘이 헤드를 디스크의 끝에서 끝으로 이동시키는데 반해 LOOK과 C-LOOK 알고리즘은 헤드의 이동 방향으로 가다 아무런 요청이 없을 경우 즉시 방향을 바꾼다. 한 방향으로 움직이기 전에 미리 요구가 있는지 없는지 확인한다.

5.6 디스크 스케줄링 알고리즘의 선택

어떠한 스케줄링 알고리즘을 사용하던 간에 알고리즘의 성능은 요청의 형태와 횟수에 의해 좌우된다. 그리고 디렉토리와 색인 블록의 위치 또한 중요하다. 모든 파일은 사용이 가능하기 때문에 파일의 위치를 담고 있는 디렉토리에 먼저 접근해야 한다. 이렇다 보니 가장 빈번하게 접근되게 된다. 따라서 디렉토리는 디스크의 가장 안쪽이나 끝 보다는 중간 정도의 실린더에 있는게 더욱 좋다.
디스크 스케줄링 알고리즘은 운영체제와 분리된 알고리즘으로 작성되는 것이 좋다. 그래야 필요에 따라 다른 알고리즘으로 교체할 수 있다. 특별한 이유가 없다면 SSTF나 LOOK이 무난하다.

5.7 회전지연시간 최적화

• 모든 스케줄링 방법은 트랙을 찾아가는 시간인 탐색시간(seek time)의 최적화만을 다루고 있다. 초창기엔 회전지연시간보다 헤드암을 구동하는 데 걸리는 시간이 훨씬 커서 탐색시간의 최적화가 더 중요했다.
• 하지만 최근엔 회전지연시간에 대한 최적화도 중요해졌다. 특히, 한 트랙 내 여러 곳에 분산된 섹터 중 일부만 요구하는 요청이 많을 경우 회전지연시간을 최적화하여 성능을 개선해야한다.
• 이러한 최적화 알고리즘에는 SLTF, SPTF, SATF 등이 있다.

5.7.1 SLTF(Shortest-Latency-Time-First) 스케줄링

회전하는 방향상 가까운 순서로 서비스해준다. 트랙상 서비스할 섹터들이 도열되어 있다는 의미에서 섹터큐잉(Sector Queueing)이라고도 불린다. 이론적으로 회전지연시간을 최소화한다는 측면에서 최적전략에 근접하고, 구현하기 쉽다.

5.7.2 SPTF(Shortest-Positioning-Time-First) 스케줄링

탐색시간과 회전지연시간의 합인 ‘위치 결정시간(Positioning time)’이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 처리량이 많고 평균 반응시간도 짧지만, SSTF와 같이 가장 안쪽과 바깥쪽 실린더가 기아상태에 빠질 위험이 있다.

5.7.3 SATF(Shortest-Access-Time-First) 스케줄링

위치결정시간과 전송시간의 합인 접근 시간(Access time)’이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 3가지 시간지연요소를 모두 고려한다는 점과 SPTF보다 처리량이 많다는 장점이 있지만, 작은 크기의 요청이 연속으로 요청될 때는 큰 크기의 요청이 기아상태에 빠질 위험이 있다.

5.8 RPM의 한계

• 디스크의 성능을 높이는 가장 직접적인 방법은 디스크의 회전속도를 물리적으로 높이는 것이다.
• 하지만 열, 소음, 전력소비 등의 문제로 RPM은 지난 수십년 동안 겨우 몇 %수준으로밖에 증가하지 못했다.
• 이러한 흐름에 따라 대안으로 등장한 것이 RAID이다.

6. 디스크 관리

운영체제는 이 외에도 디스크 관리와 관련된 몇 가지 책임을 져야 한다.

6.1 디스크 포맷팅

새로운 디스크는 아무런 정보도 없이 비어있는 상태이다. 이러한 디스크에 자료를 저장하기 전에 섹터들로 나누어야 하며, 이 과정을 저수준 포맷팅(Low-Level Format) 또는 물리적 포맷팅이라고 한다. 이는 섹터를 구분하기 위해 적절한 자료구조로 채우는 것이며, 보통 헤더 자료 구역(보통 512B의 데이터 영역, 트레일러(ECC 및 섹터 번호) 등의 정보를 가지고 있다.

• 파티션 나누기 : 하드 디스크의 경우 각각의 파티션을 별도의 디스크처럼 취급하다.
• 논리적 포맷팅 : 파일 시스템을 만드는 행위, 운영체제가 시스템 자료구조에 저장된다.

6.2 부트 블록

컴퓨터를 시작하기 전에 전원을 켜거나 재부팅할 때 시스템을 시작시키는 프로그램이다.
대부분의 시스템은 ROM을 따로 두어 안에 부트스트랩 프로그램을 저장한다. ROM이기 때문에 초기화할 필요도 없고 항상 고정 위치에 있어 편리하다만 교체를 위해서는 ROM 칩셋 전체를 들어내야 한다.

• MBR Master Boot Record : 주로 하드디스크의 첫번째 섹터에 저장되는 정보로 부트 코드와 파티션 테이블이 들어있다. 어떤 파티션이 부트되어야 하는가에 대한 표시가 같이 되어있다.

6.3 손상된 블록

디스크는 컴퓨터의 다른 부품들에 비해 매우 고장나기가 쉽다. 고장이 아주 심해서 디스크 전체를 교체해야할 때도 있으나, 대부분의 경우 한개, 두개의 섹터에 결함이 생기는 수도 있다.
MS-DOS의 포맷 명령어는 논리적으로 포맷을 하는데, 과정의 일환으로 손상된 블록이 있는지 검사한다. 만약 손상된 블록이 있으면 그 블록을 더이상 사용하지 않도록 FAT 테이블에 표시해 놓는다.

• 섹터 옮기기/섹터 남기기 : SCSI 디스크의 경우 손상 블록이 발생하면, 손상 블록 리스트를 유지하고, 이에 저수준 포맷팅을 미리할 때 보이지 않는 예비 섹터를 둔다. 이를 손상된 블록과 교체시킬 수 있다. 일부 디스크의 경우 포맷팅할 때에 예비 섹터를 각 실린더마다 배치하고 예비 실린더도 배치한다. 그리고 섹터가 손상되면 예비 섹터를 찾아서 대치시킨다.
• 섹터 밀어내기 : 블록 17에 결함 첫번째 예비 섹터가 202번인 경우 17~202까지의 섹터들을 한칸씩 이동시킨다.
• 연성 에러(soft error) : 손상된 블록 데이터를 복사하고 예비 블록으로 대체할 수 있는 경우
• 경성 에러(hard error) : 데이터를 잃어버리게 되면 사람이 직접 백업본을 들고 와서 에러유무를 체크해야한다.

7. 스왑 공간 관리

swap : 프로세스 전체를 디스크나 주 메모리를 옮기는 것. 물리 메모리가 아주 작아질 때 활성화된다. 근데 가상 메모리로 활용되는 영역은 디스크 영역으로 메모리에 비해 현저히 느릴 수 밖에 없다. 그렇기에 스왑 공간의 설계와 구현 즉, 스왑 공간을 어떻게 쓰고, 디스크상에 어디에 위치시켜야 하는가에 대해 알아본다.

7.1 스왑 공간 사용

스왑 공간은 사용하는 운영체제에 따라 다양하게 운영된다. 시스템에 따라서는 프로세스의 이미지 전체를 스왑 공간에 가지고 있을 수 있다. 페이징 시스템에서는 단순히 주 메모리에서 밀려나는 페이지들을 스왑 공간에 다 들고 있을수도 있으므로 수 메가에서 수 기가바이트까지의 크기를 가진다.

7.2 스왑 공간 위치

스왑 공간은 두 군데에 있을 수 있다.
[1] 일반 파일 시스템이 차지하고 있는 공간
만일 하나의 통짜 파일이라면 구현이 매우 간단해 할당과 관리가 편하다. 다만 스왑을 할 때마다 디렉토리 구조와 디스크 할당 자료구조를 거쳐야 하기 때문에 추가로 디스크 액세스가 필요하다.
[2] 별도의 파티션에 따로 관리한다.
보통 스왑 공간은 별도의 디스크 파티션에 둔다. 일반 파일/디렉토리는 이 공간에 저장되지 않는다. 스왑 관리 루틴은 공간 효율성보다는 속도 효율성을 최적화하기 위한 알고리즘을 쓴다. 파일 시스템에 비해 훨씬 자주 접근되기 때문이다. 내부 단편화가 자주 발생하겠지만 훨씬 짧은 시간동안만 사용하므로 큰 문제가 되지는 않는다.

• 리눅스의 경우 별도의 파티션을 두는 방법과, 파일 시스템 공간 모두에 스왑이 가능하다.

7.3 스왑 공간 관리: 예

UNIX의 경우 원래 전체 프로세스 이미지를 메모리/디스크 내에 연속적인 공간으로 스와핑하는데에서 출발했다. 하드웨어 페이징 기술이 발전함에 따라 페이징과 스와핑을 함께 쓰는 방식으로 발전했다.
SunOs의 경우 페이지를 교체할 때 스왑 아웃 시키기보다는 그냥 할당 해제하고 필요할 경우 파일 시스템으로부터 다시 읽는다. 굳이 스왑 공간을 한번 더 거치면 비효율적이기 때문이다.

리눅스의 경우 스왑 공간을 익명 메모리(힙, 스택 등으로 초기화되지 않은 메모리) 혹은 다수의 프로세스들이 공유하는 메모리 영역에만 사용한다. 스왑 영역은 일반 파일로도, 스왑 파티션으로도 있을 수 있다. 각 스왑 영역은 연속된 페이지 슬롯으로 구성되고 이 페이지 슬롯에 스왑된 페이지들을 적재한다. 그리고 몇 개의 프로세스가 그 스왑 공간을 이용하는 지를 체크해 카운터 개수를 센다.
해당 카운터가 0인 영역은 해당 페이지 슬롯이 사용 가능하다는 의미이다.

8. RAID 구조

Redundant Array of Independent (Inexpensive) Disk
디스크 만드는 기술이 발전함에 따라 디스크의 가격이 점점 더 저렴해졌고, 여러 개의 디스크를 이용하여 병렬 처리를 하여 더 신뢰성이 높고, 더 빠른 데이터 전송률을 확보하기 위해 사용한다.

8.1 중복을 통한 신뢰성 향상

디스크를 한개만 사용하여 데이터를 저장하는 경우 한번 디스크 오류가 발생하면 엄청난 양의 데이터 손실이 발생할 수 있다.
따라서 중복하여 데이터 저장을 허용하는 방법으로 데이터의 분실을 막는 방법이다.
가장 단순하고 비용이 많이 드는 방법으로 디스크의 복사본을 만드는 방법이 있다. 이는 미러링이라고 불린다. 미러링을 사용하는 하나의 논리 디스크는 두개의 물리 디스크로 구성된다. 물론 이렇게 구성한 경우라도 미러링된 디스크에서 두 디스크가 동시에 고장이 날 수도 있기에 완벽한 방법은 아니지만, 단일 디스크를 사용하는 것에 비해 훨씬 안정적이다.
두 디스크를 사용하여 동시에 쓰기를 진행하는 경우 갑자기 한쪽에만 오류가 생겨 내용이 달라질 수가 있다. 이러한 현상을 방지하기 위해 NVRAM 캐시(비휘발성 메모리 캐시)를 RAID영역에 두고 첫번째 디스크에 쓰기 작업을 마친 후, 두 번째 디스크에 쓰기 작업을 마친다. 이는 전원이 나가있는 동안의 데이터 손실이 없다.

8.2 병렬성을 통한 성능 향상

디스크를 병렬로 접근하게 된다면 한개의 요청으로 두개의 디스크에 동시에 쓰기 작업 혹은 읽기 작업이 가능하다.

• 데이터 스트라이핑 : 여러 디스크를 한번에 읽기/쓰기 작업을 진행하여 데이터 전송 비율을 향상시킬 수 있다.
• 비트 레벨 스트라이핑 : 예를 들어 8개의 디스크를 가지고 있는 경우 각 디스크의 i에 비트 i를 쓴다. 크기도 8배가 되고 접근 성능도 8배가 된다. 일반적으로 8의 배수 또는 8의 약수개의 디스크를 사용한다고 일반화할 수 있다.
• n개의 디스크에서 파일의 i번째 블록은 (i mod n) +1의 디스크로 간다. 스트라이핑도 비트 레벨이 아닌 바이트 레벨, 섹터 레벨로 가능하다. 블록 레벨의 스트라이핑이 가장 일반적이다.

8.3 RAID 레벨

적은 비용으로 중복을 허용하는 많은 기법들이 있다.

• RAID 0(Raid Level 0) : 블록 레벨 스트라이핑 디스크 구성으로 여러개의 디스크를 사용하여 입출력 속도를 향상시키는 구성이다.
• RAID 1 : 디스크를 미러링하는 것을 뜻한다.
• RAID 2 : 메모리 스타일 오류 정정 코드 구조로 패리티 비트를 이용해 단일 비트 손상의 경우 데이터를 복구하는 방법이다. 비트 스트라이핑의 경우 8개의 비트가 스트라이핑 된다면 8개의 디스크에 데이터가 써질 것이고, 나머지 한개의 디스크에 패리티 정보를 저장한다. 오버헤드 디스크가 한개 줄어든다.
• RAID 3 : bit-interleaved parity organization : 메모리와 달리 한 섹터가 정확히 읽혔는지를 디스크 컨트롤러가 탐지할 수 있다는 사실을 이용하여, level2의 기능을 향상시킨 것이다. 하나의 오버헤드 디스크를 가진다. 이 방법 때문에 RAID2는 주로 사용되지 않는다.
• RAID 4 : block-interleaved parity organization : 블록 단위의 스트라이핑을 사용하여 N개의 디스크에 대한 패리티 블록을 다른 디스크에 저장한다. 대규모 읽기 쓰기에 대해 높은 성능을 보이지만, 작은 개별적인 영역의 경우, 패리티 비트를 블록 단위로 기록하기 때문에 읽기-변경-쓰기의 번거로운 단계를 거쳐야 한다.
• RAID 5 : block-interleaved distributed parity : RAID 3,4의 경우 다른 디스크에 패리티비트 정보를 저장하는데 이럴 경우 패리티 비트가 저장된 하드가 손실된 경우가 있다. 이를 막기 위해 비트 정보와 함께 패리티 정보도 N+1개로 나누어 분산시켜 저장한다.
• RAID 6 : P + Q 중복 기법 : RAID 5와 유사하지만 여러 디스크 오류에 대비하기 위해 추가 중복 정보를 저장한다. 패리티비트 대신에 Reed-Solomon Codes 같은 에러 교정 코드를 사용한다. 4비트마다 2비트의 중복 데이터를 허용하므로 시스템 내의 2개의 디스크 오류가 생길 수 있다.
  
• RAID 0 + 1 : 높은 성능과 높은 신뢰성 두가지를 모두 사용할 수 있는 대신에 하드디스크 사용량이 두배로 는다. 하나의 디스크 집합이 스트라이프 되고, 그 스트라이프가 다른 스트라이프로 미러링된다. 4 + 4
• RAID 1 + 0 : 0 + 1의 경우 한개의 디스크가 고장난다면 그 집합 전체에 접근이 불가능해진다. 따라서 다른 RAID 종류로 디스크를 미러링한 후 그 쌍을 스트라이프 하면서 사용하는 방법이 생겼다. 2 + 2 + 2 + 2 하나의 디스크가 고장나더라도 미러드 디스크를 통해 데이터에 접근이 간으하다.
• 커널 혹은 시스템 소프트웨어 계층 내에서 볼륨 관리 소프트웨어로 RAID를 구성할 수 있다. 패리티 RAID의 경우 소프트웨어로 구성할 경우 상당히 느려지므로 RAID 0 + 1 또는 1 + 0 이 사용된다.
• RAID는 HBA 하드웨어에 구현될 수 있다. 비용은 적게 드나 융통성이 없을 수 있다.
  

8.4 RAID 레벨 선택

복구 능력의 측면에서 : 복구 능력은 RAID 레벨에 따라 천차만별이다.

8.5 확장

RAID의 개념은 테이프나 무슨 시스템의 데이터를 브로드캐스트 하는 일을 포함하여 여러 저장장치에 적용된다.
테이프 구조에는 데이터 복구율을 향상시킬 수 있고, 무선 시스템의 브로드캐스팅은, 패리티를 함께 브로드캐스팅 하여 전송 손실이 생기더라도 복구가 가능하다.

8.6 RAID의 문제점들

RAID는 운영체제나 사용자에게 데이터가 가용하다는 것을 항상 보장하지 않는다. 물리적인 오류는 보호할 수 있으나 다른 하드웨어나 소프트웨어 버그는 보호하지 못한다.

9. 안정적인 저장장치 구현

안정적인 저장 장치 : 일단 한번 저장이 되면 그 정보는 절대 손실되지 않는다 라는 뜻인데, 이를 구현하기 위해서는 필수적으로 여러 대의 저장장치에 복사본을 만들어 두어야 한다. 그리고 update를 새로 설계하여 고장으로부터 복구할 때에는 모든 복사본의 값이 일관성이 있고, 올바른 값이 될 수 있어야 한다.
이를 위해 필요한 방법들로 디스크 쓰기는 다음 3가지 결과 중 하나를 낳는다.

• 성공적인 완료 : 자료가 디스크에 올바르게 기록되었다.
• 부분적 실패 : 전송 도중 고장이 발생하여 섹터 중 몇 개만이 제대로 기록되고, 고장 당시 기록중이던 섹터는 손상되었을 수도 있다.
• 완전 실패 : 디스크 쓰기가 시작되기 전에 고장이 발견되어 디스크에 데이터가 그대로 있다.

고장이 발생한 경우 한 쌍의 물리 블록들을 조사하여 에러여부를 체크한다. 하나의 블록에 오류가 발생한다면 다른 쪽에 데이터로 복구가 가능하다. 두 블록에 모두 오류가 났더라도 위치가 다르다면 복구가 가능하다.

10. 3차 저장장치 구조

디스크에 비해 가격이 저렴하다는 장점이 있다.

10.1 3차 저장장치

이동식 매체 : 플로피디스크, 테이프, CD, DVD, USB등이 일반적이다.

10.1.1 이동식 디스크

• 하드디스크에 버금가게 속도가 빨라지고 있지만, 디스크 표면의 긁힘으로 손상을 받을 위험이 있다. 플로피, CD, DVD 등등 이들 중 재기록이 가능한 매체를 읽기-쓰기 디스크라고 불린다.
• 이와 반대로 한번 밖에 쓰지 못하는 디스크를 WORM(Write-Once, Read-Many-times) 디스크라고 한다.
• 대부분의 이동식 디스크는 비이동식 디스크보다 읽기/쓰기가 느리다.

10.1.2 테이프

• 일반적으로 테이프는 광디스크/자기 디스크에 비해 훨씬 싸게 많은 자료를 기록할 수 있다. 전송 속도도 비슷하다.
• 그러나 임의 접근을 할 때 탐색하는 시간이 훨씬 느리다. 감기/되감기 동작이 오래 걸리기 때문이다.
• 따라서 디스크 자료의 백업 용도로 사용된다.

10.1.3 미래 기술

• SSD : 비싸지만 메모리만큼 빠르다. 노트북의 소형화에 이용할 수 있다. 모터를 사용하지 않아 전력소모가 줄어든다.
• 홀로그래픽 저장장치 : 홀로그램을 픽셀의 3차원 배열로 생각할 수 있고 홀로그램의 모든 픽셀은 한번의 레이저 광선으로 전달이 가능하다.
• MEMS (micro-electronic mechanical systems) 작은 10000개의 디스크 헤드 배열을 저장하고 자기 저장 물질을 shifting 시켜 모든 헤드가 다음 트랙을 읽을 수 있게 만든다. DRAM보다 싸면서 자기디스크보다 빠른 기술을 제공할 수 있을 것으로 예상된다.

10.2 운영체제의 지원

운영체제는 물리 장치를 관리하고, 응용 프로그램에 가상 기계의 추상화를 제공해야 한다. 다음은 저장 매체가 이동식일 때의 운영체제가 자신의 작업을 어떻게 실행하는가에 대한 설명이다.

10.2.1 응용 인터페이스

• 고정된 디스크를 관리하는 것과 거의 똑같은 원리로 이동식 디스크들을 관리한다.
• 테이프의 경우 하드디스크와는 아주 다르게 관리한다.

10.2.2 파일 네이밍

• 이동식 장치들에 대한 이름을 어떻게 붙일까에 대한 문제이다.

10.2.3 계층적 저장장치 관리 (HSM)

• 저장장치 계층을 주 메모리와 보조 저장장치, 제 3차 저장장치로 확장한다. 주로 사용하지 않고 일시적, 주기적으로 사용되는 대용량의 데이터를 가진 설비에서 주로 사용한다. 이를 확장하여 완전한 ILM(Information Life-cycle Management)를 제공한다.
• 7년 동안 이메일을 보관하고 이후에 삭제한다 등의 정책 등을 관리할 때 쓴다.

참고

http://blog.skby.net/%EB%94%94%EC%8A%A4%ED%81%AC-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-disk-scheduling/
https://inuplace.tistory.com/390
https://inuplace.tistory.com/383?category=884574