AWS에 여러명이 원격으로 접속을 하려다보니 PEM키를 공유하는 것보다 아이디 비밀번호로 접속하는 것이 더 쉬울 것 같아서 시작하게되었다. (보안성이 떨어지니 주의)
기존에 PEM 키를 가지고 있다면 아래와 같이 pem키를 가지고 명령어를 입력하여 접속해야 한다.
ssh -i ./final.pem ubuntu@[AWS IP주소]
우선 pem 키를 사용하여 ubuntu에 접속하자. 위의 명령어를 입력하여 접속하면 디렉토리가 홈으로 되어있을 것이다. 아래의 흐름을 따라가보자.
1. 경로 이동하기
cd ..
cd ..
cd etc
cd ssh
를 입력하여 root 디렉토리의 etc/ssh 폴더로 이동한다.
2. 파일 수정하기
sudo vim sshd_config를 입력하여 파일을 아래와 같이 수정한다.
3. root계정으로 swich하여 신규 계정 만들기
sudo su root
adduser "신규 계정 이름"
이후 아래와 같이 생성을 완료한다.
4. 권한 부여하기
sudo visudo를 입력한 뒤 아래와 같이 새로운 user(server)에 모든 권한을 부여한다. 다 작성하고 Ctrl-X를 누른 뒤 [Different-name = yes] → [파일명 뒤에 .tmp 삭제] → [overwrite = yes] 를 순서대로 수행하면 된다.
5. 재시작하기
sudo service ssh restart
6. 접속하기
위와 같이 특정 명령어를 입력해서 서버에 접속하고 싶으면 home 디렉토리의 ./bashrc(혹은 ./zshrc)같은 파일을 아래와 같이 편집하면 된다.
웹이 어떻게 작동하는지, HTTP란 무엇인지 알아보기 위해 HTTP 완벽 가이드란 책을 읽기 시작했다. 한 달 안에 무조건 끝내는 것을 목표로 시작한다!
1장 : HTTP 개관
웹의 구성요소들을 알아보고, 간단한 예제를 통해 작동방식을 파악한다.
1. HTTP란?
우리는 인터넷을 사용하며 HTTP 혹은 HTTPS라는 단어를 수도없이 봐왔다. 이 단어들은 도대체 무슨 의미를 가진 것일까? HTTP는 Hypertext Transfer Protocol의 약자이다. HTTP는 인터넷에서 대부분의 사람들이 사용하는 통신 규칙이며, 이 규칙을 바탕으로 작성하여 메시지를 전달/수신하면 세계 어디서나 통신이 가능하다! 모스부호를 사용할 때 지켜야 하는 규칙이 있듯이, 인터넷 통신을 하는데 사용되는 통신 규칙이라고 생각하면 된다.
2. 웹 클라이언트와 서버
인터넷을 사용하는 구성원은 크게 클라이언트와 서버로 나눌 수 있다. 클라이언트는 서버에 특정 작업을 요청(Request)하는 주체이고, 서버는 클라이언트로부터 받은 요청에 대한 응답(Response)를 Return하는 주체이다. 간단한 예시로는 웹 브라우저(크롬, 익스플로러)와 웹 서버(네이버의 서버)의 관계를 생각하면 된다.
3. 리소스
: 서버가 관리하는 모든 요소들을 지칭한다. 여기엔 text, image, video 등이 있는데, 이들을 구분하기 위해 미디어 타입을 정하고 URI라는 식별자를 붙인다.
1) MIME(Multipurpose Internet Mail Extensions) : 모든 객체 데이터에 MIME 타입을 붙여서 구분한다.
2) URI(Uniform Resource Identifier) : 리소스를 지칭하기 위한 식별자이다. URL과 URN이 있다. 대중적으로 쓰이는 것은 URL이다.
HTTP 통신은 Request와 Response로 구성된다. 클라이언트가 서버에게 요청(Request)을 보내고, 서버에서는 이 요청을 받고 응답(Response)을 보내준다.
1) Request : 클라이언트에서 서버로 보내는 요청. 요청 목적에 따라 Method Type을 지정해줘야 한다. Method의 종류는 GET, PUT, DELETE, POST, HEAD 등이 있다.
2) Response
a. 상태 코드 : 서버가 받은 Request를 정상적으로 처리할 수 있는지 여부를 Return한다. 처리할 수 없는 경우(ex : 찾고자 하는 리소스를 서버가 가지고 있지 않은 경우)에는 실패를 나타내는 상태 코드를 Return한다.
5. 메시지
요청(Request), 응답(Response)은 모두 메시지이며, Start Line, Header, Body로 이루어진다.
6. TCP 커넥션
HTTP는 어플리케이션 계층이고, 전송 계층(TCP)와 네트워크 계층(IP)를 통과해온 데이터를 해석한다. TCP 커넥션을 맺기 위해서는 IP 주소와 포트 번호를 알아야 하고, 이 정보는 URL에 포함되어있다.
( 이 아래부터는 간략한 내용만 들어있어, 추후 더 자세히 포스팅할 예정이다.)
7. 프락시
클라이언트와 서버 사이에 위치하여, 클라이언트의 모든 HTTP 요청을 받아 수정이 필요한 경우 수정하여 서버에 전달한다. 보안을 위해 주로 사용되며, 추후 자세히 다룬다.
8. 캐시
자신을 거쳐 가는 문서들 중 자주 찾는 것들은 클라이언트쪽에 저장해두고 필요할 때 불러오는 것이 훨씬 통신 속도를 빠르게 한다. 이렇게 자주 쓰는 리소스들을 가까이에 저장해두는 행위를 캐싱이라고 한다. 웹 캐시와 캐시 프락시는 이런 캐싱을 해주는 프락시 서버라고 한다.
9. 게이트웨이
서버들의 중개자 역할을 하는 특별한 서버이다.
10. 터널
Raw 데이터를 두 커넥션 사이에서 그대로 전송해주기 위해 사용된다.
11. 에이전트
사용자를 위해 HTTP 요청을 만들어주는 클라이언트 프로그램. 웹 브라우저 등을 지칭한다.
[ 1장 요약 ]
웹에는 클라이언트, 서버라는 구성원들이 있다. 통신을 위하여 클라이언트에서 서버로 요청(Request) 메세지를 보내고, 서버는 클라이언트가 요청한 작업을 수행한 결과를 응답(Response)메시지에 담아 클라이언트로 전송한다. HTTP는 이런 웹 통신이 진행되기 위하여 정해진 통신 규약 중 하나이다!
Telnet을 사용하면, 아래와 같은 Request 메시지 요청을 보내고 받는 과정을 직접 해볼 수 있다.
telnet google.com 80 이라는 명령어는 telnet을 사용하여 google.com의 80 포트에 접속하라는 의미이다. 요청 명령어, 응답 메시지를 확인해볼 수 있다.
141개의 Test들을 통과하고 드디어 Pintos의 마지막 관문인 File System에 도착했다.
다음과 같은 4개의 과제가 우릴 마주한다. 또 다시 '도대체 뭐하라는거지?' 라는 생각이 든다.
간략한 과제 내용은 아래와 같다.
0. FAT File System : 과제마다 다를 수 있지만, 우리는 FAT 방식으로 File System을 구현하라는 과제를 받았다. 실제 리눅스 등에서는 Multi Level Indexing으로 구현되어있다고 한다. (FAT 방식이 훨씬 쉽다고 한다.)
1. Extensible files : 현재 핀토스의 모든 파일들은 기존 할당된 크기에서 유동적으로 파일 크기를 키울 수 없다. 기존 할당된 크기보다 더 쓰더라도 유동적으로 파일의 크기가 늘어나도록 변경하라. + System Call
2. Subdirectories : 현재 핀토스는 무조건 루트 경로에서 모든 일을 수행한다. 루트의 하위 경로들도 만들 수 있도록 변경하고, 바로가기(Soft Link)를 구현하라. + System Call
3. Buffer cache : 현재 핀토스에서는 Disk에서 읽은 데이터를 물리메모리에서 제거하는 경우 Swap Disk로 보내거나 Disk에 바로 써버린다. 이런 경우 접근하려고 할 때 다시 disk_read를 해야하므로, 시간이 오래 걸린다. 따라서 자주 쓸 것 같은 데이터는 물리 메모리에 Cache를 만들어 놓고 여기다 넣는다.
4. Remaining miscellaneous items : Extra
수정 파일 : filesys/filesys.c, filesys/fat.c, filesys/file.c, filesys/inode.c, userprog/syscall.c
Project 4 - 개념
1. FAT
컴퓨터는 아래와 같은 하드웨어 구조를 가지고 있다. 아래 있는 계층은 바로 위의 계층의 캐시 역할을 한다.
이번 프로젝트를 통해 다룰 메모리 공간은 맨 아래에 있는 Disk Drive(SSD 포함)이다. Disk 공간은 아래와 같이 512Byte의 Sector 단위로 나눠져 있다. (자세한 내용은 disk.c 참고) 기존 Pintos에서는 free map을 활용하여 disk를 연속적인 sector 단위로 관리한다. 예를 들면, 1024byte의 데이터를 쓴다고 하면 반드시 sector 0, 1, 2, 3에 쓰는 방식이다. 이런 식으로 관리를 하면 아래 그림과 같이 외부 단편화(External Fragmentation)가 발생한다. 공간은 3개 있지만 3개짜리 파일이 들어갈 공간이 없는 것이다.
이런 외부 단편화의 문제를 해결하기 위해, FAT(File Allocation Table)를 활용한다. FAT 방식은 빈 Sector들을 찾아 데이터를 기록한 뒤, 파일들이 연결된 정보를 File Allocation Table에 기록해놓는다. 아래의 그림을 보면, 3개의 빈 Sector가 있는데 파일 크기가 3인 파일을 기록할 수 없었던 기존 방식과는 달리 3개의 빈 Sector가 있다면 File D를 기록할 수 있다.
FAT 방식은 File Allocation Table이라는 표를 만들어서, 파일이 기록된 섹터들의 정보를 Chain 형태로 저장해놓은 것이다. 아래의 File D가 저장된 공간을 보면 4 - 9 - 10번 Sector에 순서대로 저장되어 있다. 이 정보를 FAT에 기록된 형태를 보면, FAT[4] = 9, FAT[9] = 10, FAT[10] = -1이 기록되어 있다. 4번 섹터의 다음 섹터는 9번 섹터이고, 9번 섹터의 다음 섹터는 10번 섹터이며, 10번 섹터가 해당 파일의 마지막 섹터라는 정보를 나타낸 것이다. (마지막 섹터에는 -1 혹은 구분할 수 있는 값을 넣어놓는다.)
구현할 때 생각해야 할 점은 FAT 자체도 disk에 저장되어야 한다는 점이고, 이 부분은 침범되어서는 안된다는 것이다. 그래야 컴퓨터를 끄고 킬 때도 파일에 대한 정보가 남아있을 것이다.
지금은 FAT의 기본 단위(Cluster)가 1 sector와 같다고 가정했지만, 임의의 갯수의 sector를 하나의 cluster로 묶어서 관리하는 것도 가능하다.
2. Inode
Inode란 파일이나 디렉토리에 대한 metadata를 가지고 있는 고유 식별자이다. 파일과 디렉토리는 모두 inode를 하나씩 가리키는 inode 포인터를 가지고 있다. inode 구조체는 파일이나 디렉토리를 열 때 발생하는 inode_open() 함수 실행 시에 생성되며, 열리지 않았을 때는 inode_disk인 상태로 Disk에 저장되어 있다. inode는 메타데이터 정보를 담고있는 512Byte의 inode_disk를 하나씩 가지고 있고, inode_disk는 실제 파일에 대한 메타데이터를 포함하고 있다. 실제 파일의 경우 아래와 같이 디스크에 저장되어있다.
* Metadata : 속성을 설명하는 정보
ex : 글의 길이, offset ...
이제 inode 구조체의 원소들을 하나씩 살펴보자.
Inode
1. elem : inode를 생성하면 open_inodes라는 list에 추가해주기 위해 필요한 요소.
2. sector : inode_disk가 저장되어있는 disk의 sector를 나타낸다.
3. open_cnt : inode가 열려있으면 닫으면 안된다. 이를 관리해주기 위해 변수를 생성하여 카운팅한다.
4. removed : 삭제해도 되는지 여부를 저장한다. inode_remove()를 참조.
5. data : 디스크에 저장된 메타데이터 정보를 물리메모리에 올려놓은 것이다. 매번 disk에 참조할 수 없기 때문에 물리 메모리에 올려놓고 사용하며, 더이상 필요가 없어지면 inode_close()시에 다시 disk에 write back한다.
Inode Disk
1. start : 파일의 inode인 경우 파일의 실제 내용, 디렉토리의 inode인 경우 directory entry들이 저장되어 있는 disk의 sector 번호를 나타낸다.
2. length : 저장된 공간의 길이를 나타낸다(Sector 단위)
+ : 나머지 공간은 sector size인 512byte를 맞춰주기 위해 넣어둔 데이터이다. (Disk Write/Read 시에는 반드시 512byte 단위로 해야한다. 이 공간을 잘 활용할 수 있으면 좋다.
3. File
File Open을 하면 생성되는 파일 구조체이다. 코드 상의 inode는 File의 inode를 가리키고 있으며, 이 inode 안에는 File Data에 대한 Metadata가 저장되어있다(inode_disk). 하나하나 살펴보자.
1. inode : 파일 데이터에 대한 정보를 포함하고 있다.
2. pos : 파일을 읽거나 쓸 때 처음부터 다 읽거나 쓸 필요는 없다.
3. deny_write : 읽기 전용 파일을 나타내기 위해 사용하는 변수.
4. Directory
디렉토리도 파일이다. 자세히 보면 구조체 내에 inode가 동일하게 위치하고 있는 것도 볼 수 있다. 다만 File에 Data가 있었다면 Directory에는 directory_entry들이 있을 뿐이다. 기억해야 할 것은 directory를 조회하기 위해 dir 구조체를 따라 들어가면 inode가 있고, inode 안의 inode_disk에 기록된 sector를 따라가보면 dir_entry들이 기록되어있는 것이다. 내가 원하는 이름을 가진 dir_entry를 찾고, 이녀석이 가리키는 sector로 다시 가면 내가 원하는 데이터가 있을 것이다.
Directory, Directory_entry 구조체에 대해 알아보자.
Dir
1. inode : 하위 dir_entry들을 저장하고 있는 sector를 찾아가기 위해 이용한다.
2. pos : 어디까지 읽었는지 확인한다.(readdir()구현 시 사용)
Dir Entry
1. inode_sector : dir_entry의 정보를 담고있는 sector를 가리킨다.
2. name : 파일이나 디렉토리의 이름이다.
3. in_use : lookup 할 때 사용할 정보이다. 이 위치에 dir_entry가 저장되어있는지에 대한 정보를 나타낸다.
Project 4 - 구현
0. FAT
1) fat.c에 기본적인 내용(boot 시 fat를 load하고 종료 시 fat를 write back하는 기능)은 구현되어있다.
2) 우리가 해야할 일은 fat 테이블을 업데이트하고, 컴퓨터를 끄고 키더라도 동일한 위치에 저장되어있도록 보장하는 것이다.
3) Root Directory는 format할 때 만들어줘야 한다.
4) Cluster to sector 함수를 잘 생각하고 만들어야 한다. fat table도 disk에 저장되어야 한다는 점을 꼭 기억하자. 이부분을 아예 없다고 생각하고 Cluster to sector을 만들 것인지, 아니면 있다고 생각하되 데이터가 이미 기록되어있음을 File Allocation Table에 기록할 것인지를 선택해야한다. Sector가 들어가야 하는 위치에 Cluster가 인자로 들어가거나, 반대로 된 경우가 없는지 반드시 체크하자.
1. Extensible Files
1) FAT를 구현했다면 이건 쉽다. inode_create이나 Write/Read시에 내가 잘 만들어놓은 Chain을 따라가게 하면 된다. 만약 File length를 늘린다고 하면, 새로운 chain을 하나 추가하여 기록한다.
2) File length가 늘어난다고 하면 inode_disk에 이 data를 업데이트해줘야 하며, sector_size와 file_length는 다르다는 점을 인지하자.
3) inode_disk는 data의 길이에 포함되지 않는다.
2. Subdirectories
1) 입력을 받은 뒤 parsing하여 효율적으로 인자를 전달하는 것이 생각보다 까다롭다. 예외처리와의 싸움일 것이다. 인자가 비어있거나, 존재하지 않거나, 지우면 안되거나 등등을 고려해야 한다.
2) .과 ..은 기본적으로 directory에 추가해주는 것이 좋다.
3) 파일을 열었다면, 반드시 잘 닫아줘야 한다. open_cnt 때문인데, 일반적으로 open_cnt가 0일 때 inode의 사용이 끝났음을 인지하고 disk에 write back해주기 때문이다. 그렇다면 open_cnt가 언제 증가하고 언제 감소하는지에 대해 이해하고 있어야 한다. inode_open(dir_open이 아님)이나 reopen시에 증가하고, inode_close 시에 감소한다. inode_open함수는 어디서 사용하는지 확인해보자.
4) directory인지, file인지 확인이 필요할 때가 있다. Syscall마다 이를 구분할 필요가 있는 경우에는 처리해준다.
5) directory도 open할 수 있다. open된 directory는 제거하면 안된다.
3. Persistence
1) 위의 과정을 제대로 했다면 종료 후 다시 Booting을 하더라도 데이터가 잘 기록되어있어야 한다.
2) 위에서 말했던 open_cnt를 잘 고려하지 않았거나, root directory를 boot 시마다 갱신해주는 것은 아닌지 확인해보자
Project 4 - 후기
드디어 192개의 모든 Test를 안정적으로 통과하는 것을 확인했다. 길고 길었던 Pintos, 잠도 잘 못자는 경우가 다반사였지만, 많은 것을 느낄 수 있었던 기간이었다. Linux에 대한 기본적인 이해도 할 수 있었고, 아예 모르는 것에 대한 두려움을 많이 줄일 수 있었다. Pintos를 처음 시작하는 사람이라면, 처음에 진짜 아무것도 몰라서 막막하더라도 조금씩 이해하다보면 끝낼 수 있다고 말해주고 싶다.
100개 가까운 테스트를 통과하고 Project3 - Virtual Memory에 도달하여 매우 기쁘지만, 아래와 같은 문구가 Project 3에서 우릴 기다리고 있다. 이제까지 제대로 만들었길 기도하자. (이번에도 도대체 뭐하라는거야 가 기다리고 있으니 너무 기대하지 말자.)
"You should take care to fix any bugs in your project 2 submission before you start work on project 3, because those bugs will most likely cause the same problems in project 3."
간략한 과제 내용은 아래와 같다.
0. 프로그램을 실행하려면, 실행에 필요한 데이터(Ex : Code)를 물리메모리(RAM)에 올려야 한다. 지금은 실행 전에 load(), load_segment()라는 함수에서 실행에 필요한 모든 데이터를 물리메모리에 올려버리고 있다. 이 방식은 매우 비효율적이므로, 모든 데이터를 다 올리는 대신에 실행 중에 해당 데이터가 필요하게 되면 그 때 물리메모리에 올리는 방식으로 변경하자.(Lazy Load)
1. 현재 스택은 한개의 Page만 할당되어 있고, 한 Page 이상의 데이터를 저장하는 경우는 고려되지 않았다. 한 Page를 넘는 데이터를 저장하더라도 유동적으로 늘릴 수 있도록 변경하라.(Stack Growth)
2. 프로그램을 많이 실행하거나, 많은 데이터를 저장하다보면 물리메모리가 가득 차서 무언가를 빼내야 하는 상황이 발생한다. 이를 고려하여 임시로 저장하는 공간인 Swap Disk를 만들고 빼낸 데이터는 잠시 이 곳에 넣어두기로 한다. Swap Disk는 갈 곳이 없는 것들만 넣어두는 것이고, File에서 불러온 데이터는 다시 File에 쓰면 된다.
Project 3 - 개념
Project 3을 진행하기 위해서는 아래의 내용들을 이해해야 한다.
우선 전체적인 그림을 한번 알아보자.
Pintos 내에서 생성되는 모든 Thread는 각자 독립된 가상주소공간(0 ~ KERN_BASE)을 가진다. KERN_BASE가 0x8004000000이므로, 각 프로세스는 550Giga Byte의 주소공간을 표현할 수 있다.(하지만 실제로 사용되는 공간은 매우 작다.) 각자의 Thread가 KERN_BASE 이하의 특정 주소의 데이터를 읽으려고 하면, Thread에 저장되어있는 Page Table에서 이 주소를 실제 물리 주소로 변경한 뒤 실제 물리주소에서 데이터를 읽어오게 된다.
0) Virtual Address
위에서 말한 가상주소공간은 Thread별로 할당된 것이며, 각각의 Thread는 이 가상주소공간만큼의 크기를 모두 쓸 수 있을 것만 같은 착각을 가진다. 하지만 사용자가 0x400000에 data를 Write하라고 명령을 내리더라도, Thread는 이 주소를 실제 물리주소로 변환한 뒤에 그곳에 Write한다. 이렇게 함으로써 OS는 사용자가 만든 Thread가 실수를 하더라도 다른 Thread의 공간을 침범하는 것을 막을 수 있다.
1) Page
가상 공간의 Data에 대한 정보를 저장하고 있는 구조체이다. 모든 물리메모리공간은 Page(1024Bytes)단위로 관리된다. Page 내에는 어떤 인자들이 있는지 확인해보자.
1. operations
Page는 anon, uninit, file이라는 3가지 Type이 존재한다. 이유는 Stack이나 Code, 등 데이터의 종류에 따라 다른 방식으로 처리해줘야하기 때문이다. 아래와 같이 type별로 swap_in, swap_out, destroy 시 실행해야 하는 함수를 별도로 저장해두고 실행한다.
* Swap in : 해당 Page를 물리 메모리(RAM)에 Load하는 행위
* Swap Out : 해당 Page를 물리 메모리에서 제거하는 행위. 돌아갈 곳이 없는 Page는 Swap Disk에, Disk에 다시 써도 되는 녀석들은 Disk에 Write하는 행위를 해줄 것이다.
* Destroy : 해당 Page를 제거하는 행위
2. va : 데이터가 저장된 가상주소의 시작점이다.
3. frame : page와 matching된 frame을 가리킨다.
2) Frame
: 물리공간에 대한 정보를 가지고 있는 구조체이다. Page Table에는 Page의 va : Frame의 kva가 매칭되어 있다.
1. kva : 실제 물리주소이다. (실제 저장되는 물리주소는 (kva - KERN_BASE)이긴 하다.)
3) Page Table
모든 Thread는 각각pml4라는 이름의Page Table을 가지고 있다. (thread_create()함수의 pml4_create() 참고) Page Table에는 va : kva로 mapping이 되어있기 때문에, 가상주소에서 물리주소로의 번역이 가능하다. Mapping 정보를 확인하기 위해 va를 가지고 Page Table을 찾았는데, 매칭되는 kva가 없다면 Page Fault가 발생한다.
5) Page Fault
사용자가 원하는 임의의 가상 주소에 접근하려고 했을 때, thread는 해당 주소가 포함된 Page의 시작 주소(va)를 찾은 뒤(=pg_round_down(va)), 이것에 매칭된 물리주소(kva)가 있는지 Page Table에서 찾는다. 만약 matching 된 정보가 없다면 Page Fault를 발생시킨다. Page Fault Handler에서 Page Fault에 대한 처리를 하면, 해당 가상 주소는 이제 접근이 가능하게 된다. 현재는 Page Fault Handler에서 아무런 조치를 하지 않는다. 이런 경우 외에도, 읽기 전용인 페이지에 Write를 하려고 해도 Page Fault가 발생한다.
Page Table에 va : kva 매핑하는 작업은 install_page(), 매핑된 정보를 제거하는 작업은 clear_page()를 참고하자.
6) Bitmap
메모리공간의 사용가능여부를 나타내는 Bit들의 집합이다. 1이면 사용중, 0이면 비어있음을 나타내도록 사용할 수 있다. bitmap.c 파일에 자세히 나와있다.
7) MMAP
사용자가 명시적으로 파일의 내용을 물리메모리에 올리도록 요청하는 System Call이다. 사용자가 요청하는 바는 디스크에 있는 파일의 데이터를 물리메모리에 올리라는 것이나, 당장 사용하지 않을 데이터를 모두 한정된 물리메모리에 올려놓는 것은 비효율적이기 때문에 load_segment와 마찬가지로 페이지 정보만 등록해놓고 필요할 때 물리메모리에 Load하기로 한다.
8)Supplemental Page Table
Lazy Load를 구현하려면, Page에 대한 정보(어디서 가져와야 하는 데이터인지, 어떤 데이터인지..)를 어디엔가 등록해놓은 뒤 Page Fault가 발생하면 이 정보를 찾아 메모리에 Load해야 한다. 따라서 Page에 대한 정보를 저장해놓을 공간이 필요한데, 이게 SPT다. SPT에서 Page에 대한 정보를 찾는 시간을 최소화하기 위해 Hash Table을 사용한다.
9) Swap Table
위에서 설명했듯이, 물리메모리가 가득찼을 때 기존에 있던 Page들 중 하나를 밖으로 빼내고 새로운 Page를 넣어야 한다. 새로 물리 메모리에 Load되는 Page는 Swap In 된다고 하고, 기존에 물리메모리에 올려져 있었으나 꺼내지는 Page는 Swap Out 된다고 부른다.
위에서 살펴봤듯이, Page의 종류는 3가지가 있다. Uninit, Anon, File이다. Uninit Type은 초기화되지 않은 Page로 Page 정보는 생성되었으나 사용자가 해당 Page에 접근하지 않았다는 것을 의미한다. 따라서 물리메모리에 올라가있는 페이지가 Uninit일수는 없다. File Type은 mmap된 Page이다. File Type은 Swap In될 때 disk에서 직접 읽어오면 되고, Swap Out될 때는 직접 Disk에 다시 쓰면 된다. Anon Type은 Stack, Text 등을 포함한다. Anon Type은 Swap Out될 때 디스크에 다시 돌아갈 곳도 없고, 무작정 제거하면 다음에 접근할 수 없다. 따라서 물리 Disk에 Swap Disk란 공간을 별도로 할당해서 이곳에서 Swap In/Out되는 Anon Type Page들을 관리한다.
Swap Table은 Swap Disk의 할당 정보를 포함하고 있는 Table이라고 생각하면 된다. bitmap을 사용하여 Swap Table을 구현할 수 있다.
* 교체 Policy
물리메모리가 가득 차서 현재 Load된 Page들 중 하나를 빼낼 때 어떤 녀석을 빼낼 것인가에 대한 정책이다. FIFO도 가능하고, LRU 등 다양한 교체 알고리즘이 있다. Test Case들은 FIFO 방식으로 구현해도 시간은 충분했다. (컴퓨터 환경에 따라 조금씩 다를 수 있다.)
* Accessed and dirty bit
File Type Page가 Swap Out되는 경우를 생각해보자. 만약 데이터를 사용자가 읽기만 하고 변경하지 않았다면, 굳이 disk에 다시 써줄 필요가 없다. 고맙게도 CPU는 사용자가 특정 Page를 수정했다면 dirty bit를 1로 바꿔주는데, 이를 확인한 뒤 Disk Write back을 할지 말지 결정한다.
* Copy On Write
기본적으로 fork 구현 시 frame을 모두 새로 할당하여 복사해주었을 것이다. 이런 경우도 마찬가지로 비효율을 초래할 수 있다. 따라서 fork할 때 자식은 부모가 할당한 물리 메모리 공간을 가리키게 하되, writable을 0으로 해준다. 읽는 것은 가능하지만, 무언가 쓰려고 하면 Page Fault가 발생할 것이고 이 때 새로 물리메모리 공간을 할당해서 복사를 진행한다. writable을 0으로 모두 할당할 것이지만, 기존에 존재하던 Page의 writable여부도 반드시 저장해서 새로 물리공간을 할당할 때 update해줘야 한다는 것을 잊지 말자.
Project 3 - 구현
전체적인 그림을 한번 잡고 시작할 수 있다면 더 좋을 것 같다.(가능할진 모르겠지만) 위의 내용들을 이해했고 무엇을 해야할지 파악했다면, 구현하는건 조금이나마 더 수월할 것이다. 제대로 된 데이터가 Load되는지, Swap In/Out 된 데이터가 일치하는지 여부를 hex_dump()함수를 활용하여 직접 확인해보는 것을 추천한다.
(실제 구현은 root 여부를 확인하기 위해 Tree 구조체도 같이 전달하는 방식으로 구현했다. 특정 key를 삭제했을 때 root가 사라지는지 확인하는 과정이 꼭 필요하다.)
key X를 삭제하는 과정은 Tree의 root Node로부터 시작해서 X가 들어있는 노드를 찾는 것으로 시작한다. 삭제하는데 발생가능한 경우는 아래와 같이 크게 세 가지로 나눠볼 수 있다.
1. N이 Leaf Node인 경우
→ Node N의 key들에 대하여 for문을 돌며 확인한 뒤, X가 존재하면 삭제한 뒤 True를 return, 없다면 False를 return한다.
2. Node N 안에 key X가 있는 경우
a) key X의 선행 자식 Node Y가 최소 t개의 키를 가진다면, X의 선행키(Predecessor) K를 X와 바꾼 뒤, K를 삭제한다. 이후 아래 노드로 내려가며 X를 삭제한다.
ex) 아래 그림에서 key 16을 지우려는 경우이다.
1. 16의 선행자식 Node Y는 3개의 Key를 가지고 있으므로 t(2)개 이상을 만족한다. 따라서 선행키인 15와 교환한 다.
2. key X(16)를 지우러 내려간다.
b) key X의 후행 자식 Node Z가 최소 t개의 키를 가진다면, X의 후행키(Successor) K'과 X를 바꾼 뒤, 아래 노드로 내려가며 X를 삭제한다.
c) key X의 선행 자식 Node Y와, 후행 자식 Node Z 모두 t-1개의 자식을 가진다면, Node Y와 Z를 합치고(merge) X를 삭제한다.
선행키와 후행키란 ?
아래 그림의 Tree에서 key = 12를 삭제하려고 한다. 선행키와 후행키는 어떤 값인가?
* 선행키(Predecessor) : 특정 Key의 왼쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 오른쪽에 있는 값 = 11
* 후행키(Successor) : 특정 Key의 오른쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 왼쪽에 있는 값 = 13
3. Node N 안에 key X가 없는 경우
계속 X를 찾아 들어가야 하므로, 다음 살펴볼 Node C를 정한다. (Node N의 key 값을 기준으로 비교한 뒤 정한다.) 해당 Child Node가 t-1개의 자식을 가진 경우, 아래와 같은 두가지 경우가 있을 수 있다.
a) Node C 양 옆의 Node 중 t개 이상의 key를 가진 Node가 있는 경우
→ 하나의 key를 해당 Node에서 빌려온 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C))
(Node C의 key 개수는 2t-2개가 된다.)
b) Node C 양 옆의 Node들이 모두 t-1개의 자식을 가진 경우
→ 양 옆 중 하나의 Node와 병합한 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C)) 이 때, 두 Node를 가리키는 Child Pointer들 사이에 있는 key는 병합된 Node C로 같이 내려온다. (Node C의 key 개수는 2t-1개가 된다.)
※ 참고할 사항 ※
* 여기서도 삽입할 때 Split을 해주며 찾아내려간 것과 마찬가지로, 만약 Node N이 t-1개의 자식을 갖고있다면 옆의 Node와 Merge를 하거나 옆 Node에서 Key를 빌려서 충분한 key의 개수를 충족시킨 후 내려간다.
: 여기서부터 조금 복잡하다. 키를 루트에 삽입할 때 사용하는 함수는 insert(), insertNonfull(), split()이다. 우리가 깊이 고민해야되는 부분은 '임의의 노드가 이미 키를 2t-1개 가지고 있을 때, 어떻게 삽입해줘야 하는가' 이다. 우선 간단한 예시를 살펴보자.
아래 그림과 같이 최대차수가 4(최소차수 t = 2)인 트리의 루트에 키가 3개 들어있다. 새로운 키 1개(3)가 더 들어가면 어떻게 될지 살펴보자.
1. 키 삽입 시도
노드 한개에 들어갈 수 있는 키는 최대 3개이다.
2. 새로운 노드 생성 후 루트 노드로 지정
: 새로운 노드 s를 만들어 tree의 root로 지정하고, 기존 노드 r을 가리키게 한다.(삽입하려는 노드가 root가 아닌 경우에는 실행하지 않는다.) r의 isLeaf속성은 True로 바뀌어야 한다.
3. 기존 노드 Split
1. r의 가운데 key를 노드 s로 올려준다.
2. 새로운 노드 z를 만들고, r의 가운데 key 기준 우측 key값(t+1번째부터 2t-1번째까지)들을 모두 z로 옮긴다.
3. Split하려는 노드가 Leaf 노드가 아니어서 Child Pointer들을 가지고 있는 경우, r의 Child Pointer도 노드 z로 옮겨줘야 한다.
4. 각 노드들의 key 개수(key_num)을 업데이트한다.
4. 삽입 완료
: Split이 완료되면 기존 노드(r)와, 새로 생긴 2개의 노드(s,z)는 모두 t-1개의 키를 갖는다. 모든 노드들이 새로운 키값을 넣을 공간이 있으므로, 새로운 키(3)을 알맞은 위치에 넣어준다.
※ 참고할 사항 ※
1. 삽입하는 과정에서, 새로운 키는 항상 Leaf Node에 추가해야한다.
2. 트리는 항상 기존 존재하던 노드 기준으로 위(Upward)로 자란다.
3. root 노드인 경우는 별도의 작업으로 처리해줘야하기 때문에 insert()함수가 존재하고, root가 아닌 노드인 경우에는 insertNonfull()에서 처리한다.
4. 키를 삽입할 때 들어가야 할 자리(Leaf Node)를 찾기 위해 노드들을 탐색하며 내려가게 되는데, Leaf Node가 아니더라도 내려가는 과정의 모든 Node에 대해서 키의 개수가 2t-1개(최대)이면 split을 해줘야 한다. 이는 Leaf Node가 가득차서 Split을 할 경우에 다시 위로 올라가서 연산하는 것을 방지하기 위함이다.
5. 가득 찬 경우에는 split()을 하지만, 가득차지 않은 경우에는 split()을 진행하지 않는다.
Project 1에서는 Kernel 영역에서 쓰레드들을 생성하고 Scheduling을 제대로 수행하도록 만들었다. Project2에서는 사용자의 입력을 받아 원하는 작업을 수행할 수 있는 기능을 구현하고, 사용자의 명령을 Kernel 영역에서 실행해줄 System Call들을 만든다. 프로젝트를 완료하면, PINTOS에서 특정 파일을 실행시켜 원하는 결과를 얻을 수 있다.
* 이번 프로젝트는 System Call들을 구현하기 전까지 제대로 구현했는지 테스트를 통해 알아보기 힘들기 때문에, hex_dump()등의 함수를 잘 활용하자.
목표 : User의 입력을 받는 기능을 구현하고, User가 의도한 결과를 return하기 위해 Kernel 영역에서 수행되는 System Call들을 만든다.
Project 2 - 기본 내용
1. User Mode / Kernel Mode + User Stack
프로세스/쓰레드는 User Mode와 Kernel Mode를 왔다갔다하며 수행한다. User Mode는 사용자가 사용을 하는 영역, Kernel Mode는 사용자의 입력을 받아 Kernel 단에서 수행을 해주는 영역이다. User Mode에서 사용자가 입력을 하면 해당 입력 내용이 User Stack에 저장되고, Kernel Mode에서 입력 내용을 꺼내어 원하는 작업을 수행하게 된다. User Mode에서 사용자의 입력을 User Stack에 저장하는 작업을 여기선 Argument Stack이라고 부른다.
2. System Call
사용자(User)가 시스템의 Hardware 또는 관리가 필요한 기능들을 사용하고자 할 때 호출하는 함수이다. User Mode에서 System Call을 호출하면, Kernel Mode로 전환하여 해당 내용을 수행하게 된다. Pintos에서 작용하는 방식을 간단히 살펴보자.
사용자가 특정 파일을 열고자 open()이라는 함수를 호출한다. User Mode에서 해당 함수를 호출하면, lib/user 폴더에 있는 syscall.c에서 open()이라는 System Call이 실행되고, 이 함수는 현재 레지스터 상태들을 저장(User Mode 상태 저장)한 뒤 Kernel mode에서 userprog/syscall.c에 있는 open 함수를 수행한다. (초기에는 정의되어있지 않으므로 구현이 필요하다.) 해당 System Call을 수행한 결과값은 intr_frame의 rax에 저장되어 User Mode로 복귀하게 된다.
프로젝트 진행
1. User의 입력을 받는 기능을 구현한다.
argument_stack() 함수를 구현한다. 들어온 데이터를 parsing하여 word-align되도록 데이터를 자른 뒤, User Stack에 차곡차곡 쌓는다. 다 쌓고난 뒤 데이터 시작 위치를 rsi에, argument 개수를 rdi에 넣어주면 된다.
2. System Call들을 구현한다.
앞의 내용들을 다 구현하고 System Call을 구현하는 시점에 도달하면 이제 Test case들을 수행해볼 수 있어 한결 낫다. syscall_handler에서 switch문으로 어떤 System call을 수행해야하는지 구분해놓고, 각 system call 함수들을 구현하면 된다. 구현 시 어려운 함수는 fork(), wait(), exit()이었던 것 같다. fork()는 함수 실행 시 분기 흐름을 파악하기 어려웠고, wait(), exit()은 종료 시점을 판단하는 것과 종료 시 memory free하는 것이 어려웠다.
이번 프로젝트는 System Call을 완성하기 전까지 제대로 구현되었는지 확인할 수 없다는 점, 핀토스 내부 작동 방식을 파악해야한다는 점이 힘들었다.
