[운영체제] Chapter 12. Disk Management and Scheduling (1), (2)

[운영체제] Chapter 12. Disk Management and Scheduling (1), (2)

2023. 2. 2. 22:28ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

Disk Structure, Disk Scheduling, Disk Management, Disk Scheduling Algorithm, FCFS(First Come First Service), SSTF(Shortest Seek Time First), SCAN, C-SCAN, N-SCAN, LOOK, C-LOOK, Disk-Scheduling Algorithm의 결정, Swap-Space Management, RAID

디스크(disk)는 컴퓨터 시스템의 대표적인 2차 저장장치이다. 메모리는 휘발성(volatile) 저장장치이므로 전원이 나가면 그 내용이 모두 사라진다. 따라서 컴퓨터에서 수행한 작업의 결과를 영구히 보관하기 위해서는 디스크와 같은 2차 저장장치를 이용해야 한다.

1. 디스크의 구조

디스크 내의 물리적인 구조
- 마그네틱 원판 > 트랙 > 섹터
- 하나의 디스크에는 마그네틱 원판이 하나일 수도 있고 여러 개일 수도 있다.
- 각각의 원판은 트랙(track)으로 구성된다. 여러 개의 원판에서 상대적 위치가 동일한 트랙들의 집합을 실린더(cylinder)라고 부른다.
- 각 트랙은 섹터로 나뉘며, 섹터에 최소한의 단위 정보가 저장된다.
- 디스크에 데이터를 읽고 쓰기 위해서는 암(arm)이 해당 섹터가 위치한 실린더로 이동한 후 원판이 회전하여 디스크 헤드가 저장된 섹터 위치에 도달해야 한다.
logical block(논리 블록): 디스크 외부에서 디스크 접근의 최소 단위
- 디스크 외부에서는 디스크를 일정한 크기의 저장공간들로 이루어진 1차원 배열처럼 취급, 이 일정한 크기의 저장공간을 논리블록(logical block)이라 한다.
- 디스크 외부로 입출력이 일어날 때에도 논리블록 단위로 전송
- 논리블록에 저장된 데이터를 접근하기 위해서는 배열을 접근하는 것처럼 해당 블록의 인덱스 번호를 디스크에 전달해야 한다.
  - 디스크 컨트롤러는 밖에서 요청하는 배열을 어떠한 원판에, 어떠한 트랙에, 어떠한 조각에다가 그 논리적인 블록을 위치시킬 것인가를 결정한다.
  - 디스크 컨트롤러는 해당 논리블록이 저장된 물리적 위치를 찾아 요청된 데이터에 대한 입출력 작업을 수행한다.
sector: logical block이 물리적인 디스크에 매핑된 위치, 디스크를 관리하는 최소 단위
- 논리블록 하나가 섹터 하나와 1 대 1로 매핑되어 저장된다.
- Sector 0은 최외각 실린더의 첫 트랙에 있는 첫 번째 섹터이다.
  - Sector 0는 어떤 파일 시스템을 쓰든 간에 부팅과 관련된 정보가 저장되는 곳이다.

2. 디스크 관리

physical formatting(Low-level formatting)
- 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
- 각 섹터는 header + 실제 데이터(보통 512 bytes) + trailer로 구성
  - header와 trailer는 sector number(주소 매핑을 위한 섹터 번호), ECC(Error-Correcting Code, 그 내용이 정말 잘 저장되었는지를 확인)등의 정보가 저장되며 컨트롤러가 직접 접근 및 운영
  - ECC: 512 bytes의 데이터에 대해 축약된 코드로, 데이터를 저장할 때 header or trailer에 같이 저장한다.
Partitioning
- 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
- 섹터 영역들을 묶어서 하나의 독립적인 디스크로 만들고, OS는 이것을 독립적인 디스크로 취급(logical disk)
  - ex) C 드라이브, D 드라이브
Logical formatting
- 파일 시스템을 만드는 것
- FAT, inode, free space 등의 구조 포함
Booting
- 파일 시스템 안에 있는 운영체제가 메모리에 올라와서 부팅된다.
- 부팅의 절차
  1. 처음 메모리는 다 비어있는 상태
  2. CPU는 메모리만 접근할 수 있는 장치이기 때문에 하드 디스크는 CPU가 직접 접근할 수 없다.
  3. 전원을 켜게 되면 CPU 제어권이 ROM(전원이 나가더라도 내용 유지)의 주소를 가리키고, ROM에 저장되어 있는 “small bootstrap loader(부팅을 위한 간단한 로더)”가 instruction의 형태로 실행된다.
  4. Sector 0(boot block)을 메모리에 load 하고 실행한다.
  5. Sector 0은 “full Bootstrap loader program”
  6. 파일 시스템에서 운영체제 커널의 위치(Sector 0가 알아서 지시)를 찾아서 메모리에 올려 실행한다.
  7. OS가 메모리에 올라가서 부팅이 이루어진다.

3. Disk Scheduling

디스크에 대한 접근시간(access time)
- 탐색 시간(seek time): 헤드를 해당 실린더로 움직이는 데 걸리는 시간, 가장 큰 시간 구성 요소
- 회전지연시간(rotational latency): 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
- 전송시간(transfer time): 실제 데이터의 전송 시간, 굉장히 작은 시간 차지
Disk bandwidth: 단위 시간당 전송된 바이트의 수, bandwidth를 높이려면(= 효율적으로 동작하려면) seek time을 줄여야 한다.
디스크 스케줄링: 효율적인 디스크 입출력을 위해 여러 섹터들에 대한 입출력 요청이 들어왔을 때 이들을 어떠한 순서로 처리할 것인지 결정하는 메커니즘으로 seek time을 최소화하는 것이 목표이다.

3-1. FCFS(First Come First Service) 스케줄링

디스크에 먼저 들어온 요청을 먼저 처리하는 방식
디스크 헤드가 움직이면서 서비스하기 때문에 탐색시간이 매우 비효율적으로 늘어날 수 있다.

3-2. SSTF(Shortest Seek Time First) 스케줄링

헤드의 현재 위치로부터 가장 가까운 위치에 있는 요청을 제일 먼저 처리하는 알고리즘
헤드의 이동 거리를 줄여 디스크 입출력의 효율성을 증가시키지만, 자칫 기아 현상(starvation)을 발생시킬 수 있다.

3-3. SCAN 알고리즘

disk arm이 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다. 다른 한쪽 끝에 도달하면 역방향으로 이동한다.
엘리베이터 스케줄링 알고리즘이라고도 부른다.
FCFS처럼 불필요한 헤드의 이동이 발생하거나 SSTF처럼 일부 지역이 지나치게 오래 기다리는 기아 현상이 발생하지 않는다.
→ 효율성과 형평성을 모두 만족
실린더 위치에 따라 대기 시간이 달라, 모든 실린더 위치의 기다리는 시간이 공평한 것은 아니다.
- 제일 안쪽이나 제일 바깥쪽 < 가운데 위치가 기다리는 평균 시간

3-4. C-SCAN 알고리즘

SCAN 알고리즘의 위치에 따른 탐색시간의 편차를 보완
헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다. 그러나 SCAN과 달리 헤드가 다른 쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동한다.
SCAN보다 좀 더 균일한 대기 시간을 제공

3-5. N-SCAN

SCAN의 변형 알고리즘
일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service
기다리는 시간의 분포가 조금 더 균일하다.

3-6. LOOK and C-LOOK

LOOK 알고리즘은 헤드가 한쪽 방향으로 이동하다가 그 방향에 더 이상 대기 중인 요청이 없으면 헤드의 이동 방향을 즉시 반대로 바꾸는 스케줄링 방식
- SCAN 알고리즘에서는 요청의 존재 여부와 관계없이 헤드가 무조건 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동한다.
C-LOOK 알고리즘은 전방에 요청이 없을 때 방향을 바꾼다는 측면에서는 LOOK과 유사하며, 한쪽 방향으로 이동할 때에만 요청을 처리한다는 점에서 C-SCAN과 유사하다.

3-7. Disk-Scheduling Algorithm의 결정

SCAN 기반 알고리즘(C-SCAN, LOOK, C-LOOK 등)이 일반적으로 디스크의 입출력이 많은 시스템에서 디스크 헤드의 이동거리를 줄여서 효율적인 것으로 알려져 있다.
File의 할당 방법(연속 할당, 산발적 할당)에 따라 디스크 요청이 영향을 받는다.,
디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직하다.
- 여러 요청을 merge(묶어서) 한 번에 처리하는 경우에 디스크 I/O의 처리 효율성을 높일 수 있다.

4. Swap-Space Management

디스크를 사용하는 두 가지 이유: 메모리의 제약 조건 때문
- 메모리의 휘발적(volatile) 특성 → 파일 시스템처럼 영속적으로 데이터를 유지해야 하는 경우 비휘발성의 디스크를 사용해야 한다.
- 프로그램 실행을 위한 메모리 공간 부족 → swap space(swap area) 용도로 사용한다.
하드디스크에서 Swap-space 관리
- virtual memory system에서는 디스크를 memory의 연장 공간으로 사용
- 파일 시스템 내부에 둘 수도 있으나 별도 partition 사용이 일반적
- swap area 용도는 공간 효율성보다는 속도 효율성이 우선이다. → 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조되기 때문에 탐색시간을 줄이고자 데이터를 올리고 내리는 단위는 굉장히 큰 단위를 순차적으로 할당한다.

5. RAID

Redundant Array of Independent Disks
여러 개의 디스크를 묶어서 사용하는 방법
RAID의 사용 목적 ⇒ 중복 저장, 분산 저장
- 디스크 처리 속도 향상
  - 여러 디스크에 block의 내용을 분산 저장해서
  - 병렬적으로 읽어와서 빠르다.
  - interleaving, striping
- 신뢰성(reliability) 향상
  - 동일 정보를 여러 디스크에 중복 저장해서
  - 하나의 디스크가 고장 시 다른 디스크에서 읽어올 수 있다.
  - mirroring, shadowing
  - 단순한 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다.
  - parity: 중복 저장의 정도를 매우 낮게 해서 오류가 생겼는지를 알아내고 복구할 수 있을 정도의 중복 저장만 할 수 있게 해 준다.

[복습]

디스크의 물리적인 구조: 마그네틱 원판 > 트랙(x n = 실린더) > 섹터
- 논리 블록: 디스크 외부에서 디스크 접근의 최소 단위, 1차원 배열처럼 취급
- 섹터: 논리 블록이 물리적인 디스크에 매핑된 위치, 디스크를 관리하는 최소 단위
디스크 관리
- physical formatting: 디스크를 섹터들로 나누는 과정, header + 실제 데이터 + trailer
- partitioning: 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
- logical formatting: 파일 시스템을 만드는 것
- booting: 파일 시스템 안에 있는 운영체제가 메모리에 올라와서 부팅
디스크 스케줄링
- 탐색 시간, 회전지연시간, 전송시간, disk bandwidth
- FCFS 스케줄링
- SSTF 스케줄링
- SCAN 알고리즘: 역방향
- C-SCAN 알고리즘: 일방향
- N-SCAN
- LOOK: 대기 중인 요청이 없으면 헤드의 이동을 즉시 반대로 바꿈
- C-LOOK: 대기 중인 요청이 없으면 헤드의 이동을 출발 위치로 이동
- SCAN 기반 알고리즘이 일반적으로 입출력이 많은 시스템에서 헤드의 이동거리를 줄여서 효율적
Swap-Space Management: 메모리의 제약 조건 때문(휘발적 특성, 메모리 공간 부족)
하드 디스크에서 swap-space는 공간 효율성보다는 속도 효율성이 우선
RAID: 여러 개의 디스크를 묶어서 사용하는 방법 -> 중복 저장, 분산 저장

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제] 강의 정리입니다.

반효경 교수님의 [운영체제와 정보기술의 원리] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140523151255773807?vmode=f

반효경 [운영체제] 27. Disk Management & Scheduling 1

설명이 없습니다.

core.ewha.ac.kr

https://core.ewha.ac.kr/publicview/C0101020140527124647396004?vmode=f

반효경 [운영체제] 28. Disk Management & Scheduling 2