[Operating System] Final Exam Class 1 Fall 2020 (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 "4320", 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.

 

dd bs=1024 count=4320 if=/dev/zero of=myfd2

mkfs -t ext2 myfd2

 

 다음과 같이 빈 디스크 myfd2를 만들라. 이때 “count” 값은 “1440”이 아니라 “4320”임에 주의하라. myfd2 안에 f1 파일을 만들고 그 안에 "hi f1"을 써 넣어라. f1의 블록 번호를 계산하고, 그 블록의 내용을 보여라. 단순히 vi에서 문자열 "hi"를 검색하는 방법은 인정되지 않는다.
 반드시 superblock에서 시작해 group descriptor의 위치를 찾고, group descriptor에서 inode table의 위치를 찾는 식으로, 단계별로 f1 블록 위치를 찾아야 한다.

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.

 

 아래 프로그램에 대해 페이지 폴트를 발생시키는 페이지 번호의 순서를 예측하라. 왜 그런 예측을 했는지 자세히 설명해야 한다.
그런 다음, 페이지 폴트 주소를 출력하도록 해서 실제 결과를 확인하라. 예측한 각 페이지 번호가 실제 어떤 페이지 폴트 주소에 대응하는지 표시하라. 이 매칭을 왜 그렇게 했는지도 자세히 설명해야 한다.

 

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

 

 

(1) Answer:

1. myfd 디스크 생성

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

 

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

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

 

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 (38 04 00 00): m_inodes_count에 해당되고, 10진수로 변환하면 1080임을 알 수 있다. 즉, 최대 1080개의 inodes를 사용할 수 있다.
• 4~7Byte (e0 10 00 00): m_blocks_count에 해당되고, 10진수로 변환하면 4320임을 알 수 있다. 즉, 블록 크기 1KB로 format했을 때의 총 Block 수와 일치한다.
• 8~11Byte (d8 00 00 00)/ 13~16Byte (36 10 00 00): 각각 m_r_blocks_count와 m_free_blocks_count에 해당되고, 10진수로 변환하면 각각 216, 4150임을 알 수 있다. 

3. mount

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

 "ls -i" 명령어는 각 파일의 inode를 알 수 있는 명령어입니다.

 

Group Descriptor (0x800)

• 0~3Byte (13 00 00 00): bg_block_bitmap에 해당되고, 10진수로 변환하면 19임을 알 수 있다. 즉, 0x4c00에 해당된다. 
• 4~7Byte (14 00 00 00): bg_inode_bitmap에 해당되고, 10진수로 변환하면 20임을 알 수 있다. 즉, 0x5000에 해당된다.
• 8~11Byte (15 00 00 00): bg_inode_table에 해당되고, 10진수로 변환하면 21임을 알 수 있다. 즉, 0x5400에 해당된다.

 

Name	Super Block	Group Descriptor	DBM	IBM	Inode Table
Block Num	1	2	19	20	21
Address	0x400	0x800	0x4c00	0x5000	0x5400

 

 

DBM (0x4c00)

 

 

IBM (0x5000)

 

Inode Table (0x5400)

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

 

Root File Location (0x27000)

0x27000을 확인해보니 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번임을 확인하였으니, 0x5400 + 0x80 * (12 - 1) = 0x5980계산을 통해 "f1" 파일의 inode table 주소로 이동합니다. 

 0x5980에서 "f1'의 block location을 확인한 결과 '01 04' -> '04 01' = 1025번째 block에 위치하는 것을 알 수 있습니다. 

 

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

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

 

(2) Answer:

 

1. 프로그램 구조

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

• int y[512];: 전역 변수이므로 data 영역에 올라가고, 크기는 512 x 4byte = 2048 byte = 2KB가 된다.
• int k = 0;: 전역 변수이므로 data 영역에 올라가고, 크기는 4byte이다.
• 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가 발생한다.

→ fault 주소는 main() 근처가 된다.

 

(2) stack page

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

→ fault 주소는 &x 근처가 된다.

 

(3) data page

 'for(x=0; x<512; x++)' 반복문에서 'y[x] = 3;, k = k + y[x];' 두 코드 모두 data 영역에 접근한다. 이때 date page가 아직 메모리에 없다면 세 번째 page fault가 발생한다.

 이후 x = 1 ~ 511까지는 y와 k가 모두 같은 4KB 페이지 안에 있기 때문에 추가적인 page fault가 발생하지 않는다. 

→ fault 주소는 &k 주변 주소가 된다.

 

 따라서 프로그램으로 인해 발생하는 주요 page fault 순서는 code page → stack page → data page가 된다.

 

3. 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()’ 함수가 한 번 호출될 때마다 ++ 하도록 구현하였습니다.

 

arch/x86/kernel/syscall_table32.S

“arch/x86/kernel/syscall_table_32.S” 경로로 이동하여 사용하지 않는 35번 system call을 ‘sys_show_pfcnt’로 변경하여 선언하였습니다.

 

mm/mmap.c

 ‘sys_show_pfcnt()’ system call은 현재 저장된 'pfcnt' 값을 출력하도록 단순하게 구현하였습니다.

 

final_2020.c

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

 

 

4. 실행 결과 분석

(1) code page

• &main = 0x80483b4
• 0x804b000 <= addr < 0x8049000
• → page number = 0x8048

(2) data page

• &y[0] = 0x804a040
• &k = 0x804a024
• 0x804a000 <= addr < 0x804affff
• → page number = 0x804a

(3) stack page

• &x = 0xbfaef6f0
• 0xbfaef000 <= addr < 0xbfaeffff
• → page number = 0xbfaef

 

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

 

(1) 0x0804a018

• data page
• y[0], k가 들어 있는 데이터에 처음 접근될 때 생긴 page fault이다.

(2) 0xbfaef89b

• stack page
• &x가 있는 stack page가 처음 사용될 때 발생한 page fault이다.

(3) 0x08048034

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

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

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

(5) 0x8049f20

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

 실행 결과를 보면서 for문 안에서는 page fault가 한 번도 발생하지 않았음을 확인하였다. for문이 시작되기 전에 이미 필요한 페이지들이 전부 메모리에 올라와 있는 상태이기 때문에, 처음 접근하는 페이지가 없으므로 pafe fault가 발생하지 않는 것이다. 

 

 만약 y[512]가 y[512*512]이면 y가 차지하는 메모리 크기가 262,144 * 4byte = 1,048,576byte이므로 약 1MB에 해당된다. 따라서 페이지 하나가 4KB이므로 1MB / 4KB이면 256 page 정도를 y가 차지하게 된다. 따라서 for문으로 y의 모든 구간을 순회한다고 하면 x = 0~255 / 256~511 / 512~... / ... 이런 식으로 x가 256씩 늘어날 때마다 세 page로 넘어가므로 계속해서 page fault가 루프 안에서 최대 256번 발생학 ㅔ된다.