CS 정리 | OS | 10. 입출력시스템 (2) | 저널링과 버퍼 캐시 알고리즘 | kocw 반효경 교수님

UNIX 파일 시스템

• 전체
  
• inode
  

파일시스템의 변천사

Ext2 파일시스템

• 블록의 그룹화
  • 메타데이터와 실제 데이터를 안전하게 배치하여 디스크 탐색 시간 감소
• 수퍼블록의 중복저장
  • 수퍼블록을 그룹마다 중복저장하여 디스크 오류에 대비
• 수퍼블록
  • 아이노드 수, 가용 아이노드 수, 데이터블록 수, 가용 데이터블록 수
• 그룹 디스크립터
  • 그룹 내의 수퍼블록 역할을 함
  • 데이터블록 비트맵의 시작위치, 아이노트 비트맵의 시작위치
  • 첫 번재 아이노드의 시작주소, 가용 아이노드의 수
• 데이터 블록 비트맵 (data block bitmap)
  • 사용중인 데이터블록과 빈 데이터블록의 표시
• 아이노드 비트맵(inode bitmap)
  • 사용중인 아이노드와 빈 아이노드의 표시
• 아이노드 테이블(inode table)
  • 실제 아이노드의 저장 위치

Ext4 파일시스템

파일 작업을 하다가 전원이 나가면 어떻게 될까?

버퍼캐시에 write 후 디스크에 이를 copy하여 반영하는 도중 system crash가 발생하면 이전으로 되돌리지도 못하고 파일 자체가 아예 훼손될 수도 있다.

• 갑자스런 전원 공급 중단

  • 파일 시스템 일관성 훼손(inconsistency) 발생

• 저널링 + ext2

How to solve this problem?

• Inconsistency 문제 해결을 위해 저널링 사용
• 저널링
  • 5~30초 단위로 버퍼캐시에서 수정된 내용을 저널영역에 기록
• checkpointing
  • 수정된 내용을 파일 시스템의 원래 위치에 반영 (예:5분주기)
    

Ext4의 저널링

• 메타 데이터 저널링 모드와 데이터 저널링 모드 2가지가 존재한다.

• 메타 데이터 저널링 모드
  

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

• 데이터 저널링 모드
  

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

파일시스템을 위한 버퍼캐시 알고리즘 - LRFU 알고리즘

• 캐시 블록 x 중 그 가지평가 값 value(x)가 제일 적은 블록을 삭제
• LFU인 성질
  • 과거의 모든 참조기록이 현재 시점의 블록 가치 계산에 합산됨
• LRU인 성질
  • p<1이므로 p^(델타)는 감소함소임. 즉 델타값이 작을수록 값이 커짐
  • 최근 참조일수록 블록의 가치 평가에 대한 기여도가 큼

LRFU 알고리즘의 실효성

• 공간 overhead
  • should all the past reference times of each vlock be maintained?
• 시간 overhead
  • _should the Value of all blocks in cache be re-calculated at each replacement decision?

LRFU의 효율적인 구현 방법

• Space Complexity
  

• Time complexity

  • relatice ordering of Value's not change if nor re-references
    

• LFU와 마찬가지로 힙으로 구현
  

LRFU 알고리즘의 성능 분석