[운영체제] 디스크 관리와 스케줄링

Disk Management and Scheduling

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

Disk Structure

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

Disk Management

• physical formatting (Low-level formatting)

  • 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정

  • 각 섹터는 header + 실제 data(보통 512 bytes) + trailer로 구성

  • header와 trailer는 sector number, ECC (Error-Correcting Code) 등의 정보가 저장되며 controller가 직접 접근 및 운영

    ECC는 실제 데이터를 작게 요약한 코드임. (일종의 지문(fingerprint) 같은 것)

    에러가 발생했을 때 ECC를 어느 정도 규모를 두느냐에 따라서 그 에러를 수정까지 할 수 있는 경우가 있고, 에러를 검출만 하고 수정은 못하는 경우도 있다.

• 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 distance

    ≈ : 거의 같다(근사 기호)

Disk Scheduling Algorithm

• 큐에 다음과 같은 실린더 위치의 요청이 존재하는 경우 디스크 헤드 53번에서 시작한 각 알고리즘의 수행 결과는? (실린더 위치는 0 - 199)

  98, 183, 37, 122, 14, 124, 65, 67

• FCFS

  First Come First Service

  들어온 순서대로 처리해주는 방법

  

  순서대로 처리하다보니 헤드의 이동거리가 길어져 비효율적

• SSTF

  Shortest Seek Time First

  현재 head의 위치에서 (큐에 들어와 있는 것 중) 제일 가까운 요청을 가장 먼저 처리하는 방법

  • starvation 문제

  

  디스크 헤드의 이동거리는 줄어들지만, starvation 문제가 발생할 수 있는게 문제다.

  큐에 이러한 요청들이 들어와서 가까운 위치에 있는 걸 처리하고, 멀리있는 쪽 차례가 올 것 같을 때, 큐에 낮은 주소의 요청들이 계속해서 많이 들어온다면 head가 멀리 있는 쪽으로 영원히 가지 못할 수 있을 것이다.

• SCAN

  엘리베이터 스케줄링이라고도 부름.

  • disk arm이 디스크이 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다
  • 다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동한다
  • 문제점: 실린더 위치에 따라 대기 시간이 다르다

  

  

• C-SCAN

  • 헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리

  • 다른쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동

  • SCAN보다 균일한 대기 시간을 제공한다

    이동거리는 다소 길어질 수가 있지만…

  

  

  위 그림을 보면, 183번 이후에 요청이 없음에도 제일 끝까지 갔다가 턴을 하고, 14번 보다 더 낮은 주소에는 요청이 없음에도 0번까지 들어온 다음에 턴을 함.

• N-SCAN

  • SCAN의 변형 알고리즘
  • 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service

• LOOK

• C-LOOK

• LOOK and C-LOOK

  • SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동

  • LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동한다

    C-LOOK

    위 그림을 보면, 반대 방향으로 올 때는 처리를 하지 않고 이동만 하는데, 큐에 있는 제일 낮은 주소인 14번까지만 가서 거기서부터 처리하면서 밖으로 빠져나옴.

Disk-Scheduling Algorithm의 결정

그러면, 어떤 디스크 스케줄링 알고리즘이 좋은 알고리즘인가?

• SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK, C-LOOK 등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음

  현대의 디스크 시스템에서는, 디스크 헤드의 이동거리를 줄이는데 비교적 용이한 SCAN에 기반한 알고리즘들을 많이 쓰고 있다.

• File의 할당 방법에 따라 디스크 요청이 영향을 받음

• 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직하다

Swap-Space Management

• Disk를 사용하는 두 가지 이유

  • memory의 volatile한 특성 → file system

    ＊volatile : 휘발성의

  • 프로그램 실행을 위한 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를 저장하여 공간의 효율성을 높일 수 있다

      parity : 오류가 생겼는지 알아내고, 복구할 수 있을 정도의 중복 저장만 아주 간략하게 해주는 기법 (중복 저장을 대단히 낮게 함)

    

맨 위로 이동하기