개발 목표

해당 프로젝트에서 구현할 내용을 간략히 서술

1. Page Table Management

물리 메모리 한계를 넘어서는 프로그램의 실행을 가능하게 하는 효과적인 페이지 테이블 관리를 구현한다. 즉, 가상 페이지를 만들고 가상 메모리를 효율적으로 다루기 위해 페이지 테이블 관리를 개선한다. 이는 페이지 테이블 조회 최적화와 가상 주소에서 물리 주소로의 효율적인 변환을 포함한다. 이를 통해 더 많고 큰 프로그램을 동시에 실행할 수 있다.

2. Paging to and from (swap) disk

시스템의 물리 메모리를 넘어서는 가상 메모리를 디스크 공간을 사용하여 확장할 수 있는 스왑 메커니즘을 설계하고 구현한다. 즉, 메인 메모리의 크기에 제한되지 않고, 스왑 디스크를 활용하여 프로그램을 실행할 수 있는 페이징 기능을 구현한다.

3. Stack Growth

애플리케이션이 필요로 하는 만큼 스택이 동적으로 성장할 수 있도록 보장하여, 스택 이 확장 가능한지 여부를 판단하여 확장한다.

개발 범위 및 내용

개발 범위

- Page Table & Page Fault Handler

이전 프로젝트까지는 address가 유효한지 확인하고, 그렇지 않다면 exit(-1)을 호출했다. 이번 프로젝트부터는 address가 유효하다면 virtual page를 찾아 physical page에 할당한 후 mapping 해야 한다. 유효하지 않다면 stack 확장 여부를 확인한 후 확장해준다. 또한, 페이지 폴트 핸들러를 통해 프로그램 종료 시 할당된 자원을 적절히 해제할 수 있어야 한다. 결과적으로, 시스템의 안정성을 보장하고, 메모르 낭비를 방지한다.

- Disk Swap

물리 메모리가 가득 찼을 때 추가 공간이 필요하므로 디스크 스왑 기능이 필요하다. LRU를 통해 eviction page를 정해준다. 결과적으로, physical memory 모다 더 큰 virtual memory를 mapping이 가능해진다.

- Stack Growth

일반적으로 할당되는 것보다 더 많은 스택 공간을 필요로 하는 애플리케이션을 실행할 수 있도록 스택 성장 구현은 필수적이다. 8MB(default limit)을 기준으로 stack growth를 개발한다. growth가 가능한지 여부를 판단해야한다. 결과적으로, 더 복잡하고 메모리를 많이 요구하는 애플리케이션이 문제없이 실행될 수 있을 것으로 기대한다.

개발 내용

- Page fault가 발생하는 이유와 이를 handling하는 전반적인 과정

physical memory에 없는 page에 접근이 있을 때 page fault가 발생한다. 페이지 폴트 핸들러의 개선을 통해 시스템 호출 또는 페이지 폴트가 발생했을 때 page table내에서 address가 유효하다면, handle_mm_fault를 호출한다. hamdle_mm_fault는 vitual page에서 file을 load하는데, 호출되었을 때 empty frame을 할당받는다. 남아있는 frame이 없다면 page를 replacement algorithm을 통해 replace 하며, 있다면 disk에서 frame으로 page를 swap해준다. 그 다음 physical address와 virtual address를 mapping 해준다.

- Disk swap 발생 시 사용한 page replacement algorithm

위에서 설명한 바와 같이, frame을 가져올 때 남아있는 frame이 없다면 page를 replace 해줘야 한다. 이 때, second chance algorithm을 사용하였다. 밑 그림을 통해 볼 수 있다.

위 경우는 physical frame이 4개인 경우이다. a, b, d, g, e 5개 종류의 virtual page가 있고b g a d e a b a d e g d e 순으로 들어온다. a/1에서 1은 chance를 뜻하며 frame에 처음으로 들어올 때 1이된다. frame이 꽉 차기 전까진 victim pointer와 chance는 별 의미를 가지지 않는다. 6번째 e가 들어올 때 frame이 꽉 차있기 때문에 나머지 page의 chance가 0이 되면서 e는 1의 chance를 가지고 들어오는 것을 볼 수 있다. second chance algorithm은 FIFO queue를 사용하고 LRU와 유사하지만, 뚜렷한 특징을 가진 것을 볼 수 있다.

- Stack growth 구현 시 stack 확장 여부를 판단할 수 있는 방법

우선, 이전 project와 같이 fault_addr이 kernel영역 혹은 user 영역에 있는지 확인이 필요하다. 이후에 pintos의 default limit인 8MB를 넘어가는지 체크해준다. 8MB 체크가 끝나면, pintos manual에 따라 fault_addr가 스택 포인터 4byte 이내에 있거나 32byte아래에 있는지를 확인해줘야한다. x86 아키텍처에서 PUSH 와 PUSHA 명령어가 현재 스택 포인터 아래의 메모리 주소에 접근할 수 있기 때문에 필요한 과정이다. 이를 통과하면 스택이 적절하게 growth가 될 수 있게끔한다

추진 일정 및 개발 방법

추진 일정

11/20 ~ 11/24 : ppt and pintos manual 39 ~ 49 정독
11/25 ~ 11/30 : page table management 구현
12/1 ~ 12/4 : Paging to and from (swap) disk 구현
12/5 ~ 12/7 : stack growth와 page fault 구현
12/8 ~ 12/9 : test case pass 성적이 좋지 않아 page table management, swap disk 코드 초기화 후 stack growth, page fault 가능하게 구현

개발 방법

- userprog/exception.c 파일 내에서 page_fault 함수를 수정했다.

page fault가 발생했을 때, 해당 address가 user address인지 확인하고, page fault address가 kernel 주소에 속하지 않는지 확인한다. 또한, 해당 address의 page가 memory에 존재하지 않는 경우인지, fault_addr이 NULL인지 확인해준다.

- static bool grow_stack(struct intr_frame f, void fault_addr)stack growth가 가능하다면 true, 불가능하다면 false를 return하는 grow_stack bool 함수를 만들어주었다. 상세한 설명은 제작 내용에서 할 것이다.

연구 결과

Flow Chart

• Stack Growth
  

제작 내용

- userprog/exception.c page_fault

!user을 통해 사용자 모드가 아닌 경우를 확인한다. 또한, 현재 context가 kernel mode인지 확인한다. page_fault를 일으킨 address인 fault_addr가 kernel 가상 주소 공간에 있는지 확인하며 !not_present를 통해 page fault가 발생한 page가 memory에 없음을 확인한다. 위 조건들중 하나라도 만족하면 exit(-1)로 종료한다.
if(!grow_stack(f, fault_addr))는 stack growth 함수를 호출하여 조건을 만족하면 성장하고, 그렇지 않으면 exit(-1)로 종료하게 한다.

우선 default limit인 8MB를 limit_st_size에 1<<23(2^23)을 통해 할당한다.첫번째 if 문에서 fault_addr가 stack growth에 대해 유효한 범위 내에 있는지 확인한다. stack은 PHYS_BASE 아래로 growth하며, 이 조건은 fault_addr >= PHYS_BASE - limit_st_size일때 참이다. 그렇지 않으면 false를 return한다.page_k는 palloc_get_page 함수를 사용하여 새로운 page를 할당받는다. PAL_USER | PAL_ZERO 옵션을 통해 user mode에 할당되고, 0으로 초기화된 page를 요청한다.
다음 if문에서 fault_addr가 f->esp(스택 포인터) 바로 아래 4바이트 이내에 있거나 정확히 32바이트 아래에 있는지를 확인한다. 이는 x86 아키텍처에서 PUSH와 PUSHA명령어가 현재 스택 포인터(esp) 아래의 메모리 주소에 접근할 수 있기 때문에 중요하다. PUSH명령은 esp아래 최대 4바이트까지, PUSHA명령은 최대 32바이트까지 접근할 수 있다. 이 줄은 이러한 명령어가 실행될 때 스택이 적절히 성장하도록 하여, 페이지 폴트가 발생하고 처리될 수 있게 함으로써 새 페이지를 할당한다. 조건을 만족하지 못하면 false를 return한다.
이후에 page_k가 NULL이면(Page allocation이 fail 했으면) false를 return한다.마지막으로, pagedir_set_page함수를 사용하여 현재 스레드의 페이지 디렉토리에 새로 할당된 페이지(page_k)를 매핑하려고 시도한다. 성공적으로 매핑되면 true를 반환한다. 이 코드에서 pg_round_down(fault_addr)는 페이지 폴트가 발생한 주소를 페이지 경계로 내림하여, 해당 주소가 포함된 페이지의 시작 주소를 얻는다. 이것은 페이지 폴트가 발생한 정확한 주소가 아니라, 그 주소가 속한 페이지의 시작 주소를 찾기 위함이다. 만약 pagedir_set_page가 실패하면 (즉, false를 반환하면), 할당된 페이지(page_k)는 더 이상 필요하지 않으므로 palloc_free_page를 호출하여 페이지를 해제한다. 그리고 스택 성장 함수는 false를 반환하여 페이지 매핑이 실패했음을 나타낸다.

개발 중 발생한 문제나 이슈

• Page Table Management, Paging to and from (swap) disk 를 구현하려 해보았지만, synchronization문제 등 다양한 문제로 구현하지 못하였다.
• 처음으로 make check을 했을 때, vm test와 thread test가 겹쳐 오류가 발생하는 것을 확인하고, proj2 코드를 다시 가져온 후 시작했다.

시험 및 평가 내용