Disk Management and Scheduling-디스크 관리와 스케줄링

Disk Structure

• logical block
  • 디스크 외부에서 디스크를 관리하는 최소 단위
  • 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
  • 주소를 가진 1차원 배열처럼 취급
  • 정보를 전송하는 최소 단위
• Sector
  • 디스크 내부에서 디스크를 관리하는 최소 단위
  • Logical block이 물리적인 디스크에 매핑된 위치
  • Sector 0은 최외곽 실린더의 첫 트랙에 있는 첫 번째 섹터이다.

 

Disk Management

• Physical formatting (Low-level formatting)
  • 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
  • 각 섹터는 header + 실제 data(보통 512 bytes) + trailer로 구성
  • hear와 trailer는 sector number, ECC (Error-Correcting Code) 등의 정보가 저장되어 controller가 직접 접근 및 운영
  • 최근에 나오는 디스크는 용량이 커서 포맷 과정이 오래 걸리기 때문에 공정과정을 마친 후 포맷을 전부 한 상태로 판매된다.
• Partitioning
  • 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
  • OS는 이것을 독립적 disk로 취급 (logical disk)
• Logical formatting
  • 파일 시스템을 만드는 것
  • FAT, inode, free space 등의 구조 포함
• Booting
  • ROM에 있는 “small bootstrap loader”의 실행
  • sector 0 (boot block)을 load하여 실행
  • sector 0은 “full Bootstrap loader program”
  • OS를 디스크에서 load하여 실행

 

Disk Scheduling

• Access time의 구성
  • Seek time
    • 헤드를 해당 실린더로 움직이는데 걸리는 시간
  • Rotational latency
    • 헤드가 원하는 섹터에 도달하기까지 걸리는 회전 지연 시간
  • Transfer time
    • 실제 데이터의 전송 시간
• Disk bandwidth
  • 단위 시간 당 전송된 바이트의 수
• Disk Scheduling
  • seek time을 최소화하는 것이 목표
  • Seek time = seek distatnce

 

Disk Scheduling Algorithm

• 큐에 다음과 같은 실린더 위치의 요청이 존재하는 경우 디스크 헤드 53번에서 시작한 각 알고리즘의 수행 결과는? (실린더 위치는 0-199)
  • 98, 183, 37, 122, 14, 124, 65, 67
• FCFS
• SSTF
• SCAN
• C-SCAN
• N-SCAN
• LOOK
• C-LOOK

 

FCFS(First Come First Service)

• 총 헤드의 이동: 640 cylinders
• 가장 효율이 떨어지는 알고리즘
• Request Queue에 있는 값은 Cylinder 번호
• Queue에 존재하는 값들을 아무 절차를 거치지 않고 하나씩 pop 하여 Disk에서 검색함.
• 예시에서 98-183, 183-37 등 먼 거리를 움직이면, 그만큼 seek time이 증가하여 속도가 느려짐.

 

SSTF( Shortest Seek Time First)

• 총 헤드의 이동: 236 cylinders
• 현재 처리하고 있는 Cylinder 번호에서 가장 가까운 곳을 탐색하는 방법
• 먼 거리를 이동하진 않지만, 현재 처리 중인 Cylinder 번호에 근접한 요청이 계속 들어온다면, 상대적으로 먼 거리에 있는 요청들은 Starvation이 발생 → 사용 X

 

SCAN

• 총 head의 이동 : 208 cylinders
• Disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다.
• 다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동한다.
• 문제점: 실린더 위치에 따라서 대기 시간이 달라진다.
• 실제 사용되는 알고리즘 중 하나.
• 엘리베이터가 쭉 내려가면서, 버튼이 눌린 층에 멈춰서 사람을 태우고 다시 내려갑니다. 1층에 도달하면 사람을 모두 내려주고, 다시 위층으로 올라가게 되는데, 이 모습과 비슷하여 엘리베이터 알고리즘이라 불립니다.

 

C-SCAN

• 헤드가 한 쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리
• 다른 쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동
• SCAN보다 균일한 대기 시간을 제공한다.

 

Other Algorithms

• N-SCAN
  • SCAN의 변형 알고리즘
  • 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service
• LOOK and C-LOOK
  • SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
  • LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동한다.

 

C-LOOK

• SCAN, C-SCAN을 실제 Disk에서 구현할 때는 각각 LOOK, C-LOOK으로 구현하게 됨.
• SCAN, C-SCAN과 기본 동작은 동일
• head가 끝 부분까지 도달하는 게 아닌, 요청에서 제일 작거나 큰 번호에 도달하면 각각의 동작에 맞게 다시 요청을 처리하는 방식

 

Disk-Scheduling Algorithm의 결정

• SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK , C-LOOK 등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음
• FILE의 할당 방법에 따라 디스크 요청이 영향을 받음
• 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직함.

 

Swap-Space Management

• Disk를 사용하는 두 가지 이유
  • memory의 volatile한 특성 → file system
  • 프로그램 실행을 위한 memory 공간 부족 → swap space (swap area)
• Swap-space
  • Virtual memory system에서는 디스크를 memory의 연장 공간으로 사용
  • 파일 시스템 내부에 둘 수도 있으나 별도의 partition 사용이 일반적
    • 프로세스가 끝나면 없어지기 때문에 공간 효율성보다는 속도 효율성이 우선
    • 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조됨
    • 따라서, block의 크기 및 저장 방식이 일반 파일시스템과 다름
    

 

RAID

• RAID (Redundant Array of Independent Disks)
  • 여러 개의 디스크를 묶어서 사용
• RAID의 사용 목적
  • 디스크 처리 속도 향상
    • 여러 디스크에 block의 내용을 분산 저장
    • 병렬적으로 읽어 옴 (interleaving, striping)
  • 신뢰성(reliability) 향상
    • 동일 정보를 여러 디스크에 중복 저장
    • 하나의 디스크가 고장 (failure)시 다른 디스크에서 읽어옴 (Mirroring, shadowing)
    • 단순한 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다.

 

 

 

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>

 

• •