[Operating System] Final Exam Class 2 Fall 2021 (Week 13-14: On-Memory File System)

본 포스팅은 인하대학교 김기창 교수님의 [202502-EEC4406-001] Operating System을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

Question: 

(Submit one word/pdf/hwp file that includes the source code, the output capture, and FULL explanation about your solution.)

 

1. Predict the exact page numbers that will cause page fault for following program with explanation why you have thought that way.

 

아래 코드에 대해 발생하리라고 예측되는 정확한 페이지 폴트 넘버를 예측하고 그렇게 예측한 근거를 설명할 것. 폴트를 일으키리라고 예측되는 페이지 넘버를 실제로 제시해야 합니다.

 

int A[5][512];  // 512 not 1024. 1024가 아니고 512 입니다.

int foo(int k){
  int s;
  s=k+1;
  return s;
}

int main(){
  int i,j;
  int x;
  x=foo(30);
  for(i=0;i<5;i++){
    for(j=0;j<512;j++)
       A[i][j]=3;
    }
 }
}

 

 

2. Display actual page fault addresses for the program in Problem 1 and show which fault address matches which page fault number you have predicted.

 

위 코드에 대해 실제 발생하는 페이지 폴트 주소들을 모두 나열하고 그 중에서 위 문제 1에서 예측했던 페이저 폴트 넘버에 해당하는 주소들을 제시하시오.

 

 

(1) Answer:

 

1. 프로그램 구조

int A[5][512];  // 512 not 1024. 1024가 아니고 512 입니다.

int foo(int k){
  int s;
  s=k+1;
  return s;
}

int main(){
  int i,j;
  int x;
  x=foo(30);
  for(i=0;i<5;i++){
    for(j=0;j<512;j++)
       A[i][j]=3;
    }
 }
}

• int A[5][512];: 전역 변수이므로 data 영역에 올라가고, 하나의 행의 크기는 512 x 4byte = 2048 byte = 2KB가 된다. 따라서 전체 크기는 2KB x 5 = 10KB가 된다.
• int foo(int k): 매개변수를 k에 담으며, 지역 변수 s를 선언하는  함수이다. code 영역에 올라간다.
• int i, j, x;: main() 안의 지역 변수이므로 stack 영역에 올라간다.
• main() code: 실행 코드는 code 영역에 올라간다.

 페이지 크기는 4KB (0x1000)이며, 총 code/data/stack 3개의 페이지에 접근한다.

 

2. Page Fault가 발생하는 순서

 

(1) code page

 프로세스가 시작하면, CPU가 main()의 명령어를 가져와야 하므로 code page에 접근해야 한다. 만약 code page가 메모리에 없다면 첫 번째 page fault가 발생한다. 이때 main()과 foo()는 둘 다 같은 페이지에 있으므로, 이후 foo(30)을 호출해도 새로운 page를 호출하지 않는다. 

→ 한 개의 page fault가 발생한다.

 

(2) stack page

 main()이 호출되면, 지역 변수 i, j, x를 할당하기 위해 stack에 공간을 만든다. 또한 for문에서 'x++'을 하면서 계속해서 스택을 사용한다. 이때 stack page에 접근할 때, 아직 stack page가 메모리에 없다면 두 번째 page fault가 발생한다.

→ 한 개의 page fault가 발생한다.

 

(3) data page

 A[5][512]는 전체 크기가 10KB인 전역 배열이다. 그러면 한 페이지 크기가 4KB이므로 두 개의 행이 정확히 1개의 page가 되고, 따라서 총 3개의 Data page를 사용하므로 세 번의 page fault가 발생한다.

 

for(i=0;i<5;i++){
  for(j=0;j<512;j++)
    A[i][j] = 3;
}

• i = 0, j = 0~511에서 A[0][0]을 처음 쓰는 순간 아직 메모리에 없으므로 →  한 개의 page fault가 발생한다.
• i = 1, j = 0~511에서 여전히 같은 페이지를 사용하므로 → 추가적인 page fault는 발생하지 않는다.
• i = 2, j = 0~511에서 A[2][0]을 처음 쓰는 순간 새로운 페이지에 처음 접근하므로 →  한 개의 page fault가 발생한다.
• i = 3, j = 0~511에서 여전히 같은 페이지를 사용하므로 → 추가적인 page fault는 발생하지 않는다.
• i = 4, j = 0~511에서 A[4][0]을 처음 쓰는 순간 새로운 페이지에 처음 접근하므로 →  한 개의 page fault가 발생한다.

정리하면 이중 for문이 실행되면서 A[0][0] / A[2][0] / A[4][0]에 접근할 때마다 page fault가 발생하고, 총 세 번의 page fault가 발생한다. 프로그램으로 인해 발생하는 주요 page fault 순서는 code page → stack page → data page가 된다.

 

3. Page Fault 주소 출력

test.c

 각 주소들이 예측한대로 페이지를 공유하고 있거나 혹은 얼마나 많은 페이지를 보유하고 있는지 확인하기 위해 주어진 코드의 상단에 주소들을 출력하도록 구현하였습니다.

 

 실행하고 결과를 확인해본 결과 정상적으로 예측한대로 페이지를 공유하고 있었습니다. 페이지 번호를 확인하였으니 정확한 페이지 번호를 계산하면 아래와 같습니다.

 

(1) code page

→ main()과 foo()는 같은 코드 페이지인 0x8048에 있습니다.

 

(2) stack page

→ 지역 변수인 i, j, k는 같은 스택 페이지인 0xbfd5에 있습니다.

 

(3) data page

→ 전역 배열인  A[5][512]는 A[0][0~511]과 A[1][0~511]이 같은 데이터 페이지인 0x804a에 있습니다. 그리고 A[2][0~511]과 A[3][0~511]이 같은 데이터 페이지인 0x804b에 있고, A[4][0~511]은 0x804c에 있습니다.

 

(2) Answer:

 

arch/x86/mm/fault.c

...

  page fault는 INTERRUPT 14번 이므로 ‘do_page_fault()’가 호출됨을 알 수 있습니다. 따라서 해당 함수에서 전역 변수인 ‘pfcnt’를 1씩 증가시키도록 구현합니다.

 먼저 “arch/x86/mm/fault.c” 경로로 이동하여 전역 변수 ‘pfcnt’를 선언 및 초기화하고, ‘do_page_fault()’ 함수가 한 번 호출될 때마다 ++ 하도록 구현하였습니다.

 

test.c

 사용자 정의 파일은 위와 같이 구현하였습니다. 

 

컴파일 및 재부팅 후  현재 커널 레벨을 조절하고 컴파일 및 재부팅 후 'dmesg > x;, vi x' 를 통해 실행 결과를 확인하였습니다.  

 

4. 실행 결과 분석

 

 

(1) code page

• &main, &foo = 0x8048034
• 0x8048000 <= addr < 0x8049000
• → page number = 0x8048

(2) data page

• &A[0][0] = 0x804a014
• &A[2][0] = 0x804b000
• &A[4][0] = 0x804c000
• 0x804a000 <= addr < 0x804affff
• 0x804b000 <= addr < 0x804bffff
• 0x804c000 <= addr < 0x804cffff
• → page number = 0x804a / 0x804b / 0x804c

(3) stack page

• &i, j, x = 0xbfcc7a5b
• 0xbfcc0000 <= addr < 0xbfccffff
• → page number = 0xbfcc

 

 dmesg에 찍힌 Pafe Fault 주소와 매칭해보면 아래와 같다.

 

(1) 0x08048034

• code page
• main()과 foo()가 들어있는 code page가 처음 실행될 때 발생한 page fault이다.

(2) 0x804a014 / 0x804b000 / 0x804c000

• data page
• &A[0][0], &A[2][0]. &A[4][0]이 있는 stack page가 처음 사용될 때 발생한 page fault이다.

(3) 0xbfcc7a5b

• stack page
• 지역 변수 i, j, k가 들어 있는 stack page가 처음 실행될 때 발생한 page fault이다.

(4) 0xb7e*****, 0xb7f*****

• "/lib/ld-2.6.1.so", "glibc"과 같은 공유 라이브러리 페이지에서 발생한 page fault이다.
• 이는 #include 를 통한 library 파일의 영역을 include 하면서 발생된 page fault 로 해석된다.

(5) 0x8049f20 / 0x8049f6c

• main()을 초기화 하는 과정에서 발생하는 page fault로 해석된다.