[운영체제 11주차] - 입출력 시스템

반효경 교수님의 운영체제 강의와 Operating System Concepts 10th ed. 를 참고하였습니다.

Disk Scheduling

디스크의 구조

• track: 각 원판의 동심원을 이루는 sector의 집합
• head: 디스크에 데이터를 읽거나 쓰는 장치, head는 서로 다른 원판의 항상 동일한 track을 가르키고 있다.
• Logical block
  • 디스크의 외부(컴퓨터)에서 보는 디스크의 단위 정보 저장 공간들
  • 주소를 가진 1차원 배열처럼 취급
  • 정보를 전송하는 최소 단위
• Sector
  • Logical block이 물리적인 디스크에 매핑된 위치
  • Sector 0은 최외곽 실린더의 첫 트랙에 있는 첫 번째 섹터이다. (boot block)

Disk Management

physical formatting (Low-level formatting)

• 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
• 각 섹터는 header + 실제 data(보통 512bytes) + trailer로 구성
• header와 trailer는 sector number, ECC(Error-Correcting Code) 등의 정보가 저장되며 controller가 직접 접근 및 운영
• ECC는 데이터의 축약본이다. 데이터를 저장할 때 축약본을 생성했는데 나중에 조회했을 때 축약본의 값이 달라졌으면 뭔가 문제가 생겼다는 것을 알 수 있다.

Partitioning

• 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
• os는 이것을 독립적 disk로 취급(논리적 디스크)

Logical formatting

• 각 파티션의 파일시스템을 만드는 것
• FAT, inode, free space 등의 구조 포함

Booting

• 휘발성 메모리인 DRAM에는 부팅 시에 아무 데이터가 없다.
• 비휘발성 메모리인 ROM에 있는 "small bootstrap loader"를 실행한다
• sector 0을 load하여 실행
• sector 0은 full Bootstrap loader program이다
• os를 디스크에서 load하여 실행

Access time의 구성

• Seek time
  헤드를 해당 실린더(원판에서 같은 동심원을 모아놓은 것)로 움직이는 데 걸리는 시간
• Rotatinal latency
  헤드가 원하는 섹터에 도달하기까지 걸리는 회전 지연 시간
• Transfer time
  실제 데이터의 전송 시간

Disk bandwidth(대역폭)

단위 시간 당 전송된 바이트의 수

Disk Scheduling

• seek time이 대부분의 시간을 차지한다
• seek time을 최소화하는 것이 목표
• seek time 은 seek distance에 비례한다.

Disk Scheduling algorithm

FCFS (First Come First Served)

• disk 탐색 요청이 들어온 순서대로 처리한다.

disk queue: 98, 183, 37, 122, 14, 124, 65, 67
head starts at 53

SSTF (Shortest Seek Time First)

• SJF와 유사하다. 현재 head에 가까운 요청부터 처리한다.
• starvation 문제가 발생할 수 있다.
  

SCAN

• disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 요청을 모두 처리한다.
• 실린더 위치에 따라 대기 시간이 계속 달라진다.

C-SCAN

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

N-SCAN

• SCAN의 변형 알고리즘
• 이동을 시작하기 전에 들어온 요청만 처리하고, 새로 생긴 요청은 그 다음에 처리한다.

LOOK and C-LOOK

• 각각 SCAN, C-SCAN을 변형한 알고리즘
• 항상 끝과 끝을 찍는 SCAN과 달리 현재 요청의 한계까지만 탐색하고 되감는다.
• 헤드가 진행하다가 그 방향에 더 이상 기다리는 요청이 없으면 그 즉시 헤드의 이동방향을 바꾼다.

디스크 스케줄링 알고리즘의 결정

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

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

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

Swap-Space management

• 디스크를 사용하는 두 가지 이유
  • 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)
  • 신뢰성
    • 동일 정보를 여러 디스크에 중복 저장
    • 하나의 디스크가 고장시 다른 디스크에서 읽어옴
    • 단순한 중복 저장이 아니라 일부 디스크에 공간의 효율성을 높일 수 있다.

UNIX 파일 시스템

• 수퍼 블록

  • 파일 시스템의 총체적 레이아웃 정보 보관
  • 블록의 크기, inode의 수, data block의 수, free block list의 head

• i-node 블록

  • 메타데이터 보관 (실제 데이터 블록의 위치 정보 포함)

• data 블록

  • 실제 data 보관

Ext2 파일 시스템

• Linux 기반의 파일 시스템
• 15개의 pointer로 구성
  • direct/indirect pointer로 구성하여 다양한 크기의 블록을 표현할 수 있도록 구성

특징

블록의 그룹화

• 파일을 접근할 때 메타데이터를 먼저 접근하고 실제 데이터를 접근하는 데, 따로 보관되어있으면 헤드의 동선이 커진다.
• 메타 데이터와 실제 데이터를 그룹화하여 인접하게 배치한다.

수퍼 블록의 중복저장

• 수퍼블록을 그룹마다 중복저장하여 디스크 오류에 대비

그룹 디스크립터

• 데이터 블록 비트맵의 시작 위치, 아이노드 비트맵의 시작 위치 등 각 그룹의 정보를 담고 있는 정보가 담겨있음

• 데이터 블록 비트맵, 아이노드 비트맵, 아이노드 테이블로 아이노드와 데이터 블록을 표시함

Ext4 파일시스템

• Ext4 = Ext2 + 저널링
• 갑작스러운 전원 공급 중단 -> 파일 시스템 일관성 훼손
• 버퍼 캐시에서 작업을 진행하다가 파일 시스템에 반영을 하지 못하면 버퍼 캐시는 메모리기 때문에 휘발된다.
• 작업 도중 일부만 반영되면 내용이 깨질 수 있다.

문제의 해결

• 신뢰성을 높이기 위해 저널링 사용
• Journaling: 5~30초 단위로 버퍼캐시에서 수정된 내용을 저널 영역에 기록
• Checkpointing: 수정된 내용을 파일 시스템의 원래 위치에 반영(예: 5분 주기)
• 저널영역에 쓰는 도중에 전원이 끊어지더라도 불완전한 정보라면 저널 영역을 날리고, 이전의 정보라도 살릴 수 있다.
• 만약 저널영역에 다 쓰고 전원이 끊어지면, 마무리되었다는 마크를 보고 이 정보를 파일시스템에 반영해준다.

Ext4의 저널링

메타데이터만 저널링

• 저널링 주기가 도래하면 데이터를 파일 시스템에 저장한 후 메타데이터를 저널 영역에 기록
• 체크포인팅 주기가 도래하면 메타데이터를 파일시스템에 반영
• 크래쉬 발생 시 파일시스템 자체가 깨어지는 것 방지(일부 데이터는 훼손 가능)

메타데이터+일반데이터 저널링

• 저널링 주기마다 메타데이터, 데이터를 같이 저널영역에 기록
• 체크포인트 시에도 두 데이터 모두를 반영
• 크래쉬 발생 시 데이터 복구 보장

버퍼 캐시 알고리즘

• 파일 시스템에서 메모리 상에 올려놓는 버퍼캐시가 꽉 찼을 때 어떻게 해야 할까?
• LRU: 가장 오래 전에 사용된 블록 삭제
  • 마지막 사용시점만 고려하므로 정보를 일부만 사용
• LFU: 사용횟수를 고려하여 삭제
  • 사용횟수만 고려하고 시점을 고려하지 않는다.

LRFU

• 각각의 사용 시점에 대한 value를 계산하여 value가 가장 낮은 버퍼 캐시 블록을 쫓아낸다.
• LFU와 LRU의 성질을 적절히 조합하였다.
  • 과거 참조 정보의 value를 모두 더한다.
  • 하지만 최근에 참조될수록 value가 커진다.

실효성

• Space overhead

  • 각 블록마다 참조 정보를 저장하려면 너무 공간 복잡도가 올라가지 않는가?

• Time overhead

  • 버퍼 캐시 교체 알고리즘은 O(logN) 내에 빠르게 처리해주어야 하는데 매번 O(N) 이상의 시간이 소모되므로 매우 비효율적이다.

효율적인 구현 방법

• 공간 문제
  • 모든 정보를 저장하는 것이 아니라 한 번 저장해놓고 조회 시점의 거리를 고려한 값을 사용한다. (지수 법칙)
• 시간 문제
  • 재 참조되지 않은 block들간에는 value의 대소관계가 변하지 않는다.
  • 즉, 한번 value가 계산되고 재참조되지 않은 block에 대해서는 계산하지 않는다.
  • 힙을 이용해서 value가 가장 낮은 노드가 root node가 되는 최소 힙을 구성한다.
    • 재 참조되는 블록이 있으면 다시 heapify해준다.
    • O(logN)에 근접한다.