리눅스 커널 심층 분석 개정 3판 : 14장. Block 입출력 계층 Linux Kernel Development Third Edition : Chapter 14. The Block IO Layer

리눅스 커널 심층 분석 개정 3판 : 14장. Block 입출력 계층  

Linux Kernel Development Third Edition : Chapter 14. The Block IO Layer

리눅스 커널 심층분석

Notion에서 보기 

 

---

Linux Kernel Development

1. The Block I/O Layer

=> 이번 챕터에서 커널이 어떻게 블록 디바이스와 블록 디바이스 요청을 관리하는지에 대해 배움 ( = block I/O layer)

1. Anatomy of a Block Device

• I/O Device의 유형
• Block device:
• Block*을 랜덤으로 접근하는 하드웨어 디바이스

-> 랜덤 접근하기 때문에 블록은 연속적일 필요가 없음.

*Block = 고정된 크기의 데이터 덩어리

1. ex) 하드디스크, 블루레이, 플래시 메모리

• 현재 위치에서 back and forth로 네비게이션 가능

-> 전체적인 블록 디바이스의 구조를 파악하고 있어야 현재 위치에서 다른 곳으로 이동가능하기 때문에 커널이 블록 디바이스를 관리하는 전체 서브 시스템을 제공해야 함

• 블록 디바이스는 전체 성능에 많은 영향을 미침

-> 최적화 대상이 되어야 함

• Character device:
• Stream*을 1byte씩 순차적으로 접근하는 하드웨어 디바이스

*stream = 연속적 데이터

1. ex) 키보드, 시리얼 포트

• 하나의 위치 정보(현재 위치)만 가지고 있음
• Block Device의 구조
• Sector (=device block):
• 블록 디바이스에 접근 가능한 최소 단위 / 디바이스의 물리적 속성

->디바이스가 여러 섹터에 동시에 연산을 수행해도 sector보다 작은 단위를 대상으로 연산 불가

• 일반적으로 512 bytes

=> 모든 디바이스 입출력은 섹터 단위로 이루어짐

• Block (=filesystem block, I/O blocks):
• 커널/파일시스템에서 논리적으로 접근/연산할 수 있는 최소 단위
• 일반적으로 sector크기의 배수 (512B, 1KB, 4KB)
• 파일 시스템 블록 ⊃ 여러 개의 섹터
• 커널은 페이지보다 작은 사이즈의 블록을 2^* 개 필요로 함

->블록이 페이지 안에 적재될 수 있음

=> 물리적 단위 sector (device block) -> 논리적 단위 block in 파일시스템

• Buffers and Buffer Heads

: 블록이 메모리에 저장 -> 버퍼에 저장

• Buffer:
• 메모리에서 block을 표현하는 객체
• Block이 read, pending write 이후에 메모리에 저장되면 버퍼에 저장됨.

->메모리안에 페이지는 하나에 여러 개의 블록을 저장할 수 있음

• Buffer:Block = 1:1 (page ⊃ block ⊃ 여러 개의 sector)
• Buffer head: (-block descriptor 역할)
• 버퍼가 가지고 있는 블록, 블록 디바이스 등의 제어 정보를 담은 descriptor
• struct buffer_head 구조체 in <linux/buffer head.h>
• 물리적 메모리 버퍼 (특정 페이지의 바이트) - 논리적 디스크 블록 맵핑을 위한 정보 나타내기 위한 구조
• 담고 있는 정보: 버퍼 상태 플래그 (버퍼가 유효한 데이터를 가지고 있는지, 수정됐는지 등), 버퍼를 담고 있는 페이지 리스트, 관련된 페이지, 시작 블록 넘버, 맵핑 사이즈, 페이지 내의 데이터 위치 정보, 관련된 블록 디바이스, 입출력 완료 정보, 관련됨 맵핑, 관련된 메모리 주소, 사용 횟수

**bh_state flag: 버퍼 상태 정보 in 버퍼 헤드

: BH_PrivateStart*의 마지막 값 포함

-> 다른 코드가 사용할 수 있도록 하는 첫번째 사용가능 bit

->BH_PrivateStart와 같거나 큰 값은 블록 I/O 계층을 적절하게 사용할 수 없음 (작아야 사용가능) ->왜 이런 기능이..?

**b_count : 버퍼 사용 카운트

버퍼 헤드를 조작하기 전에 b_count를 증가시켜야 함 사용이 끝나면 다시 감소시킴

** b_bdev(블록 디바이스)에 있는 논리적 블록을 가리키는 b_blockne(버퍼) 1개

** b_page : 해당 버퍼가 담긴 페이지

** b_data: b_page 안에 있는 블록 위치 정보

**b_size: b_data/버퍼에 있는 블록의 크기 (byte)

->블록의 메모리 주소: b_data+b_size

• 메모리 ⊃ 페이지 ⊃ 버퍼 1 ⊃ 블록 1 (파일 시스템의 논리적 단위) ⊃ 여러 개의 섹터 (디스크 단위)

1. The bio Structure

: 디바이스 입출력, 연산 등을 위해 커널에게 버퍼 헤드는 중요한 자료 구조

-> 디스크 블록 - 페이지 맵핑 정보 담는 역할 + 입출력 블록 컨테이너

-> 버퍼 헤드의 문제: 너무 크고, 조작이 어렵고, 비효율적임 / 하나의 버퍼 정보만 담고 있어서 여러 블록 접근이 필요한 연산시에 여러 번 버퍼 헤드를 조작하여 연산을 쪼개서 해야 함.

-> 그래서 버퍼헤드를 대체하기 위해 등장한 블록 입출력 연산을 위한 가볍고 유연하고 새로운 컨테이너 = bio structure

• The bio Structure

: 커널 내부에 블록 입출력을 위한 베이직 컨테이너

Represent an in-filght (active) block I/O operation / block I/O request* 표현

I/O 연산에 필요한 정보: I/O 연산을 수행할 디스크 영역의 정보 + I/O 연산을 수행할 데이터를 저장하기 위한 메모리 영역 정보 (파일 시스템 블록 – 디스크 섹터 맵핑 정보)

*블록 입출력 요청은 bio_vec(메모리의 segment) 배열에 저장된 하나 이상의 블록으로 구성됨

• <linux/bio.h>
• Bio structure = segment* 리스트 형태의 블록 입출력 연산

*Segment: 메모리에 연속적인 버퍼 chunk

-> 버퍼를 chunk로 구성

**버퍼는 한 개의 블록을 담았다면 bio는 여러 개의 블록을 담고 있음

-> 커널이 메모리에 산재되어 있는 버퍼에 블록 입출력 연산 수행 가능하게 함 (= scatter-gather I/O , vector I/O)

** bi_io_vec: bio vec list/ 입출력 연산의 첫번째 segment 가리킴

**bi_vcnt: bio-vecs가 offset (bio vec 내부의 segment의 개수 )

**bi_idx: bio_io_vec에서 현재 segment인덱스 / 입출력 연산 부분적 완료시마다 갱신

->bio structure를 쪼개서 연산 수행할 수 있게 함

**bi_cnt: usage count / 0 이면 bio_structure 소멸, 메모리 반납 / 사용 전후 조작 필요

**bi_private: 해당 bio_structure의 소유자/생성자를 위한 프라이빗 필드 -권한 설정

<보충>

**bi_end_io:

• Interrupt 기반 I/O 처리: context switching을 통해 I/O 요청을 한 프로세스를 I/O 완료 인터럽트가 올때까지 해당 프로세스를 휴면상태로 전환하는 방식

=> interrupt 발생

->CPU의 각종 레지스터와 상태를 스택에 저장

-> interrupt handling을 위해 종류에 맞는 interrupt service routine 수행

-> 스택에 저장했던 CPU 정보를 다시 불러들여 원래 수행하던 프로그램 동작

=> CPU 효과적 사용 (I/O 완료 인터럽트가 없는 동안 다른 일을 할 수 있으므로) / context switching으로 인한 오버헤드

• Polling 기반 I/O 처리: context switching을 하지 않고, 주기적으로 I/O가 완료되었는지 직접 확인

=> I/O 요청 처리가 완료될 때까지 CPU를 사용하기 때문에 비효율적 CPU사용

/ 빠른 I/O처리가 가능한 고성능저장치에서는 효과적

• Hybrid I/O 처리 (리눅스 커널 10 버전부터 제공하는 방식): 프로세스를 특정 시간 .동안 휴면한 뒤 (interrupt 방식) 스케줄링하여 I/O 요청이 완료될 때까지 I/O 완료를 지속적으로 확인 (polling방식) 하는 방식

-> 각 I/O 크기별로 구분된 버킷에서 평균 응답 시간 구함

-> 평균 응답시간의 50% 동안은 휴면 + 나머지 50%는 폴링 방식으로 동작

=> 기존 폴링 방식의 절반 정도의 CPU 사용량 + 폴링 방식과 비슷한 응답 시간

(동기 I/O 요청 중 우선순위가 높은 I/O 요청의 경우에만 작동)

**bi_io_vec은 bio_vec 리스트를 가리키고 그 중 bi_idx로 현재 bio_vec에 접근, 각 bio_vec은 블록 입출력 연산에 필요한 페이지를 가리킴

• I/O vectors
• bio_vec structures: 특정 블록 입출력 연산에서 사용되는 segment (bio_vec)의 리스트

<page, offset, len> 형태의 vector로 취급

=<해당 segment가 들어 있는 페이지, 페이지 내에서 해당 블록에 접근하기 위한 오프셋, 오프셋에서부터 해당 블록의 길이> => 버퍼

• <linux/bio.h>
• 각 블록 입출력 연산마다 bi_vec에 bi_vcnt vector가 있음

bi_idx는 현재 블록 입출력 연산이 수행되는 vec을 가리킴

• 블록 I/O의 시작 지점 = submit_bio() 함수 -> bio structure를 인자로 받음
• The old vs the new = buffer head vs bio structure
• Bio structure = i/o operation : 메모리의 여러 개 페이지 포함

-> 블록 입출력 연산을 나타내는 최소한의 정보만 가지고 있어서 가벼움

->입출력 연산에 필요한 연속적 블록 포함 가능 (scatter-gather block I/O operation)

• Buffer head = 디스크에 있는 하나의 블록 : 하나의 페이지에 하나의 디스크 포함

->입출력 연산을 쪼개야 함

/ (디스크)block – (메모리)page mapping을 위해 여전히 필요함

1. Request Queues

: pending block I/O request (struct request in <linux/blkdev.h>)저장

• Request_queue in <linux/blkdev.h>

이중연결리스트 구조로 request, control information 저장

• struct request in <linux/blkdev.h> (큐에 저장된 request)

각 request는 하나 이상의 bio_structure로 구성됨 (여러 개의 연속적 블록에 연산을 수행하기 때문)

bio structure가 여러 개의 segment를 저장하기 때문에 디스크 상의 블록들은 인접해 있어야 하지만 메모리에 연속 할당할 필요는 없음

1. I/O Schedulers

• Disk seek: 디스크 헤드를 특정 블록에 위치 시키는 작업

-> 시간 오래 걸림 -> 성능에 큰 영향 -> 디스크 성능 최적화 필요

-> 커널이 block I/O operation 스케줄링 해야 함 – merging, sorting operation 수행

-> 큐에 대기 중인 block I/O operation 중에서 디스크 입출력 자원을 쪼갬

/ 블록 요청을 처리하는 블록 디바이스 가상화

• The Job of an I/O Scheduler

: 블록 디바이스의 request queue 관리

• 블록 디바이스에 대기 중인 각 요청들이 dispatch되는 시간, 순서 결정

->disk seek time을 줄여 global throughput 증가 (전체 성능 향상 효과)

• Merging: 두개 이상의 request를 하나로 합침

1. ex) 디스크의 인접한 섹터에서 read하는 연산들을 합쳐서 한 번에 요청 처리

-> disk seek 횟수, 시간 감소 / 오버헤드 감소

• Sorting: request queue에서 디스크의 섹터를 순차적으로 접근하는 request끼리 붙어있을 수 있도록 새로 들어오는 request는 디스크의 인접한 섹터에서 수행되는 request 옆에 둠
• The Linus Elevator = 리눅스의 I/O scheduler
• 4의 default I/O scheduler
• merge
• 새로운 요청이 큐로 들어오면 merge할 수 있는 요청이 있는지 기존의 대기중인 요청을 모두 살펴봄
• Front merge: new request immediately proceeds an existing request

(큐에 원래 있던 요청 앞에)

• Back merge: new request immediately precedes an existing request
• (큐에 원래 있던 요청 뒤에)
• Sort

: merge 실패

-> 대기 중인 요청 중에서 insertion point 찾기

-> 적절한 위치 찾으면 새로운 요청 삽입 / 없으면 큐의 tail에 삽입

• 삽입하려는 위치가 predefined threshold 보다 오래된 큐 앞이라면 insertion X, 새로운 요청은 tail에 삽입

-> 디스크의 한부분에서만 요청이 처리되고 다른 부분의 요청의 기아 현상 방지

-> age check 비효율적, starvation 문제

• The Deadline I/O Scheduler
• Request starvation -> writes starving reads* 유발

*writes stavring reads: write은 버퍼에서 merge, sort를 하여 연속 처리가 가능하지만 연속 처리 중 read 연산은 inter-dependent하게 동작하기 때문에 연속 처리가 불가능하다 -> read latency로 인해 시스템 전체 성능의 저하가 발생하는 현상

=> request starvation과 read starvation 최소화 보장을 위해 deadline I/O scheduler 등장

• 모든 요청은 expiration time있음 (default = 500ms for read, 5s for write)
• 디스크에 새로운 요청을 merge, sort는 elevator와 같은 방식으로 이루어짐 = sorted queue + 요청 종류에 따라 second queue*에 insert

*second queue = read FIFO queue, write FIFO queue, normal sorted queue

-> 새로운 요청들을 항상 second 큐의 tail에 삽입하게 됨

-> 각 second 큐의 head에서 expiration time이 지난 요청을 꺼내고 dispatch 큐로 삽입함

**dispatch 큐에서는 어떤 방식으로 스케줄링,,,,? FIFO??

-> 디스크 드라이브로 요청 전달

• 모든 요청이 expiration time 보다 적게 대기할 수 있도록 보장 / request starvation 방지 / read latency 최소화
• 전체 시스템 성능 향상 효과 미미
• The Anticipatory I/O Scheduler
• Deadline I/O scheduler + anticipation heuristic

: read 요청 처리 후 몇 ms (디폴트 - 6ms) 동안 아무것도 하지 않음

-> 응용프로그램이 다른 read요청을 보낼 수 있는 시간 줌 (time for anticipation)

-> 디스크의 인접한 부분에 발생하는 read 요청이면 처리 시간 빠름

/ 없으면 이전 요청을 계속해서 처리

=> 다른 작업 도중 발생한 read 요청 처리 후 back-and-forth seeking할 확률 감소

• Anticipatory I/O 스케줄러의 이점을 활용하기 위해선 경험을 기반으로 한 통계 자료를 근거로 예측 정확도를 높여야 함
• The Complete Fair Queueing I/O Scheduler

: 프로세스를 기반으로 I/O요청을 특정 큐에 삽입

1. ex) foo 프로세스에서 발생한 I/O 요청 -> foo 큐

• 각 큐에서 merge, sort 수행
• 프로세스 큐들을 RR로 서비스
• 현재 리눅스의 default I/O 스케줄러
• The Noop I/O Scheduler

: sorting, seek-prevention을 위한 알고리즘 X

• Merge는 수행함
• 완전히 랜덤 액세스를 수행하는 블록 디바이스를 위한 것

->seeking 오버헤드가 거의 없기 때문에 sorting이 필요 없음

1. ex) flash memory

• I/O Scheduler Selection

** 커맨드 라인 옵션 – elevator = (파라미터)