티스토리 뷰

크리에이티브 커먼즈 라이선스
Creative Commons License

2부 파일

제3장 버퍼 캐쉬

이전 장에서 언급했다시피, 커널은 디스크과 같은 대용량 저장장치에 파일을 유지하고, 프로세스가 새로운 정보를 저장하고 저장된 정보를 찾게 해준다. 프로세스가 파일내의 정보를 액세스할 때, 커널은 어느 메인 메모리에 데이터를 가져다 놓는데, 그 메인 메모리는 프로세스가 데이터를 검토, 변경하는 것과 파일로 저장할 수 있게 요청을 할 수 있는 공간이다. 예를들어, 그림 1.3의 copy 프로그램을 다시 살펴보자. 커널은 첫째파일의 데이터를 메모리로 읽어오고, 그 다음 두번째 파일에 읽은 데이터를 쓴다. 프로그램이 파일 데이터를 메모리로 가져다 놓을 때, 커널 또한 파일을 다루기위해 보조 데이터를 메모리에 읽어들인다. 예를 들자면, 파일 시스템의 수퍼블럭은 파일 시스템상에서 가용할 수 있는 자유 공간에 대한 정보를 담고있다. 커널은 가용 공간 정보에 액세스 하기 위해 슈퍼블럭을 메모리로 읽어들이고, 그 가용 정보를 저장하고 싶을 때 파일 시스템에 읽어들인 정보를 쓴다. 유사하게, 아이노드는 어느 파일의 레이아웃 정보를 담고 있다. 커널은 정보를 액세스 하기 위해 아이노드를 메인 메모리로 읽어들이고, 파일 레이아웃을 갱신하고 싶을 때 파일시스템에 아이노드 레이아웃을 저장한다. 명시적인 지식이나 실행중인 프로세스의 요청이 없어도, 커널은 이러헌 보조 데이터를 조작한다. 

커널은 모든 파일 시스템 접근에 대해, (다른 것을 거치지 않고)디스크로 직접 읽고 쓸 수 있지만, 디스크 전송율이 낮기 때문에 시스템 응답 시간과 처리량은 나빠질 것이다. 그래서 커널은 디스크 액세스 빈도를 적게 하기 위해, 내부에 데이터 버퍼풀을 유지하는데, 버퍼 캐시라 불리며 최근까지 사용된 디스크 블럭의 데이터를 담고 있다.

그림 2.1은 버퍼캐시 모듈이 커널 구조 내에서 파일 서브시스템과 (블럭)디바이스 드라이버 사이에 자리 잡고 있음을 보여준다. 디스크에서 데이터를 읽을 때, 커널은 버퍼 캐시에서 데이터를 읽으려고 시도한다. 만일 데이터가 캐시에 있다면, 커널은 디스크로부터 데이터를 읽지 않는다. 만일 데이터가 케시에 없다면, 커널은 데이터를 디스크에서 읽어들이며, 그것을 캐시에 저장하는데, '착한 데이터(good data)'를 가능한 많이 저장할 수 있는 알고리즘을 사용한다. 이와 유사하게, 만일 커널이 데이터를 디스크에 기록한 이후에 데이터를 다시 읽으려고 할 때, 그 데이터가 버퍼캐시에 존재할 수 있도록, 디스크에 기록되고 있는 버퍼는 캐싱된다('버퍼 캐시에서 곧바로 내리지 않고 유지한다'라는 의미). 또한 커널은 디스크에 반드시 저장해야하는 데이터인지 혹은 내용이 금방 변경되는 순간적인 데이터인지를 결정하여, 디스크 쓰기 연산의 빈도수를 최소화하려 노력한다. 고수준의 커널 알고리즘은 캐싱 효율을 극대화하기 위해, 데이터를 미리 캐시하거나 데이터 쓰기를 지연하는 것을 버퍼 캐시 모듈에 지시한다. 이 장은 캐시안의 버퍼를 조작하기 위해 커널이 사용하는 알고리즘을 설명한다. 

각주:
The buffer cache is a software structure that should not be confused with hardware caches that speed memory references.

번역 노트:
착한 데이터(good data)에 대한 고찰: '최근까지 사용 여부'라는 기준이 있으므로 good을 '착한'으로 번역한다.

3.1 버퍼 헤더

시스템을 초기화하는 동안, 커널은 버퍼를 위한 공간을 할당하는데, 메모리 크기와 시스템 성능 제약에 따라 구성할 수 있다. 버퍼는 두 부분으로 구성되어 있는데, 각각 디스크의 내용을 담고있는 메모리 배열과 버퍼를 식별하는 버퍼헤드이다. 버퍼 헤더 하나 당 데이터 버퍼로 매핑되기 때문에, 책의 뒤부분에서는 두 부분을 합쳐서 "버퍼"로 지칭하고, 논의되는 어느 부분은 책의 흐름안에서 명확하게 구별될 것이다.

버퍼에 있는 데이터는 파일 시스템상의 논리적인 디스크 블럭과 상응되며, 커널이 버퍼헤더에 있는 식별자 필드를 조사하여 버퍼 내용을 식별한다. 버퍼는 메모리에 위치한 '디스크 블럭의 복사본'이다. 디스크의 내용은 버퍼와 매핑되지만, 매핑은 커널이 그 매핑을 다른 디스크 블럭으로 변경하기 전까지 유효한 것으로, 임시적이다. 디스크 블럭은 동시에 두 개 이상의 버퍼와 매핑될 수 없다. 만일 두 버퍼가 같은 디스크 블럭의 데이터를 담고 있었다면, 커널은 어느 버퍼가 현재 데이터를 가지고 있는지 알 수 없고, 틀린 데이터를 디스크로 기록할 수도 있다. 가령, 디스크 블럭이 버퍼 A와 B에 매핑되었다고 가정해보자. 만일 커널이 처음에는 A에 데이터를 기록하고 난뒤 B에 다른 데이터를 기록했다면, 디스크 블럭에는 당연히 버퍼 B의 내용이 있어야 한다. 그러나, 커널이 버퍼를 디스크로 기록하는 순서를 A,B가 아닌 B,A 순으로 바꿨다면, 디스 블럭은 틀린 데이터를 가지게 된다.

버퍼 헤더(그림 3.1)는 파일 버퍼를 유일하도록 구별해주는 디바이스 번호 필드와 블럭 번호 필드를 가지고 있다. 디바이스 번호는 물리적 디바이스(디스크) 장치 번호가 아니라, 논리적 파일 시스템 번호(2.2.1을 참조)이다. 또한 버퍼헤더는 버퍼 배열을 가리키는 포인터를 가지고 있는데, 버퍼의 사이즈는 최소한 디스크 블럭 크기만큼 커야 한다. 버퍼헤드는 현재 버퍼의 상태를 요약해주는 상태 필드도 가지고 있다. 버퍼의 상태는 아래 컨디션의 조합으로 이루어진다. 

  • 버퍼가 현재 잠겨져(locked) 있다. (용어 "locked"와 "busy"는 교환 가능하다. "unlocked"과 "free"도 마찬가지다.)
  • 버퍼가 유효한 데이터를 가지고 있다.
  • 커널은 버퍼를 재할당 받기 이전에 버퍼 내용을 디스크에 반드시 기록해야 하며, 이 조건을 "지연된 쓰기(delayed-write)"라 한다.
  • 커널은 현재 버퍼를 읽거나 혹은 버퍼에서 디스크로 기록하는 중이다.
  • 프로세스는 현재 버퍼가 "free"될 때까지 기다리고 있는 중이다. 

또한 버퍼 헤더는 다른 포인터들도 가지고 있으며, 버퍼풀의 전반적인 구조를 유지하기 위하여 버퍼할당 알고리즘에서 이용된다. (다음 절에서 설명한다)

3.2 버퍼 풀의 구조

커널은 LRU(Least Recently Used: 최근까지 적게 사용된, '사용된지 오래된'을 내포한다.) 알고리즘에 따라 데이터를 버퍼풀에 캐시한다. 특정 디스크 블록에 대해 버퍼를 할당하고 나면, 다른 버퍼 모두가 최근에 보다 더 사용되어야, 비로소 그 버퍼를 다른 디스크 블럭을 위한 버퍼로 사용될 수 있다. 커널은 버퍼의 LRU 순서를 보존하고 있는 프리 리스트(free list)를 유지한다.(역주: 프리는 "해제"라는 뜻보다 "unlocked/free" 상태로 이해해야 한다.) 프리 리스트는 이중으로 연결된 환형 리스트이며, 리스트의 시작과 끝을 나타내는 더미해더를 가지고 있다 (그림 3.2). 시스템이 부팅 될 때, 모든 모든 버퍼가 프리 리스트에 삽입된다. 커널이 어떠한 프리 버퍼를 원하더라도, 프리 리스트의 첫번째 버퍼를 취하지만, 만일 버퍼풀에서 특정 블록의 버퍼를 원하며, 그 버퍼가 프리 리스트의 중간에 있다하더라도, 그 버퍼을 가지고 온다. 두 경우 모두, 커널은 그 버퍼를 프리 리스트에서 제외시킨다. 커널이 버퍼를 버퍼풀에 반환할 때, 버퍼를 프리 리스트의 꼬리쪽에 붙여 놓는데, 경우에 따라서 프리 리스트의 헤드에 붙이기도 한다(에러가 발생한 경우). 하지만, 중간에는 절대 붙이지 않는다. 커널이 버퍼를 프리 리스트에서 제거할 때, 유효한 데이터를 가진 버퍼는 프리 리스트의 헤더쪽으로 더욱 가까워진다 (그림 3.2). 그러므로, 프리 리스트의 헤더에 가까운 버퍼는 프리 리스트 헤드로부터 멀어지는 버퍼만큼 최근까지 사용되지 않았다.

커널이 디스크 블럭을 액세스 할 때, 적절한 디바이스-블럭 번호의 조합으로 버퍼를 찾는다. 버퍼풀 전체를 뒤져보는 것 보다는, 버퍼들을 구분된 큐로 조직하여, 디바이스와 블럭 번호의 해시값을 이용하여 검색한다. 커널은 프리 리스트 구조와 유사하게, 버퍼를 환형(circular) 큐로 연결한다(큐는 이중 링크드 리스트로 구현된다). 뒤에 나오는 바와 같이, 해시큐(hash queue)의 버퍼 개수는 시스템 운영동안 변한다. 커널은 버퍼를 해시큐 전반적으로 균등하게 분포시키는 해시함수를 이용해야 하지만, 해시 함수는 성능이 떨어지지 않도록 단순하기도 해야 한다. 시스템 관리자는 운영체제를 설치할(generating) 때 해시큐의 개수를 조정한다.

그림 3.3은 해시큐 상의 버퍼를 보여준다. 해시큐의 해더들은 그림의 왼쪽에 있고, 각 행의 사각형은 해시큐 상의 버퍼다. 이와 같이, 28, 4, 64로 표기된 사각형은 해시큐 "blkno 0 mod 4"(블럭번호 0 % 4) 상의 버퍼들이다. 버퍼사이의 점선은 이전과 이후에 대한 포인터인데, 설명이 단순하도록, 본장에서 나오는 그림들은 점선을 생략한다. 하지만, 실제로는 있다는 것을 유념해두자. 또한 그림에서는 블럭번호로 블럭을 구별하며 해시함수도 블럭번호만을 이용하지만, 실제 구현에서는 디바이스 번호도 사용한다.

각 버퍼는 해시큐상에서 항상 존재하지만, 큐상에서의 위치는 그리 중요치 않다. 위에서 언급한 것처럼, 어떤 한 블럭의 내용을 두 개의 버퍼가 동시에 가질 수 없으므로, 버퍼풀안에 있는 모든 디스크 블럭은 오직 단 하나의 큐 상에 그리고 단 한번 큐에 존재한다. 그러나, 만일 버퍼의 상태가 free(unlocked)라면 버퍼는 프리 리스트 상에도 있을 수 있다. 버퍼가 해시큐와 프리리스트에 존재할 수 있기 때문에, 커널은 버퍼를 찾기 위해 두 가지 방법을 가지고 있다. 특정한 버퍼를 찾고 있다면 해시큐에서 검색하고, 프리 버퍼를 찾는다면 프리 리스트에서 하나를 가져오는 것이다. 다음 절에서 커널이 버퍼 캐시에서 특정한 디스크 블럭을 어떻게 찾고, 해시큐의 그리고 프리 리스트의 버퍼를 어떻게 조작하는지 설명한다. 요약하자면, 버퍼는 항상 해시큐에 있으나, 프리 리스트에는 있을 수도 혹은 없을 수도 있다.

3.3 버퍼를 가져오는 시나리오

그림 2.1와 같이, 파일 시스템의 상위레벨 커널 알고리즘은 버퍼 캐시를 관리하는 (서브)알고리즘을 실행한다. 커널이 블럭을 검색(retrieve)할 때, 상위레벨 알고리즘은 액세스하고자 하는 논리 디바이스 번호와 블럭 번호를 결정한다. 예를 들자면, 만일 프로세스가 파일에서 데이터를 읽으려 한다면, 커널은 어떤 파일 시스템이 파일을 가지고 있는지와 어떤 블럭이 파일을 가지고 있는지 알아낸다(4장에서 알아본다). 특정 디스크 블럭에서 데이터를 읽을 때, 커널은 블럭이 버퍼풀에 있는 지 체크하고, 없다면, 프리 버퍼를 할당한다. 특정 디스크 블럭에 데이터를 기록할 때, 커널은 블럭이 버퍼풀에 있는지 체크하고, 없다면, 블럭에 대해 프리 버퍼를 할당한다. 디스크 블럭를 읽거나 쓰는 알고리즘은 getblk(그림 3.4)을 사용하며, getblk는 버퍼풀로부터 버퍼를 할당하는 알고리즘이다.


이번 절에서는 일반적인 다섯 가지 시나리오를 설명하며, 시나리오에서는 커널이 디스크 블럭에 버퍼를 할당하는 gelblk을 호출할 수 있다.

  1. 커널은 해시큐에서 찾고자 하는 블럭을 찾고, 그 블럭에 대한 버퍼가 "free" 상태이다.
  2. 커널이 해시큐에서 해당 블럭을 못 찾아서, 커널이 버퍼를 프리 리스트에서 제외시킨다.
  3. 커널이 해시큐에서 해당 블럭을 못 찾았다. 그래서 프리 리스트에서 버퍼를 가져오려 시도하던 차에(시나리오 2처럼), 프리리스트의 버퍼가 "지연된 쓰기(delayed write)"인 것을 발견했다. 커널은 "지연된 쓰기" 버퍼를 디스크에 기록하고, 다른 버퍼를 가져와야 한다.
  4. 커널이 해시큐에서 해당 블럭을 못 찾았고, 프리 리스트도 비어 있다.
  5. 커널이 해시큐에서 해당블럭을 찾았으나, 그 블럭은 현재 busy(locked) 상태이다.

각 시나리오를 자세하게 논의해 보자. 


디바이스-블럭 번호가 조합된 것으로 버퍼풀에서 블록을 찾을 때, 커널은 블럭을 포함해야 할 해시큐를 먼저 찾는다. 해시큐를 찾으면, 디바이스-블럭 번호가 일치하는 버퍼를 찾을 때까지 버퍼의 링크드 리스트를 따라간다(첫 번째 시나리오). 커널은 버퍼의 상태가 "free"인지 확인하고, 만일 그렇다면, (커널 모드에서 동작하는) 다른 프로세스가 액세스하지 못하도록 버퍼의 상태를 "busy"로 바꾼다. 그런 다음, 커널은 그 버퍼를 프리 리스트에서 제외시킨다. 왜냐하면, 버퍼는 "busy"이면서 프리 리스트에 존재할 수 없기 때문이다. 만약 버퍼가 "busy"인데 다른 프로세스들이 블럭에 접근하고자 한다면, 프로세스들은 버퍼가 "free"되기 전까지 sleep 한다(후에 설명함). 그림 3.5는 커널이 "blkno 0 mod 4"로 표기된 해시큐에서 4번 블럭을 찾는 첫 번째 시나리오를 보여주고 있다. 해당 버퍼를 찾으면, 커널은 프리 리스트에서 해당 버퍼를 제외시키며, 인접한 5번, 28번 블럭은 프리 리스트에 남겨둔다.


다른 시나리오를 설명하기 전에, 버퍼가 할당된 후, 버퍼에게 무슨 일이 일어났는지 살펴보자. 커널이 디스크에서 버퍼로 데이터를 읽은 후 데이터를 조작하거나, 혹은 커널이 데이터를 버퍼 혹은 (내키면) 디스크에 기록할 수도 있다. 커널은 "busy"인 버퍼를 내버려 둔다 (버퍼가 "busy"인 동안에는 다른 프로세스가 액세스해서 변경할 수 없다. 이로써 데이터의 무결성을 보존한다.) 커널이 해당 버퍼를 더 이상 사용하지 않을 때, brelse 알고리즘(그림 3.6)을 이용하여 버퍼를 해제한다. 커널이 sleep 상태인 프로세스들를 깨운다. 왜냐하면 버퍼가 "busy"였거나, 프리 리스트에 남아있는 버퍼가 없어서 sleep 상태로 들어 갔기 때문이다(역주: 그림 3.4를 참조하라). 두 경우에서, 버퍼 해제라는 것은 버퍼를 잠근 프로세스가 sleep 함으로 인해 버퍼를 사용할 수 있다는 것을 뜻한다(2.2.2.4절 참조). 심지어 버퍼를 가진 프로세스가 버퍼를 잠근 뒤 다른 프로세스가 버퍼를 획득하는 것을 방지하더라도, sleep 상태에 들어가면 그 버퍼는 해제되어 사용 가능할 것이다. 정상적인 경우의 버퍼인 경우, 커널은 버퍼를 프리 리스트의 끝부분에 놓는다(이번 장에서 설명). I/O 에러가 발생하거나 버퍼가 "old"라고 표기되어 있다면, 경우에서 커널은 버퍼를 프리 리스트의 첫번째 부분에 놓는다(이장 뒤에서 설명). 버퍼는 이제 "free"이며, 다른 프로세스가 버퍼를 요청할 수 있다.


프로세스가 버퍼를 사용할 필요가 없을 때 커널이 brelse를 호출하는 것처럼, 디스크 인터럽트 핸들러가 실행되었는데 비동기(asynchronous) I/O에 사용된 버퍼를 해제하는 경우에도, 커널이 brelse를 호출한다.(3.4절에서 설명함). 커널은 프리 리스트를 조작하는 동안 프로세스의 실행 레벨을 높이는데, 그 동안 디스크 인터럽트가 발생되는 것을 막기 위해서이다. 안그러면 brelse가 중첩적으로 호출(nested call)되어 버퍼 포인터가 깨질 수 있다. 만일 프로세스가 getblk를 실행하던 중간에 인터럽트 핸들러가 brelse를 호출한다면, 이와 유사한 악영향이 발생한다. 따라서 커널은 getblk 안의 중요한 부분에서 프로세서 실행 레벨을 높인다. 이경우를 연습문제에서 상세히 다룬다.


알고리즘 getblk의 두번째 시나리오에는, 커널이 블럭을 담고 있는 해시큐안을 검색하나, 안에 없는 없는 경우이다. 어느 블럭은 다른 해시큐를 '해시'할 수 없으므로, 해당 블럭은 다른 해시큐에 있을 수 없다. 따라서 블럭은 버퍼캐시에 없다. 따라서 커널은 프리 리스트의 첫번째 버퍼를 가져온다. 그 버퍼는 다른 디스크 블럭의 내용을 가지고 있고, 뿐만아니라 어느 해시큐 상에 존재한다. 만일, "delayed-write"로 표시된 버퍼가 아니라면(추후에 설명함), 커널은 버퍼를 "busy"라 표시하고, 현재 소속된 해시큐에서 제외시킨다. 그 다음, 버퍼 헤더에 디바이스 번호와 블록 번호를 기록하고, 끝으로 해당 해시큐에 달아놓는다. 커널은 버퍼를 사용하지만, 커널은 버퍼가 한때 다른 디스크 블럭의 데이터를 담았다고 기록하지 않는다. 자기가 사용하던(old) 디스크 블럭을 찾는 프로세스는 버퍼풀에서 해당 블럭을 찾을 수 없을 것이고, 프리리스트에서 새로운 블럭을 할당받아야 할 것이다. 커널이 버퍼를 다 사용하면, 위에서 설명한 것처럼 해제한다. 예를들어, 그림 3.7에서 커널이 블럭 18을 찾으려고 하나, 해시큐 "blkno 2 mod 4"에서 못 찾을 것이다. 따라서 커널은 프리리스트의 첫번째 버퍼(블럭 3)을 가져와서 블럭 18로 할당하고, 적합한 해시큐("blkno 2 mod 4") 안에 놓는다.


알고리즘 getblk의 세번째 시나리오는, 이번에도 역시 커널이 프리 리스트에서 버퍼를 가져온다. 그러나, 커널이 가져온 버퍼가 "delayed write"라고 표시된 것을 발견했다. 그래서 커널이 버퍼를 사용하기 전에 버퍼의 내용을 디스크에 기록해야 한다. 커널이 비동기 쓰기를 시작하고, 프리리스트에서 다른 버퍼를 할당받으려 할 것이다. 비동기 쓰기가 완료되면, 커널은 버퍼를 해제하고, 프리 리스트의 헤더에 달아 놓는다.(역주: 이 일은 디스크 인터럽트 핸들러가 한다. 3.4절 마지막 문단 참조) 해당 버퍼는 과거에 프리 리스트의 끝에서 시작하여, 프리 리스트 헤더쪽으로 이동했었다(역주: 즉, 해당 블럭이 victim이 될 차례였다). 만일 비동기 쓰기가 완료된 후에 커널이 프리리스트의 끝에 놓았다면, 버퍼는 프리리스트를 공짜로 통과했을 것인데, 이는 LRU 알고리즘에 위배된다. (역주: 나중에 들어온 다른 버퍼가 victim이 되버리므로 이는 명백히 규칙을 위반한 것이다). 예를 들어, 그림 3.8에서 커널은 블럭 18을 찾을 수 없다. 프리리스트의 처음 두 버퍼(한번에 하나)를 가져오려고 시도하지만, "delayed-write"라고 표시된 것을 발견할 것이다. 커널은 프리 리스트에서 앞의 두 버퍼를 프리 리스트에서 가져와 쓰기 작업을 시작할 것이고, 세 번째 버퍼 "블럭 4"를 가져온다. 그런 다음, 버퍼 헤더에 디바이스-블럭 번호를 해당 값으로 설정하고, 버퍼를(블럭 18) 적합한 해시큐에 넣는다.


네 번째 시나리오(그림 3.9)에서 프로세스 A를 위해 동작하는 커널은 해시큐에서 어느 디스크 블럭에 해당하는 버퍼를 을 찾을 수 없어서, 2번 시나리오처럼 프리리스트에서 새로운 버퍼를 가져오는 것을 시도할 것이다. 그러나, 프리리스트에 버퍼가 없으므로, 프로세스 A는 다른 프로세스가 brelse(버퍼를 해지)을 실행하기 전까지 sleep 상태에 들어간다. 커널이 프로세스 A를 스케줄링할 때, 커널은 해시큐안에 해당 블럭이 있는지 다시 찾아봐야 한다. 커널은 프리 리스트의 버퍼를 즉각적으로 가져올 수 없다. 왜냐하면, 여러 프로세스가 버퍼를 할당받기 위해 대기중이였는데, 그 프로세스 중 하나가 프로세스 A가 원하던 블록에 대한 버퍼를 할당받았을 수도 있기 때문이다. 이와 같이, 블럭 버퍼를 다시 한번 살펴보는 것은 "디스크 블럭와 매핑되는 버퍼는 단 하나"라는 것을 보장해준다. 그림 3.10에서는 두 프로세스가 하나의 프리 버퍼를 두고 경쟁하는 것을 보여준다.


마지막 다섯 번째 시나리오(그림 3.11)은 복잡하다. 왜냐하면, 다수의 프로세스간에 복잡한 관계를 가진 경우이기 때문이다. 프로세스 A를 위해 동작하는 커널이 디스크 블럭을 검색하고 버퍼를 할당받았지만, 버퍼를 free 하기 전에 sleep 된다고 가정하자. 예를들어, 만일 프로세스 A가 2번 시나리오처럼 디스크 블럭을 읽고 버퍼를 할당받는 것을 시도한다면, 프로세스는 I/O 전송이 끝나길 기다리는 동안 sleep 상태가 될 것이다. 프로세스 A가 sleep 인 동안, 커널이 프로세스 B를 스케줄링 했다는 것을 가정해보자. 프로세스 B는 어느 블럭에 접근하려 하는데, 그 블럭은 A가 lock한 버퍼에 매핑된 것이라는 것도 가정하자. 그렇다면, 프로세스 B(5번 시나리오을 통과하는?)는 해시큐 상에 있는 해당 블럭이 잠겨저 있다는 것을 알게 된다. locked 버퍼를 사용하는 것과 같은 블럭에 대해 두번째 버퍼를 할당 받는 것은 규칙 위반이기 때문에 (그렇게 하지 않고) 프로세스 B는 해당 버퍼에 "in demand" 라고 표시한 다음, 프로세스 A가 버퍼 해제하기를 sleep 하며 기다린다.


번역 노트:
in demand 요구가 많은


이후에 프로세스 A는  버퍼를 unlock하고, 버퍼가 "in demand"인 것에 주목한다. 프로세스 A는 "해당 버퍼가 free됨"을 기다리는 모든 프로세스(B도 포함)를 깨운다. 커널이 프로세스 B를 스케줄링할 때, B는 버퍼가 free인지 검증한다. 프로세스 C는 같은 버퍼를 기다려 왔었고, 커널은 B 이전에 C가 실행되도록 C를 스케줄링 했었다. C가 버퍼가 잠긴채로 sleep 상태가 되었을 수도 있다. 따라서 프로세스 B는 블럭이 실제로 free 인지 확인해야 한다.


또한, 프로세스 B는 버퍼가 원래 요청한 블럭과 매핑되어 있는지 검증해야 한다. 왜냐하면, 2번 시나리오처럼 프로세스 C가 버퍼를 다른 디스크 블럭에 매핑했을 수 도 있기 때문이다. 프로세스 B가 실행될 때, 프로세스가 B가 틀린 버퍼를 기다려온 것을 알게 된다면, 블럭을 해시큐에서 다시 찾아야 한다. 왜냐하면 다른 프로세스가 해당 블럭을 할당받았을 수 있기 때문이다. 이를 간과하고 프리 리스트로에서 버퍼를 가져온다면, 이중적으로 버퍼를 할당하는 문제가 발생한다.

최종적으로 프로세스 B는 해당 블럭을 찾을 것인데, 2번 시나리오처럼 프리리스트에서 가져온 버퍼를 할당받았을 수 도 있다. 예를들어, 그림 3.11에서 블럭 99을 찾는 프로세스가 해당 버퍼를 해시큐에서 찾지만, 버퍼가 "busy"이다. 프로세스는 블럭이 "free"될 때까지 sleep 하며, (깨어난다면) getblk 알고리즘을 처음부터 다시 시작한다. 그림 3.12는 locked 버퍼에 대해 경쟁하는 것을 보여준다. 


버퍼 할당 알고리즘은 반드시 안전해야 한다. 프로세스들은 영원히 sleep 하면 안되며, 언젠가는 프로세스들이 버퍼를 획득해야 한다. 커널은 버퍼를 기다리는 모든 프로세스가 wakeup되는 것을 보장한다. 왜냐하면, 커널은 시스템 콜이 실행되는 동안 버퍼를 할당하며, 시스템 콜의 실행이 끝나기 전에 버퍼를 free 하기 때문이다*. 유저모드 프로세스는 커널 버퍼의 할당을 직접적으로 제어할 수 없다. 따라서, 유저모드 프로세스는 버퍼를 고의적으로 독식(hog)하지 못한다. 커널이 버퍼에 대해 제어할 수 없을 때는 버퍼에 대해 디스크 I/O가 발생해서 그것이 끝나길 기다릴 때이다. 디스크 드라이브에 에러가 발생해서 CPU를 인터럽트할 수 없는 것을 생각해볼 수 있는데, 커널이 버퍼를 free하는 것을 막아버린다. 디스크 드라이버는 그런 경우에 대비해 하드웨어를 모니터해야 하며, 잘못된 디스크 작업에 대해 커널에게 에러를 알려야 한다. 간단히 말해, 커널은 '버퍼를 기다리며 sleep하는 프로세스가 언젠가 wakeup 하는 것'을 보장한다.

 

mount() 시스템 콜은 예외이다. 왜냐하면 unmount()를 호출하기 이전까지 메모리를 해제하지 않는다. 이 예외는 치명적이지 않다. 총 버퍼 수가 마운트한 파일 시스템의 수보다 훨씬 클 것이기 때문이다.


프로세스가 버퍼를 기다리다가 굶주리는(starve) 상황도 상상할 수 있다. 예를들어, 4번 시나리오에서 몇몇 프로세스들은 그 버퍼가 free 되기 전까지 sleep 한다. 나중에 그 프로세스들이 버퍼를 할당받을 때, 커널은 요청한 순서대로 할당하는 것을 보장 못한다. 프로세스들이 sleep 인데, 버퍼가 free되면 wakeup 한다. 그러나 다른 프로세스가 먼저 버퍼 제어권을 먼저 얻으면, 나머지 프로세스는 sleep 한다. 이론적으로는 영원히 sleep 될 수도 있겠지만, 실제적으로는 시스템에서 설정되는 버퍼가 많기 때문에 이것은 문제가 되지 않는다.


3.4 디스크 블럭의 I/O

이제 버퍼 할당 알고리즘은 설명하였으니, 디스크 읽기/쓰기 프로시져를 쉽게 이해할 것이다. 디스크 블럭을 읽기 위해(그림 3.13), 프로세스 getblk 알고리즘을 사용하여 버퍼캐시에서 버퍼를 찾는다. 만일 찾고자 하는 버퍼가 캐시 안에 있다면, 커널은 디스크에서 읽지 않아도 된다. 그 버퍼가 캐시 안에 없다면, 커널은 디스크 드라이버를 호출하여 읽기 작업을 스케줄링하고 난 후, 자신은 sleep 하여 I/O가 끝나기를 기다린다. 디스크 드라이버는 디스크 컨트롤러에게 읽기 원하는 데이터가 있다는 것을 알리고, 이후 디스크 컨트롤러는 데이터를 버퍼로 전송한다. 마침내, I/O가 끝나면 디스크 컨트롤러는 프로세스를 인터럽트하며, 디스크 인터럽트 핸들러는 sleep 하던 프로세스를 깨운다. (이 시점에 디스크 블럭의 내용은 이네 버퍼에 있다). 특정 블럭을 요청했던 모듈은 이제 데이터를 가진다. 버퍼 안의 데이터를 더 사용하지 않는다면, 버퍼는 unlock되어서 다른 프로세스가 사용할 수 있게 된다. 


프로세스가 순차적으로 읽을 때, 상위 수준 커널 모듈(파일 서브시스템처럼)이 두번째 디스크 블럭에 대한 수요를 어떻게 예측하는 가를 5장에서 설명한다. 모듈이 두 번째 I/O를 비동기적으로 미리 요청한다. 데이터를 요구할 때 메모리 안에 미리 있으면 성능이 향상 된다. 이것을 하기 위해 커널은 블럭 미리 읽기 알고리즘 breada을 실행한다. 커널은 첫번째 블럭이 캐시안에 있는지 체크하고, 없다면 디스크 드라이브를 호출하여 디스크 블럭을 읽는다. 만약 두 번째 블럭이 버퍼 캐시에 없다면, 커널은 I/O에게 명령하여 두번째 블럭을 비동기적으로 읽어 들인다. 그런 다음 프로세스는 sleep 상태로 들어가 첫번째 블럭을 읽는 I/O가 끝나길 기다린다. 깨어난 후, 첫번째 블럭을 반환하며, 두번째 블럭을 읽는 I/O는 신경쓰지 않는다. 만일 두번째 블럭 I/O가 끝났다면, 디스크 컨트롤러는 시스템을 인터럽트한다. 즉, 인터럽트 핸들러는 두번째 읽기가 비동기 I/O 였음을 알아내고 버퍼를 unlock 한다 (brelse 알고리즘). 만일 버퍼를 unlock 하지 않으면, 버퍼는 lock 된 상태로 남으므로 어떤 프로세스라도 접근할 수 없다. 버퍼는 미리 unlock 될 수 없다. 왜냐하면, 그 버퍼에 대한 I/O가 진행중이었으므로 버퍼의 내용 역시 유효하지 않을 것이다. 그 동안 I/O가 완료된 후에 프로세스가 두번째 블럭을 읽기 원한다면, 버퍼캐시에서 찾아야 한다. 만일 breada 의 시작 부분에서 첫번째 블럭이 버퍼캐시에 있었다면, 커널은 즉각 두번째 블럭이 캐시에 있는지 체크하고 위에서 설명했던 내용 그대로 진행한다.

 

버퍼의 내용을 디스크로 쓰는 알고리즘(bwrite)도 위와 비슷하다.(그림 3.15) 디스크 드라이버는 디스크로 기록되어야 버퍼를 가지고 있으며, 커널은 디스크 드라이버에게 쓰기 명령을 내린다. 명령을 받은 디스크 드라이버는 I/O 블럭을 스케줄링 한다(역주 10.1.2.4절 참조). 만일 쓰기가 동기적이라면, bwrite를 호출한 프로세스는 sleep 상태가 되어 I/O가 끝나길 기다리고, wakeup 후에 버퍼를 unlock 한다. 만일 비동기적으로 쓴다면, 커널은 쓰기를 시작하지만 쓰기가 완료되길 기다리지 않는다. 커널은 I/O가 완료될 때, 버퍼를 unlock 한다. 


다음 두 장에 걸쳐 설명하겠지만, 커널이 디스크에 곧바로 쓰지 않는 경우가 있다. 만일 "delayed write"를 해야한다면, 버퍼에 그것을 표시하고, brelse을 사용하여 버퍼를 unlock하며, I/O를 스케줄링하지 않고 하던 일을 진행한다. getblk의 3번 시나리오에서 설명한 바와 같이, 커널이 "delayed write" 버퍼를 디스크로 기록되어야만, 다른 프로세스가 해당 버퍼를 재할당받을 수 있다. 커널은 버퍼가 디스크로 기록되기 이전에, 프로세스가 버퍼에 엑세스 하길 원한다. 즉, 프로세스가 버퍼의 내용을 I/O 전에 수정한다면, 커널은 디스크 I/O 연산을 줄일 수 있다.


지연된 쓰기는 비동기 쓰기와는 다르다. 비동기 쓰기를 할 때, 커널은 디스크 연산을 곧바로 시작하지만, 연산이 끝나길 기다리지 않는다. "delayed write"의 경우, 커널은 실제 디스크 쓰기를 가능한 뒤로 연기한다. getblk의 3번 시나리오처럼, 커널은 버퍼에 "old"라고 표시하고, 디스크에 비동기적으로 기록한다. 디스크 쓰기가 끝난 후에, 디스크 컨트롤러는 시스템(디스크 드라이버)를 인터럽트하여, 인터럽트 핸들러가 호출되고, 핸들러는 brelse를 호출하여 버퍼를 unlock 한다. (이때 해당 버퍼는 프리리스트의 헤드에 위치하게 된다. 왜냐하면 사용하지 않은지 "오래된" 것이기 때문이다. 두개의 비동기 I/O, 블럭 미리 읽기(breada)와 "delayed write", 때문에 커널은 인터럽트 핸들러에서 brelse를 호출한다. 따라서, 커널은 버퍼 프리 리스트를 조작하는 프로시져 내에서 인터럽트가 발생하는 것을 막아야 한다. 왜냐하면, brelse는 프리리스트에 버퍼를 넣기 때문이다. 

3.5 버퍼 캐쉬의 장단점

버퍼를 사용하는 것은 장점도 있지만 단점도 있다.

  • 버퍼를 사용하면 균등하게 디스크에 엑세스 한다. 왜냐하면 커널은 I/O의 이유를 알 필요가 없기 때문이다.(역주: 어떤 논리로 저 앞 두문장을 붙였는지 모르겠다. 허나 다음 문장을 보고 유추해 보면, 대충 '왜냐하면 커널은 I/O를 항상하지 않기 때문이다'로 유추된다.) 대신에, 데이터를 버퍼로 혹은 버퍼에서 복사한다. 그리고 복사할 데이터가 파일의 일부분인지, 아이노드인지, 슈퍼블럭인지 개의치 않는다. 디스크 I/O에 대해 버퍼를 두면 코드는 좀 더 모듈화가 된다. 다시 말해, 시스템 설계가 단순해진다.

  • 유저프로세스가 I/O를 할 때, 데이터의 얼라인먼트(alignment)을 맞추지 않아도 된다. 왜냐하면 커널이 내부적으로 얼라인먼트를 맞추기 때문이다. 하드웨어에 따라서 데이터의 얼라인먼트가 다르다(메모리에 데이터를 2 혹은 4 바이트 단위로 맞추는 것처럼). 버퍼 메커니즘이 없다면, 커널이 아닌 프로그래머가 정확한 데이터 얼라인먼트를 보장해야만 한다. 그렇게 되면, 프로그래머들이 실수를 많이 할 수 있으며, 프로그램은 엄격하게 얼라인먼트를 검사하는 하드웨어로는 이식될 수 없을 것이다. 유저 버퍼에서 시스템 버퍼로(혹은 반대로) 데이터를 복사하므로, 커널은 유저 버퍼에 대한 얼라인먼트를 신경쓰지 않아도 된다. 이는 사용자 프로그램의 단순함과 이식성을 높인다.

  • 버퍼캐시를 사용하면, 디스크 혼잡을 줄일 수 있다. 그래서, 전체적인 시스템 전송율이 증가하고 응답시간은 짧아진다. 파일을 읽어들이는 프로세스는 캐시에서 블럭을 찾으면 디스크 I/O를 하지 않아도 된다. 커널 "delayed write"를 이용하여 불필요한 디스크 쓰기를 줄인다. 즉 썼던 버퍼를 놔두고 이 블럭이 캐시 히트가 되길 바란다. 버퍼가 크다면 캐시 히트 확률은 확실히 높다. 그러나 적절한 버퍼의 크기는 너무 크지 않아야 한다. 즉 프로세스를 실행하기 위한 적당한 메모리 크기로 제한된다. 만약 버퍼 공간이 너무 크다면, 프로세스 스와핑이나 페이징이 빈번하게 일어나 시스템이 느려질 것이다.

  • 버퍼 알고리즘은 파일시스템 무결성을 보장하는데 도움이 된다. 왜냐하면, 버퍼 알고리즘은 하나의 디스크 블럭에 대해 하나의 이미지만을 공유하기 때문이다. 만약 두 프로세스가 하나의 블럭을 동시에 조작하려한다면, 버퍼 알고리즘(예를들어 getblk)은 프로세스가 순서대로 접근하게 만둘며, 데이터가 깨지는 것을 막는다.

  • 전송량과 응답시간을 좋게 하기 위해서, 디스크 혼잡을 줄이는 것은 중요하다. 그러나, 캐시 전략에는 몇 가지 단점이 있다. 커널이 "delayed write"를 하기 때문에, 시스템은 디스크를 잘못된 상태로 만드는 크래쉬(crash)에 노출되어 있다. (역주: 만일 프로세스가 write()를 호출하면, 기록된 줄 알고 있을 것이다. 하지만, 실제로는 기록이 delay 된 상태이다. 이 때 컴퓨터 전원이 나가면 문제가 발생한다). 비록 최근 운영체제 구현물들은 치명적인 장애로 인한 피해를 줄여주지만, 위와 같은 근본적인 문제는 여전히 남아있다. 사용자 프로그램이 write()을 호출했음에도, 데이터를 디스크로 기록하는 시점이 언제인지 확실하지 않다.(C 언어의 standard I/O 라이브러리에는 fflush() 가 포함되어 있다. 이 함수는 사용자 공간의 데이터를 커널로 기록한다(flush). 그러나 데이터가 디스크로 기록되는 시점은 여전히 알 수 없다.) (역주: sync()는 캐시버퍼에서 디스크로 기록한다. 자세한 것은 인터넷으로..)

  • 버퍼캐시를 사용하면 부가적인 복사 연산이 필요하다. 즉, 사용자 프로세스와 버퍼캐시 간에 데이터 복사가 필요하다. 데이터를 기록하는 프로세스는 커널 안으로 데이터를 복사하며, 커널은 데이터에서 디스크로 복사한다. 데이터를 읽는 프로세스는 데이터를 가지고 있는데, 데이터는 디스크에서 커널로, 다시 커널에서 유저 프로세스로 읽어들인 것이다. 큰 데이터를 전송해야할 때, 이러한 복사로 인해 성능이 떨어진다. 하지만, 작은 데이터를 전송할 때, 성능이 개선된다. 왜냐하면, 커널이 데이터를 버퍼링(getblk와 "delayed write"을 이용)하여 디스크에 직접엑세스 하는 것을 줄이기 때문이다.

3.6 요약


이번장은 버퍼캐시의 구조와 블럭을 캐시에 넣는 방법에 대해 알아보았다. 버퍼 알고리즘은 몇 가지 단순한 개념들이 결합되어 있으며, 개념들은 캐시 매커니즘을 세련되게 해준다. 커널은 LRU 교체 알고리즘을 사용하여 버퍼캐시에서 블럭들을 관리하는데, LRU 알고리즘은 최근에 액세스된 블럭은 조금있다가 다시 이용될 것이다라는 것을 가정한다. 프리리스트 안 버버의 순서는 마지막으로 사용된 순서를 알려준다.(역주: 헤더에 달린 버퍼는 '마지막에 이용', 끝에 달린 버퍼는 '최근에 이용'을 의미) FIFO(First-In-First-Out) 혹은 LFU(Least-Frequently-Used)와 같은 다른 버퍼 교체 알고리즘은 구현하기 어렵거나 낮은 히트율을 보인다. 커널은 해시 함수와 해시큐를 이용하여 특정 블럭을 빠르게 찾을 수 있다. 그리고, 이중 링크드 리스트를 이용하면 리스트에서 버퍼를 쉽게 빼낼 수 있다. 


커널은 블럭을 식별할 때, 블럭이 위치한 논리 디바이스 번호와 블럭 번호를 이용한다. getblk 알고리즘은 블럭과 매핑되는 버퍼캐시를 찾고, 만일 캐시에 있고 free라면, 버퍼를 lock하고 그것을 반환한다. 만일 찾은 버퍼가 lock되었다면, 버퍼를 요청한 프로세스는 버퍼가 free되기 전까지 sleep 한다. locking 메커니즘은, 어느 시점에 특정 버퍼를 조작하는 프로세스가 단 하나임을 보장 해준다. 만일 블럭이 캐시에 없다면, 커널은 블럭에 대한 버퍼를 할당하고, 버퍼를 lock하여 반환한다. bread 알고리즘은 버퍼를 할당하고, 디스크에서 버퍼로 데이터를 읽어들인다. 알고리즘 bwrite는 앞서 할당받은 버퍼에 데이터를 기록한다. 만일 상위 레벨 알고리즘이 실행되고 있을 때, 커널은 데이터를 디스크로 즉각 쓰지않고, "delayed wrtie"라고 표시하여 불필요한 I/O를 줄인다. 불행하게도, "delayed write" 스키마에서는 데이터가 디스크로 언제 기록되는지 확신하지 못한다. 만약 커널이 디스크에 비동기적으로 기록한다면, 커널은 디스크 드라이버를 호출하며, 호출된 디스크 드라이버가 데이터를 파일시스템에 기록한다. 그동안 커널은 디스크 드라이버가 I/O를 완료하길 기다린다.


커널은 다양한 방법으로 버퍼캐시를 이용한다. 응용프로그램과 파일시스템 이 데이터를 주고 받을 때, 커널은 버퍼캐시를 이용한다. 그리고 파일시스템과 상위 레벨의 커널 알고리즘이 아이노드 같은 보조 시스템 데이터를 받을 떄도 버퍼캐시를 이용한다. 또한 프로그램을 실행하기 위해, 프로그램을 메모리로 읽어들일때도 버퍼캐시를 이용한다. 


다음 장에서는 다양한 알고리즘을 설명하는데, 그 알고리즘들은 이번장에서 나온 프로시져들를 이용한다. 메모리의 페이지와 아이노드를 캐싱하는 알고리즘에서도, 버퍼캐시 기법과 비슷한 기법이 이용되고 있다.

3.7 연습문제


저작자 표시 비영리 변경 금지
신고
댓글
댓글쓰기 폼