[Operating System] Final Exam Class 1 Fall 2022 (Week 9-10, 13-14: File System, On-Memory File System)

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

 

Question: 

 

1. Create an empty disk, myfd2, as follows. Note "count" value is "2880", not "1440". Create file f1 in myfd2 and write "hi f1" in it. Compute the block number of f1 and show its block content. You have to explain in detail how you have computed f1's block number. Just searching "hi" in Vi as a string will not be accepted; you have to start from superblock to find the location of the group descriptor, and from group descriptor to find the location of inode table, etc.

 

 myfd2 안에 파일 f1을 만들고, 그 안에 문자열 "hi f1" 을 쓴다. 그 다음 f1이 차지하는 블록 번호를 계산하고, 해당 블록의 내용을 보여라. 이때 f1의 블록 번호를 어떻게 계산했는지 superblock → group descriptor → inode table → 디렉터리 엔트리 순서대로 자세히 설명해야 한다.
 단순히 xxd/vi에서 "hi" 문자열을 검색해서 블록을 찾으면 감점이고, 반드시 파일 시스템 구조를 이용해 찾아야 한다.

 

dd bs=1024 count=2880 if=/dev/zero of=myfd2
mkfs -t ext2 myfd2

 

 

2. Predict the order of page numbers that will cause page fault for following program. You have to explain in detail why you have made such prediction. Check your prediction by displaying page fault addresses. Indicate which page fault address corresponds to which page number you have predicted. Again, you have to explain in detail why you are making such matching.

 

 다음 프로그램에 대해 page fault를 일으키는 페이지 번호들의 순서를 예측하라. 왜 그렇게 예측했는지 자세히 설명해야 한다. 그 다음, 실제로 page fault 주소들을 출력하는 방식으로 예측을 검증하라. 예측한 “페이지 번호”와 실제로 출력된 page fault 주소가 어떻게 매칭되는지 모두 표시하고, 각 매칭에 대해 왜 그렇게 판단했는지 역시 자세히 설명하라.

 

int y[1024];

void main(){
   int x;
   
   for(x=0;x<1024;x++)
     y[x]=3;
}

 

(1) Answer:

1. myfd 디스크 생성

 먼저 "myfd2"의 디스크를 위와 같이 생성할 수 있습니다. 'dd bs=1024 count=2880 if=/dev/zero of=myfd2' 명령어를 사용하여 생성할 수 있고, 디스크의 정보는 아래와 같습니다.

 

• block size = 1024 (=1K Bytes)
• count = 2880 (block 개수)
• if=/dev/zero (입력 파일)
• of=myfd (출력 파일 이름이 myfd인 디스크 생성

 따라서 총 2.88 MB (1KB * 2880 = 2880KB) 크기의 디스크를 생성합니다. 

 

2. 기본적인 디스크 구조

Name	Super Block	Group Descriptor	DBM	IBM	Inode Table
Block Num	1	2~7	8	9	10~32
Address	0x400	0x800	0x2000	0x2400	0x2800

 

  "mkfs -t ext2 myfd2" 명령어를 이용해 myfd를 "ext2" 형식으로 변환해준 다음 myfd2 디스크의 Super Block 위치를 확인해보면, 정보들이 담겨져 있음을 확인할 수 있습니다.

 

 Super Block이 시작되는 위치에서 값들의 의미들은 아래와 같습니다.

• 0~3Byte (68 01 00 00 → 0x168): m_inodes_count에 해당되고, 10진수로 변환하면 360임을 알 수 있다. 즉, 최대 360개의 inodes를 사용할 수 있다.
• 4~7Byte (40 0b 00 00 → 0xb40): m_blocks_count에 해당되고, 10진수로 변환하면 2880임을 알 수 있다. 즉, 블록 크기 1KB로 format했을 때의 총 Block 수와 일치한다.
• 8~11Byte (90 00 00 00 → 0x90) / 12~15Byte ( f5 0a 00 → 0xaf5): 각각 m_r_blocks_count와 m_free_blocks_count에 해당되고, 10진수로 변환하면 각각 144, 2805임을 알 수 있다. 

3. mount

 "temp" 디렉토리를 만들고 "mount -o loop myfd2 temp" 명령어를 통해 myfd2 디스크와 temp 디렉토리를 서로 연결해주었습니다.  

 

 -g1 옵션을 써서 byte 단위로 디스크를 확인합니다.

 

Group Descriptor (0x800)

• 0~3Byte (0e 00 00 00 → 0xe): bg_block_bitmap에 해당되고, 10진수로 변환하면 14임을 알 수 있다. 즉, 14 x 0x400 = 0x3800에 해당된다. 
• 4~7Byte (0f 00 00 00 → 0xf): bg_inode_bitmap에 해당되고, 10진수로 변환하면 15임을 알 수 있다. 즉, 15 x 0x400 = 0x3c00에 해당된다.
• 8~11Byte (10 00 00 00 → 0x10): bg_inode_table에 해당되고, 10진수로 변환하면 16임을 알 수 있다. 즉, 16 x 0x400 = 0x4000에 해당된다.

 

Name	Super Block	Group Descriptor	DBM	IBM	Inode Table
Block Num	1	2	14	15	16
Address	0x400	0x800	0x3800	0x3c00	0x4000

 

 

DBM (0x3800)

 

IBM (0x3c00)

 

Inode Table (0x4000)

 root 디렉토리에 대한 정보를 확인하기 위해 Inode table의 주소인 0x4000으로 이동합니다. 이때 root 디렉토리는 inode table 2번에 위치하기 때문에 root 디렉토리의 inode table 주소는 0x4080입니다. 여기에서 확인해야할 것은 Block location을 가리키는 (3d00 0000 → 0x3d) 입니다. 

 

 따라서 root file location은 0x3d를 10진수로 변환하면 61이므로, 61 x 0x400 = 0xf400임을 알 수 있습니다.

 

Root File Location (0xf400)

0xf400을 확인해보니 root 디렉토리 안에 생성된 f1 파일이 존재함을 확인하였습니다. struct를 참고하여 해석해 보면

 

1)

m_inode = '02 00 00 00' → '00 00 00 02 ' → 2번 inode

m_inode = '0c 00' → '00 0c' → 12 recode length

m_name_len = '01' → 1 name length

m_file_type = '02' → 2 directory file

m_name = '2e 00 00 00' → “.” name

 

2)

m_inode = '02 00 00 00'  → '00 00 00 02' → 2번 inode

m_inode = '0c 00' → '00 0c' → 12 recode length

m_name_len = '02'  → 2 name length

m_file_type = '02'  → 2 directory file

m_name = '2e 2e 00 00'  → “..” name

 

4)

m_inode = '0b 00 00 00' → '00 00 00 0b' → 11번 inode

m_inode = '14 00' → '00 14' → 20 recode length

m_name_len = '0a' → 10 name length

m_file_type = '02' → 2 directory file

m_name = '6c 6f 73 74 2b 66 6f 75 6e 64' → “lost+found” name

 

5)

m_inode = '0c 00 00 00' → '00 00 00 0c' → 12번 inode

m_inode = 'd4 03' → '03 d4' → 980 recode length

m_name_len = '02' → 2 name length

m_file_type = '01' → 1 regular file

m_name = '66 31 00 00' → “f1” name

 

 "f1" 파일의 inode가 12번임을 확인하였으니, 0x4000 + 0x80 * (12 - 1) = 0x4580계산을 통해 "f1" 파일의 inode table 주소로 이동합니다. 

 0x4580에서 "f1'의 block location을 확인한 결과 '01 08' → 0x801 = 2049번째 block에 위치하는 것을 알 수 있습니다. 

 

 따라서 "f1" 파일의 파일 주소는 0x801 * 0x400 = 0x200400에 존재하고 있습니다.

 파일 주소로 이동하여 확인해본 결과, "hi f1"이 정상적으로 저장되어 있음을 확인하였습니다.

 

(2) Answer:

 

1. 프로그램 구조

int y[1024];

void main(){
   int x;
   
   for(x=0;x<1024;x++)
     y[x]=3;
}

• int y[1024];: 전역 변수이므로 data 영역에 올라가고, 크기는 1024 x 4byte = 4096 byte = 4.096KB가 된다. 따라서 2개의 페이지를 사용함을 알 수 있다.
• int 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가 발생한다.

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

 

(2) stack page

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

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

 

(3) data page

  전역 변수 y[1024]는 data에 위치한다. 프로그램이 시작되면 전역 변수 초기화를 위해 data 영역에 접근되므로 page fault가 발생한다. 이때 배열 y[1024]는 4KB를 초과하므로, 두 개의 data page를 사용한다. 따라서 세 번째, 다섯 번째 page fault가 발생한다. 

→  개의 page fault가 발생한다.

 

3. Page Fault 주소 출력

test3.c

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

 

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

 

(1) code page

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

 

(2) stack page

→ 지역 변수인 x는 같은 스택 페이지인 0xbfd9에 있습니다.

 

(3) data page

→ 전역 변수인 y[1024]는 데이터 페이지인 0x804a / 0x804b에 있습니다. 대략적으로 x = 0에서 0x804a에 접근하고, x = 1000 이상일 때 0x804b에 접근됨을 예측할 수 있습니다.

 

Page Fault 주소 출력

arch/x86/mm/fault.c

...

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

 

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

 

test3.c

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

 

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

 

 

4. 실행 결과 분석

 

(1) code page

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

(2) data page

• &y[1024]= 0x804a014 / 0x804b000
• 0x804a000 <= addr < 0x804afff
• 0x804b000 <= addr < 0x804bfff
• → page number = 0x804a  / 0x804b

(3) stack page

• &x = 0xbf8178db
• 0xbf81000 <= addr < 0xbf81fff
• → page number = 0xbf81

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

 

(1) 0x08048034

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

(2) 0x804a014 / 0x804b000

• data page
• 반복문을 통해 전역 변수인 y[1024]에 접근될 때 두 개의 data page를 사용하여 발생한 page fault이다.
• 0x804a014: y[0] 일 때 사용
• 0x804b000: y[1000~1023] 일 때 사용

(3) 0xbf8178db

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

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

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

(6) 0x8049f20 / 0x8049f6c

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

 따라서, 예측한 네 개의 페이지(code, 두 개의 data page, stack)에 대해 실제 page fault 주소가 존재함을 확인했으며, 나머지 page fault는 라이브러리 및 초기화 코드에 의한 것으로 해석하였습니다.