• DISK MANAGEMENT

Chapter 12. Mass Storage Management

• DISK STRUCTURE

• DISK SCHEDULING

– FCFS, SSTF

– SCAN, C-SCAN, AND LOOK, C-LOOK – SECTOR QUEUEING

• DISK MANAGEMENT

• DISK MANAGEMENT

• SWAP-SPACE MANAGEMENT

• RAID STRUCTURE

• PERFORMANCE AND RELIABILITY IMPROVEMENTS

• STORAGE HIERARCHY

DISK MANAGEMENT

• BACKGROUND

– DISK AND TAPE ARE SECONDARY STORAGE DEVICES.

BUT TAPES ARE MAINLY USED FOR JOURNAL OR DATA EXCHANGE AND DOES NOT INTERFACE CLOSELY WITH OS AS DISK DOES. HENCE ONLY DISKS WILL BE

CONSIDERED IN SECONDARY STORAGE DEVICE MANAGEMENT.

– MAIN MEMORY IS TOO SMALL FOR ALL THE

INFORMATION IN A SYSTEM AND FURTHERMORE, IT IS INFORMATION IN A SYSTEM AND FURTHERMORE, IT IS VOLATILE. THEREFORE, WE NEED DISKS TO STORE LARGE AMOUNT OF DATA PERMANENTLY.

• DISK STRUCTURE

– PHYSICAL STRUCTURE

» TRACK, SECTOR, AND CYLINDER

» FIXED-HEAD AND MOVING-HEAD DISK

» FIXED AND REMOVABLE DISKS

» FLOPPY DISKS

DISK MANAGEMENT

» DISK DRIVE AND CONTROLLER

» BLOCK

– DEVICE DIRECTORY

DISK MANAGEMENT

• 포매팅

– 물리적 포매팅 (저수준 포맷팅): 컴퓨터에서 디스크를 사용하기 위해 섹터를 구분하고 관련 정보를 수록하는 과정

» 섹터를 구분하기 위해 디스크를 적절한 자료구조로 채움

» 섹터의 자료구조는 보통 header, 자료 구역, trailer로 구성

» 또한 디스크를 여러 실린더로 이뤼지는 파티션(partition)으로 분할한다.

» 공장에서 이미 저수준 포맷팅이 되어 출하된다.

» 공장에서 이미 저수준 포맷팅이 되어 출하된다.

– 논리적 포매팅: OS에 의해서 논리적 포매팅을 해주어야만 그 디스크를 사용할 있다. 즉 파일 시스템을 만드는 것이다. (역할) 빈 디렉토리를 만들어서 이를 디스크에 쓰고, FAT, 가용

공간정보 리스트, 초기의 빈 디렉토리 구조 등 디스크의 내용을 추적하는데 필요한 정보를 포함.

DISK MANAGEMENT

• 부트 적재기

– 1) 컴퓨터를 시작시키기 위해 전원을 넣을 때, 시스템을

시작시키는 프로그램으로 여러 하드웨어 (CPU 레지스터, 장치 제어기, 메모리 등)의 초기화하고,

– 2) 디스크에서 OS를 찾아서 메모리 상주 부분에 적재하고, – ROM에 디스크에 있는 부트 적재기를 적재하는 역할만

수행하고, 나머지는 적재기에서 하도록 하는 방법을 많이 사용.

(30 바이트)

• 불량 블록

– 일부 섹터가 고장나서 사용할 수 없는 곳으로 이에 대한 조치는 OS에서 알아서 해주어야 한다.

– 불량 블록에 대한 조치는 사용을 금지하는 것

– 불량 블록 목록: 포매팅 과정에서 작성되고, 사용 중에 추가로 발견되면 그 정보를 장치 제어기에서 이 목록에 추가한다.

DISK MANAGEMENT

• 교체 공간 (Swap Space Management)

– 스왑 공간은 일반 파일 시스템이 차지하는 공간 안에 만들 수도 있고, 또는 별도의 디스크 파티션을 만들어 사용할 수 있다.

– 보통 스왑 공간은 별도의 디스크 파이션에 둔다.

– 디스크를 메모리의 연장으로 생각할 수 있도록 하는 개념 – 페이징 시스템에서는 메모리로부터 대치된 페이지만을 수용 – 교체 공간의 크기

» 사용 용도와 예비하는 메모리 양에 따라 변화한다.

» 사용 용도와 예비하는 메모리 양에 따라 변화한다.

» (예) PC: 수백만 바이트, UNIX W/S: 수천 – 수억 바이트

» 약간 과다하게 설정하는 것이 안전하다.

– (예)

» BSD 4.3

» Solaris 1

» Solaris 2

DISK MANAGEMENT

– 교체 공간의 위치

» 모두 디스크에 존재한다

» (예) MS Windows: 교체 공간이 단순 파일 시스템 내에 있는 큰 파일로 간주
비효율적

» (예) 교체 공간을 별개의 디스크 분할(PARTITION)로 생성하는 방법
속도가 빠르다.

– 교체 공간의 경영(관리)

» 하나의 프로세스에 두 개의 교체 맵이 존재

» 하나의 프로세스에 두 개의 교체 맵이 존재

» 코드 세그먼트

• 크기가 고정되어 있으며, 대략 512KB 단위로 할당되고,

• 마지막 부분은 나머지 페이지들을 수용하는데, 1KB 단위이다.

» 자료 세그먼트

• 각기 다른 크기의 교체 공간 주소를 가짐

DISK MANAGEMENT

• Disk Partitioning

– OS에 의해 하나의 디스크로 취급되는 디스크 영역

– 디스크 분할 집합을 단일 디스크 볼륨으로 종합하는 방법으로 여러 입출력이 동시에 진행될 수 있어 성능향상 기대

– 분할된 각 영역을 하나의 HDD와 같이 디스크 드라이브 이름이 부여되고 그 이름으로 참조된다.

DISK MANAGEMENT

• 디스크 스케줄링 알고리즘

– 평균 디스크 처리 시간을 개선하기 위함

– 모든 입출력 장치는 처리를 원하는 작업의 큐(queue)를 갖는다 – 어떤 프로세스가 디스크에 대한 입출력을 요구할 때마다

OS에게 시스템 호출을 낸다.

• DISK SCHEDULING Algorithm

– 디스크 드라이브에게 빠른 접근 시간과 높은 전송량을 제공해야 함

– 디스크 접근 시간 =

» 탐색 시간(seek time) +

» 회전지연시간(rotational latency) +

» 전송시간 (transfer time)

– 탐색 시간 = 디스크 암이 헤드를 해당 실린더로 이동하는데 걸리는 시간

– 회전지연시간 = 디스크 헤드가 원하는 섹터 위치로 도달하기까지 걸리는 시간

DISK MANAGEMENT

• DISK SCHEDULING Algorithm

– FCFS (First Coming First Service)

» 디스크의 접근을 요청한 트랙 순서대로 서비스를 제공

» (예) 다음과 선형 디스크 큐의 요청이 있는 경우 – SSTF (Shortest Seek-Time First)

» 현재의 헤드 위치에서 가장 가까운 요구 순서대로 서비스 – NOTE THE SIMILARITY OF ABOVE ALGORITHMS TO

THOSE OF THE CORRESPONDING ONES IN CPU THOSE OF THE CORRESPONDING ONES IN CPU SCHEDULING.

• 디스크 스케줄링 알고리즘의 선택

– SCAN, C-SCAN 스케줄링은 디스크를 많이 사용하는 시스템에 적합하다.

– 링크 파일 또는 색인 파일의 경우는 블럭들이 디스크에 널리 산재되어 있어 많은 헤드 이동을 요구한다.

– 보통 SSTF, LOOK이 무난한 선택이다.

– 운영체제, 이계영저, 정익사, 7장, pp.410-415 참조요망.

DISK MANAGEMENT

– SCAN

» ELEVATOR ALGORITHM. SHOVELING OF SNOW.

» WHEN NO FURTHER REQUEST EXISTS IN THAT

DIRECTION, HEAD GOES TO THE EXTREME ADDRES, REVERSES ITSELF, AND MOVES TO THE OPPOSITE DIRECTION.

– C-SCAN

» MORE UNIFORM WAIT. UNIDIRECTIONAL OR MOVES IN ONE DIRECTION ONLY. SCAN DISCRIMINATES AGAINST REQUESTS TO BOTH ENDS OF THE DISK.

REQUESTS TO BOTH ENDS OF THE DISK.

» SCAN & C-SCAN은 디스크를 많이 쓰는 시스템에 적합하다.

» 특히 C-SCAN이 성능이 일정하게 좋음 – LOOK ALGORITHMS

» HEAD REVERSES ITSELF WHEN NO REQUEST EXISTS IN THAT DIRECTION WITHOUT GOING TO THE EXTREME

ADDRESS. LOOK HAS CORRESPONDING ALGORITHMS TO SCAN AND C-SCAN.

– SECTOR QUEUEING

» PRIMARILY USED FOR FIXED-HEAD DISKS (드럼).

DISK MANAGEMENT

큐 = 98, 183, 37, 122, 14, 124, 65, 67 헤드 시작은 53이라 가정.

0 14 37 53 65 67 98 122 124 183 199

< FCFS 디스크 스케줄링의 예>

평균 헤드 이동 거리 = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640

DISK MANAGEMENT

큐 = 98, 183, 37, 122, 14, 124, 65, 67 헤드 시작은 53이라 가정.

0 14 37 53 65 67 98 122 124 183 199

< SSTF 디스크 스케줄링의 예>

평균 헤드 이동 거리 = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 또는

평균 헤드 이동 거리 = (67 – 53) + (67 – 14) + (183 – 14) = 236

DISK MANAGEMENT

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

헤드 시작은 53이라 하고, 트랙 0 방향으로 이동 중이라 가정.

0 14 37 53 65 67 98 122 124 183 199

< SCAN 디스크 스케줄링의 예>

평균 헤드 이동 거리 = (53 – 0) + (183 – 0) = 53 + 183 = 236

DISK MANAGEMENT

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

헤드 시작은 53이라 하고, 트랙 0 방향으로 이동 중이라 가정.

0 14 37 53 65 67 98 122 124 183 199

< LOOK 디스크 스케줄링의 예: SCAN과 대조됨>

평균 헤드 이동 거리 = (53 – 14) + (183 – 14) = 39 + 169 = 208

DISK MANAGEMENT

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

헤드 시작은 53이고, 트랙 0 방향으로 이동 중이라 가정

0 14 37 53 65 67 98 122 124 183 199

< C-SCAN 디스크 스케줄링의 예>

평균 헤드 이동 거리 = (53 – 0) + (199 - 0) + (199 – 65) = 386

DISK MANAGEMENT

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

헤드 시작은 53이고, 트랙 0 방향으로 이동 중이라 가정

0 14 37 53 65 67 98 122 124 183 199

< C-LOOK 디스크 스케줄링의 예>

평균 헤드 이동 거리 = (53 – 14) + (183 – 14) + (183 – 65) = 326

DISK MANAGEMENT

• Disk Scheduling 문제

– 연습문제 12.2

– 운영체제, 이계영저, 정익사, 7장, pp.410-415 문제 풀이

DISK MANAGEMENT

• PERFORMANCE AND RELIABILITY IMPROVEMENTS

– DISK CRASH IS A MAJOR PROBLEM AND BACKUPS ARE NEEDED. BUT THEY TAKE A LOT OF TIME.

– TO IMPROVE SPEED, DISK STRIPPING (OR

INTERLEAVING) HAS BEEN PROPOSED. A GROUP OF DISKS IS TREATED AS ONE STORAGE UNIT, WITH EACH BLOCK BROKEN INTO SEVERAL SUBBLOCKS AND

STORED IN THEM. SINCE SUBBLOCKS ARE STORED IN THEM. SINCE SUBBLOCKS ARE TRANSFERED IN PARALLEL, THEY ARE FATER.

– TO IMPROVE RELIABILITY, RAID(REDUNDANT ARRAY OF INEXPENSIVE DISKS) HAS BEEN PROPOSED.

DISK MANAGEMENT

• STORAGE HIERARCHY

– THE WIDE VARIETY OF STORAGE IN A COMPUTER SYSTEM CAN BE ORGANIZED IN A HIERARCHY

ACCORDING TO EITHER SPEED OR COST. HIGHER LEVEL MEMORIES ARE EXPENSIVE BUT FAST AND AS WE MOVE DOWN THE HIERARCHY, COST DECREASES BUT ACCESS TIME INCREASES.

– THE DESIGN OF MEMORY SYSTEM ATTEMPTS TO BALANCE THESE FACTORS. NOTE THE SYMMETRY BALANCE THESE FACTORS. NOTE THE SYMMETRY BETWEEN LEVELS!!!!

DISK MANAGEMENT

registers

cache

memory

backing store backing store

disk drives

magnetic-tape library SRORAGE HIERARCHY

DISK MANAGEMENT

• RAID (Redundant array of inexpensive disk)

– 중복으로 신뢰성 향상에 역점: Mirroring or Shadowing

» 높은 신뢰성을 제공하지만 비용이 많이 소요 – 병렬성을 이용한 성능 향상: 데이터 스트라이핑

» 여러 디스크에 각 바이트의 비트를 나누어 저장함으로써 구성한다. 예로, 8 개의 디스크를 가지고 있다면, 각

디스크 i에 각 바이트의 비트 i를 기록하는 것이다.

» 높은 전송률을 제공하지만 신뢰성을 향상시킬 수는 없다

» 높은 전송률을 제공하지만 신뢰성을 향상시킬 수는 없다

DISK MANAGEMENT

• RAID 레벨

– RAID Level 0:

– RAID Level 1: 디스크 미러링 사용

– RAID Level 2: 메모리 스타일 오류 정정 코드 구조

» 각 바이트는 자신과 연관된 하나의 패러티 비트를 갖는다.

– RAID Level 3: bit-interleaved parity organization

» 한 섹터가 정확히 읽혔는지를 디스크 컨트롤러가 탐지할 수 있다.

수 있다.

– RAID Level 4: block-interleaved parity organization

» 블록 단위의 스트라이핑을 사용

– RAID Level 5: block-interleaved distributed parity – RAID Level 6: P + Q 중복 기법

– RAID Level 0 + 1:

Chapter 13. I/O SYSTEM

• 입출력 하드웨어

– Port

– Bus line – Controller

– Polling & Interrupt

• 입출력 관련 서비스 시스템

• 입출력 관련 서비스 시스템

– 입출력 스케줄링 – Buffering

– Caching – Spooling

– 장치 예약 및 에러 처리

입출력 하드웨어

• 입출력 장치

– 특성에 맞는 제어가 필요하다

– 케이블 또는 무선으로 신호를 보내 컴퓨터 시스템과 통신 – 포트(port)라는 연결점을 통해 컴퓨터와 연결한다.

» Port: 각 입출력 제어기에 부여된 주소

– 버스 선은 회선 집합으로 이를 통해 메시지를 송수신할 수 있는지를 정한 프로토콜까지를 포함한다.

• 제어기 (Controller)

• 제어기 (Controller)

– Port, bus line, 입출력 장치를 제어하는 전자 회로의 집합체 – Disk controller: SCSI, IDE

– Graphic controller

• I/O Port: 보통 4 개의 레지스터로 구성

– 상태 레지스터 – 제어 레지스터 – 입력 레지스터 – 출력 레지스터

입출력 관련 서브시스템

• 호스트와 하드웨어 사이의 프로토콜

– Polling (busy waiting) – Interrupt

• Buffering

– 입출력 장치와 응용 프로그램 사이에 데이터가 전송되는 동안 그 데이터를 임시로 저장하는 메모리 영역

– 사용하는 이유:

» 데이터의 생산자와 소비자 사이의 속도 차이 극복

» 데이터의 생산자와 소비자 사이의 속도 차이 극복

» 서로 다른 장치들 간에 데이터 전송 크기 문제 해결

» 응용 프로그램의 입출력 복제 시멘틱(copy semantics)을 지원: 응용 프로그램이 시스템 호출을 한 시점의 버퍼 버전만이 디스크에 저장되는 것을 보장한다.

• Caching

– 자주 사용되는 자료의 복사본을 저장하는 빠른 메모리 영역 – 보통 CPU 내에 위치하며, 캐싱과 버퍼링은 메모리의 한

영역이 두 가지 목적으로 사용될 수 있음.

입출력 관련 서브시스템

• Spool

– 프린터 같은 장치를 위해 출력 데이터를 보관하는 버퍼