📀 KAIST:PINTOS | Implementation | Frame Table

Frame Table의 개념

Frame Table은 운영체제의 가상 메모리 시스템에서 물리 메모리 페이지(프레임)를 전역적으로 관리하기 위한 자료구조이다. 운영체제의 가상 메모리는 프로세스마다 각기 다른 가상 주소 공간을 제공하고, 이 가상 주소는 실제 물리 메모리의 프레임으로 매핑된다. 이때 물리 메모리의 실제 사용 현황을 파악하고, 어떤 프레임이 누구(어떤 프로세스)의 가상 페이지를 담고 있는지를 추적하기 위해 Frame Table이 필요하다.

프레임은 한 번 할당되면 어떤 유저 페이지의 데이터를 담고 있는지 연결되어야 하며, 프레임이 부족해지면 교체(eviction) 정책을 통해 다른 프레임을 swap-out하거나 새로운 프레임을 할당해야 한다. Frame Table은 이러한 프레임 관리의 중심 역할을 맡는다.

---

Frame Table이 필요한 이유

가상 메모리에서 새로운 페이지를 요구할 때마다 물리 메모리에서 빈 프레임을 찾아야 한다. 하지만 물리 메모리는 유한하기 때문에, 항상 빈 프레임이 있는 것은 아니다. 프레임이 부족하면 교체 정책을 사용하여 다른 프로세스나 다른 페이지의 프레임을 비워야 한다. 이를 효율적으로 처리하기 위해 Frame Table이 있어야 한다.

또한, 스레드나 여러 프로세스가 동시에 메모리에 접근할 수 있기 때문에, Frame Table은 동시 접근을 안전하게 관리할 수 있도록 락(lock)으로 보호해야 한다.

---

Frame Table의 주요 데이터

Frame Table의 각 엔트리는 하나의 프레임을 나타내며 보통 다음과 같은 정보를 담는다.

• 물리 메모리의 커널 가상주소
  void *kva
palloc_get_page()로 얻은 실제 메모리의 커널 가상주소이다.

• 연결된 유저 페이지
  struct page *page
  어떤 유저 페이지가 이 프레임을 사용 중인지 나타낸다. 이는 Supplemental Page Table(SPT)의 엔트리와 연결된다.

• pinned 여부
  Eviction 과정에서 잠깐 보호할지 여부를 나타낸다. 예를 들어, 파일 읽기나 쓰기 중에는 페이지를 Eviction으로 내보낼 수 없기 때문에 pinned 상태로 둔다.

• 기타 정보
  Eviction 알고리즘(예: LRU Clock)을 구현할 때는 접근 비트나 다른 상태 비트도 추가할 수 있다.

---

구현 흐름 및 함수

자료구조 선언

Frame Table은 보통 전역 리스트 형태로 선언한다.
vm.c 또는 vm.h에 아래처럼 선언한다.

struct frame {
    void *kva;               // 실제 물리 메모리의 커널 가상주소
    struct page *page;       // 연결된 유저 페이지
    struct list_elem elem;   // 리스트에서의 위치
    bool pinned;             // Eviction 중 보호 여부
};

struct list frame_table;
struct lock frame_table_lock;  // 멀티스레드 보호용 락

---

프레임 할당 함수

유저 페이지가 새로운 프레임을 요청할 때 호출되는 함수이다.

struct frame *frame_allocate(enum palloc_flags flags, struct page *page) {
    void *kva = palloc_get_page(flags);
    if (kva == NULL) {
        // 프레임이 부족하면 Eviction을 수행해 프레임 확보
        kva = evict_frame();
        if (kva == NULL) {
            PANIC("Cannot evict any frame!");
        }
    }

    struct frame *f = malloc(sizeof(struct frame));
    f->kva = kva;
    f->page = page;
    f->pinned = false;

    lock_acquire(&frame_table_lock);
    list_push_back(&frame_table, &f->elem);
    lock_release(&frame_table_lock);

    return f;
}

이 함수의 주요 역할은 새로운 프레임을 확보하고 Frame Table에 등록하는 것이다. 프레임이 부족할 때는 Eviction 정책을 사용해 확보한다.

---

프레임 해제 함수

프로세스가 종료되거나, 프레임을 더 이상 사용하지 않을 때 호출된다.

void frame_free(struct frame *f) {
    lock_acquire(&frame_table_lock);
    list_remove(&f->elem);
    lock_release(&frame_table_lock);

    palloc_free_page(f->kva);
    free(f);
}

해당 프레임을 Frame Table에서 제거하고, 실제 메모리를 반환한다.

---

Eviction 정책과 연계

프레임이 부족할 때 어떤 프레임을 내보낼지 결정하는 것이 Eviction 정책이다. 보통 LRU Clock 알고리즘이 자주 사용된다.

Eviction의 핵심 흐름은 다음과 같다.

1. Frame Table을 순회하여 교체할 수 있는 프레임을 찾는다.
2. 선택된 프레임의 데이터를 swap-out하거나 파일에 다시 기록한다.
3. 해당 프레임의 연결된 SPT를 업데이트한다.
4. Eviction으로 확보된 프레임을 다시 할당한다.

---

주의할 점

• Frame Table은 전역 자료구조이므로 여러 스레드나 프로세스에서 접근할 수 있다. 반드시 락을 사용해 동시 접근을 막아야 한다.
• palloc_get_page()나 palloc_free_page()는 PintOS에서 실제 물리 메모리 할당과 해제를 처리하는 함수이므로 정확히 언제 호출되는지 확인해야 한다.
• SPT와 Frame Table은 유기적으로 연결된다. SPT의 페이지가 프레임을 사용 중이라면 Frame Table의 엔트리와 연결되어야 한다.