입출력 시스템

Disk Scheduling

• Read-write head
  • 모든 헤드들은 동일한 실린더, 트랙의 위치를 읽는다.
    

Disk Structure

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

Disk Management

• Physical formatting (Low-level formatting)
  • 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
  • 각 섹터는 header + 실제 data(보통 512bytes) + trailer로 구성
  • header와 trailer는 sector number,ECC 등의 정보가 저장되며 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하여 실행

FCFS

SSTF (Shortest Seek Time First)

SCAN

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

C-SCAN

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

N-SCAN

• 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service

LOOK and C-LOOK

• SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
• LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동바얗ㅇ을 즉시 반대로 이동한다.

DIsk-Scheduling Algorithm의 결정

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

Swap-Space Management

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

RAID

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

UNIX 파일 시스템

Ext2 파일 시스템

• 포인터가 15개
  

• 블록의 그릅화
  • 메타데이터와 실제 데이터를 인접하게 배치하여 디스크 탐색 시간 감소
• 슈퍼블록의 중복저장
  • 슈퍼블록을 그룹마다 중복저장하여 디스크 오류에 대비
    

• 슈퍼블록
  • 아이노드 수, 가용 아이노드 수, 데이터블록 수, 가용 데이터블록 수
  • 그룹 당 블록 수, 시간 정보
• 그룹 디스크립터
  • 데이터블록 비트맵의 시작위치, 아이노드 비트맵의 시작위치
  • 첫 번재 아이노드의 시작주소, 가용 아이노드의 수
• 데이터 블록 비트맵
  • 사용중인 데이터블록과 빈 데이터블록의 표시
• 아이노드 비트맵
  • 사용중인 아이노드와 빈 아이노드의 표시
• 아이노드 테이블
  • 실제 아이노드의 저장 위치

Ext4

• Ext2 + 저널링

• LInux, macOS, Android

• 컴퓨터에 갑작스럽게 전원 공급이 중단된다면?

  • 파일 시스템 일관성 훼손(inconsistency) 발생
  • 버퍼 캐시는 휘발성이라서 사라진다.

저널링

• inconsistency 문제를 해결하기 위해 사용
• 5~30초 단위로 버퍼캐시에서 수정된 내용을 저널영역에 기록
  • 전원이 끊겨도 저널영역에 저장되어있음
  • 파일시스템에 기록하는 것이 아니기 때문에 파일이 깨지는 일이 없음
• checkpointing
  • 수정된 내용을 파일시스템의 원래 위치에 반영

Ex4의 저널링(메타 데이터 저널링 모드)

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

Ex4의 저널링(데이터 저널링 모드)

• 메타데이터와 일반데이터를 모두 저널링
  • 저널링 주기가 되면 데이터와 메타데이터를 저널영역에 기록
  • 체크포인팅 주기가 도래하면 데이터와 메타데이터를 파일시스템에 반영
  • 크래쉬 발생 시 데이터 자체의 복구 보장

LRFU 알고리즘

• 캐시블록 x 중 그 가치평가값 Value(x)가 제일 적은 블록 삭제

• LFU적인 성질

  • 과거의 모든 참조기록이 현재 시점의 블록 가치 계산에 합산됨

• LRU적인 성질

  • 최근 참조일수록 블록의 가치 평가에 대한 기여도가 큼

• Space overhead
  • 각 블록의 과거 참조 횟수를 유지해야하는가?
• Time overhead
  • 교체 결정마다 모든 블록의 Value를 다시 계산해야하는가?

LRFU 효율적 구현

• Space Complexity

  • 블록마다 공간 복잡도가 O(1)

• Time Complexity
  

  • O(log2n)
  • heap으로 구현해서 비교 재사용된 block만 재정렬