data structures

pintos project 1과 2에서는 대부분 array이나 linked list 자료구조를 사용했다. project 3에 들어오면서 사용해야할 자료구조가 추가되었는데, bitmap과 hash table이다.

1. bitmap

개요

• memory의 주소 하나는 1byte를 나타낸다.
• 그러므로, C언어에서 제일 작은 자료형은 char (1Byte)이다.
• boolean만 저장하는 배열이 필요한 경우에도 char 배열만 사용해야한다.
• 필요한 공간 (1bit)보다 많은 (7bit)가 낭비된다.
• 이를 해소하기 위해, element 를 정의하고 그 element를 쪼개서 boolean(true or false)을 표현한다.
  - ex 1) char를 element로 사용하면, 한 element로 boolean 8개를 나타낼 수 있음.
  - ex 2) int를 element로 사용하면 한 element로 boolean 32개를 나타낼 수 있음.
• 그리고, bit연산을 편하게 할 여러 함수를 정의한다.

bitmap 구조체

struct bitmap {
  size_t bit_cnt;  /* Number of bits. */
  elem_type *bits; /* Elements that represent bits. */
};

• bit_cnt : bitmap의 bit개수
• bits
  - bitmap 자료구조는 unsigned long 을 element로 가짐
  - unsigned long이므로 element 1개당 bit가 64개
  - bitmap_create()로 생성시 필요한 element의 개수만큼, 메모리를 동적할당 받는다.
• bitmap.h 파일에 없고 bitmap.c 파일에만 있으므로 멤버변수를 직접 접근하는 것은 불가능하다.
• bitmap 자료구조에서 제공하는 함수를 통해 bitmap 자료구조를 사용할 수 있다.

bitmap 함수

• bitmap.h 파일 참고

1. Creation and destruction

1. struct bitmap *bitmap_create (size_t bit_cnt)
   • bitmap 자료구조를 생성한다.
   • bit 개수를 인자로 받아, 필요한 만큼 element를 동적할당함.
2. struct bitmap *bitmap_create_in_buf (size_t bit_cnt, void *, size_t byte_cnt)
   • 이미 할당된 블록에 bitmap 자료구조를 생성한다.
3. size_t bitmap_buf_size (size_t bit_cnt)
   • 원하는 크기의 bitmap을 생성하기위해 필요한, 메모리의 크기를 알 수 있다.
4. void bitmap_destroy (struct bitmap *)
   • bitmap 자료구조를 삭제한다.

bitmap_create() 만 사용하는 것 보다.
1. bitmap_buf_size()로 필요한 크기를 알아내고
2. 그 크기만큼 동적할당한 후
3. bitmap_create_in_buf() 로 생성
하는 방식이 더 자주쓰일 것 같다. (메모리에서 연속된 공간에 구조체와 동적배열을 생성할 수 있으므로)

2. Bitmap size

1. size_t bitmap_size (const struct bitmap *)
   • bit_cnt 멤버변수를 리턴한다.
   • bitmap 구조체의 크기가 아님

3. Setting and testing single bits

1. void bitmap_set (struct bitmap *, size_t idx, bool)
   • bitmap에서 idx 번째 요소를 bool값으로 세팅함
2. void bitmap_mark (struct bitmap *, size_t idx)
   • bitmap에서 idx 번째 요소를 true값으로 세팅함
3. void bitmap_reset (struct bitmap *, size_t idx)
   • bitmap에서 idx 번째 요소를 false값으로 세팅함
4. void bitmap_flip (struct bitmap *, size_t idx)
   • bitmap에서 idx 번째 요소를 반전함 (원래 값과 반대로)
5. bool bitmap_test (const struct bitmap *, size_t idx)
   • bitmap에서 idx 번째 요소의 값을 리턴함

• single bit 연산은 모두 어셈블리어 수준에서 atomic
• bitmap_set()을 사용하는 것 보다, 가능하면 bitmap_mark()와 bitmap_reset()을 사용하는 편이 좋을것 같다. (함수의 이름만으로 기능을 명시할 수 있기 때문에)

4. Setting and testing multiple bits

1. void bitmap_set_all (struct bitmap *, bool)
   • bitmap의 모든 비트를 bool 로 초기화
2. void bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소를 bool 로 초기화
3. size_t bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소 중 값이 bool 인 요소의 개수를 리턴함
4. bool bitmap_contains (const struct bitmap *, size_t start, size_t cnt, bool)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소 중 값이 bool인 요소가 존재하는지 여부를 확인함
5. bool bitmap_any (const struct bitmap *, size_t start, size_t cnt)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소 중 값이 true인 요소가 존재하는지 여부를 확인함
6. bool bitmap_none (const struct bitmap *, size_t start, size_t cnt)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소 중 값이 false인 요소가 존재하는지 여부를 확인함
7. bool bitmap_all (const struct bitmap *, size_t start, size_t cnt)
   • bitmap에서 start 번째 요소부터 cnt 개 만큼의 요소 중 값이 true인 요소만 존재하는지 여부를 확인함

5. Finding set or unset bits.

1. size_t bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool)
   • bitmap에서 start 번째 요소부터 시작하여, cnt 개 만큼의 요소가 연속적으로 bool인 위치를 확인함
2. size_t bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool)
   • bitmap_scan()후 확인된 위치에서부터 cnt 개 만큼의 bit를 filp함
   • palloc_get_multiple()에서 first-fit 정책에 사용됨

7. Debugging

1. void bitmap_dump (const struct bitmap *)
   • hex_dump()를 bitmap용으로 래핑한 함수