학습 목표 및 학습 내용

• 학습 목표
  • 디스크의 내부구조를 설명할 수 있다.
  • 디스크 스케줄링 알고리즘을 설명할 수 있다.
• 학습 내용
  • Disk Structure
  • Disk Scheduling Algorithms
  • Disk Formatting
  • Swap Space Management

Hard Disk Internals

Moving head disk mechanism

• Disk I/O service time
  • Seek time + Rotational delay + Data transfer time
  • Seek time
    • Time to move the disk head to the desired track.
    • Seek time ≈ seek distance
  • Rotational delay
    • Time for the desired sector to rotate to the disk head.
    • Best case = 0
    • Worst case = time for one rotation
  • Data transfer time
    • Time for transferring data from disk media to the disk buffer, and vice versa.
  • Seek time or rotational delay >> data transfer time

하드 디스크 내부

• 이동 헤드 디스크 메커니즘: 이는 디스크의 트랙 사이를 움직여서 헤드를 원하는 위치로 가져갈 수 있게 합니다. 이 헤드는 데이터를 읽고 쓰는 데 사용됩니다.
• 디스크 I/O 서비스 시간: 디스크에서 데이터를 읽거나 쓰는 데 걸리는 총 시간을 의미합니다. 이 시간은 3가지 주요 요소로 구성됩니다:
• 탐색 시간(Seek Time): 디스크 헤드를 원하는 트랙으로 이동시키는 데 걸리는 시간입니다. 일반적으로 탐색 거리에 비례합니다.
• 회전 지연(Rotational Delay): 원하는 섹터가 디스크 헤드로 회전하는 데 걸리는 시간입니다. 최선의 경우, 이 시간은 0이며 최악의 경우, 이 시간은 한 바퀴 회전하는 데 필요한 시간입니다.
• 데이터 전송 시간(Data Transfer Time): 디스크 미디어에서 디스크 버퍼로 데이터를 전송하는 데 걸리는 시간, 그리고 그 반대입니다. 대부분의 경우 탐색 시간이나 회전 지연이 데이터 전송 시간보다 훨씬 길게 됩니다.

Hard Disks

• Platters range from .85” to 14” (historically)
  • Commonly 3.5”, 2.5” and 1.8”
• Range from 30GB to 3TB per drive
• Performance
  • Transfer Rate – theoretical – 6 Gb/sec
  • Effective Transfer Rate – real – 1Gb/sec
  • Seek time from 3ms to 12ms – 9ms common for desktop drives
  • Average seek time measured or calculated based on 1/3 of tracks
  • Latency based on spindle speed
  • 1 / (RPM / 60) = 60 / RPM
  • Average latency = ½ latency

하드 디스크

• 플래터 크기는 이력적으로 .85인치에서 14인치까지 다양하지만, 일반적으로는 3.5인치, 2.5인치, 1.8인치 크기가 일반적입니다.
• 드라이브 별로 30GB부터 3TB까지 저장 공간을 가질 수 있습니다.
• 성능:
  • 전송률(Transfer Rate) - 이론적으로는 초당 6Gb, 실제로는 초당 1Gb가 될 수 있습니다.
  • 탐색 시간은 3ms에서 12ms 사이이며, 데스크탑 드라이브에서는 일반적으로 9ms입니다.
  • 평균 탐색 시간은 트랙의 1/3을 기준으로 측정되거나 계산됩니다.
  • 지연 시간은 스피들 속도에 기반합니다. 평균 지연 시간은 전체 지연 시간의 절반입니다.

Solid-State Disks

• Nonvolatile memory used like a hard drive
  • Many technology variations
• Can be more reliable than HDDs
• More expensive per MB
• Maybe have shorter life span
• Less capacity
• But much faster
• Busses can be too slow -> connect directly to PCI for example
• No moving parts, so no seek time or rotational latency

솔리드 스테이트 디스크 (Solid-State Disks)
솔리드 스테이트 디스크(SSD)는 비휘발성 메모리를 사용하여 하드 드라이브처럼 작동합니다. SSD에는 여러 가지 기술 변형이 있습니다. SSD는 하드 디스크 드라이브(HDD)보다 더 안정적일 수 있지만, 메가바이트(MB) 당 비용이 더 비쌉니다. 또한 수명이 짧을 수 있으며, 용량도 더 작지만 훨씬 빠릅니다. 데이터 버스의 속도가 너무 느려질 수 있으므로, PCI와 같은 인터페이스에 직접 연결할 수 있습니다. SSD에는 움직이는 부품이 없으므로 탐색 시간이나 회전 지연이 없습니다.

Magnetic Tape

• Early secondary-storage medium
  • Evolved from open spools to cartridges
• Relatively permanent and holds large quantities of data
• Access time slow
• Random access ~1000 times slower than disk
• Mainly used for backup, storage of infrequently-used data, transfer medium between systems
• Kept in spool and wound or rewound past read-write head
• Once data under head, transfer rates comparable to disk
  • 140MB/sec and greater
• 200GB to 1.5TB typical storage

자기 테이프 (Magnetic Tape)
자기 테이프는 초기의 보조 저장 매체로, 열린 스풀에서 카트리지 형태로 발전했습니다. 자기 테이프는 상대적으로 영구적이며 대량의 데이터를 저장할 수 있습니다. 하지만 접근 시간은 느리며, 디스크에 비해 무작위 접근이 약 1000배 느립니다. 주로 백업용, 자주 사용하지 않는 데이터의 저장, 시스템 간의 전송 매체로 사용됩니다. 스풀에 보관되어 읽기/쓰기 헤드 앞에서 앞뒤로 감기거나 감아 풀리게 됩니다. 데이터가 헤드 아래에 있으면, 전송률은 디스크와 비슷하며, 140MB/초 이상으로 달할 수 있습니다. 일반적인 저장 용량은 200GB에서 1.5TB입니다.

NAS(Network-Attached Storage)

• Network-attached storage (NAS) is storage made available over a network rather than over a local connection (such as a bus)
  • Remotely attaching to file systems
• NFS and CIFS are common protocols
• Implemented via remote procedure calls (RPCs) between host and storage over typically TCP or UDP on IP network
• iSCSI protocol uses IP network to carry the SCSI protocol
  • Remotely attaching to devices (blocks)

네트워크 연결 스토리지 (Network-Attached Storage)
네트워크 연결 스토리지(NAS)는 로컬 연결(예: 버스)이 아닌 네트워크를 통해 제공되는 저장 공간입니다. 이는 원격으로 파일 시스템에 연결하는 것을 가능하게 합니다. NFS와 CIFS는 일반적인 프로토콜이며, 일반적으로 TCP나 UDP를 이용한 IP 네트워크 상에서 호스트와 스토리지 간의 원격 프로시저 호출(RPC)을 통해 구현됩니다. iSCSI 프로토콜은 IP 네트워크를 사용하여 SCSI 프로토콜을 운반합니다.

Disk Scheduling Algorithms

Disk I/O scheduler

• Generally, new requests for service will be placed in the request queue.
  • Request – a scheduling unit in the disk I/O scheduler
    • type(R/W), disk address, the number of sectors
      
• When a request is completed, disk I/O scheduler chooses the next one.
• Average disk I/O service time depends on disk I/O scheduling algorithm.

Objective of disk scheduling algorithm

• Minimizes the seek time and rotational delay.
• Cylinder-based mapping in disk controller
  
• But, operating system cannot estimate the rotational delay.
  • The rotation speed and the number of sectors per track of disks are different.
• Generally, disk scheduling focus on minimizing the seek time.

Evaluation of disk scheduling algorithms

• The state of the request queue and the current position of disk head are given.
• → For each disk scheduling algorithm, the total head movements is computed.

디스크 스케줄링 알고리즘

디스크 스케줄링은 디스크 I/O 요청을 처리하는 순서를 결정하는 알고리즘입니다. 이는 디스크의 성능과 효율성에 큰 영향을 미칩니다.

디스크 I/O 스케줄러

• 일반적으로 새로운 서비스 요청은 요청 큐에 배치됩니다.
• "요청"은 디스크 I/O 스케줄러에서의 스케줄링 단위로, 요청의 유형(읽기/쓰기), 디스크 주소, 섹터 수 등을 포함합니다.
• 요청이 완료되면, 디스크 I/O 스케줄러는 다음 요청을 선택합니다.
• 평균 디스크 I/O 서비스 시간은 디스크 I/O 스케줄링 알고리즘에 따라 달라집니다.

디스크 스케줄링 알고리즘의 목표

• 탐색 시간과 회전 지연을 최소화하는 것입니다.
• 디스크 컨트롤러에서는 실린더 기반 매핑을 사용합니다.
• 그러나 운영 체제는 회전 지연을 추정할 수 없습니다. 이는 디스크의 회전 속도와 트랙 당 섹터 수가 다르기 때문입니다.
• 일반적으로 디스크 스케줄링은 탐색 시간을 최소화하는 데 초점을 맞춥니다.

디스크 스케줄링 알고리즘의 평가

• 요청 큐의 상태와 디스크 헤드의 현재 위치가 주어집니다.
• 각 디스크 스케줄링 알고리즘에 대해, 헤드의 총 이동 거리가 계산됩니다.
• 이렇게 디스크 스케줄링 알고리즘은 디스크 I/O 요청을 어떻게 처리할지 결정하여 디스크의 성능과 효율성을 향상시키는 데 중요한 역할을 합니다.

FCFS (First Come First Served)

• Services the requests in the arrival order.
• E.g.
• Queue state → R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
• Position of disk head → 22
  
• It has too long seek distance.

FCFS (First Come First Served)

FCFS는 매우 간단한 디스크 스케줄링 알고리즘입니다. 이 알고리즘은 요청이 도착한 순서대로 요청을 처리합니다. 위의 예시에서, 요청들이 도착한 순서는 R1, R2, R3, R4, R5, R6, R7, R8이며, 디스크 헤드의 초기 위치는 22입니다. 따라서 이 순서대로 디스크 헤드가 이동하게 됩니다.

이 알고리즘의 장점은 단순함과 예측 가능성입니다. 하지만 단점은 탐색 거리가 너무 길다는 것입니다. 이로 인해 디스크의 전체 성능이 저하될 수 있습니다.

SSTF (Shortest Seek Time First)

• Services the request with the minimum seek time from the current head position.
• E.g.
  • Queue state → R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
  • Position of disk head → 22
    
• It is a greedy algorithm.
• It may cause starvation of some requests.

SSTF (Shortest Seek Time First)

SSTF 알고리즘은 현재 디스크 헤드 위치에서 탐색 시간이 가장 짧은 요청을 먼저 처리합니다. 위의 예시에서, 디스크 헤드의 초기 위치는 22이고, 이 위치에서 가장 가까운 요청은 R1(25)입니다. 따라서 이 요청을 먼저 처리하고, 그 다음으로 가장 가까운 요청을 선택하여 처리하는 방식을 계속합니다.

이 알고리즘은 '욕심쟁이(greedy)' 알고리즘이며, 탐색 거리를 크게 줄일 수 있어 디스크의 성능을 향상시키는데 효과적입니다. 하지만 이 알고리즘의 단점은 일부 요청에 대한 '기아(starvation)' 현상을 발생시킬 수 있다는 것입니다. 즉, 다른 요청들에 비해 위치가 먼 요청이 계속해서 무시되어 처리되지 않을 수 있습니다.

SCAN

• The disk head starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the end, where head movement is reversed and servicing continues.
• It is also called elevator algorithm.
• E.g.
• Queue state → R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
• Position of disk head → 22
  

SCAN
SCAN 알고리즘은 '엘리베이터 알고리즘'이라고도 불립니다. 디스크 헤드가 디스크의 한쪽 끝에서 시작하여 다른쪽 끝으로 움직이며 요청을 처리하고, 끝에 도달하면 움직임이 반대로 바뀌어 계속하여 요청을 처리하는 방식입니다. 위의 예시에서, 디스크 헤드의 초기 위치는 22이며, 이 위치에서 시작하여 한쪽 끝으로 움직이면서 요청을 처리하게 됩니다.

이 알고리즘의 장점은 모든 요청이 공정하게 처리된다는 것입니다. 그러나, 탐색 효율성을 최대화하기 위해 디스크 헤드는 디스크의 끝까지 이동해야 하므로 일부 요청은 다소 긴 대기 시간을 가질 수 있습니다.

C-SCAN

• It is a variant of SCAN.
• It provides a more uniform wait time than SCAN.
• When it reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests on the return trip.
• E.g.
  • Queue state → R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
  • Position of disk head → 22
    

C-SCAN
C-SCAN 알고리즘은 SCAN 알고리즘의 변형입니다. 디스크의 한쪽 끝에서 다른쪽 끝까지 움직이며 요청을 처리한 후, 서비스 요청 없이 바로 처음 위치로 되돌아갑니다. 이렇게 하면 SCAN에 비해 대기 시간이 더 균일해집니다. 다만, 디스크 헤드가 처음 위치로 되돌아갈 때는 요청을 처리하지 않으므로 이 시간 동안은 유휴 상태가 됩니다.

C-LOOK

• It is a practical implementation of C-SCAN.
• The disk head goes only as far as the final request in each direction. Then, it reverses direction immediately without going all the way to the end of disk.
• E.g.
  • Queue state → R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
  • Position of disk head → 22
    

C-LOOK
C-LOOK 알고리즘은 C-SCAN 알고리즘의 실질적 구현입니다. 디스크 헤드가 각 방향에서 최종 요청까지만 움직이고, 디스크의 끝까지 가지 않고 바로 방향을 바꿉니다. 따라서 C-SCAN에 비해 디스크 헤드의 이동 거리가 짧아져 전체적인 성능이 향상됩니다.

Disk Formatting

디스크 포맷팅
디스크 포맷팅은 디스크를 사용할 수 있도록 구성하는 과정입니다. 이 과정은 물리적 포맷팅과 논리적 포맷팅으로 크게 나눌 수 있습니다.

Physical formatting (low-level formatting)

• Before using a disk, it must be divided into sectors that the disk controller can read and write.
• Most hard disks are physically formatted in manufacturing process.
• During this process, a special data structure for each sector is added.
  
• The header and trailer contain information used by the disk controller.
  • E.g. sector number, error-correcting code (ECC)

물리적 포맷팅 (저수준 포맷팅)
물리적 포맷팅은 디스크를 읽고 쓸 수 있는 섹터로 나누는 과정입니다. 대부분의 하드 디스크는 제조 과정에서 물리적 포맷팅이 이루어집니다. 이 과정에서 각 섹터마다 특별한 데이터 구조가 추가되며, 이 데이터 구조는 헤더와 트레일러로 구성됩니다. 헤더와 트레일러에는 디스크 컨트롤러가 사용하는 정보가 포함되어 있습니다. 예를 들어, 섹터 번호, 오류 수정 코드 (ECC) 등이 이에 해당합니다.

Partition

• A disk can be divided into multiple logical disks.
  
• Operating system can treat each partition as though it were a separate disk.

파티션
디스크는 여러 개의 논리적인 디스크로 나눌 수 있는데, 이를 파티셔닝이라고 합니다. 이를 통해 운영체제는 각 파티션을 별도의 디스크처럼 다룰 수 있게 됩니다.

Logical formatting

• Operating system store the initial file system data structures.
  • Superblock, free space bitmap, etc.
    

논리적 포맷팅
논리적 포맷팅은 운영체제가 초기 파일 시스템의 데이터 구조를 저장하는 과정입니다. 이 과정에서 슈퍼블록, 자유 공간 비트맵 등의 파일 시스템 데이터 구조가 디스크에 구성됩니다. 이 과정을 거쳐서 디스크는 운영 체제에서 파일 저장을 위한 준비가 완료되며, 사용자가 파일을 저장하고 조회할 수 있게 됩니다.

Swap Space Management

Swap space

• Virtual memory uses disk space as an extension of main memory.
• It can be implemented as two types.
  • A normal file in file system - e.g. Windows
  • A separate disk partition – e.g. UNIX
    

스왑 공간 관리
스왑 공간은 가상 메모리에서 디스크 공간을 주 메모리의 확장으로 사용하는 영역입니다. 이는 일반적으로 파일 시스템의 일반 파일 형태 (예: Windows) 또는 별도의 디스크 파티션 형태 (예: UNIX)로 구현될 수 있습니다. 이 스왑 공간은 주 메모리에 담을 수 없는 데이터를 일시적으로 저장하는 임시 저장소 역할을 합니다.

스왑 공간의 구현 형태는 운영체제에 따라 다르며, 성능과 효율성에 따라 선택됩니다. 파일 시스템 내의 일반 파일로 스왑 공간을 구현하면 디스크 공간 관리가 유연해지지만, 디스크 입출력 성능이 약간 저하될 수 있습니다. 반면, 별도의 디스크 파티션으로 스왑 공간을 구현하면 디스크 입출력 성능이 높아지지만, 디스크 공간의 유연한 관리가 어려울 수 있습니다.

Summary

• Disk I/O service time is modeled as sum of seek time, rotational delay, and data transfer time.
• Disk I/O scheduler chooses the next request in the request queue when a request is completed.
• There are many disk I/O scheduling algorithms to minimize the seek time. SSTF, SCAN, and C-SCAN are such examples.
• Before using a disk, it should be physically and logically formatted.
• Swap space can be implemented as a normal file in file system or a separate disk partition.

요약

• 디스크 I/O 서비스 시간은 탐색 시간, 회전 지연, 그리고 데이터 전송 시간의 합으로 모델링됩니다.
• 디스크 I/O 스케줄러는 요청이 완료되면 요청 큐에서 다음 요청을 선택합니다.
• 탐색 시간을 최소화하기 위한 다양한 디스크 I/O 스케줄링 알고리즘이 있습니다. SSTF, SCAN, 그리고 C-SCAN 등이 그 예입니다.
• 디스크를 사용하기 전에 물리적 및 논리적 포맷팅이 필요합니다.
• 스왑 공간은 파일 시스템 내의 일반 파일 또는 별도의 디스크 파티션으로 구현될 수 있습니다.