매일 성장하는 블로그

Project 4 - File System

141개의 Test들을 통과하고 드디어 Pintos의 마지막 관문인 File System에 도착했다.

다음과 같은 4개의 과제가 우릴 마주한다. 또 다시 '도대체 뭐하라는거지?' 라는 생각이 든다.

간략한 과제 내용은 아래와 같다.

0. FAT File System : 과제마다 다를 수  있지만, 우리는 FAT 방식으로 File System을 구현하라는 과제를 받았다. 실제 리눅스 등에서는 Multi Level Indexing으로 구현되어있다고 한다. (FAT 방식이 훨씬 쉽다고 한다.)

1. Extensible files : 현재 핀토스의 모든 파일들은 기존 할당된 크기에서 유동적으로 파일 크기를 키울 수 없다. 기존 할당된 크기보다 더 쓰더라도 유동적으로 파일의 크기가 늘어나도록 변경하라. + System Call

2. Subdirectories : 현재 핀토스는 무조건 루트 경로에서 모든 일을 수행한다. 루트의 하위 경로들도 만들 수 있도록 변경하고, 바로가기(Soft Link)를 구현하라. + System Call

3. Buffer cache : 현재 핀토스에서는 Disk에서 읽은 데이터를 물리메모리에서 제거하는 경우 Swap Disk로 보내거나 Disk에 바로 써버린다. 이런 경우 접근하려고 할 때 다시 disk_read를 해야하므로, 시간이 오래 걸린다. 따라서 자주 쓸 것 같은 데이터는 물리 메모리에 Cache를 만들어 놓고 여기다 넣는다.

4. Remaining miscellaneous items : Extra 

수정 파일 : filesys/filesys.c, filesys/fat.c, filesys/file.c, filesys/inode.c, userprog/syscall.c

Project 4 - 개념

1. FAT

  컴퓨터는 아래와 같은 하드웨어 구조를 가지고 있다. 아래 있는 계층은 바로 위의 계층의 캐시 역할을 한다.

이번 프로젝트를 통해 다룰 메모리 공간은 맨 아래에 있는 Disk Drive(SSD 포함)이다. Disk 공간은 아래와 같이 512Byte의 Sector 단위로 나눠져 있다. (자세한 내용은 disk.c 참고) 기존 Pintos에서는 free map을 활용하여 disk를 연속적인 sector 단위로 관리한다. 예를 들면, 1024byte의 데이터를 쓴다고 하면 반드시 sector 0, 1, 2, 3에 쓰는 방식이다. 이런 식으로 관리를 하면 아래 그림과 같이 외부 단편화(External Fragmentation)가 발생한다. 공간은 3개 있지만 3개짜리 파일이 들어갈 공간이 없는 것이다.

  이런 외부 단편화의 문제를 해결하기 위해, FAT(File Allocation Table)를 활용한다. FAT 방식은 빈 Sector들을 찾아 데이터를 기록한 뒤, 파일들이 연결된 정보를 File Allocation Table에 기록해놓는다. 아래의 그림을 보면, 3개의 빈 Sector가 있는데 파일 크기가 3인 파일을 기록할 수 없었던 기존 방식과는 달리 3개의 빈 Sector가 있다면 File D를 기록할 수 있다. 

  FAT 방식은 File Allocation Table이라는 표를 만들어서, 파일이 기록된 섹터들의 정보를 Chain 형태로 저장해놓은 것이다. 아래의 File D가 저장된 공간을 보면 4 - 9 - 10번 Sector에 순서대로 저장되어 있다. 이 정보를 FAT에 기록된 형태를 보면, FAT[4] = 9, FAT[9] = 10, FAT[10] = -1이 기록되어 있다. 4번 섹터의 다음 섹터는 9번 섹터이고, 9번 섹터의 다음 섹터는 10번 섹터이며, 10번 섹터가 해당 파일의 마지막 섹터라는 정보를 나타낸 것이다. (마지막 섹터에는 -1 혹은 구분할 수 있는 값을 넣어놓는다.)

  구현할 때 생각해야 할 점은 FAT 자체도 disk에 저장되어야 한다는 점이고, 이 부분은 침범되어서는 안된다는 것이다. 그래야 컴퓨터를 끄고 킬 때도 파일에 대한 정보가 남아있을 것이다. 

  지금은 FAT의 기본 단위(Cluster)가 1 sector와 같다고 가정했지만, 임의의 갯수의 sector를 하나의 cluster로 묶어서 관리하는 것도 가능하다.

2. Inode

  Inode란 파일이나 디렉토리에 대한 metadata를 가지고 있는 고유 식별자이다. 파일과 디렉토리는 모두 inode를 하나씩 가리키는 inode 포인터를 가지고 있다. inode 구조체는 파일이나 디렉토리를 열 때 발생하는 inode_open() 함수 실행 시에 생성되며, 열리지 않았을 때는 inode_disk인 상태로 Disk에 저장되어 있다. inode는 메타데이터 정보를 담고있는 512Byte의 inode_disk를 하나씩 가지고 있고, inode_disk는 실제 파일에 대한 메타데이터를 포함하고 있다. 실제 파일의 경우 아래와 같이 디스크에 저장되어있다. 

* Metadata : 속성을 설명하는 정보 

  ex : 글의 길이, offset ...

  이제 inode 구조체의 원소들을 하나씩 살펴보자. 

Inode

1. elem : inode를 생성하면 open_inodes라는 list에 추가해주기 위해 필요한 요소.

2. sector : inode_disk가 저장되어있는 disk의 sector를 나타낸다.

3. open_cnt : inode가 열려있으면 닫으면 안된다. 이를 관리해주기 위해 변수를 생성하여 카운팅한다.

4. removed : 삭제해도 되는지 여부를 저장한다. inode_remove()를 참조.

5. data : 디스크에 저장된 메타데이터 정보를 물리메모리에 올려놓은 것이다. 매번 disk에 참조할 수 없기 때문에 물리 메모리에 올려놓고 사용하며, 더이상 필요가 없어지면 inode_close()시에 다시 disk에 write back한다.

Inode Disk

1. start : 파일의 inode인 경우 파일의 실제 내용, 디렉토리의 inode인 경우 directory entry들이 저장되어 있는 disk의 sector 번호를 나타낸다.

2. length : 저장된 공간의 길이를 나타낸다(Sector 단위)

+ : 나머지 공간은 sector size인 512byte를 맞춰주기 위해 넣어둔 데이터이다. (Disk Write/Read 시에는 반드시 512byte 단위로 해야한다. 이 공간을 잘 활용할 수 있으면 좋다.

3. File

  File Open을 하면 생성되는 파일 구조체이다. 코드 상의 inode는 File의 inode를 가리키고 있으며, 이 inode 안에는 File Data에 대한 Metadata가 저장되어있다(inode_disk). 하나하나 살펴보자.

1. inode : 파일 데이터에 대한 정보를 포함하고 있다.

2. pos : 파일을 읽거나 쓸 때 처음부터 다 읽거나 쓸 필요는 없다. 

3. deny_write : 읽기 전용 파일을 나타내기 위해 사용하는 변수.

4. Directory

  디렉토리도 파일이다. 자세히 보면 구조체 내에 inode가 동일하게 위치하고 있는 것도 볼 수 있다. 다만 File에 Data가 있었다면 Directory에는 directory_entry들이 있을 뿐이다. 기억해야 할 것은 directory를 조회하기 위해 dir 구조체를 따라 들어가면 inode가 있고, inode 안의 inode_disk에 기록된 sector를 따라가보면 dir_entry들이 기록되어있는 것이다. 내가 원하는 이름을 가진 dir_entry를 찾고, 이녀석이 가리키는 sector로 다시 가면 내가 원하는 데이터가 있을 것이다. 

Directory, Directory_entry 구조체에 대해 알아보자.

Dir

1. inode : 하위 dir_entry들을 저장하고 있는 sector를 찾아가기 위해 이용한다.

2. pos : 어디까지 읽었는지 확인한다.(readdir()구현 시 사용)

Dir Entry

1. inode_sector : dir_entry의 정보를 담고있는 sector를 가리킨다.

2. name : 파일이나 디렉토리의 이름이다.

3. in_use : lookup 할 때 사용할 정보이다. 이 위치에 dir_entry가 저장되어있는지에 대한 정보를 나타낸다.

Project 4 - 구현

0. FAT

  1) fat.c에 기본적인 내용(boot 시 fat를 load하고 종료 시 fat를 write back하는 기능)은 구현되어있다.

  2) 우리가 해야할 일은 fat 테이블을 업데이트하고, 컴퓨터를 끄고 키더라도 동일한 위치에 저장되어있도록 보장하는 것이다.

  3) Root Directory는 format할 때 만들어줘야 한다.

  4) Cluster to sector 함수를 잘 생각하고 만들어야 한다. fat table도 disk에 저장되어야 한다는 점을 꼭 기억하자. 이부분을 아예 없다고 생각하고 Cluster to sector을 만들 것인지, 아니면 있다고 생각하되 데이터가 이미 기록되어있음을 File Allocation Table에 기록할 것인지를 선택해야한다. Sector가 들어가야 하는 위치에 Cluster가 인자로 들어가거나, 반대로 된 경우가 없는지 반드시 체크하자.

1. Extensible Files

  1) FAT를 구현했다면 이건 쉽다. inode_create이나 Write/Read시에 내가 잘 만들어놓은 Chain을 따라가게 하면 된다. 만약 File length를 늘린다고 하면, 새로운 chain을 하나 추가하여 기록한다. 

  2) File length가 늘어난다고 하면 inode_disk에 이 data를 업데이트해줘야 하며, sector_size와 file_length는 다르다는 점을 인지하자.

  3) inode_disk는 data의 길이에 포함되지 않는다.

2. Subdirectories

  1) 입력을 받은 뒤 parsing하여 효율적으로 인자를 전달하는 것이 생각보다 까다롭다. 예외처리와의 싸움일 것이다. 인자가 비어있거나, 존재하지 않거나, 지우면 안되거나 등등을 고려해야 한다.

  2) .과 ..은 기본적으로 directory에 추가해주는 것이 좋다.

  3) 파일을 열었다면, 반드시 잘 닫아줘야 한다. open_cnt 때문인데, 일반적으로 open_cnt가 0일 때 inode의 사용이 끝났음을 인지하고 disk에 write back해주기 때문이다. 그렇다면 open_cnt가 언제 증가하고 언제 감소하는지에 대해 이해하고 있어야 한다. inode_open(dir_open이 아님)이나 reopen시에 증가하고, inode_close 시에 감소한다. inode_open함수는 어디서 사용하는지 확인해보자.

  4) directory인지, file인지 확인이 필요할 때가 있다. Syscall마다 이를 구분할 필요가 있는 경우에는 처리해준다.

  5) directory도 open할 수 있다. open된 directory는 제거하면 안된다.

3. Persistence

  1) 위의 과정을 제대로 했다면 종료 후 다시 Booting을 하더라도 데이터가 잘 기록되어있어야 한다.

  2) 위에서 말했던 open_cnt를 잘 고려하지 않았거나, root directory를 boot 시마다 갱신해주는 것은 아닌지 확인해보자

Project 4 - 후기

  드디어 192개의 모든 Test를 안정적으로 통과하는 것을 확인했다. 길고 길었던 Pintos, 잠도 잘 못자는 경우가 다반사였지만, 많은 것을 느낄 수 있었던 기간이었다. Linux에 대한 기본적인 이해도 할 수 있었고, 아예 모르는 것에 대한 두려움을 많이 줄일 수 있었다. Pintos를 처음 시작하는 사람이라면, 처음에 진짜 아무것도 몰라서 막막하더라도 조금씩 이해하다보면 끝낼 수 있다고 말해주고 싶다. 

Goodbye PINTOS ~

Project 3 - Virtual Memory

100개 가까운 테스트를 통과하고 Project3 - Virtual Memory에 도달하여 매우 기쁘지만, 아래와 같은 문구가 Project 3에서 우릴 기다리고 있다. 이제까지 제대로 만들었길 기도하자. (이번에도 도대체 뭐하라는거야 가 기다리고 있으니 너무 기대하지 말자.)

"You should take care to fix any bugs in your project 2 submission before you start work on project 3, because those bugs will most likely cause the same problems in project 3." 

간략한 과제 내용은 아래와 같다.

0. 프로그램을 실행하려면, 실행에 필요한 데이터(Ex : Code)를 물리메모리(RAM)에 올려야 한다. 지금은 실행 전에 load(), load_segment()라는 함수에서 실행에 필요한 모든 데이터를 물리메모리에 올려버리고 있다. 이 방식은 매우 비효율적이므로, 모든 데이터를 다 올리는 대신에 실행 중에 해당 데이터가 필요하게 되면 그 때 물리메모리에 올리는 방식으로 변경하자.(Lazy Load)

1. 현재 스택은 한개의 Page만 할당되어 있고, 한 Page 이상의 데이터를 저장하는 경우는 고려되지 않았다. 한 Page를 넘는 데이터를 저장하더라도 유동적으로 늘릴 수 있도록 변경하라.(Stack Growth)

2. 프로그램을 많이 실행하거나, 많은 데이터를 저장하다보면 물리메모리가 가득 차서 무언가를 빼내야 하는 상황이 발생한다. 이를 고려하여 임시로 저장하는 공간인 Swap Disk를 만들고 빼낸 데이터는 잠시 이 곳에 넣어두기로 한다. Swap Disk는 갈 곳이 없는 것들만 넣어두는 것이고, File에서 불러온 데이터는 다시 File에 쓰면 된다. 

Project 3 - 개념

Project 3을 진행하기 위해서는 아래의 내용들을 이해해야 한다.

우선 전체적인 그림을 한번 알아보자.

  Pintos 내에서 생성되는 모든 Thread는 각자 독립된 가상주소공간(0 ~ KERN_BASE)을 가진다.  KERN_BASE가 0x8004000000이므로, 각 프로세스는 550Giga Byte의 주소공간을 표현할 수 있다.(하지만 실제로 사용되는 공간은 매우 작다.) 각자의 Thread가 KERN_BASE 이하의 특정 주소의 데이터를 읽으려고 하면, Thread에 저장되어있는 Page Table에서 이 주소를 실제 물리 주소로 변경한 뒤 실제 물리주소에서 데이터를 읽어오게 된다.

0) Virtual Address

  위에서 말한 가상주소공간은 Thread별로 할당된 것이며, 각각의 Thread는 이 가상주소공간만큼의 크기를 모두 쓸 수 있을 것만 같은 착각을 가진다. 하지만 사용자가 0x400000에 data를 Write하라고 명령을 내리더라도, Thread는 이 주소를 실제 물리주소로 변환한 뒤에 그곳에 Write한다. 이렇게 함으로써 OS는 사용자가 만든 Thread가 실수를 하더라도 다른 Thread의 공간을 침범하는 것을 막을 수 있다.

1) Page

  가상 공간의 Data에 대한  정보를 저장하고 있는 구조체이다. 모든 물리메모리공간은 Page(1024Bytes)단위로 관리된다. Page 내에는 어떤 인자들이 있는지 확인해보자.

1. operations

  Page는 anon, uninit, file이라는 3가지 Type이 존재한다. 이유는 Stack이나 Code, 등 데이터의 종류에 따라 다른 방식으로 처리해줘야하기 때문이다. 아래와 같이 type별로 swap_in, swap_out, destroy 시 실행해야 하는 함수를 별도로 저장해두고 실행한다.

* Swap in : 해당 Page를 물리 메모리(RAM)에 Load하는 행위

* Swap Out : 해당 Page를 물리 메모리에서 제거하는 행위. 돌아갈 곳이 없는 Page는 Swap Disk에, Disk에 다시 써도 되는 녀석들은 Disk에 Write하는 행위를 해줄 것이다.

* Destroy : 해당 Page를 제거하는 행위

2. va : 데이터가 저장된 가상주소의 시작점이다. 

3. frame : page와 matching된 frame을 가리킨다.

2) Frame

  : 물리공간에 대한 정보를 가지고 있는 구조체이다. Page Table에는 Page의 va : Frame의 kva가 매칭되어 있다.

1. kva : 실제 물리주소이다. (실제 저장되는 물리주소는 (kva - KERN_BASE)이긴 하다.)

3) Page Table

  모든 Thread는 각각 pml4라는 이름의 Page Table을 가지고 있다. (thread_create()함수의 pml4_create() 참고) Page Table에는 va : kva로 mapping이 되어있기 때문에, 가상주소에서 물리주소로의 번역이 가능하다. Mapping 정보를 확인하기 위해 va를 가지고 Page Table을 찾았는데, 매칭되는 kva가 없다면 Page Fault가 발생한다.

5) Page Fault

  사용자가 원하는 임의의 가상 주소에 접근하려고 했을 때, thread는 해당 주소가 포함된 Page의 시작 주소(va)를 찾은 뒤(=pg_round_down(va)), 이것에 매칭된 물리주소(kva)가 있는지 Page Table에서 찾는다. 만약 matching 된 정보가 없다면 Page Fault를 발생시킨다. Page Fault Handler에서 Page Fault에 대한 처리를 하면, 해당 가상 주소는 이제 접근이 가능하게 된다. 현재는 Page Fault Handler에서 아무런 조치를 하지 않는다. 이런 경우 외에도, 읽기 전용인 페이지에 Write를 하려고 해도 Page Fault가 발생한다.

  Page Table에 va : kva 매핑하는 작업은 install_page(), 매핑된 정보를 제거하는 작업은 clear_page()를 참고하자.

6) Bitmap

  메모리공간의 사용가능여부를 나타내는 Bit들의 집합이다. 1이면 사용중, 0이면 비어있음을 나타내도록 사용할 수 있다. bitmap.c 파일에 자세히 나와있다.

7) MMAP

  사용자가 명시적으로 파일의 내용을 물리메모리에 올리도록 요청하는 System Call이다. 사용자가 요청하는 바는 디스크에 있는 파일의 데이터를 물리메모리에 올리라는 것이나, 당장 사용하지 않을 데이터를 모두 한정된 물리메모리에 올려놓는 것은 비효율적이기 때문에 load_segment와 마찬가지로 페이지 정보만 등록해놓고 필요할 때 물리메모리에 Load하기로 한다.

8) Supplemental Page Table

  Lazy Load를 구현하려면, Page에 대한 정보(어디서 가져와야 하는 데이터인지, 어떤 데이터인지..)를 어디엔가 등록해놓은 뒤 Page Fault가 발생하면 이 정보를 찾아 메모리에 Load해야 한다. 따라서 Page에 대한 정보를 저장해놓을 공간이 필요한데, 이게 SPT다. SPT에서 Page에 대한 정보를 찾는 시간을 최소화하기 위해 Hash Table을 사용한다.

9) Swap Table

  위에서 설명했듯이, 물리메모리가 가득찼을 때 기존에 있던 Page들 중 하나를 밖으로 빼내고 새로운 Page를 넣어야 한다. 새로 물리 메모리에 Load되는 Page는 Swap In 된다고 하고, 기존에 물리메모리에 올려져 있었으나 꺼내지는 Page는 Swap Out 된다고 부른다. 

  위에서 살펴봤듯이, Page의 종류는 3가지가 있다. Uninit, Anon, File이다. Uninit Type은 초기화되지 않은 Page로 Page 정보는 생성되었으나 사용자가 해당 Page에 접근하지 않았다는 것을 의미한다. 따라서 물리메모리에 올라가있는 페이지가 Uninit일수는 없다. File Type은 mmap된 Page이다. File Type은 Swap In될 때 disk에서 직접 읽어오면 되고, Swap Out될 때는 직접 Disk에 다시 쓰면 된다. Anon Type은 Stack, Text 등을 포함한다. Anon Type은 Swap Out될 때 디스크에 다시 돌아갈 곳도 없고, 무작정 제거하면 다음에 접근할 수 없다. 따라서 물리 Disk에 Swap Disk란 공간을 별도로 할당해서 이곳에서 Swap In/Out되는 Anon Type Page들을 관리한다.

  Swap Table은 Swap Disk의 할당 정보를 포함하고 있는 Table이라고 생각하면 된다. bitmap을 사용하여 Swap Table을 구현할 수 있다.

* 교체 Policy

  물리메모리가 가득 차서 현재 Load된 Page들 중 하나를 빼낼 때 어떤 녀석을 빼낼 것인가에 대한 정책이다. FIFO도 가능하고, LRU 등 다양한 교체 알고리즘이 있다. Test Case들은 FIFO 방식으로 구현해도 시간은 충분했다. (컴퓨터 환경에 따라 조금씩 다를 수 있다.)

* Accessed and dirty bit

  File Type Page가 Swap Out되는 경우를 생각해보자. 만약 데이터를 사용자가 읽기만 하고 변경하지 않았다면, 굳이 disk에 다시 써줄 필요가 없다. 고맙게도 CPU는 사용자가 특정 Page를 수정했다면 dirty bit를 1로 바꿔주는데, 이를 확인한 뒤 Disk Write back을 할지 말지 결정한다.

* Copy On Write

  기본적으로 fork 구현 시 frame을 모두 새로 할당하여 복사해주었을 것이다. 이런 경우도 마찬가지로 비효율을 초래할 수 있다. 따라서 fork할 때 자식은 부모가 할당한 물리 메모리 공간을 가리키게 하되, writable을 0으로 해준다. 읽는 것은 가능하지만, 무언가 쓰려고 하면 Page Fault가 발생할 것이고 이 때 새로 물리메모리 공간을 할당해서 복사를 진행한다. writable을 0으로 모두 할당할 것이지만, 기존에 존재하던 Page의 writable여부도 반드시 저장해서 새로 물리공간을 할당할 때 update해줘야 한다는 것을 잊지 말자.

Project 3 - 구현

  전체적인 그림을 한번 잡고 시작할 수 있다면 더 좋을 것 같다.(가능할진 모르겠지만) 위의 내용들을 이해했고 무엇을 해야할지 파악했다면, 구현하는건 조금이나마 더 수월할 것이다. 제대로 된 데이터가 Load되는지, Swap In/Out 된 데이터가 일치하는지 여부를 hex_dump()함수를 활용하여 직접 확인해보는 것을 추천한다.

끝-!

B-Tree 삭제

B-Tree 구현 중 제일 복잡한 부분이다. 우선 함수를 살펴보자.

deleteNode(Node N, key x) : Node N에서 key x를 찾는다.

(실제 구현은 root 여부를 확인하기 위해 Tree 구조체도 같이 전달하는 방식으로 구현했다. 특정 key를 삭제했을 때 root가 사라지는지 확인하는 과정이 꼭 필요하다.)

key X를 삭제하는 과정은 Tree의 root Node로부터 시작해서 X가 들어있는 노드를 찾는 것으로 시작한다. 삭제하는데 발생가능한 경우는 아래와 같이 크게 세 가지로 나눠볼 수 있다.

1.  N이 Leaf Node인 경우

  → Node N의 key들에 대하여 for문을 돌며 확인한 뒤, X가 존재하면 삭제한 뒤 True를 return, 없다면 False를 return한다.

2. Node N 안에 key X가 있는 경우

  a) key X의 선행 자식 Node Y가 최소 t개의 키를 가진다면, X의 선행키(Predecessor) K를 X와 바꾼 뒤, K를 삭제한다. 이후 아래 노드로 내려가며 X를 삭제한다.

ex) 아래 그림에서 key 16을 지우려는 경우이다.

1. 16의 선행자식 Node Y는 3개의 Key를 가지고 있으므로 t(2)개 이상을 만족한다. 따라서 선행키인 15와 교환한 다.

2. key X(16)를 지우러 내려간다.

  b) key X의 후행 자식 Node Z가 최소 t개의 키를 가진다면, X의 후행키(Successor) K'과 X를 바꾼 뒤, 아래 노드로 내려가며 X를 삭제한다.

  c) key X의 선행 자식 Node Y와, 후행 자식 Node Z 모두 t-1개의 자식을 가진다면, Node Y와 Z를 합치고(merge) X를 삭제한다.

선행키와 후행키란 ? 

아래 그림의 Tree에서 key = 12를 삭제하려고 한다. 선행키와 후행키는 어떤 값인가?

* 선행키(Predecessor) : 특정 Key의 왼쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 오른쪽에 있는 값 = 11

* 후행키(Successor) : 특정 Key의 오른쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 왼쪽에 있는 값 = 13

3. Node N 안에 key X가 없는 경우

  계속 X를 찾아 들어가야 하므로, 다음 살펴볼 Node C를 정한다. (Node N의 key 값을 기준으로 비교한 뒤 정한다.) 해당 Child Node가 t-1개의 자식을 가진 경우, 아래와 같은 두가지 경우가 있을 수 있다.

  a) Node C 양 옆의 Node 중 t개 이상의 key를 가진 Node가 있는 경우

      → 하나의 key를 해당 Node에서 빌려온 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C)) 

          (Node C의 key 개수는 2t-2개가 된다.)   

  b) Node C 양 옆의 Node들이 모두 t-1개의 자식을 가진 경우

      → 양 옆 중 하나의 Node와 병합한 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C)) 이 때, 두 Node를 가리키는 Child Pointer들 사이에 있는 key는 병합된 Node C로 같이 내려온다. (Node C의 key 개수는 2t-1개가 된다.)

※ 참고할 사항 ※

* 여기서도 삽입할 때 Split을 해주며 찾아내려간 것과 마찬가지로, 만약 Node N이 t-1개의 자식을 갖고있다면 옆의 Node와 Merge를 하거나 옆 Node에서 Key를 빌려서 충분한 key의 개수를 충족시킨 후 내려간다. 

B-Tree의 구현은 크게 4가지로 나뉜다. 구현방법은 사람에 따라 달라질 수 있다. 개념을 이해하는데 걸리는 시간에 비해 구현에 시간이 오래걸리는데, indexing에 항상 주의하자.

0. 구조체 정의

1. 트리 및 루트노드 생성

2. 키 삽입

3. 키 삭제

0. 구조체 정의

  : Tree 구조체와, 그 안에 우리가 넣어줄 Node 구조체를 만든다. 차수에 따라 동적으로 할당해주기 위해 포인터와 malloc을 사용한다.

  1) Node

typedef struct btNode {

	int key_num;
	int* keys;
	struct btNode** child_pointer;
	struct btNode* link;
	bool isLeaf;

}btNode;

  2) Tree

typedef struct bTree {

	//int order;
	struct btNode* root;
	//int node_count;

}bTree;

1. B-tree의 생성(초기화)

1. 빈 Tree 생성

  : 빈 Tree를 만들고, root Node 한개를 만들어 추가한다. 처음에는 root Node가 leaf이기 때문에, isLeaf에 True를 할당한다.

bTree* create_tree(int order) {

	bTree* tree;
	tree = (struct bTree*)malloc(sizeof(struct bTree));
	tree->root = create_node(order, true);
	return tree;
}

2. 빈 Node 생성

  : 빈 Node를 만들고 key, child_pointer 배열을 최대차수에 따라 동적으로 할당한다.(최대차수는 전역변수로 선언한 뒤 입력받았다.)  

btNode* create_node(bool isLeaf_) {

	btNode* node;
	node = (struct btNode*)malloc(sizeof(struct btNode));
	node->child_pointer = (struct btNode**)malloc((order) * sizeof(struct btNode*));
	node->link = NULL;
	node->isLeaf = isLeaf_;
	node->key_num = 0;
	node->keys = (int*)malloc((order - 1) * sizeof(int));
	for (int i = 0; i < order - 1; i++) {
		(node->keys)[i] = -1;
	}
	return node;
}

3. 키 삽입

 : 여기서부터 조금 복잡하다. 키를 루트에 삽입할 때 사용하는 함수는 insert(), insertNonfull(), split()이다. 우리가 깊이 고민해야되는 부분은 '임의의 노드가 이미 키를 2t-1개 가지고 있을 때, 어떻게 삽입해줘야 하는가' 이다. 우선 간단한 예시를 살펴보자.

아래 그림과 같이 최대차수가 4(최소차수 t = 2)인 트리의 루트에 키가 3개 들어있다. 새로운 키 1개(3)가 더 들어가면 어떻게 될지 살펴보자.

1. 키 삽입 시도

2. 새로운 노드 생성 후 루트 노드로 지정

  : 새로운 노드 s를 만들어 tree의 root로 지정하고, 기존 노드 r을 가리키게 한다.(삽입하려는 노드가 root가 아닌 경우에는 실행하지 않는다.) r의 isLeaf속성은 True로 바뀌어야 한다.

3. 기존 노드 Split

    1. r의 가운데 key를 노드 s로 올려준다.

    2. 새로운 노드 z를 만들고, r의 가운데 key 기준 우측 key값(t+1번째부터 2t-1번째까지)들을 모두 z로 옮긴다.

    3. Split하려는 노드가 Leaf 노드가 아니어서 Child Pointer들을 가지고 있는 경우, r의 Child Pointer도 노드 z로 옮겨줘야 한다.

    4. 각 노드들의 key 개수(key_num)을 업데이트한다.

4. 삽입 완료

  : Split이 완료되면 기존 노드(r)와, 새로 생긴 2개의 노드(s,z)는 모두 t-1개의 키를 갖는다. 모든 노드들이 새로운 키값을 넣을 공간이 있으므로, 새로운 키(3)을 알맞은 위치에 넣어준다.

※ 참고할 사항 ※

1. 삽입하는 과정에서, 새로운 키는 항상 Leaf Node에 추가해야한다.

2. 트리는 항상 기존 존재하던 노드 기준으로 위(Upward)로 자란다.

3. root 노드인 경우는 별도의 작업으로 처리해줘야하기 때문에 insert()함수가 존재하고, root가 아닌 노드인 경우에는 insertNonfull()에서 처리한다. 

4. 키를 삽입할 때 들어가야 할 자리(Leaf Node)를 찾기 위해 노드들을 탐색하며 내려가게 되는데, Leaf Node가 아니더라도 내려가는 과정의 모든 Node에 대해서 키의 개수가 2t-1개(최대)이면 split을 해줘야 한다. 이는 Leaf Node가 가득차서 Split을 할 경우에 다시 위로 올라가서 연산하는 것을 방지하기 위함이다. 

5. 가득 찬 경우에는 split()을 하지만, 가득차지 않은 경우에는 split()을 진행하지 않는다.

github.com/SunghyunChoi/btree_algorithm/blob/main/BTree.c

Project 2 - User Programming

  Project 1에서는 Kernel 영역에서 쓰레드들을 생성하고 Scheduling을 제대로 수행하도록 만들었다. Project2에서는 사용자의 입력을 받아 원하는 작업을 수행할 수 있는 기능을 구현하고, 사용자의 명령을 Kernel 영역에서 실행해줄 System Call들을 만든다. 프로젝트를 완료하면, PINTOS에서 특정 파일을 실행시켜 원하는 결과를 얻을 수 있다.

* 이번 프로젝트는 System Call들을 구현하기 전까지 제대로 구현했는지 테스트를 통해 알아보기 힘들기 때문에, hex_dump()등의 함수를 잘 활용하자.

목표 : User의 입력을 받는 기능을 구현하고, User가 의도한 결과를 return하기 위해 Kernel 영역에서 수행되는 System Call들을 만든다. 

Project 2 - 기본 내용

1. User Mode / Kernel Mode + User Stack

  프로세스/쓰레드는 User Mode와 Kernel Mode를 왔다갔다하며 수행한다. User Mode는 사용자가 사용을 하는 영역, Kernel Mode는 사용자의 입력을 받아 Kernel 단에서 수행을 해주는 영역이다. User Mode에서 사용자가 입력을 하면 해당 입력 내용이 User Stack에 저장되고, Kernel Mode에서 입력 내용을 꺼내어 원하는 작업을 수행하게 된다. User Mode에서 사용자의 입력을 User Stack에 저장하는 작업을 여기선 Argument Stack이라고 부른다.

2. System Call

  사용자(User)가 시스템의 Hardware 또는 관리가 필요한 기능들을 사용하고자 할 때 호출하는 함수이다. User Mode에서 System Call을 호출하면, Kernel Mode로 전환하여 해당 내용을 수행하게 된다. Pintos에서 작용하는 방식을 간단히 살펴보자.

  사용자가 특정 파일을 열고자 open()이라는 함수를 호출한다. User Mode에서 해당 함수를 호출하면, lib/user 폴더에 있는 syscall.c에서 open()이라는 System Call이 실행되고, 이 함수는 현재 레지스터 상태들을 저장(User Mode 상태 저장)한 뒤  Kernel mode에서 userprog/syscall.c에 있는 open 함수를 수행한다. (초기에는 정의되어있지 않으므로 구현이 필요하다.) 해당 System Call을 수행한 결과값은 intr_frame의 rax에 저장되어 User Mode로 복귀하게 된다.

프로젝트 진행

1. User의 입력을 받는 기능을 구현한다.

  argument_stack() 함수를 구현한다. 들어온 데이터를 parsing하여 word-align되도록 데이터를 자른 뒤, User Stack에 차곡차곡 쌓는다. 다 쌓고난 뒤 데이터 시작 위치를 rsi에, argument 개수를 rdi에 넣어주면 된다. 

2. System Call들을 구현한다.

  앞의 내용들을 다 구현하고 System Call을 구현하는 시점에 도달하면 이제 Test case들을 수행해볼 수 있어 한결 낫다. syscall_handler에서 switch문으로 어떤 System call을 수행해야하는지 구분해놓고, 각 system call 함수들을 구현하면 된다. 구현 시 어려운 함수는 fork(), wait(), exit()이었던 것 같다. fork()는 함수 실행 시 분기 흐름을 파악하기 어려웠고, wait(), exit()은 종료 시점을 판단하는 것과 종료 시 memory free하는 것이 어려웠다.

  이번 프로젝트는 System Call을 완성하기 전까지 제대로 구현되었는지 확인할 수 없다는 점, 핀토스 내부 작동 방식을 파악해야한다는 점이 힘들었다. 

오늘부터 PINTOS(KAIST ver.) 프로젝트를 시작했다. 핀토스를 처음 접했을 때 느끼는 점은 도대체 뭐하라는거지? 이다.

Project 1 - Threads 에서는

1. Thread들의 생성 및 관리

2. Timer Interrupt

3. Synchronization

4. Scheduling

에 대해 알아본다. 개념 - 프로젝트 진행 순서로 정리한다.

PINTOS = Pint OS

Pint OS, 즉 작은 OS라는 뜻이다. 작은 OS를 가지고 여러가지 프로젝트를 수행한다.

1. 사용법

1. /pintos 경로에서 source ./activate (로그인할때마다 해야하므로 .bashrc에 명령어를 추가하는 것이 좋다.)

2. threads 폴더 들어가서 make clean - make check를 수행하면 Test Case들에 대해서 채점을 수행한다.

3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.

pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)

ex) pintos -T 10 -- -q run alarm-multiple

→ alarm-multiple 이라는 test case를 수행하며, 10초 후에는 무조건 종료하라.(무한루프에 빠지는 경우를 방지할 수 있다.)

4. 수행한 결과는 threads/build/tests/threads 폴더에 들어가면 확인해볼 수 있으며, Test Case에 관한 정보/코드는 pintos/tests/threads에 있다.

threads/build/tests/threads/ 에 .output파일이 내가 짠 코드의 Test Case 결과이며, 틀렸을 경우 Expected Output과 Actual Output이 비교되어 출력된다.

2. 개념

1) Synchronization

  동기화란, 임의의 메모리 공간을 공유하는 쓰레드들이 의도한 순서대로 작업을 수행하도록 보장하는 작업이다. 한 Process 안에 있는 Thread들 간에는 Scheduler에 의해 임의적으로 Preemption(CPU를 차지하는 행위)이 발생하게 되는데, 이 과정에서 프로그램 작성자의 의도와 다르게 실행되는 경우를 방지한다. 이번 프로젝트에서는 동기화에 사용되는 5가지 방법들을 구현한다. (동기화가 필요한 이유는 아래 글을 참고)

one-step-a-day.tistory.com/122

2) Interrupts

  Interrupt란 원하는 Event가 발생했을 때 알림을 받기 위한 장치이다. Interrupt를 끄면 Preempt가 일어나지 않기 때문에 동기화가 보장된다. (non-maskable interrupt도 있다.) 하지만 Interrupt를 끄게 되면 필요한 신호들을 받지 못할 수 있기 때문에, 활용 시 주의해야 한다.

Ex ) 핸드폰의 벨소리나 진동 같은 기능이라고 생각하면 된다. 벨소리나 진동이 없다면, 우리는 전화나 메시지가 오는지 항상 핸드폰을 보고있어야 할 것이다. 벨소리나 진동이 있기 때문에 다른일을 하다가도 전화가 온 것을 인지하고 받을 수 있다.

3) Semaphore

여러 Process/Thread 사이의 Critical Region을 정상적으로 관리하기 위한 Nonnegative Integer이다. 

Semaphore의 값을 1이라고 가정하자. Critical Region에 접근할 때 Semaphore의 값을 1 감소시키고,  나올 때 1을 증가시킴으로써 Critical Region에 접근하는 쓰레드는 항상 1개 이하로 유지할 수 있다.(Semaphore의 값을 증가/감소시킬 때는 Atomic Operation을 보장하기 위하여, Interrupt를 Disable한다.)

  1. P(Down) : 양수이면, 1 줄여라.

  2. V(Up) : 1 늘려라.

* 정확히 한번 일어날 Event에 대해서는 0으로 초기화된 semaphore를 사용할 수 있다. 예를 들어 A라는 쓰레드가 있고 A 쓰레드가 B 쓰레드를 시작시키고 특정 작업이 완료되면 B가 A에게 signal을 보내길 기다린다고 하자. A는 0으로 초기화된 semaphore를 만들고 P(Down)을 수행한다. 이 때 이미 0이므로 수행하지 못하고 기다리게 되고, B에게 수행권을 넘긴다. B가 실행되었을 때, 업무를 완료한 뒤 V(up)를 실행한다. 그럼 semaphore는 1이 되고, A가 Down을 실행하여 다시 semaphore는 0이 된다. (Cond-val 수행 시 이 용도로 사용된다.)

* Semaphore를 Up하면, 마지막에 Priority에 따라 Preempt(thread_yield)를 수행할 것이다. 이 때 Interrupt handler가 sema_up 함수를 호출하는 경우를 고려해야 한다. (감이 오지 않는다면 Project3까지 꼭 기억해두기로 하자.)

관련 파일 : synch.c, synch.h

4. Locks(Mutex)

Binary Mutex를 Lock이라고 부른다. Thread 프로젝트에서는 Semaphore의 소유권을 정하기 위해 사용된다. (synch.h의 struct lock에서 정의되어 있다.)

관련 파일 : synch.c, synch.h.

5. Monitors

세마포어나 Lock보다 한층 고차원의 동기화 수단이다. 특정 조건을 충족했을 때 Thread에 signal을 보내 작업을 수행하게 할 수 있다. 이번 프로젝트에서는 Cond라는 test에서 사용된다.

* Monitor의 구성요소

1) data being syncronized

2) lock(monitor lock)

3) one or more condition variables

* Monitor 작동 순서(protected Data에 접근할 때)

1) monitor lock을 획득한다.(=모니터 안으로 들어간다.)

2) 모니터 안에 들어가게 되면, 쓰레드가 protected data에 대한 control을 갖게 된다.

3) 작업이 끝나면 monitor lock을 release한다.

Monitor의 condition variable은 access를 허용하는 조건을 control할 수 있다. '특정 데이터가 도착할 때까지' 혹은 '사용자가 최종적으로 키를 친 뒤 10초 후 ' 라던지의 조건이다. 이런 조건들이 true가 되는 조건들을 걸어놓으면, lock을 release(+1)하고 특정 조건을 만족할 때까지 기다린다. condition이 true가 되면, 특정 기다리는 쓰레드를 깨우거나 모든 쓰레드를 깨우는 등의 작업을 할 수 있다.

include/threads/synch.h.

5. Optimization Barriers

(동기화의 수단으로 어떻게 사용되는지 잘 모르겠다.)

: 사용자의 의도와 다르게 Compiler Optimization 되는 것을 막아준다. barrier()를 쓴 곳에서는 Compiler Optimization이 수행되지 않는다. 코드 곳곳에서 사용되는 것을 볼 수 있다.(pintos/devices/timer.c)

* Compiler Optimization이란?

 : 컴파일러가 코드의 내용을 파악하여 필요없는 부분을 수행하지 않거나 작업 순서를 변경하는 등의 방법으로 최적화하는 행위

6. Priority

  Thread들은 Priority(우선순위)라는 정보를 가지고 있고, 반드시 Priority가 높은 Thread가 먼저 실행되어야 한다. (만일 Priority가 높은 것이 실행되지 않는다면, 중요하지 않은 프로그램이 실행되느라 중요한 프로그램이 계속 실행되지 못하는 상황이 벌어질 수 있다.) 하지만 Semaphore나 Lock을 사용하다 보면, Priority가 낮은 프로세스가 실행되는 상황이 발생한다.

* Priority Donation

  Priority가 10인 Thread A가 Lock A를 가지고 실행되는 도중 Priority가 30인 Thread B가 생성되는 상황을 가정하자. Thread B는 생성이 완료된 후 Ready Queue에 추가되고, Priority가 Thread A보다 높으므로 실행된다. Thread B가 실행 도중 Lock A를 요청한다면 어떻게 될까?

  Thread A가 Lock을 가지고 있기 때문에, Thread A가 실행이 되고 Thread B는 Lock을 획득할 때까지 기다리게 된다. 이렇게 되면 Priority가 10인 Thread A가 Priority 30인 Thread B보다 먼저 실행이 되는 상황이 발생한다. 이런 상황을 Priority Inversion이라고 부르고, 이런 상황을 방지하기 위해 Thread B의 Priority 30을 Thread A에게 부여하게 된다. 그럼 Thread A는 Priority 30이 되므로, Priority Inversion이 일어나지 않는다. 이를 Priority Donation이라고 부른다.

프로젝트 진행

1. Alarm Clock : 

목표 : Thread를 생성한 뒤 특정 시간이 지나면 특정 작업을 수행하게 하고싶다. 기본적으로 구현되어있긴 하지만, Busy Waiting 방식을 사용하고 있어 매우 비효율적이다. timer_sleep() 등 함수를 수정하여 Busy Waiting 방식을 효율적으로 변경한다.

* Busy Waiting : Thread A가 5tick 뒤에 특정 작업을 실행하길 원한다고 하자. 매 Tick마다 Thread A가 실행되어 5tick이 되었는지를 확인하는 방법을 Busy Waiting이라고 한다.

[ 상세 설명 ] 

1) 현재 :

   1. thread_create() 함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   2. thread가 실행되며 목표한 시간이 지났는지 확인한다.

   3. 목표한 시간에 도달하지 않았으면 ready_list에 넣는다.

   4. ready_list의 맨 앞에 있는 thread를 실행한다.

thread를 여러개 생성한 뒤, 2-3-4를 반복하면서 계속 목표한 시간에 도달되었는지 확인하고, 도달하면 thread를 종료시킨다. Test Case 수행 결과를 보면 kernel ticks, idle ticks, user ticks가 있는데 의미하는 바는 아래와 같다.

kernel ticks : kernel thread들이 수행되는데 걸리는 시간

idle ticks : idle thread가 수행되는데 걸리는 시간

user ticks : 사용자 프로그램이 수행되는데 걸리는 시간

Busy Waiting으로 구현되어있기 때문에, 모든 thread들이 종료될 때까지 idle thread는 수행되지 않는다. (user ticks는 현재 보지 않아도 된다.) 따라서, Busy Waiting으로 수행하면 아래와 같은 결과를 얻을 수 있다.

idle ticks : 0, kernel ticks : 800, user ticks : 0 

2) 목표 : 

   1. Sleep List를 만든다.

   2. thread_create()함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   3. thread가 time_sleep 함수를 실행하며 목표한 시간이 지났는지 확인한다.

   4. 목표한 시간이 지나지 않았으면 sleep_list에 추가한다.

   5. Sleep List에 있는 Thread들의 최소 Wakeup Tick을 전역변수에 저장한다.

   5. timer interrupt(매 tick마다 발생)마다 최소 Wakeup Tick보다 작은지 확인한다.

   6. 목표한 시간에 도달하면, sleep list에서 해당 thread를 제거하고, ready_list에 추가한다.

   7. ready_list에 추가된 thread는, 자신의 차례가 되면 실행되고 종료된다.

위와 같이 실행하면, 목표한 시간에 도달하지 못한 thread들은 모두 sleep_list에서 실행되지 않고 자고 있다. 따라서 idle_thread가 실행되며 아래와 같은 결과를 얻을 수 있다.(결과는 조금씩 다를 수 있다.)

idle ticks : 500, kernel ticks : 300, user ticks : 0 

2. Priority Scheduling

목표 :

   1. 현재는 thread들이 생성되면 ready_list의 맨 뒤에 넣고 순차적으로 실행된다. 하지만 thread에는 priority라는 우선순위를 나타내는 변수가 있다. 우선순위가 높은 것들이 먼저 실행되도록 관련 함수들을 변경한다.

   2. Semaphore와 Lock을 사용하여, Critical Region에서 Atomic Operation이 일어남을 보장한다.

   + Critical Region에 여러개의 쓰레드가 동시에 접근할 때, 하나의 작업이 종료되기 전에 다른작업이 시작되면 데이터가 이상해질 수 있다. 따라서 Critical Region에서 작업하는 Thread에게는 Lock의 소유권을 부여하고, Lock을 소유하지 못한 Thread들은 Lock의 소유권이 풀릴 때까지 Waiters에서 기다린다.  

   3. 2번의 상황에서 Priority가 높은 Thread가 Priority보다 낮은 Thread가 먼저 수행되는 것을 막기 위해, Priority Donation 이라는 개념을 적용한다.

3. Cond Var(Monitors)

   1. Monitor 구조를 활용한다.

4. Multi Level Feedback Queue Scheduler

   1. Priority Donation만으로는 Starvation 등의 문제를 해결하지 못한다. recent_cpu, load_average 등의 변수를 활용하여 Priority를 유동적으로 변경해주는 Multi Level Feedback Queue Scheduler를 적용한다.

후기

OS의 맛을 볼 수 있는 재미있는 프로젝트였다. 앞으로 훨씬 더 어려워질 것 같아 걱정이지만 열심히 공부하고 정리해야겠다.

Debugging은 gdb보단 printf와 뇌버깅이 훨씬 더 편한것같다..

가상 메모리, Heap, 동적 할당기, Malloc Lab 과제에 대한 글입니다.

1. Virtual Memory

  메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리라고 알려진 메인 메모리의 추상화를 제공한다. 가상 메모리는 각 프로세스에 하나의 크고 통합된, 사적 주소공간을 제공하며, 기능을 크게 세 가지로 요약할 수 있다.

1) 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급한다.

2) 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.

3) 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

2. Heap

  프로세스는 Stack, Heap, bss, data, text로 메모리 공간을 나눠놓고 사용하는데, Heap이라는 영역은 사용자가 필요에 따라 원하는 메모리 Block을 요청하고, 반환할 수 있다. Heap 영역은 일반적으로 낮은 주소에서 높은 주소로 자란다.

3. 동적 할당기 (Memory Allocator)

: 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우가 있기 때문에 동적 할당을 사용하는데, Heap 영역을 관리하는 도구를 동적 메모리 할당기라고 부른다. 할당기에는 두 가지 종류가 있다.

1) 명시적 할당기 : 명시적으로 malloc을 통해 공간을 할당하고, free를 통해 공간을 반환해야 하는 방식의 할당기. 즉, 사용자가 직접 공간을 할당하고 반환하는 작업을 명시적으로 해줘야 한다.

2) 묵시적 할당기 : 사용자가 할당한 메모리 Blcok들에 대하여, 더 이상 프로그램에 의해 사용되지 않는 Block을 검출하여 반환시켜주는 작업을 수행하는 할당기. 가비지 컬렉터라고 부르며, Block을 반환하는 작업을 가비지 컬렉션이라고 부른다.

* 명시적 할당기 예시 - C의 표준 라이브러리 : Malloc

  사용자가 요청한 크기의 빈 Block을 찾고, 포인터를 return한다. 32bit 시스템은 8의 배수, 64비트 시스템은 16의 배수로 align된 주소값을 return한다. 사용 가능한 메모리보다 큰 Block을 요청하는 경우 null을 return하고, 성공적으로 메모리 Block을 return하는 경우에도 메모리 블럭의 내용을 초기화하지는 않는다. 이를 원한다면 할당된 메모리를 0으로 초기화하는 calloc을 사용할 수 있다. 이미 할당된 메모리 Block의 크기를 변경하고자 한다면 realloc을 사용한다.

명시적 할당기의 구현

  명시적 할당기를 구현하는 과정이 Malloc Lab의 과제였다. 메모리 할당 과정은 아래와 같은 함수들로 구성된다. (Block에 관한 자세한 설명은 맨 아래 참조)

mem_sbrk() : Heap 전체 사이즈를 늘린다. 요청된 메모리 Block을 만족하는 빈 공간이 없을 때 호출된다.

find_fit() : 허용된 Heap 영역 내에서, 요청된 메모리 Block Size를 만족하는 빈 공간이 있는지 찾는다.

coalesce() : 빈 공간이 연속적으로 있다면, 합친다.

malloc() : 메모리 공간을 할당하기 위해 호출된다.

free() : 메모리 공간을 반환한다.

동적 할당은 아래와 같은 과정으로 이루어진다.

1) Heap을 초기 사이즈인 CHUNK_SIZE(ex : 4KB)로 생성한다.

2) 사용자의 요청에 따라 Heap 내에 공간을 할당한다.

3) 할당된 Heap 내에 더이상 할당할 공간이 없다면, CHUNK_SIZE 단위로 Heap을 증가시킨다.

실제로 구현하는 방법은 아래와 같이 구조/기능에 따라 다양하다.

[ 구조 ]

1) 묵시적 가용 리스트(Implicit Free List) : Allocated Block, Free Block이 할당된 채로 아무것도 하지 않은 구조. Header/Footer를 확인하며 순차적으로 검색한다.

2) 명시적 가용 리스트(Explicit Free List) : Free Block들만 연결 List로 연결한 뒤, Free List에서 요청한 크기를 만족하는 Free Block을 찾는다. 이 때 Free Block에 연결 List를 구성하기 위한 추가 데이터를 넣는다. 어짜피 비어있는 공간이라 메모리 낭비는 발생하지 않는다.

3) 분리 가용 리스트(Segregated Free List) : Free List를 크기 별로 관리한다. 크기를 관리하는 방법은 다양하다. 특정 크기가 들어왔을 때 해당 크기가 포함된 범위의 Free List만 살펴보면 되므로 검색 시간이 단축될 수 있다.

[ 기능 ]

1) First Fit : 처음부터 끝까지 순차적으로 검색하며 조건을 만족하는 Block을 바로 return한다.

2) Next Fit : 가장 최근에 할당된 Block을 기록해놓은 뒤, 그 다음 것 부터 찾는다.

3) Best Fit : 모든 공간을 검색해본 뒤, 가장 가까운 크기를 갖는 Block을 return한다.

할당기의 성능

할당기의 성능은 아래와 같이 측정할 수 있다.

할당된 공간 / 전체 Heap Size

위의 값이 클수록, 단편화(Fragmentation)가 적게 일어나서 메모리가 효율적으로 사용된 것이다.

(단편화에 관한 자세한 설명은 맨 아래 참조)

* 묵시적 할당기 예시 : 가비지 컬렉터

아래와 같은 경우 가비지(사용자가 메모리 Block을 동적 할당해놓고 반환하지 않는 경우)가 발생한다.

  이런 가비지들을 Free하기 위해서, 다양한 방법들이 있지만 가장 기초적인 Mark & Sweep 방법을 소개한다. 아래 그림과 같이 루트 노드들과 힙 노드들로 이루어진 방향성 도달 그래프로 메모리 참조 관계를 나타낸다. 각 힙 노드는 하나의 할당된 Block을 나타내며, 어떤 루트 노드에서도 특정 힙 노드 p로 향하는 경로가 없다면, p는 가비지로 인식된다.

Mark : 루트 노드들의 도달 가능하며 할당된 하위노드들을 표시하는 행위

Sweep : 표시되지 않은 블록을 반환하는 행위

  어떤 가비지 컬렉터는 별도의 쓰레드로서 실행되어 그래프를 관리하며 가비지를 회수하기도 하고, 어떤 가비지 컬렉터는 가용 블럭이 더이상 없을 때 호출되어 찾기도 한다. 후자를 보수적인 가비지 컬렉터라고 한다. 

* Segmentation Fault : 페이지 테이블에는 허가 비트라는 것이 있어서 가상 페이지 내용으로의 접근을 제어하는데, 어떤 인스트럭션이 이 허가사항을 위반할 경우 Fault를 발생시키며, 이것이 Segmentation Fault이다.

* Stack Buffer Overflow : 버퍼의 사이즈를 할당해놓고 입력을 받을 때, 입력의 사이즈가 버퍼의 크기를 넘어가는 경우 발생한다. fgets를 사용하여 입력 사이즈를 제한하여 해결한다.

* Block과 Free Block, Allocated Block

  이 글에서 명시하는 Block은 Heap 영역 내에 쪼개진 하나의 저장 공간을 의미한다. Allocated Block은 사용자가 명시적으로 할당을 요청한 Block이고, Free Block은 Allocated되지 않은 Block이다. 우선 하나의 Block은 어떤 구조를 갖는지 살펴보자.

  Block은 아래와 같은 구조를 갖는다. 맨 앞, 맨 뒤에 있는 식별자인 Header, Footer는 Free 시에 활용된다. 예를 들어 Allocated Block을 Free시킨다고 하자. 해당 Block을 Free시키는 것은 문제가 없지만, 외부 단편화와 내부 단편화를 막기 위해 앞뒤로 Free Block이 있는 경우 합치는 작업(Coalesce)을 진행해야 한다. 이 때 앞뒤에 있는 Block의 할당 여부, 크기를 알기 위해서 사용되는 것이 Header와 Footer이다.

* Header : 크기와 할당 여부를 나타내는 1Word 크기의 식별자

* Payload :  사용자가 할당을 요청한 데이터 영역. Malloc의 경우 해당 영역을 초기화하지 않는다.

* Footer : 크기와 할당 여부를 나타내는 1Word 크기의 식별자

* 외부 단편화(External Fragmentation) : 사용자가 요청한 메모리 할당을 위한 Free Space는 충분하지만, 연속적이지 않아 메모리 할당이 불가능한 경우. 아래와 같이 Free Space(흰색)와 Allocated Space(회색)가 있고, 사용자가 50KB의 메모리 공간 할당을 요청했다고 하자. 전체 Free Space의 합은 55KB로 요청한 메모리 할당을 위한 공간이 충분하지만, 연속적이지 않아 할당이 불가능하여 Heap 영역을 늘려야 한다. (이 때, 임의로 Assigned Block을 이동시켜 Free Block들을 합치는건 불가능하다.)

* 내부 단편화(Internal Fragmentation) : 할당기의 규칙에 의해 할당한 메모리 공간에서 실제로 사용되는 공간이 작은 경우 발생한다. 아래와 같이 Assigned Space보다 Used Space가 작을 때 발생한다. Padding이나 메모리 할당 방식의 차이에 따라 발생한다.

1. B-Tree의 정의

  B-Tree란 디스크 등의 보조기억장치에서 데이터를 검색하는데 시간을 최소화하기 위하여 고안된 자료구조이다.

2. B-Tree를 사용하는 이유

  특정 Data를 CPU에서 사용하기 위해서는, 원하는 데이터를 디스크에서 찾은 뒤 메인 메모리에 올려야 한다. 원하는 데이터를 찾기 위해서는 특정 데이터를 메인 메모리에 올린 후 원하는 데이터인지 비교함으로써 알 수 있는데, B-Tree를 사용하면 이 비교하는 횟수를 작게할 수 있다.

  임의의 Tree에서, 하나의 노드가 가진 데이터의 크기가 메모리의 크기와 동일하다고 하자. 원하는 데이터를 찾기 위해서는, 하나의 노드에 접근할 때마다 노드가 가진 데이터를 메인 메모리에 올려서 찾는 데이터가 맞는지 확인하는 과정이 필요하다. 트리의 높이가 낮을수록 비교하는 연산이 줄어들게 되며, B-Tree의 높이 h는 다음과 같이 정의된다.(t : 최소 차수, 뒤에서 추가 설명)

3. B-Tree의 정의

  B-Tree를 구현하는 방법은 다양하다. 여기서는 Introductions to Algorithms에서 정의하는 방식을 사용한다. (최대차수는 짝수만 가능하다.) 모든 노드는 KEY와 CHILD이라는 구성요소를 가진다. KEY는 트리 안에서 찾아야 하는 값이며, CHILD은 자식 노드를 가리키는 포인터이다.

1. B-Tree의 모든 노드는 아래와 같은 정의를 가진다.

  1) 모든 노드는 포함할 수 있는 KEY의 개수의 범위가 정해져 있다. 범위를 정하는 숫자 t를 최소 차수라고 하며, 최소 차수는 2 이상의 정수이다. 특정 노드의 KEY의 개수가 x개라면, CHILD의 개수는 x+1개이다.

  2) 루트를 제외한 모든 노드는 t-1 개 이상의 KEY를 가진다.(최소 KEY의 개수)

  3) 루트를 제외한 모든 노드는 t개 이상의 CHILD를 가진다.(최소 CHILD의 개수)

  4) 리프는 CHILD을 가지지 않는다.

  5) 모든 노드의 최대 KEY의 개수는 2t-1개이며, 최대 CHILD의 개수는 2t이다.(이 때 가득 차 있다고 표현한다.)

  6) 노드 내의 KEY는 정렬되어 있다.

  7) 특정 키 X의 왼쪽 CHILD에는 X보다 작은 KEY 값들만 존재하며, 오른쪽 CHILD에는 큰 KEY 값들만 존재한다.

이를 만족하는 최소 트리(t=2)는 아래와 같다.

다음 포스팅에서 B-Tree를 구현해본다.