지금 열심히 읽고 있는 책은 '객체지향의 사실과 오해' 와 'Akka 코딩 공작소' 이다. 앞의 책은 1~2장의 내용으로 글을 올렸고 이후에 계속 읽고 있는데, 포인트가 조금씩 다르고 깊이가 다르긴 하지만 전체적인 맥락에선 '역할, 책임, 협력' 을 그대로 가지고 가고 있어 글을 정리해 쓰기 어려운 것 같다. Akka 코딩 공작소 는 Scala 기반으로 비동기로 동작하는 액터모델인 Akka 에 대해 다루는데, 흥미로운 내용이고 조금씩 배워가고 있지만 처음 접하는 내용이다보니 잘 이해되지 않아도 일단 넘어가는 것이 많아 또 정리하기 어려운 것 같다.

어쩌면 공부하는 속도를 조절하고 시간이 조금 걸리더라도 정리하는걸 열심히 할 필요가 있을 것 같기도 하다. 확실히 다시 생각해보며 정리할 수 있고 놓친 부분이 있다면 더 깊게 파볼 수도 있다. 깊이 공부할때 또 깨달아지는 맛이 좋기도 하다. 하지만 이제 처음 접하는 것들에 대해 맛을 보고 있는 상황에서 깊이 하려다간 오히려 지치지 않을까 하는 생각이 더 크다. 정글에서 했었던 것처럼 처음엔 이런 내용들에 대해 인덱싱한다는 생각으로 읽고, 그 후에 필요에 따라서 고민하고 찾아보며 공부할 때 더 재미있게 할 수 있었던 것 같다.

그래서 일단은,,, 정리하면서 글을 썼던 것은 멈추고, 매일 공부한 부분에 대해 정말 간단한 일지 정도만 남겨보려 한다. 더불어 몸의 균형, 체력, 그리고 근육을 좀 만들고 싶어서 헬스 pt를 시작했다. 이것도 운동하는 날마다 어떤 운동했는지 일지를 남겨봐야겠다.

간단 정리

결론부터 요약하면 implicit 은 암시적으로 형 변환을 가능하게 해준다. 예를 들면 Int 형의 파라미터를 받는 함수에 Double 형의 데이터를 넣는 경우 다른 언어에서는 type 에러가 발생한다. 하지만 scala 에서 implicit 을 사용하면 자동으로 형 변환이 되도록 만들 수 있다. Scala 컴파일러는 타입에러가 발생하는 경우 바로 포기하는 것이 아니라 암시적 변환을 할 수 있는 함수나 클래스 등이 스코프 내에 있는지 찾아보고, 가능한 경우 형변환을 하여 에러발생 없이 코드가 진행되도록 한다.

이러한 암시는 아래와 같은 세가지 경우에 쓰인다.

• 예를 든 것과 같이 예상되는 type이 있는 경우 해당 type으로 변환시키는 경우이다.
• 호출 대상인 객체의 변환이다. 예를 들어 a.add() 라는 코드를 작성하였으나 a가 add 메서드를 가지고 있지 않고 있고 b가 add 메서드를 가지고 있는 경우에 a를 b로 변환시킬 수 있다면 변환시켜 메서드가 실행되게 하는 경우다. 대표적인 예시는 Map 자료구조를 사용할 때 Map(key -> val) 과 같은 방식으로 사용하는데, 이때 -> 는 scala의 문법이라기 보다는 ArrowAssoc 이라는 클래스의 한 메소드이다. 어떤 값에 대해 ArrowAssoc 으로 형변환하는 implicit 함수가 정의되어 있기에 key 는 ArrowAssoc(key) 로 형변환 되고 -> 메소드가 실행되어 key, val 쌍의 튜플 형태로 return 되고 Map 의 인자로 전달되는 것이다. -> 가 문법인 것처럼 보였듯이 implicit 을 활용하면 새로운 문법을 만드는 것과 같은 효과를 볼 수 있다.
• 함수의 파라미터로 암시를 사용하는 경우이다. 예를 들어 method(a : Int)(implicit b : User) 와 같은 메소드가 있고 스코프 내에 implicit val user : User = new User() 와 같이 선언된 객체가 있다면 method(a) 와 같이 뒷부분을 생략하고 호출하여도 user 를 자동으로 넣어준다.

암시는 코드를 좀 더 자연스럽고 가독성있게 하고 기존의 자료형들과도 자연스럽게 어우러지게 하지만 아무래도 명시적이지 않은 만큼 조심해서 사용해야 한다. 자칫 잘못하면 코드가 이해하기 어려워지거나 의도한대로 동작하지 않거나 할 수 있을 것이다.

내 생각

implicit 이 대체 뭘까 모호해서 어렵게 생각했는데 책을 읽고 공부해보니 꽤나 재미있는 부분인 것 같다. 스칼라가 유연한 언어라는 말을 봤었지만 이해되지 않았고, -> 와 같은 부분들도 왜 이렇게 만들었을까 이해가 되지 않았었는데 어떤 원리인지 알고나니 오히려 재미가 느껴졌다. C에서도 float형 변수에 int 데이터를 저장하면 자동으로 형 변환이 되었었는데 스칼라는 이런 부분을 개발자가 활용할 수 있도록 열어둔듯한 느낌도 든다.

scala 를 처음 접했을 땐 난해하게 느낀 부분이 많았는데, 점점 알아가는 재미가 있는 것 같다. 더 많이 알아가보고 싶다!

클래스는 빵틀, 객체는 붕어빵?

완전히 객체지향을 처음 접하게 될 때 누구나 듣게되는 말이 아닐까? 개발 공부를 처음 시작하고 C 를 배워 절차지향적인 프로그래밍을 하면서 객체지향이란 것도 그냥 C 에 있는 struct 같은 것을 함수랑 같이 묶어놓은 것에 불과한게 아닌가 생각했었다. 하지만 요즘 기술온보딩을 통해 OOP 를 배우고 책을 읽으면서 이런 생각들이 잘못되었음을 알아가고 있다.

온보딩에서 OOP 를 배울때 가장 기억에 남는 부분은 객체로부터 상태를 꺼내 쓰려고 하기보다는 상태를 가진 객체에게 메시지를 보내 처리하도록 해야한다는 점이었다. 이 가이드를 처음 들었을 때에는 굳이 왜 그렇게 해야할까 싶었고, 그래도 가이드가 그렇게 주어졌기에 그렇게 하려고 노력했었다.

역할, 책임 그리고 협력

이 책에서는 객체를 '역할과 책임을 바탕으로 협력하는 자율성을 가진 존재' 로 표현한다. 따라서 객체의 상태는 객체 자신만이 바꿀 수 있어야 하며 외부에서 객체에게 메시지를 보내 책임을 다하도록 요청함으로써 객체들이 협력하게 된다고 얘기한다.

C 의 struct 는 데이터를 담아두는 공간에 불과했지만 객체지향에서의 객체는 스스로 책임을 다하는 생명체와 같다. 그렇기에 객체에서 상태를 강제로 뺏어서 처리하는 것이 아니라 객체가 객체의 역할을 할 수 있도록 메시지를 보내야 했던 것이다.

중요한건 상태가 아니라 행동

이러한 객체지향의 특성을 반영한다면, 객체를 설계할 때 상태를 먼저 생각하는 것이 아니라 행동을 먼저 생각해야 한다고 한다. 클래스를 생각하고, 상태를 생각하고, 그에 맞는 행동을 생각한다면 협력을 위한 객체가 아니라 고립된 객체가 될 가능성이 높으며 재사용성이 낮은 객체가 될 수 있다. 어떤 기능을 위해 어떤 협력을 해야할지, 어떤 행동이 있어야 하며 그 행동을 할 객체가 무엇이고 행동을 하기 위해 어떤 상태가 필요한지 고민하며 접근해야 협력을 위한 객체를 설계할 수 있다.

정리

책을 읽으면서 다양한 부분들을 생각했는데 정리하려니 역시 정리가 잘 안된다. 시간이 없어서 요 며칠새 읽었던 부분을 한꺼번에 적었는데, 역시 하루에 조금씩 나눠서 정리하는게 생각을 더 잘 정리할 수 있을 것 같다. 어쨌든 횡성수설했지만, 오늘의 정리 끝..!

정글, 그 후

취업 준비 4개월

정글을 수료하고 나서 바로 취업시장에 뛰어들었다. SW사관학교 정글의 협력사 6곳에 지원서를 제출하였지만, 한 곳은 CS 면접에 대한 준비가 부족해 1차 면접 탈락, 한 곳은 회사 사정이 어려워 코딩테스트 기회조차 받지 못했고, 또 한 곳은 코딩테스트의 서술형을 풀지 못해 탈락, 그리고 나머지 세 곳은 연락조차 받지 못했다.

수료 후 1개월쯤 지났을 무렵부터는 협력사 이외의 기업에도 지원을 시작했다. 원티드와 프로그래머스를 통해 다양한 기업들에 지원을 했고 프로그래머스의 벡앤드 취업연계 코딩테스트 또한 진행했다. 많은 기업들에서 코딩테스트나 면접의 기회를 받지 못했다. 아마 경험이 짧고 이렇다할 스펙이나 실무스킬이 부족해서지 않았을까 생각한다. 또한 최근 경제상황이 안좋아지면서 취업시장이 얼어붙은 것도 있을 것 같다. 몇개의 기업에서는 코딩테스트를 통과하고 면접까지 진행했지만 한개의 기업을 제외하고는 과정에서 모두 불합격을 받았다. 한개의 기업은 최종 합격하였지만 조금 더 욕심을 내보고 싶었고, 대기업 면접을 남겨두고 있었기에 입사 제안을 거절했다.

카카오는 정글에서 알고리즘을 공부할 때부터 문제들의 난이도가 정말 높다고 생각했었다. 카카오톡이 나오면서부터 사용하고 응원해온 기업인 만큼 꿈의 회사로 생각했지만, 첫 회사로 들어가기엔 내 실력이 부족할거라 생각했다. 취업을 준비하는 시기에 카카오 블라인드 공채가 시작되었고 그냥 코딩테스트 연습을 해보자 하는 생각으로 공채에 지원했다. 그런데 생각과 다르게(?) 1차 코딩테스트에서 7문제 중 6문제를 풀어버렸고 2차 코딩테스트에서는 상위 OO 등에 들면서 자신감이 붙었고 꼭 최종합격 해야겠다 생각하게 되었다. 그리고 기술 면접과 최종 면접의 결과, 카카오의 신입 개발자로 최종합격을 받을 수 있었다.

카카오 입사 후 요즘

카카오에서 진행하는 신입 온보딩 과정을 열심히 수행하며 성장하고 있다. 자바와 스프링으로 과제를 진행하면서 TDD와 OOP, MVC 모델, 클린코드 등을 배워나가고 있다. 그리고 부서로 들어갔을 때 사용하게 될 scala play에 관한 책을 읽으며 미리 맛을 보고 있다.

앞으로 나는

취업을 준비하는 과정에서 매일같이 알고리즘을 풀고 CS 지식을 보충하고, 입사 후에도 많은 지식들을 습득했지만 그 과정들에 대한 기록이 하나도 없는 것에 아쉬움이 있다. 조금이라도 그날그날의 깨달음들, 성장했던 부분들을 기록해두었다면 좀 더 성장에 대한 보람을 느낄 수 있지 않았을까.

나는 글을 깔끔하게 쓰지 못하는 편이고 글을 쓰다보면 생각이 많아져 시간이 오래걸리는 편이다. 그렇다보니 글을 쓰는 것을 좀 기피해왔다. 이제부터는 하루에 짧게라도 조금씩 글을 써보려고 한다. 특히 책을 읽고 배운 부분들에 대해 적어보려 한다.

누군가와 기술적인 대화를 나누거나 내가 아는 지식을 전하는 것은 정말 좋아하지만, 기술적인 글을 쓴다는 것은 많은 노력이 필요한 것 같다. 당분간 내 글은 기술을 공유하기 위한 글이라기보다 내 생각을 끄적이는 작은 성장일기가 될 것이다. 그렇게 글 쓰는 습관을 들이다 언젠가 기술블로그에 대한 욕심이 생기면 또 열심히 하게되지 않을까.

암튼 그렇게 시작해보려 한다. 열심히 즐겁게 살아보자!

PintOS 마지막 프로젝트이자 user program을 실행시키기 위한 프로젝트들 중 세번째로 File System(이하 FS)을 구현한다.

프로젝트3까지의 핀토스는 disk의 free 영역을 관리하기 위해 bitmap을 사용해왔으며 파일들은 disk의 연속된 sector를 할당받아 사용하고 있었다. 이러한 경우 외부 단편화가 심하게 발생할 수 있다. 여러개의 큰 덩어리로 인해 할당 가능한 영역이 나뉘어있으면 할당 가능한 용량은 충분히 되는데도 연속으로 할당할 수 없어 할당에 실패하게 되는 것이다. 이번 프로젝트에서는 이러한 문제를 해결하기 위해 FS를 도입하고 FS가 FS답게 동작할 수 있도록 subdirectory, link 등을 구현한다.

Indexed and Extensible Files

File system 에는 FFS, EXT, FAT 등 다양한 종류가 있다.

FFS는 Fast File System인데, 이는 말 그대로 빠르게 동작하는 FS를 구현하기 위해 만들어졌다. SSD를 사용하는 최근의 secondary memory의 경우에도 해당되는지는 잘 모르겠으나 이전에 사용되던 HDD의 경우 물리적인 디스크를 사용하였으며 원하는 sector를 읽기 위해서는 disk head를 움직여야했다. 이 작업을 seek라고 하는데 읽으려는 sector가 여기저기 분산되어있으면 seek 동작이 자주 일어나고 disk를 읽는 속도가 느려지게 된다. FFS는 이를 개선하기 위한 방법으로 짧은 시간 내 다시 읽힐 가능성이 큰 data를 가까운 곳에 배치하는 방법이다. Disk를 여러개의 cylinder로 나누고 어떠한 디렉토리와 이와 연결된 파일의 inode와 data 등을 하나의 cylinder에 배치하는 방식으로 구현된다.

EXT는 리눅스계열의 FS로 FFS와 multi level indexing(아래에서 설명) 등의 적용에 따라 ext2, ext3, ext4 등으로 발전되어온 방식이다. 자세한 설명은 필자의 지식이 부족한 관계로 생략한다.

위와 같은 다양한 FS는 대부분 disk의 할당가능한 영역을 bitmap으로 관리한다. 그리고 파일들은 연속된 sector들도 이루어지는것이 아니라 여기저기 흩어져있는 sector들로 이루어진다. 그렇다면 흩어져있는 sector들을 어떻게 하나의 file로 읽어오는 것일까. (일단 가상메모리가 연속된 가상주소로 접근되지만 실제 물리메모리에는 프레임들이 여러군데로 흩어져있었던 그림이 상상된다.)

파일의 메타데이터(파일과 관련된 정보들:파일크기, 생성일자, 수정일자 등)는 inode라는 자료구조로 관리된다(여기서 inode는 index node의 줄임말이다). 이 inode에는 다양한 정보를 저장하는데, 파일의 실제 data가 어느 sector에 위치하는지에 대한 정보도 포함된다. 이를 포인터라고 하는데 하나의 포인터는 하나의 섹터 또는 클러스터의 첫번째 주소를 가리킬 수 있다. 사이즈가 큰 파일의 경우 많은 수의 섹터 또는 클러스터로 이루어지기에 수 많은 포인터를 필요로 하게 된다. 하나의 inode에 모든 포인터를 담을 수 없기에 정해둔 수 만큼의 포인터를 inode에 담고 더 필요한 경우 포인터들을 담아둔 다른 섹터를 다시 가리키게 하는 방식으로 data를 관리하는데, 이를 multi level indexing이라고 한다. 보통 바로 데이터를 가리키는 12개(11개?)의 직접포인터와 포인터들을 담아둔 섹터를 가리키는 1개의 간접포인터로 구성된다고 한다. 의아할 수 있는 점이 직접포인터의 개수가 간접포인터의 개수보다 훨씬 많다는 점인데, 이는 통계적으로 컴퓨터에서 작은 사이즈의 파일이 훨씬 많기 때문에 작은 사이즈의 파일을 빠르게 읽을 수 있도록 하기 위함이라고 한다.

Multi level indexing은 구현하기에 굉장히 복잡한데, 이에 비해 FAT 파일 시스템은 cluster들의 연결관계를 단순한 방법으로 관리한다. FAT은 File Allocation Table로 data area의 할당여부와 cluster들의 연결관계를 관리하는 table을 의미한다. 이 table의 entry개수는 data영역의 총 cluster수와 같으며 각 entry의 index는 cluster들의 index(number)와 같다. 할당되지 않은 cluster의 entry는 0으로 세팅되어있어 file 생성시 FAT의 entry들 중 0 값을 갖는 entry를 찾음으로서 cluster를 할당할 수 있다. 할당된 cluster의 entry는 그 다음으로 연결된 cluster의 index값을 저장하며 마지막 cluster일 경우에는 지정된 EOC(End Of Chain)값을 저장한다. 이로써 파일을 읽을 때 연결된 cluster를 찾아 data가 저장된 sector를 찾을 수 있다.

이 챕터에서는 이전까지의 free map allocator 방식을 FAT 방식으로 바꾸어 FS를 구현한다. 이는 FS에 FAT이 적용되어야 할 뿐만 아니라, 기존의 방식으로 구현되어있는 모든 부분(inode, directory 등)에 FAT이 적용되어 FS가 정상적으로 작동할 수 있도록 대폭 수정이 필요하다.

기존의 FS에서는 파일의 크기가 초기에 확정되며 이후에는 파일의 크기를 변경할 수 없었다. FAT을 적용한 후의 PintOS는 파일이 확장될 수 있어야 한다. 파일의 확장은 파일에 write할 때 필요에 따라 발생될 수 있으며 필요한 크기에 따라 추가로 cluster를 할당받고 사용할 수 있도록 초기화를 해주어야 한다.

아래는 필자가 현 챕터 구현을 위해 노션에 정리한 내용이다. 공부하고 설계하면서 초반에 작성한 내용이라 중간에 바뀐 내용들이 덜 반영되기도 하였고 정리가 덜 되어있기도하니 참고만 하면 좋을 듯 하다.

Subdirectories and Soft Links

현재 PintOS의 FS는 모든 파일이 root directory안에만 존재할 수 있다. 이 챕터에서는 directory안에 directory가 존재 할 수 있도록 subdirectory를 구현해야 한다.

Unix에서는 directory를 하나의 file로 관리한다. 즉 directory는 file과 동일하게 inode를 가지며 실제 data가 저장된 cluster들로 구성된다. 일반 file과 다른점은 일반 file의 경우 file에 무슨 내용이 있는지 OS가 알 수 없지만 directory는 특정한 규칙?대로 내용이 구성되어있어 OS가 내용을 예측하고 읽어올 수 있다는 점이다.

Directory는 directory entry들로 채워진 sector를 가진 파일이다. 각 entry는 file이나 directory를 저장할 수 있는데, 이때 저장한다는 것은 file의 inode가 있는 sector와 file name등을 저장하는 것을 의미한다. 파일을 open하는 동작을 간단하게 살펴보면, 먼저 directory에서 파일이 위치하는 directory의 파일을 찾아 열면서 타고들어간 뒤 파일이 있는 directory에서 파일을 찾고 해당 파일을 열게 된다.

Directory에는 절대경로와 상대경로가 있는데 절대경로는 root directory로부터 시작하는 경로로 /a/b/c와 같은 방식으로 표현되며 상대경로는 현재 directory로부터 시작되는 경로로 ./a/b/c와 같은 방식으로 표현된다. 특히 ..은 부모 directory를 가리키며 .은 현재 directory를 가리킨다. 모든 directory는 ..과 .을 저장하고 있어야 하며 root directory의 경우 부모 directory가 없으므로 ..과 . 은 root directory 자신을 가리켜야 한다.

Subdirectory가 구현되고나면 FS와 관련된 여러 system call에서 경로를 포함한 file name이 입력되더라도 해당 directory에서 file을 찾을 수 있어야한다. 따라서 입력으로 들어온 string을 parsing하는 과정이 구현되어야한다.

Link는 쉽게말해 바로가기를 의미한다. Link에는 hard link와 soft link가 있다. Hard link는 directory entry가 직접 file을 가리키는 방법이며 이 경우 원본 file은 자신을 가리키는 link의 수 (참조횟수)를 기록하여 해당 참조횟수가 0이 되어야 실제로 file이 remove된다. Soft link는 이와 달리 file에 원본파일의 경로를 저장하는 방식으로 원본파일이 삭제되면 파일에 접근할 수 없게 된다. 이 챕터에서는 이 soft link를 구현하여 soft link로 접근하여도 원본 파일로 접근할 수 있도록 해야한다.

Buffer Cache (Extra)

현재의 FS은 file을 읽거나 쓸때 요청 시점에 바로 disk에 요청을 보내 읽어오거나 쓰고 있다. 하지만 disk I/O의 작업은 상당히 느려서 요청이 있을 때마다 처리하면 OS의 성능이 좋지 않아진다. 그래서 대부분의 실제 OS는 disk에 대한 읽기 쓰기 요청을 지연시켰다가 일괄적으로 처리하는데 이를 buffer cache라고 한다. 이 extra 챕터에서는 PintOS에서도 이 buffer cache가 작동할 수 있도록 buffer cache page를 만들고 적절한 때에 swap in/out action을 통해 data를 읽거나 쓸 수 있도록 한다.

Synchronization (Extra)

Disk와 disk내 file들은 공유자원이다. 그러므로 한번에 한 프로세스만 작업할 수 있도록 동기화가 필요하다. Disk의 경우 이미 lock이 구현되어있다. 하지만 file의 경우에는 추가적인 구현이 필요하다. 파일을 read하는 경우 여러 프로세스에서 동시에 read가 가능해야하지만 write의 경우 한번에 한 프로세스만 write할 수 있도록 구현해야한다(read/write문제).

Journaling & Mount (Extra)

FS에서 write를 하다가 crash가 나는 경우에 OS는 원자성(atomicity)을 보장해야한다. 즉, write가 성공하거나 아니면 아예 바뀌지 않거나 해야하는 것이다. 이를 위해 OS는 원본 File에 write를 하기 전에 따로 동일한 내용을 다른 영역에 기록하고, 이 기록이 성공하면 원본 file에 write를 한다. Write하다가 컴퓨터가 꺼지는 등의 문제가 발생하면, 부팅시 해당 영역을 확인하고 필요하면 해당 write작업을 진행하여 원본file이 정상적으로 변경될 수 있도록 한다. 이렇게 다른 영역에 기록해놓는 것을 Journaling이라고 하며 기록된 것을 log라고 한다. USB와 같이 외부 FS가 연결되는 경우 OS에서는 root FS에 외부 FS를 연결하여 사용할 수 있도록 해야한다. 이를 Mount라고 한다.

회고

마지막 PintOS프로젝트였던 File system은 정글의 마지막 프로젝트인 '나만의 무기를 만들자'를 앞두고 바로 직전의 프로젝트였고 기간도 일주일로 짧았다. 분위기도 술렁이고 쉽지 않았지만 그래도 가능한 한 끝까지 해보고싶어서 열심히 해보았는데 결국 모든 과제를 수행하지는 못해 아쉬웠다. 하지만 subdirectory와 soft link를 구현하고 디버깅에 성공하자 extra 과제와 관련된 test case 2개를 제외하고는 모두 pass가 되어 그래도 의미있게 PintOS를 마무리할 수 있었다.

File system은 이전 project들에 비해서 안내되는 내용이 부족하여 어디까지 수정해야하는건지 찾는데 꽤 어려움을 겪었다. 안내자료에는 거의 FAT을 구현하는 부분만 소개가 되었는데 내 생각으로는 file system이 바뀌는만큼 많은 부분에서 수정이 되어야할 것이라고 생각했다. 역시나 기존 code의 많은 부분에서 기존의 system에 특화되어 적용되어있어 수정이 많이 필요해보였는데, code에는 수정이 필요하다거나 구현하라는 내용이 전혀 없었다(기존에는 일부 code에 to do 또는 your code goes here와 같이 어느정도 힌트가 포함되어있었다). 그럼에도 내 생각에는 반드시 수정이 필요하다고 판단되어서 팀원들과 얘기를 나누고 역할을 나누어 세세한 부분까지 수정을 진행했다. 진행하면서도 이렇게까지 해야하는게 맞을까 의문이 많이 들었지만 그렇지 않으면 작동하지 않을거라 생각했기에 끝까지 진행했고 그 끝에 test case들이 통과하는것을 보면서 이렇게 하는것이 맞았다는 것을 확인할 수 있었다. 너무도 코드 수정의 자유도가 높았어서 극악의 난이도였지만 그만큼 통과하는것을 봤을때 더 뿌듯함을 느낄 수 있었다. 안내자료에 세세한 부분들이 소개되어있지 않은 부분들이 조금은 불만이었지만 현업에서는 어떤 안내 없이 내가 구현해야하는 또는 구현하고싶은 것을 직접 설계하고 구현해야하는 만큼 큰 도움이 되었다고 생각이 들고 이런 것을 의도한 것이 아닐까 싶기도 했다.

특히 기억에 남는 부분은 속도가 많이 느린 부분을 개선한 부분이다. 디렉토리에서 엔트리를 검색하는 과정이었는데, 기존의 코드에서는 디렉토리 엔트리를 확인하기 위해 엔트리의 크기만큼을 반복해서 디스크에서 읽어오고 있었다. 그리고 디스크에서 읽어오는 동작에서는 디스크에서는 섹터 단위로 읽을 수 있기 때문에 512바이트만큼을 읽어오는데, 그 중에서 엔트리는 32바이트(그렇게 설계했다)이기 때문에 읽어온 512바이트 중에 32바이트에 해당하는 부분만 복사하여 돌려주고 있었다. 엔트리 16개가 들어있는 512바이트를 이미 다 읽어왔으면서도 그 중 32바이트만 쓰고 나머지는 버리고 있었고, 그래놓고 다시 32바이트를 똑같은 섹터에서 반복해서 읽어오고 있던 것이다. 그래서 필자는 디렉토리로부터 실제 디렉토리에 있는 엔트리의 수만큼을 한번에 메모리로 읽어오고 메모리에서 엔트리들을 검색할 수 있도록 수정했고, 이 개선으로 인해서 타임아웃이 발생했던 여러 케이스를 통과시킬 수 있었다.

이제는 정글의 마지막 프로젝트인 나만무 만 앞두고 있다. 하루 빨리 개발자로 성장하여 취업하고 싶었는데 어느새 수료까지 두달도 남지 않았다. 그래서 기대도 되지만 조금은 두려운 마음이 든다. 두려움보다는 자신감과 기대감으로 취업할 수 있게 남은 기간 알고리즘도 프로젝트도 놓치지 않도록 노력해야겠다.

User Program을 실행시키기 위한 프로젝트들중의 두번째로 Virtual Memory(이하 VM)을 구현한다. 프로젝트2까지의 핀토스는 반쪽짜리 VM을 사용하고 있다. 가상 주소 공간을 사용하고 있고 Page map level 4 (이하 pml4)를 사용하고 있기는 하나, process를 실행시키는데 필요한 자원들이 처음부터 모두 다 물리메모리에 올려지고 있으며 process가 종료되지 않는 한 물리메모리를 점유하고 있어 메모리를 효율적으로 관리하지 못하고 있다. 따라서 가상메모리 기술의 핵심인 page fault또한 활용하지 못하고 있다. 이번 프로젝트에서는 이 반쪽짜리 VM이 VM답게 작동할 수 있도록 디자인한다.

Virtual Memory

도입배경

초창기의 메모리는 커널과 유저 프로세스들이 물리메모리를 직접 접근하여 사용하며 모든 프로세스들이 물리메모리를 공유하고 있는 형태였다. 이러한 형태에서의 문제점은 각각의 프로세스가 다른 프로세스의 메모리(심지어 커널에도)에 접근하여 수정할 수 있다는 점이었다. 따라서 프로그램들이 오작동하기 쉬웠으며 보안에도 취약했다. 그리하여 커널을 유저 프로세스로부터 보호(Protection)하고 유저 프로세스들 간에 분리(또는 고립. Isolation)하기 위한 가상메모리(VM)가 등장하게 되었다.

VM의 발전

가상 주소 공간의 이점 VM의 기본 컨셉은 프로세스들에게 각각의 독립된 가상 주소공간을 제공하고 해당 주소들을 물리메모리에 매핑하여 프로세스가 가상 주소로 접근할 때 해당되는 물리메모리로만 접근할 수 있게 하는 것이다. 이로써 유저 프로세스가 주어진 어떤 주소로 접근하더라도 독립된 주소공간을 사용하고 있기 때문에 접근이 허용되어있는 매핑된 메모리에만 접근할 수 있어 유저 프로세스들간의 isolation이 가능해진다. 또한 같은 맥락에서 유저 프로세스가 메모리 공간을 독차지하고있다는 환상을 갖게 되어 다른 프로세스를 전혀 신경쓰지 않고 자유롭게 프로그램을 작성할 수 있게된다.

VM을 구현하는 방식은 시간이 흐름에 따라 발전되어왔다.

베이스 바운드 Base and bound 방식은 VM이 매핑되는 물리메모리의 첫번째 주소를 base로 하여 주소를 번역하고 VM의 크기를 bound에 저장하여 bound를 넘는 주소로 접근시 부적절한 접근으로 판단하여 처리하는 방식이다. 예를 들어 물리메모리가 총 16KB이고 가상메모리가 4KB라고 가정하며 물리메모리 주소의 8K 지점에서 VM이 매핑된다고 하면, 8K 지점을 base로 하여 가상 주소를 더하는 방식(8K + 가상주소)으로 주소가 번역되어 메모리에 접근할 수 있게 되는 것이다. 또한 가상주소가 4KB를 초과하게 되면 bound에 걸려 접근할 수 없게 된다. 이 방식이 적용되던 때 base와 bound는 base register와 bound register에 저장되어 관리되었다고 한다. 이 방식은 단순하였지만 가상주소 공간을 통째로 물리메모리에 매핑하였기 때문에 실제 사용하지 않는 영역까지 메모리를 점유하게 되어 내부 단편화가 심한 방식이었다.

세그멘테이션 Segmentation 방식은 일반화된 Base and bound 방식으로, 가상주소공간을 용도에 따라 segment로 나누고 해당 segment들을 base and bound 방식으로 물리메모리에 매핑시키는 방식이다. 사용하지 않는 영역은 매핑시키지 않기 때문에 내부 단편화는 개선되나 하나의 세그먼트를 덩어리로 매핑시키다보니 여전히 외부단편화는 피할 수 없는 방식이다.

페이지 페이지 방식은 물리메모리와 가상메모리를 4KB 단위로 나누어 매핑하는 방식이다. 가상주소 공간을 4KB로 나눈 하나의 덩어리를 page라고 하며 물리메모리를 4KB로 나눈 덩어리는 물리페이지 또는 물리프레임이라고 한다. Kaist PinsOS에서는 이를 혼동이 없도록 하기 위해 프레임이라고 하기에, 필자도 이하에서는 프레임이라고 하겠다. Page방식은 4KB 덩어리로 관리하는 만큼 할당되었으나 사용되지 않는 영역이 포함되어 내부단편화가 발생하긴 하나 크지 않으며, 메모리를 잘게 나누었기 때문에 여러page를 묶어서 할당하지 않는 한 외부단편화는 발생하지 않는다.

32비트 운영체제에서는 2의 32제곱 만큼의 가상주소공간을 사용할 수 있다. 이는 32비트 운영체제가 메모리를 4GB까지밖에 사용할 수 없는 이유이기도 하다. 반면에 64비트 운영체제에서는 2의 64제곱 만큼의 가상주소공간을 사용할 수 있지만, 실제로는 48제곱까지만 사용한다. 이는 가상주소공간이 커질수록 늘어나는 페이지에 대응하는 페이지테이블이 필요하고 이를 위한 굉장히 큰 공간이 추가로 필요해지기 때문이며, 48제곱 만으로도 256TB라는 충분한 크기의 공간을 제공할 수 있기 때문이라고 한다.

48개의 비트로 표현되는 가상주소 체계에서는 256TB의 공간을 사용할 수 있으며 이를 페이지로 표현하면 64G개에 해당된다. VM에서 가상페이지와 물리프레임의 매핑은 페이지테이블로 관리되는데, 이 하나하나의 페이지테이블 또한 4KB의 페이지들로 관리된다. 하나의 페이지테이블이 4KB이고 각각의 페이지의 매핑정보를 담는 페이지테이블 엔트리(PTE: Page Table Entry)는 주소를 저장하므로 8바이트에 해당하기에 하나의 페이지테이블에는 512개의 PTE를 담을 수 있다. 48비트 가상주소의 페이지매핑을 전부 저장하기 위해서는 128M개의 페이지테이블이 필요하며 이의 크기는 512GB에 달한다. 현실적으로 불가능한 크기라고 할 수 있다. 메모리의 크기는 커질수록 속도가 느려지며 최근 컴퓨터들도 보통 8GB에서 32GB 사이의 물리메모리를 사용할 뿐이다.

VM은 실제로 가상주소공간에 대응되는 페이지테이블들을 한번에 다 만들지 않는다. 오히려 필요한 페이지들만 미리 만들어놓고 user process에 의해 추가적으로 필요한 경우에 추가로 테이블을 생성한다. 이를 구현하기 위한 체계가 Page Map Level 4(pml4)이다. 48비트 가상주소에서 하위 12개 비트는 page offset을 의미한다(1page는 4KB이며 이는 12개 비트로 표현되기 때문). 그 외 상위 36개 비트는 page의 number를 의미하는데, 이를 9비트씩 4개 구간으로 나누면 해당 구간마다 512(2의 9제곱)개의 하위 테이블의 number를 의미하도록 구분할 수 있다. 예를 들어 page offset 상위 첫번째 구간은 page table에서의 Entry number를 의미하며, 이보다 한단계 상위구간은 page table을 '가리키는' table의 page table index를 의미한다고 볼 수 있다. 여기서 구간을 9비트로 나누는 이유는 각각의 테이블 또한 4KB의 페이지로 관리되며 각 엔트리는 8바이트이므로 512개를 담을 수 있기 때문이다.

User process가 가상주소로 접근할 경우 매핑되어있는 물리주소로의 주소번역이 필요하다. 매핑되는 정보는 페이지테이블에 있기에 커널에 의해 소프트웨어 수준에서 주소를 번역하여 데이터에 접근하고 user에게 돌려줄 수도 있으나 이는 매우 느린 과정이다. 이렇게 소프트웨어 수준에서 속도가 나지 않는 경우 하드웨어의 도움을 받아 해결하곤 한다. 그래서 탄생하게 된 것이 MMU(Memory Management Unit)라는 주소번역 하드웨어이며, 페이지테이블을 메모리에서 가져오는 과정의 느린 속도를 개선하기 위해 자주 사용되는 페이지테이블 엔트리를 캐싱하는 하드웨어가 바로 TLB(Translation Loockaside Buffer)이다.

Memory Management

Project2까지 진행한 PintOS는 반쪽짜리 VM이 적용되어있다. Kernel의 protection과 user process간의 isolation은 구현되어 있지만 메모리가 효율적으로 관리되고 있지는 않다. 당장 필요하지 않은 자원들까지도 한번에 물리메모리에 올리고 있기 때문이다. 그렇다면 적시 적절한 자원을 메모리에 적재할 수 있도록 관리하려면 어떠한 방법을 써야하는걸까?

우선 자원들은 바로 물리메모리에 load 및 매핑하지 않고 이후에 load할 수 있도록 필요한 정보만 따로 저장해두어야 한다. 이후 아래와 같은 두가지 방법을 통해 자원들을 관리한다.

첫번째는 page fault이다. Page fault는 user process가 어떤 가상주소에 접근했을 때 NULL 접근이거나 kernel 주소와 같이 권한이 없는 주소에 대한 접근일 때 발생하거나 매핑된 정보가 없을 때 발생한다. 전자와 같이 부적절한 접근일 경우에는 프로세스를 종료해야한다. 하지만 후자의 경우에는 해당 주소에 해당되는 페이지가 유효한지(이전에 저장해둔 정보가 있는 페이지인지) 확인하고 유효하다면 load 및 매핑을 통해 user process가 원하는 data에 접근할 수 있도록 해주어야 한다. 이 방법을 사용하면 user process가 필요로 할 때에만 data를 물리메모리에 적재하여 program 실행시 load하는 시간을 단축시킬 수 있으며 물리메모리 공간을 절약할 수 있다.

두번째는 swap이다. Page fault 발생시 물리메모리(프레임)을 할당하고 해당 공간에 필요한 data를 적재하고 매핑하는 것이 swap in이다. 문제는 물리메모리가 가득 찬 경우 발생한다. 이때에는 적재되어있는 data(page) 중 우선순위가 낮은 data를 victim으로 선택하고 eviction하여 물리프레임을 확보하는데 이를 swap out이라고 한다. 우선순위를 판단하는 기준은 LRU 등 다양하지만 단순한 알고리즘으로는 Clock 알고리즘이 있다. PTE에는 accessed라는 bit가 있는데 이는 process가 해당 page를 읽거나 쓰면 1로 변경되는 bit이다. 따라서 eviction을 수행하는 시점에 accessed가 0인 PTE가 있다면 이를 우선순위가 낮은 page로 판단할 수 있다. Accessed bit가 모두 1일때는 어떻게 해야할까? 이때 사용되는 알고리즘이 Clock 알고리즘이다. 하나하나의 accessed bit를 확인할때 1이면 0으로 바꿔준 뒤 다음 프레임을 확인한다. 그러다가 모든 페이지의 bit가 1이어서 한바퀴 돌게되면 처음으로 확인하고 0으로 바꿔주었던 페이지를 만나게 되는데 이때 이를 우선순위가 낮다고 판단하고 eviction하는 것이다. 이러한 Swap을 사용하여 당장 사용하지 않는 페이지를 물리프레임에서 제거하고 필요한 page만 물리메모리에 있도록 하여 메모리를 효율적으로 사용할 수 있다.

이러한 방법들을 적용하여 메모리를 관리하기 위해서는 관련된 자료들을 저장하고 관리할 data structure가 필요하다.

Supplemental Page Table

PintOS에서는 Supplemental Page Table(이하 spt)을 통해 페이지들을 관리한다. Spt에 저장되는 data는 page라는 구조체이다. 각각의 page는 해당하는 가상주소와 해당 주소에 매핑되어야할 정보들을 저장할 수 있는 field들로 구성되어있다. Page fault 발생시 이 table에서 fault가 발생한 주소에 해당하는 페이지가 있는지 검색하고, 있다면 유효한 페이지라고 판단하여 load(또는 swap in)을 진행하게 된다. 이 외에도 어떠한 주소가 유효한 페이지인지 확인이 필요한 경우에도 활용될 수 있다.

Page fault를 빠르게 수행하기 위해서는 spt에서의 검색 속도가 빨라야 한다. 이를 위해 다양한 디자인을 할 수 있겠지만, 필자는 hash 자료구조를 사용하여 구현하였다. PintOS에서 제공하는 hash table은 최적의 경우 O(1~2)에서 최대 O(4)의 시간복잡도로 구현되어 매우 빠르게 검색을 수행할 수 있다.

Frame Table

물리메모리의 User pool에 대한 프레임 관리를 위해 table이 필요하다. 특히 swap out시 eviction을 위해 victim을 찾을 때 대상들을 관리하기 위해 필요하다. 이 또한 다양한 디자인이 가능하지만, clock 알고리즘을 적용하기 위해서는 선형탐색만 가능하면 되기 때문에 필자는 linked list를 이용하여 frame table을 구현하였다.

Anonymous Page

Page의 종류 중 anonymous page(익명 페이지)는 매칭되는(또는 기반이되는?) 특정한 file source가 없는 페이지이다. PintOS에서 anonymous page는 stack과 segment에 해당한다. Stack은 그렇다쳐도 segment는 왜 anonymous 인지 의아할 수 있다. 실행 file(executables)로부터 data를 읽어오기 때문에 file source가 있다고 생각이 들기 때문이다. 실행 file의 data는 해당되는 page가 initialize 되는 때에 딱 한 번만 file로부터 data를 읽어온다. 그 이후에는 해당 file에서 data를 읽어오거나 쓸 일이 없다. 왜냐하면 실행하는데 필요한 data를 초기에 읽어오고 이후에 .bss나 .data에 해당하는 세그먼트의 경우 실행되는 도중에 data가 바뀌는데 이를 실행file에 저장해서는 안되기 때문이다. 실행file의 data들은 실행을 위한 초기값들을 저장하고 있기 때문에 내용이 바뀌어서는 안된다. 따라서 실행file에서 읽어오는 segment는 돌아갈 수 있는 파일(backing file)이 없는 anonymous page로 관리된다.

PintOS에서 모든 page는 uninit page로 시작된다. Uninit page의 swap in operation은 initializer로 되어있으며, page fault가 발생되어 swap in이 실행될 때 이 initializer가 실행되어 미리 설정해놓은 type에 따른 initializer와 그 외 추가적으로 지정해둔 initializer가 실행된다. Anonymous page의 경우 type은 VM_ANON type으로 uninit page를 생성한다. 이에 따라 추후에 anon initializer가 실행될 수 있게 된다. 또한 segment의 경우에는 segment로 분류하기 위해 VM_SEGMENT를 or연산하여 함께 넣어준다. 마찬가지로 stack의 경우에는 VM_STACK으로 함께 넣어준다.

Proj2 까지의 PintOS는 user program이 실행될 때 모든 segment data를 물리메모리에 적재시켰으나 이번 프로젝트에서는 해당 시점에는 추후에 initialize 될 수 있도록 uninit page만 생성하며, initialize시에 data가 올라갈 수 있도록 lazy load 기능을 구현하고 uninit page 생성시 인자로 전달해준다. Stack의 경우에는 user program 실행시 arguments를 passing하기위해 setup되어있어야 하므로 반드시 lazy load없이 initialize해야 한다.

Stack Growth

User stack의 꼭대기에 위치한 첫번째 스택 영역의 경우 process의 load단계에서 바로 setup 해주었으나 현재 상태에서는 이후에 process가 진행되다가 해당 영역을 벗어나는 경우 유효하지 않은 주소를 참조한 것으로 판단되어 process는 kernel에 의해 종료된다. 따라서 stack이 성장하는 경우 이를 판단하여 추가적인 메모리를 할당해 줄 필요가 있다.

X86-64의 PUSH Intruction은 rsp를 아래로 내리고 데이터를 저장하기 전에 먼저 8바이트 아래의 주소가 유효한지 확인한다. 이때 해당 주소가 유효하지 않다면 rsp는 변동되지 않은 채로 page fault가 발생하게 된다. 따라서 kernel은 user process에서의 rsp와 fault address를 비교하여 8바이트 차이가 나면 stack growth가 필요한 상황으로 판단하고 추가 메모리를 할당해줄 수 있다.

위와 같은 경우 외에도 stack growth라고 판단할 수 있는 경우가 한가지 더 있다. 함수 내에서 초기화되지 않는 지역변수가 선언되는 경우이다. 이러한 지역변수가 선언되는 경우 PUSH instruction이 실행되지 않는다. 초기화하지 않았기 때문에 해당 변수의 값에는 접근이 일어나지 않으며 단지 해당 변수에 stack의 일부 영역과 그 주소가 주어질 뿐이다. 또한 rsp는 PUSH 없이 해당 변수의 아래로 이동하게 된다. 따라서 그 시점에 해당되는 stack 메모리가 할당되지 않으며 지역변수에 접근이 일어났을 때 page fault가 발생된다. 이 경우에는 위처럼 8바이트의 차이로는 stack growth라고 판단할 수 없다. 따라서 다른 방법을 생각해야 한다.

System call이나 interrupt가 user process에서 발생되어 kernel로 mode switching이 발생한 경우 interrupt frame에 user process의 rsp값이 저장되지만 kernel에서 진행하다가 page fault가 발생하는 경우 interrupt frame에는 원하지 않는 값이 저장되어있다. 따라서 system call이나 interrupt 발생 시 user에서 바로 넘어온 경우 tcb 등 가능한 다른 공간에 rsp값을 저장하여 page fault 발생 시 rsp를 읽어올 수 있도록 해주어야 한다.

Memory Mapped Files

Page의 종류 중 File mapped page(Memory Mapped File)는 file을 기반으로 한 page이다. Initialize할 때에는 Anon page와 비슷한 방식으로 물리메모리에 load되지만 destroy(unmap)시에는 load되었던 물리메모리의 변경사항 유무에 따라 원본 file에 수정이 일어나는 점이 anon page와의 차이점이다.

File mapped page는 user process의 mmap system call에 의해 만들어지며 munmap에 의해 제거된다. User process의 mmap 요청에 대해 kernel은 인자로 전달된 가상주소에 file을 mapping할 수 있도록 필요한 data들을 담아 page를 생성한다. 추후에 process가 해당되는 주소로 접근했을 때 page fault가 발생되면 segment와 마찬가지로 lazy load 방법으로 물리메모리에 file을 읽어와 매핑시키게 된다. Mmap 구현시 user process로 넘어온 fd(file descriptor)에 해당하는 file을 찾되 그대로 사용하는 것이 아니라 file_reopen 함수를 통해 file 구조체를 새로 만들어 사용해야한다. 그 이유는 먼저 user가 넘겨준 fd를 가지고 user는 다시 read, write, close 등을 수행할 수 있어야한다. 따라서 file 구조체의 offset이 file mapped page에 의해 변동되어서는 안되며 file이 먼저 close되어서도 안된다. 또한 user가 fd를 사용하여 file을 close하더라도 munmap하지 않았다면 mmap에 의해 이루어진 매핑이 유지되어야 한다. 이와 같은 이유로 mmap이 수행될 때에는 mmap만을 위해 file을 reopen하여 사용해야한다.

User process가 munmap system call을 요청하면 kernel은 인자로 전달된 가상주소가 이전에 mmap에 의해 file이 매핑되어있는 주소가 맞는지, 그리고 이전에 munmap된 주소는 아닌지 확인하고 유효하다면(unmap이 진행될 수 있다면) 해당 주소에 매핑되어있는 page의 destroy를 진행한다. File mapped page의 destroy을 진행할 때에는 매핑되어있는 물리메모리의 수정이 일어났는지 확인하고 수정이 되어있다면 file에 수정을 반영하고 수정이 되어있지 않다면 별도 반영 없이 매핑을 해제한다. 물리메모리의 수정이 일어나면 해당 물리메모리에 접근하기 위해 사용된 user 가상 주소에 해당하는 PTE의 dirty bit가 0에서 1로 변경된다. 따라서 destroy의 대상이되는 page의 PTE의 dirty bit를 확인함으로써 file에 저장을 해야할지 유무를 판단할 수 있다.

Mmap시 요청된 length가 page의 크기 4KB보다 크다면 전달된 가상주소로부터 연속된 페이지로 file을 매핑할 수 있도록 page를 생성한다. User가 인자로 넘겨준 addr로부터 읽고싶은 위치만큼 offset을 주고 계산하여 접근하였을 때 원하는 data를 읽을 수 있게 하기 위함이다. 반대로 munmap시 user는 매핑되어있는 주소 중 맨 첫번째 주소만 인자로 넘겨주는데 kernel은 그 주소로 요청받아 매핑하였던 page들을 모두 unmap해주어야 한다. 여러 page로 매핑되어있는 경우 user의 가상주소에 연속된 페이지로 매핑되도록 page를 생성하였기 때문에 총 page수를 저장해두었다면 어렵지 않게 해당되는 page들을 찾아 destroy를 진행할 수 있다.

User process가 mmap으로 file을 매핑한 후에 munmap을 호출하지 않고 종료하더라도 매핑되어있는 page들은 정리되어야 한다. 이는 process exit시에 clean up 하는 과정에서 이루어지는데, 문제는 의도적인 unmap 과정과 다르게 page들에 random하게 접근하여 destroy를 진행하게 되면서 발생된다. File mapped page가 destroy될 때에는 mmap시 reopen했던 file을 close해주어야 하는데, 이는 여러 page가 생성되었더라도 모든 페이지가 정리되고 마지막 페이지가 destroy될 때 close되어야 한다. Munmap시에는 의도적으로 destroy되는 순서를 정할 수 있지만 process exit시에는 모든 spt의 page들에 대해서 random하게(정확히는 hash table에 저장되어있는 순서대로) destroy가 진행되기 때문에 어떤 순서로 destroy되더라도 마지막 page가 정리될 때 file을 close할 수 있도록 구현해야 한다. 다양한 방법이 있겠으나 필자의 팀은 해당 시점마다 정리되어있지 않은 페이지수를 저장하고 page들이 해당 변수를 공유할 수 있도록 pointer와 malloc을 활용하였다. 예를 들면 총 3페이지로 구성된다면 malloc으로 할당받은 count변수에 3을 저장하여 각각의 페이지에 포인터변수로 저장해두고 각각의 페이지가 destroy될 때마다 해당 값을 1씩 감소시켜 값이 0이 되었을 때에 마지막 page로 간주하고 file을 close하는 방식이다.

Fork가 일어날 때에는 동일한 context로 진행되도록 하기 위해 부모의 모든 spt의 page들을 copy해주어야 한다. Page 종류에 따라 이런저런 신경써주어야할 것이 많기에 굉장히 까다로운 부분이다. 그 중에서도 mmap page는 더욱 그렇다. Page안에 page type 별로 필요한 contents를 담을 수 있도록 struct들을 union으로 묶어놓은 field가 있는데, file page의 경우 load와 destroy(또는 swap in/out)을 위해 필요한 data들을 저장해야하기 때문이다. 특히 file은 여러 page로 매핑되었더라도 하나의 file 구조체를 가리켜야 하고 위에서 언급한 count는 여러 page가 같은 변수를 참조하고(가리키고) 있어야 의도한대로 작동될 수 있기 때문이다. 따라서 부모의 page들을 copy할 때에 이러한 점들을 충분히 고려하여 design할 필요가 있다. 필자의 팀은 file mapped page의 경우 initialize될 때 copy상황인지 판단하고, copy상황이라면 동일한 file로 매핑되어야하는 page들 중 이미 initialize된 page가 있는지 확인하여 있다면 해당 page의 file과 count변수를 가져와 저장하고, 없다면 file reopen과 malloc으로 새로 생성하여 저장하는 방식으로 구현하였다.

Swap In/Out

위에서 언급한 것처럼 page fault 발생시 해결할 수 있는 fault(유효한 page가 있는 경우)라면 해당되는 data를 load(또는 swap in)하여 user가 해당 addr에 접근할 수 있도록 해야한다. 그러나 그 과정 중에 물리메모리가 모두 할당되어 추가 할당할 수 있는 공간이 없다면 다양한 방법(한가지 방법 Clock 알고리즘은 위에서 간단히 언급하였다)을 통해 eviction 대상이 될 page를 찾고 해당 page를 swap out하여 이후에 다시 해당 page에 접근 시 swap in이 될 수 있도록 하고 물리frame을 확보하여야 한다.

File mapped page의 경우 swap in/out이 비교적 단순하다. Backing store가 되는 file이 있기 때문에 swap out의 경우 destroy와 마찬가지로 수정여부를 확인 후 file에 반영하면 되고 swap in은 lazy load처럼 file로부터 data를 읽어와 물리메모리와 매핑하기만 하면 된다.

Anon page의 경우는 file mapped page와 달리 추가적인 구현이 필요하다. Backing store가 되는 file이 없기 때문에 임시로 저장해둘 공간이 따로 필요하기 때문이다. 이를 위해 disk의 일부 partition을 swap partition으로 사용하는데 PintOS에서는 이를 swap disk로 제공하며 disk를 initialize하고 read/write하기 위한 interface를 제공한다.

Swap disk는 swap out시 data를 임시 저장하기 위한 공간으로 다시 swap in operation이 일어나기 전까지 해당 data는 안전하게 유지되어야 한다. 따라서 swap disk의 할당여부를 관리하기 위한 swap table이 필요하다. Swap disk는 page를 저장하기 위해 4KB씩 나누어 관리하며 이 단위를 swap slot이라고 한다. Swap table은 이 swap slot의 할당여부를 관리해야하는데 이는 간단하게 1(할당됨)과 0(할당가능)으로 관리할 수 있기에 PintOS에서 제공하는 bitmap을 사용하면 간단하게 구현할 수 있다.

PintOS의 bitmap은 사용할 수 있는 bit의 개수를 저장하는 bit cnt와 실제 bit를 저장하는 bits로 구성되며, bits는 32bit unsigned long의 배열로 되어있다. bitmap create시 bit cnt를 인자로 넘겨주면 해당 bit를 표현하기 위해 필요한 unsigned long의 개수를 계산하여 bits배열을 생성한다. 예를 들어 100개의 bit를 관리해야한다면 100개의 bit를 표현하기 위해서는 32bit unsigned long이 4개 필요하므로 길이 4의 배열을 생성한다. 이후 swap slot의 할당을 위해 bitmap scan and flip을 호출하면 bits 배열의 처음부터 scan하여 할당되지 않은(bit가 0인) 인덱스를 찾아 반환한다. 또한 swap slot을 반납하기 위해 bitmap set을 실행하면 해당 index가 배열의 몇번째 인덱스에 속하며 몇번째 offset에 위치하는지 계산하고 그 위치에 접근하여 값을 set하게 된다.

Disk는 sector라는 최소단위로 data를 관리하며 sector의 크기는 시스템마다 다를 수 있으나 PintOS에서는 512bytes를 사용한다. 따라서 한개의 page를 저장하기 위해 한개의 swap slot은 8개의 sector를 사용해야한다. 또한 disk를 read/write할 때에 disk에서의 위치는 sector no.로 표현하기 때문에 swap slot과 swap slot당 sector수인 8의 곱으로 실제 disk에 write/read해야할 위치를 계산할 수 있다.

Copy-on-write (Extra)

동일한 file에 대해서 여러 process가 mmap요청을 하는 경우 이미 물리메모리에 mapping되어있는데도 추가로 메모리를 할당하여 매핑하는 것은 비효율적이다. 특히 write가 발생하지 않는 경우라면 완전히 동일한 data를 여러 메모리에 load하고 매핑하게되어 정말 비효율적이다. 하여 이미 매핑된 물리메모리가 있는 경우 우선 같은 물리메모리를 참조하도록 하여 user process가 해당 data에 접근하여 read할 수 있도록 하고 write동작이 발생할 때에야 물리메모리의 copy를 진행하여 각각 data를 따로 수정할 수 있도록 한다. 이러한 방법을 copy-on-write 방식이라고 한다.

Copy-on-write 방식을 구현하려면 user process의 write 동작을 kernel이 알아챌 수 있어야 한다. 이는 단순히 PTE의 writable bit를 0으로 세팅하여 read only page인것처럼 만들어놓고 write동작이 일어나면 page fault가 발생되는것을 이용하여 write 동작을 알아채도록 할 수 있다.

PintOS에서는 이 챕터는 extra에 해당하는 부분으로 fork시에 file mapped page를 copy하는 경우에만 copy-on-write가 적용되도록 구현하라고 하고 있다.

회고

Project2까지는 한양대 ppt 자료를 참고하여 구현해왔지만 이번 VM 프로젝트에서는 기타 자료의 참고 없이 kaist git book과 PintOS의 base code만을 참고하고 설계하여 프로젝트를 진행했다. 그래서 세세하게 신경써서 설계하고 구현한 코드가 정상적으로 동작할때 정말 즐거웠고 자신감이 많이 올랐던 것 같다. 특히 여러모로 신경을 많이 써야했고 우리만의 로직을 적용해서 구현해야했던 supplemental page table copy부분은 정말 흥미진진했다. 이전에도 reference code를 참고하지 않고 도움이되는 ppt자료만 보고 구현했기에 물론 의미가 있었지만 이번 프로젝트를 진행하면서 충분히 직접 설계할 수도 있었을텐데 그렇게 하지 않았던 것에 대해 아쉬움을 많이 느꼈다.

거의 모든 test case가 통과되었지만 page-merge-par, page-merge-stk, page-merge-mm 이 세가지 case는 random하게 pass/fail이 발생했다. 다른 모든 각각 기능에 대한 case는 통과되고 있고 이 case들에서도 종종 pass가 되어서, 그리고 워낙 case가 복잡하고 print가 잘 되지 않아서 어떤 부분에서 fail이 발생하는지 찾지 못한채 이번 프로젝트가 종료되었다. 조금 더 집착을 가지고 깊게 tracking해보면 해결할 수 있을텐데 시간의 한계로 해결하지 못한 부분이 아쉬움으로 남았다. 또한 copy on write는 시간관계상 구현하지 못했는데 내용을 읽어보니 흥미로워서 조금 더 목표를 높게 잡고 이 부분까지 구현했더라면 또 재미있었겠다 하는 생각이 든다.

지난주에 비해 내용이 너무 방대하여 여러가지 빼먹은 부분도 많고 글도 좀 횡성수설 하는 부분이 있는 것 같다. 혹시나 이 글의 독자가 있다면 거를건 거르고 도움이 되는 부분만 잘 골라 얻어가길 바란다. 잘못된 내용에 대한 태클은 언제나 환영입니다.

Project 1 에서는 커널에 있는 thread와 커널에서 일어나는 일들, interrupt handler와 scheduling 등에 대한 과제를 수행했다. 이번주차부터는 User Program을 실행시키기 위한 작업들을 해나간다. 그 중에서도 Project 2는 user program 실행시 입력된 argument들을 program에서 사용할 수 있도록 user영역에 넘겨주는 작업 Argument Passing, user가 system call을 호출할 때 전달한 인자의 유효성을 검사하는 작업 User Memory, user가 호출한 system call을 수행하고, 적합한 return값을 돌려주는 작업 System Calls, user process가 종료될 때 종료메세지를 띄워주는 작업 Process Termination Messages, 실행 중인 파일에 대해 수정되지 않도록 조치하는 작업 Denying Writes to Executables 을 수행한다.

Argument Passing

PintOS는 부팅되면서 먼저 kernel의 thread, interrupt, timer, syscall 등의 기능들에 대해 초기화한다. 이후 입력된 인자를 바탕으로 User Program을 실행시킬 준비를 한다.

먼저 커널은 들어온 command line에서 filename을 parsing하고 해당 name으로 program을 실행시키기 위한 thread(process : PintOS에서는 멀티쓰레딩이 지원되지 않아 process는 thread와 동일시될 수 있다)를 생성한다.link

filename으로 생성된 thread가 schedule되면 이 thread는 User Program이 실행될 수 있도록 여러가지 환경을 만들어준다: interrupt frame, user memory(initializing, loading), arguments.link

** Interrupt Frame** link Context를 switching할때는 실행되던 context를 나중에 그대로 되살릴 수 있도록 저장해두어야 한다. 이는 schedule로 인한 thread간의 switching 뿐만 아니라 동일 thread에서 kernel과 user간의 switching 시에도 필요하다. 이를 위해 context를 저장하는 frame을 PintOS에서는 interrupt frame(if)이라고 한다. thread간의 switching에서는 tcb(thread control block)에 위치한 if을 사용하며(thread launch() in schedule()), kernel-user간 switching에는 kernel thread의 stack영역에 if를 쌓아 사용한다. kernel-user간 switching은 user mode로 process 실행 도중 interrupt 발생 또는 exception, trap(syscall) 발생 등에 의해 일어난다.

User Memory link Process들은 각각 독립된 가상 메모리 영역을 갖는다. 따라서 User Program을 실행할 때마다 가상 메모리 공간을 세팅해야 하며, 실행가능한 파일 형식인 ELF(Executable and Linkable Format)의 세그먼트 정보에 따라 program을 물리 메모리로 load하고 가상 메모리 주소와 mapping 시킨다.

Arguments link User program을 실행시키기 위해 입력된 Command line은 한 줄로 되어있다. 따라서 kernel은 arguments를 parsing해야하며 실제 user program이 실행될 때 이 arguments를 사용할 수 있도록 인자로 전달해주어야 한다. user program은 user 가상 메모리 영역 안에 있는 data에 접근할 수 있기 때문에 user의 stack영역에 arguments를 setting하고 if를 통해 user program이 실행될 때 main함수의 인자로 argc와 argv가 전달될 수 있도록 if의 rdi, rsi에 값과 해당 포인터를 저장한다. stack에 쌓인 arguments 바로 아래엔 fake return address를 넣어주고, if의 rsp를 fake return address가 저장된 곳을 가리키도록 변경해준다.

이러한 환경이 모두 완성되면 kernel은 작성한 if를 인자로 do_iret(interrupt return)함수를 실행하고 cpu의 register들을 if에 저장된 값으로 바꾸어 줌으로써 User program을 실행시킨다.

User Memory

Process(또는 thread)가 진행되는 동안 실행되는 instruction 중 일부는 특별한 권한이 있어야만 실행할 수 있도록 되어있다. 이를 Privileged Instruction 이라고 한다. 이러한 instruction은 kernel(ring0)만 실행될 수 있고 user(ring3)는 실행할 수 없다. 이는 하드웨어가 가장 높은 권한을 가지고 있으며 하드웨어가 kernel만 해당 instruction을 실행할 수 있도록 정해두었기 때문에 그렇다. 하드웨어는 code를 실행할 때 해당 segment에서 권한을 표시하는 특정 bit를 확인하고 cpu의 mode bit를 설정한다. 그리고 이 mode bit에 따라서 instruction을 수행할지 말지 결정한다.

User는 Previleged Instruction을 직접 수행할 수 없지만 때로는 해당 instruction들이 실행되어야 한다. 예를 들면 디스크에서 파일을 읽고 쓰거나 자식 프로세스를 생성해야하는 경우 등이 있다. 이를 위해 운영체제는 사용자를 대신하여 kernel이 이 instruction을 수행할 수 있도록 system call을 지원한다.

X86 Architecture에서 system call은 일반적인 exception과 동일한 방식으로 동작하였다고 한다. 이 일반적인 방식이란 exception이 먼저 발생하고 exception vector table에서 해당되는 handler를 찾아 실행되는 방식이다. 이와 다르게 X86_64 에서는 syscall이라는 instruction을 지원하여 user가 system call을 호출하면 trap이 발생하고 바로 syscall handler로 진행되도록 한다.

User가 System call을 호출하여 인자를 넘겨주면 kernel에서는 해당 인자가 유효한지 확인해야한다. 특히 들어온 인자가 virtual address라면 해당 주소가 유효한 주소인지 (kernel 영역을 접근하고 있지는 않은지, NULL을 넘겨준 것은 아닌지, User에게 할당된 영역이 맞는지) 반드시 확인한 후 해당되는 함수를 진행해야 한다.

System Calls

운영체제는 부팅할 때 system call이 호출되면 어떠한 instruction들을 수행한 뒤 handler 함수를 진행하도록 하드웨어를 설정한다. 이후 user program이 실행되고 user program에서 system call을 호출하면 하드웨어는 설정된 instruction들을 수행하고 system call handler를 실행한다.

PintOS에서는 syscall 호출시 syscall_entry.S에 작성된 instruction을 먼저 수행한다. 이는 tss로부터 저장된 kernel stack에서의 stack pointer를 가져와 rsp에 세팅하고, kernel stack으로 이동하여 user mode에서 실행되던 context를 stack에 interrupt frame 형식으로 쌓는다. 그리고 마지막 rsp의 값(if를 가리키는 주소)를 rdi에 저장하고 handler 함수로 이동함으로써 함수의 인자로 if를 전달한다.

System call handler에서는 인자로 들어온 if의 rax값을 확인(syscall을 수행하기 전에 syscall number를 rax에 저장하기 때문)하여 해당되는 syscall 요청에 따라 함수를 수행한다. 인자로 들어온 값들이 정상적이라면 syscall number에 따라 요청받은대로 작업을 진행한 뒤 if의 rax에 return 값을 setting하고, if을 인자로하여 do_iret함수를 호출함으로써 syscall을 호출한 user에게 해당되는 return값을 돌려주게 된다. 이로써 system call이 완료된다.

System call interface에는 exit, wait, exec, fork 등의 process 관련 함수들과 open, read, write, close 등의 file system 관련 함수들이 존재한다. 이들 중에서도 필자가 느끼기에는 fork가 가장 system call 동작 방식을 이해하기에 적합하다고 느꼈다.

Fork system call은 fork를 호출한 process와 동일한 자식 process를 생성하는 함수이다. 특이한 점은 return을 두 번 한다는 점이다. 부모에게는 자식의 pid(tid)를 return하지만 자식에게는 0을 return 한다. 이로써 부모와 자식에 따라 다른 code를 실행하도록 분기할 수 있다. 그렇다면 kernel은 fork를 어떻게 처리해야하며, 어떻게 해야 두 번의 return을 진행할 수 있을까?

우선 user가 fork를 호출하면 다른 system call과 동일하게 trap이 발생된 뒤 kernel mode에서 syscall handler가 실행되고, syscall number가 저장된 if의 rax의 값에 따라 해당되는 함수가 실행된다. 실행된 함수에서는 들어온 인자(fork의 경우 user에서 자식 process의 name을 인자로 전달함)가 유효한지 확인하고, 유효하다면 fork를 진행한다.

우선 부모 process의 kernel mode에서, 자식 process를 생성하기 위해 실제 fork를 진행하는 함수와 user context가 담긴 if를 인자로하여 thread를 create한다. 이때 create을 진행하면서 생성되는 자식 thread를 부모 thread의 자식 리스트에, 그리고 부모 thread를 자식 thread의 부모 필드에 저장한다. 또한 부모는 자식 process가 fork를 마치기까지 기다려야하므로 자식 thread의 fork_sema를 0으로 초기화한다. 자식 thread의 create을 마치면, 부모 process는 자식 thread의 fork_sema를 sema down하여 자식 process가 fork를 마치고 신호를 줄 때까지 대기한다.

자식 thread가 schedule되면 본격적으로 부모 process를 fork한다. 여기서 중요한 점은, fork의 대상은 fork를 호출한 부모 process의 user관련 context라는 점이다. 부모와 동일한 process를 생성한다고 하면 kernel mode에서 실행되던 context까지 전부 동일해야 할 것 같지만, 사실 user mode로 실행되던 context만 동일하게 만들면 되는 것이다(자식 thread가 schedule 되어 실행되는 순간부터 이미 부모와 자식은 다른 kernel context를 실행하고 있다). 이러한 점에서 fork가 어떻게 부모와 자식에게 다른 return값을 전달하게 되는지 의문이 풀리게 된다.

자식 thread는 thread create시 인자로 전달된 함수와 인자로 fork를 진행한다. 부모 process의 user if를 kernel stack에 복제하고 가상 메모리 공간과 메모리들을 모두 복제한다. 또한 부모의 file descriptor table과 file table들을 그대로 복제하여 자식 process의 그것들에 setting 한다. 이러한 일련의 작업들이 성공적으로 진행되면 자신의 thread에 있는 fork_flag를 갱신하고 fork_sema 를 sema up하여 fork가 완료되기를 기다리는 부모 process를 깨워준다. 마지막으로 부모로부터 복제했던 if의 rax값을 0으로 setting한 뒤 do_iret을 실행하여 user에게 return하게 된다.

Sema down하고 기다리고 있었던 부모 thread가 schedule되면 자식의 fork_flag를 통해 fork가 정상적으로 이루어졌는지 확인하고, 정상적이라면 자식의 pid값을 if의 rax에 담고 do_iret을 실행하여 user에게 또한 return 한다. 이로써 부모와 자식은 kernel mode의 각각 다른 위치(부모는 system call handler, 자식은 do_fork)에서 if - rax 값을 setting하고 return하였지만 user process는 동일한 fork를 실행한 결과로 각각 다른 return 값을 받게 된다.

Process Termination Messages

User process가 자식 process를 생성하면 부모 process는 자식 process를 청소할 의무(?)가 생긴다. 부모 process가 만일 자식 process보다 먼저 종료되면 자식 process는 실행하지도 종료하지도 못하는 상태(좀비 process)가 되기 때문이다. 따라서 부모 process는 어느 시점에서 자식 process가 termination 되기를 wait 한다.

자식 process의 user program이 main함수에서 0을 return하거나 exit(0)을 호출하면 exit system call이 실행된다. 그 결과로 kernel mode에서는 user program을 위해 사용되었던 file descriptor table과 file table, 가상 메모리 공간 등을 모두 청소하고 exit여부와 exit status를 저장하며 자신의 exit_sema를 sema up한 뒤 다른 thread를 schedule함으로써 process를 종료한다.

자식 process를 wait하던 부모 process가 schedule 되면 자식이 종료된 것을 확인하고 자식 thread를 청소하며 자식의 exit status를 if - rax에 저장한 뒤 user에 return한다.

PintOS는 termination message를 통해 자식 process의 exit과 부모 process의 wait이 정상적으로 작동되는지 확인한다. 하여 해당 chapter에서는 exit system call에서 exit되는 thread name과 exit status를 출력하도록 구현한다.

Denying Writes to Executables

User Program이 load될 때 loader는 실행파일을 open하고 ELF 정보를 읽어 실행시키는데 필요한 segment를 memory로 load한다. 이후에 기존에 구현되어있는 PintOS에서는 해당 file을 close하고 program을 실행시키도록 되어있다. 그러나 파일이 실행되는 중간에 코드가 변경되는 등의 파일 수정이 발생하면 예상치 못한 상황이 생길 수 있기에 실행되고 있는 파일은 수정될 수 없도록 보호할 필요가 있다.

File을 open하면 file system은 file로부터 metadata를 inode 구조체 형식으로 읽어온다. 그리고 이 inode를 가리키며 파일을 읽거나 쓰는 위치를 가리키는 offset pointer를 갖는 file 구조체를 만든다. Kernel은 process마다 file의 pointer를 저장하는 배열을 만들어 관리하며, 이것을 file descriptor table이라 하고 이 table의 file을 구분할 수 있는 구분자 index를 file descriptor라고 한다.

inode는 모든 process를 통틀어 동일한 file이라면 한 개만 생성된다. 즉, 모든 process는 동일한 file에 대해 유일한 inode를 갖는다(== 다른 process가 수정하면 모든 process에서도 수정된다 == inode는 공유자원이다). 이 inode의 member중에 하나(deny_write_cnt)가 파일을 수정할 수 있는지의 여부를 저장한다. 값이 0이면 수정 가능하며 1이상이면 수정이 불가하다. 대표적인 파일 수정 interface인 write함수에서도 이 값을 확인하고 수정이 가능할 때 수정을 진행하는걸 확인할 수 있다. 이렇듯 파일의 수정여부를 inode에 저장하며 inode는 공유자원이므로 해당 값을 1 이상으로 변경함으로써 다른 process로부터 file이 수정되는 것을 막을 수 있다.

File system은 이러한 값을 변경할 수 있도록 파일의 수정을 막기위한 file_deny_write와 파일의 수정을 허용하는 file_allow_write interface를 제공한다. 추가로 file을 닫는 file_close는 file_allow_write를 내장하고 있다. 따라서 program load시 file open 직후 file의 수정을 막도록 조치하고 file을 close하지 않은 상태로 유지한 뒤, program 종료시 해당 file을 close 함으로써 실행중인 파일이 수정되는 것을 막을 수 있다.

회고

지난 Project에서는 kernel에서 일어나는 일만 다루다가 user program으로 넘어오면서 헷갈리고 어려운 부분들이 많이 있었다. 쓰레드는 어디에 위치하는 것이며 지난주부터 등장했던 인터럽트 프레임은 도대체 어디에 쓰이는 것인가... 가상메모리 영역에도 스택이 있는데 커널 쓰레드에도 스택이 있고 그럼 rsp는 대체 어딜 가리키고 있는 것인가... 처음에 이런 질문에 부딪히면서 골치아프고 힘들었지만, 이 의문들이 해소되고나서는 이후의 문제들은 어렵지 않게 풀어갈 수 있었던 것 같다. 위에서 그런 내용들을 잘 정리해두긴 했지만, 들었던 의문점들에 대해 다시한번 정리해보려 한다.

1. 쓰레드는 어디에 위치하는 것인가? 지난 Project에서도 thread를 다루었는데 그럼 kernel의 일을 하는 thread가 있고 User program을 위한 thread가 따로 있는 것인가? 그럼 User program을 위한 thread는 user의 가상메모리 영역에 있는 것인가??? -> (실제 linux 등의 운영체제는 다르겠지만 PintOS에서는) 커널의 일을 하기위한 쓰레드가 따로 존재하는건 아니다. 지난 Project에서는 테스트를 위해 여러개의 쓰레드를 만들고 sleep 시키는 등을 했지만, 실제로는 PintOS가 부팅될 때 main thread를 만들고 main thread에서 User program을 실행시키기 위한 쓰레드를 만든다. 물론 timer, disk, syscall등을 initialization하지만 이들을 위한 쓰레드가 따로 있는 것은 아니다. User process에서 interrupt나 system call과 같이 kernel의 권한으로 실행되어야하는 instruction이 있을 때 동일한 thread 내에서 user mode에서 kernel mode로 이동되며, 이때 kernel에서 준비된 code들을 실행하게 되는 것이다. -> User program을 위한 thread는 기존에 thread가 생성될 때 그러하였듯이 page allocator에 의해 동일한 kernel영역에 만들어진다. Kernel mode로 code가 진행될 때에는 이 kernel영역에 있는 thread 내의 stack을 사용한다. 그래서 kernel-user mode 전환시 interrupt frame이 쌓이는 곳도 바로 이 stack이다. User mode에서 user code가 진행될 때에는 user를 위한 가상메모리 영역의 stack을 사용한다. 멀티쓰레딩이 가능한 OS에서는 이 user stack영역을 thread마다 할당하여 나누어 사용하지만, PintOS에서는 One Process-One Thread이기 때문에 user stack영역은 따로 나누어지지 않고 해당 process가 전부 사용한다. 멀티쓰레딩이 가능한 OS의 경우 하나의 kernel thread에 여러개의 user thread가 매칭될 수도 있고, 여러개의 kernel thread가 여러개의 user thread에 매칭될 수도 있다.

2. 도대체 인터럽트 프레임은 무엇인가? 인터럽트 발생시 정보를 담고있는 구조체? 그렇다면 왜 register 정보를 담고있는거지? 어디에 사용되고 있는건가?? -> 기본적으로 인터럽트 처리를 위해 사용되는 frame이 맞다. Frame 안에 있는 vec_no 로 해당 interrupt가 어떤 interrupt인지 판단하고 interrupt handler를 가리키고있는 vector table에서 해당 interrupt를 해결하기 위한 handler가 실행되도록 할 수 있다. 이 외에도 interrupt를 처리한 뒤 interrupt가 발생하기 전의 context로 돌아갈 수 있도록 해당 context를 저장하는 역할을 한다. Interrupt 발생시 intr_stubs.S의 intr_entry가 실행되어 rsp를 user stack에서 kernel stack으로 이동하며 kernel stack에 현재 register를 interrupt frame형식으로 저장한다. Interrupt handler 진행이 완료되면 interrupt frame에 저장되어있는 context를 다시 cpu로 restore시켜 기존의 user program context로 돌아갈 수 있게 된다. -> 하지만 이 interrupt frame은 이 외에도 가능한 context switching에서 사용된다. System call 발생시에도 동일한 방법으로 kernel-user mode간에 전환이 일어난다. 또한 schedule에 의한 thread간의 switching에서도 interrupt frame이 사용되는데, 이 때에는 user program의 context가 아닌 kernel mode에서의 context가 필요하므로(schedule은 timer interrupt의 handler처리 후 종료시점에서 일어나거나 system call 처리 중 sema down/up하는 경우 등 kernel mode에서만 발생함) thread의 tcb에 구성해둔 interrupt frame을 사용하여 switching 전 thread의 context를 저장하고 switching 대상 thread의 interrupt frame을 restore하여 switching하게 된다.

이번 Project에서는 code가 어떻게 진행되는지 이해하기 위해 assembly 언어를 이해할 필요성을 많이 느꼈다. 기계어와 맞닿아있는 부분이라 많이 어렵지만 확실히 assembly를 이해하려고 노력하다보니 어떠한 방법으로 운영체제가 user program을 실행시키고 요청사항을 처리해주는지 잘 이해할 수 있었다.

Alarm Clock

Interrupt는 Hardware에 의해 발생한다. (division by zero 같은 경우 제외) 컴퓨터에서의 시간은, Timer Hardware가 특정 시간동안 특정 Frequency로 보내는 Interrupt를 Count하는 방식으로 계산된다. PintOS 에서는 Timer Hardward에 의해 1초에 100번씩 Timer Interrupt가 발생되며, 이때마다 전역변수로 선언된 ticks를 1씩 올려줌으로써 시간을 계산한다.

Timer Interrupt Handler는 다양한 일을 수행한다. 단순하게 ticks를 올려주어 시간 계산을 할 수 있을뿐만 아니라, 이에 따라 각 프로세스의 동작 시간을 계산할 수 있으며, 현재 진행중인 thread가 cpu를 점유하고 있는 시간을 계산하여 스케쥴링을 하기도 한다.

(PintOS에서)1초에 100번 Interrupt Handler가 작동한다는 것이 사람의 생각으로는 굉장히 자주 handler가 작동되는 것 같아보여서 다른 일은 언제하나 싶어보인다. 하지만 10ms라는 시간은 컴퓨터에게는 굉장히 긴 시간인 듯 하다. 생각해보면 그 느리다는(상대적으로) 파이썬으로 알고리즘을 풀어도, 잘 짠 코드는 코드를 수행하는데 1ms가 채 안걸린다. 따라서 10ms마다 interrupt가 발생하고, 짧은 시간을 계산하여 다양한 process나 thread를 scheduling함으로써 동시에 많은 일을 처리하도록 할 수 있다.

Priority Scheduling

Round robin (RR) 방식의 Scheduling이란 ready queue에 작업이 들어온 순서대로 작업을 처리하는 방식이다. 초기 PintOS는 RR방식으로 구현되어있다. 하지만 현실은 중요한 작업들이 있고 상대적으로 덜 중요한 작업들이 존재한다. 그래서 우선순위priority를 고려한 Scheduling이 필요하다.

PintOS는 thread를 통해 동시성을 구현하고있다. Process는 각각의 Virtual Memory(VM) 영역을 가지지만, Thread는 Process의 VM영역 안에서 만들어지는 것으로 Process의 VM을 공유하고 있다. 이때 문제가 되는 것이 공유자원이다. Thread는 VM을 공유하기 때문에 VM의 stack, heap 등에 접근할 수 있다. 문제는 동시적(실제로 동시에 일어나지는 않으나, 아주 짧은 시간 간격을 두고 스케줄링함으로써 구현되는)으로 작업이 이루어지다보니, 여러개의 Thread가 동일한 data에 접근을 하면 data가 잘못 변경될 수 있는 것이다. 이를 해결하기 위해 semaphore, lock, monitor(condition variables) 등의 기법이 사용된다.

Priority Scheduling은 높은 우선순위의 작업을 우선 진행하여 작업의 효율성을 높인다. 하지만 공유자원을 관리하기 위해 semaphore 등이 도입된 경우 문제가 발생한다. 낮은 우선순위의 thread가 semaphore를 보유하였으나 이후 높은 우선순위의 thread가 동일한 자원에 접근하는 경우 해당 semaphore를 보유할 수 있을 때까지 해당 thread는 block 상태가 되는데, 어중간한 우선순위를 갖는 thread가 ready queue에 있을 경우 semaphore를 보유한 thread보다 이 thread가 먼저 scheduling되어 높은 우선순위의 thread가 장기간 대기하게 되는 경우이다. 이런 상황을 Priority Inversion Problem 이라고 한다. 이 경우는 높은 우선순위를 가진 thread가 필요한 semaphore를 보유하고있는 thread에게 자신의 priority를 임시로 빌려줌으로써 해결할 수 있으며 이를 Priority Donation이라고 한다.

Advanced Scheduling (mlfqs)

위 단계까지는 priority가 thread가 생성될 때 초기화되고 변하지 않는 경우였다. 하지만 현실은 시간이 지남에 따라 각 thread는 특성이 변할 수 있다. 실시간 응답이 필요하여 우선순위가 높았던 thread가 어느 순간에는 입출력이 필요하여 우선순위가 낮아질 수 있다(입출력은 상대적으로 많이 느린 작업이므로). 또한 priority가 변하지 않는 기존 방식에서는 높은 우선순위의 thread가 계속 투입되면 낮은 우선순위의 thread는 진행이 필요함에도 불구하고 진행되지 않을 수 있다. 이러한 점을 개선한 방식이 mlfqs(MultiLevel Feedback Queue Scheduling)이다.

mlfqs 방식은 우선순위 level에 따라 queue를 따로 두어 thread를 관리한다. 또한 모든 thread의 우선순위는 정해진 시간마다 재계산된다. 우선순위가 재계산 되는 방식은 다양하게 있지만, PintOS에서는 4.4BSD 방식(?)을 사용한다. 우선순위는 최근에 CPU를 점유한 정도를 나타내는 recent_cpu와 1분당 cpu에서 진행된 평균 process수를 의미하는 load_avg를 활용한 수식으로 계산된다. 이를 통해 우선순위가 낮아 진행되지 못하던 thread들도 골고루 scheduling되어 진행될 수 있게 된다. 또한 한 thread가 CPU를 오래 점유하지 않도록 scheduling하기 위해 특정 시간마다 해당 thread의 우선순위를 재계산하며(PintOS에서는 4ticks, 즉 40ms마다), thread의 특성 변화에 따라 골고루 scheduling하기 위해 특정 시간마다 load_avg와 전체 thread의 recent_cpu, priority를 재계산한다(PintOS에서는 1초마다).

회고

가장 어렵다는 PintOS를 시작하며 궁금했던 OS를 깊게 공부하고 이해할 수 있다는 점에서 기대가 많이 되었지만 한편으론 얼마나 어려울까싶어서, 그리고 정글 프로그램안에서는 첫번째 협업이라 덜컥 겁이 났었다. 하지만 팀원들과 협업하면서 결국 이번 주차의 목표치를 온전히 이루었을뿐만 아니라, 많은 부분을 배울 수 있었고 일주일 전보다 훨씬 성장할 수 있었다.

이번 프로젝트는 여러가지 면에서 너무나 성공적이었다.

첫번째. Teamwork이 좋았다

여러모로 Teamwork이 좋아서 synergy가 잘 났다. 모두가 프로젝트를 끝까지 완성하고자하는 욕심이 있었고, 직접 코드를 구현해보고자하는 욕심이 있었다. 그렇기에 각 단계마다 deadline을 정하여 각자 공부하고, 구현할 코드를 할당하고, 실제 구현하고 debugging하는 모든 과정에서 버거울 수도 있었지만 모두 열심을 가지고 해낼 수 있었다. 또한 앎에 대한 욕구가 모두에게 있었다. 누구 한명이 이해되지 않는 부분을 공유하면 함께 고민하고 googling하고 코드를 파고들어서 결국은 알아내어 함께 깨달음의 기쁨을 나누었다.

두번째. 협업 Tool을 잘 활용했다

두가지 tool을 활용했다. 과제를 공유하고 업무(?)를 나누고 각 단계를 마친 후 회고를 기록하기위해 notion을 활용했다. 실시간으로 서로가 작성하는 내용이 공유되기에, 서로의 업무 진행상황을 파악하기 수월했고, 각자가 구현한 코드를 공유하여 코딩중에 참고할 수 있었다. 작업을 관리하기 위해 git을 활용했다. 잘 구현된 코드, 개발중인 코드, 그리고 각자 구현중인 코드 파일들을 분리하여 관리하기 위해 master branch외에 thread/main branch(thread단계 메인branch), thread/dev branch(thread단계 개발진행용 branch), thread/* branch(팀원들의 각 branch) 를 나누어 관리하였다. 또한 각 기능단위로 각자 구현이 완료되면 PR(Pull Request)를 하고 함께 코드를 리뷰하여 수정이 필요한 부분들은 바로바로 수정하였다. 이러한 방법으로 debugging 시간을 크게 줄이는 등 작업의 효율을 높일 수 있었으며, 본인이 직접 구현하지 않은 코드에 대한 이해도도 높일 수 있었다.

세번째. 다른 사람들의 코드를 참고하지 않고 끝까지 구현했다

물론 어느정도 자료들을 찾아 solution을 참고하기는 했지만, 도저히 debugging이 어려운 상황이거나 과제가 이해되지 않는 경우가 아니라면 다른 사람들의 코드를 참고하지 않고 직접 구현했다. 직접 구현했기에 test case가 통과되었을 때 이루말할 수 없는 기쁨을 느꼈다. 또한 debugging 상황에 부딪히면서 각자의 개선점을 알게되고 개선할 수 있었으며, 해낼 수 있다는 자신감도 더 생길 수 있었다.

네번째. OS에 대해 이해가 조금은 생겼다

과제와 함께 제공된 git book과 keyword googling, 그리고 PintOS관련 ppt자료 등을 참고하고, PintOS에 이미 구현되어있는 코드를 이해한뒤 필요한 부분을 구현하는 방식으로 과제를 진행했다. 이 과정에서 컴퓨터에서는 시간이 어떻게 흐르며 어떻게 작업이 scheduling되는지 등 전체적인 흐름에 대해서 어느정도 이해할 수 있었다. 관련된 내용들을 deep하게 공부하기에는 시간이 부족했기에, 구현하는데 필요한 지식들 위주로 공부하고, 구현하는 과정에서 부딪히는 문제들에대해 고민하고 퍼즐을 맞춰가면서 이해도를 높였다(마치 BFS 알고리즘처럼 너비우선으로). 그래서 더 재미있고 속도감있게 과제들을 진행할 수 있었다.

이 부분에선 한편으론 아쉽기도 했다. 전체적인 흐름을 이해할 수 있는 점은 좋았지만, 더 개념적으로 깊이 공부하지 못한 부분이 너무 아쉬웠다. 물론 시간이 한정적인 자원이기에 앞으로도 이번과 같은 방식으로 진행해나가야 하겠다고 생각하지만, 가능하다면 조금 더 개념을 잡고 진행할 수 있다면 좋을 것 같다.

또한 개인적으로 느낀 점도 있었다.

1. 문제를 잘 정의하는 것이 이해도를 높인다. (내가 뭘 모르는걸까?)

이번 과제를 진행하면서 내 강점이라고 느낀 부분이 있었다. 나는 퍼즐이 맞추어지지 않으면 찝찝하고, 찝찝함이 남아있으면 진행이 되지 않는다. 그래서 찝찝한 부분을 해결하기 위해 필요한 부분을 파고들고, 고민하고, 사람들과 공유한다. 이러한 점이 문제를 명확하게 정의하게 하고, 이 이해를 바탕으로 코드를 빠르게 작성할 수 있게 한다. 내가 어느 부분에서 찝찝함이 남아있는지, 무엇을 모르는 것인지 고민하고 생각해내는 능력이 강점으로 작용하는 것 같다.

2. 협업의 중요성. 나 혼자 할 수 있는 일보다 훨씬 빠르게 더 많은 일을 할 수 있다.

협업은 어렵다. 살아온 인생이 다른 사람들이 모여 일을 나누어 해야하기 때문이다. 하지만 함께 문제를 이해하고 각자가 해야할일을 적당히 분담하고 필요에따라 충분히 소통이 이루어질 때 협업은 엄청난 힘을 발휘한다.

혼자 많은 줄의 코드를 모두 작성하려고 했다면 시간이 오래 걸렸을 뿐만 아니라 하나하나의 코드를 집중해서 작성하기 어려워 많은 debugging 요소가 발생했을 것이다. 또한 이 요소들은 발견하기 어려워 시간이 부족해졌을 것이다. 하지만 팀원들과 구현부들을 나누었기에 각자의 구현부에 집중할 수 있었고, 각자 더 깊이 이해하고 공유하여 모두가 더 깊이 이해할 수 있었다. 또한 코드리뷰를 통해 많은 debugging 요소들을 사전에 처리할 수 있었다.

일주일간 정말 많이 성장했다. OS를 배우는 것도, 과제를 진행하는 것도, 팀과 협업하는 것도 너무나 즐거웠고 의미있었다. 그렇기에 앞으로의 PintOS가 더욱 기대된다. 여전히 두려움이 있지만 이 기대감을 계속 유지해서 끝까지 해내고싶다.

UNIX I/O - file discriptor, file table, system call (Robust IO) Socket Interface Network Layer - LAN, WiFi, 5G ... -> IPv4, IPv6 -> TCP, UDP -> http, ssh, and so on

7주차 회고

cache가 적용된 proxy 구현 과정에서

LRU policy 캐싱에 대해서 우선순위 관리가 어려운 부분

• 구현한 방식은 캐시를 list로 관리하고 캐시블럭 안에 priority를 저장함. 새로운 요청에 대해 캐싱하기 위해 낮은 우선순위의 블럭을 찾을 때 항상 선형탐색을 해야한다는 단점. 그리고 캐싱된 블럭을 찾아 바로 요청에 응답할 수 있는 상황이라면 해당 블럭의 priority를 높여주어야 하는데 이 priority 또한 공유자원이라 수정하기 어려운 점이 있었음.

• 큐(Queue)를 사용해서 가장 낮은 우선순위는 항상 front에, 높은 우선순위는 항상 rear에 붙여넣는다면 해결될 것 같음. 우선순위 낮은 캐시블럭 찾을땐 popleft하면 끝나고, 우선순위 높은 캐시블럭은 항상 오른쪽에 있어서 관리가 쉬워질 것 같음. 또한 read 될 때마다 해당 블럭을 빼내고 (나머지들끼리 연결해주고) 맨 오른쪽에 붙여주기만 하면 됨. 이 때 cache queue의 순서를 수정하기 위한 qMutex, 캐시블럭을 읽고 수정하기 위한 wMutex, readCnt를 수정하기 위한 rcMutex 필요할 듯. 구현해보고 싶었으나 시간이 없어서 pass...

컴퓨터 시스템 스터디

몇 주간 진행되었던 컴퓨터시스템(CS:APP) 스터디 어렵지만, 살아오면서 궁금했던 것들이 깨달아져 퍼즐이 맞춰졌을떄 오는 기쁨, 유레카!

이번 주차는 동적 메모리를 할당하는 Malloc과 free를 구현하면서 가상메모리와 동적할당에 관해 공부했다.

간단하게 정리하면, 각 프로세스마다 독립된 가상메모리를 갖는데 이 안에는 실행할 code가 들어있는 .text 영역과 초기화된 전연변수가 들어있는 .data, 초기화되지 않은 전역변수가 들어있는 .bss, 함수의 매개변수와 지역변수 등을 저장하는 user stack, 그리고 런타임에 생성되는 변수나 구조체 등이 저장되는 heap 영역 등으로 구성된다. 이 영역들 중에서 heap영역을 확장하고 필요한 만큼 메모리를 할당해주는 함수가 바로 malloc 이다.

malloc은 힙의 영역 상태와 인자로 들어온 사이즈에 따라 필요하다면 시스템콜 함수를 호출하여 힙을 확장하고 메모리를 할당하여 해당 메모리의 첫번째 포인터를 void *형으로 반환해준다. 프로그래머는 malloc을 통해 메모리를 할당받아 사용하고, free를 호출하여 메모리를 반납함으로써 불필요한 메모리 낭비를 피할 수 있으며, 특히 프로그램을 짤 때는 크기를 알 수 없으나 런타임에야 알 수 있는 경우 (예를 들면 배열 길이) malloc을 사용함으로써 쉽게 해결할 수 있다.

주의할 점은, (1) 메모리 누수를 막기 위해 할당받은 메모리 사용이 완료된 경우 반드시 free로 반납해주어야하며, (2) 반납한 메모리영역을 저장하고 있는 변수는 잘못된 접근을 방지하기 위해 NULL값으로 변경해주어야한다.

malloc의 구현방식에는 여러가지가 있는데, 이들은 가용리스트를 관리하는 방식에 따라 나뉜다. 여기서 가용리스트란, 시스템콜을 통해 확장한 힙 영역 중 할당하지 않은 영역을 의미한다. 메모리 할당을 관리할 때에는 두가지 인자를 중요하게 여기는데, 한가지는 Throughput(할당완료까지 걸리는 시간이 짧아야함)이고 다른 한가지는 utilization(메모리 활용도: 내부단편화와 외부단편화가 적어야함)이다. 가용리스트를 관리하는 방식에 따라 이 두가지 인자가 달라지게 된다.

이번 구현에서 고려한 방식들은 아래와 같다. implicit free list : 묵시적 가용 리스트. 메모리 블럭의 header와 footer에 해당 블럭의 사이즈와 할당여부를 표현하는 bit를 넣고, 모든 블럭을 탐색하면서 할당가능한 영역을 찾는 방식. 가용리스트를 따로 만들지 않고 전체를 탐색하면서 확인하기 때문에 묵시적 리스트임. explicit free list : 명시적 가용 리스트. 가용한 블럭들에 대해서 predeccesor와 succesor를 가리키는 포인터를 저장하여 연결리스트로 만들고, 메모리 할당 요청시 이 연결리스트를 탐색하여 가능한 블럭을 찾는 방식. segregated free list : 가용 블럭들의 사이즈에 따라 클래스를 나누고 각 클래스마다 오름차순으로 정렬된 연결리스트로 관리하여, 메모리 할당 요청시 필요한 사이즈 클래스부터 큰 사이즈 클래스 순으로 탐색함으로써 first fit으로 best fit이 가능하도록 구현한 방식. buddy system : 외부단편화를 해결하기 위한 방식으로, 모든 블럭은 2의 k승의 사이즈로 할당함. 따라서 사이즈 클래스 또한 2의 k승인 사이즈로 나누어짐.

회고

이번 주차는 시간이 부족하여 모든 과제를 완료하지는 못하였다. 가장 간단한 implicit은 교재를 참고하고, 이후에 explicit과 segregated는 내용을 이해하고 코드는 직접 고민해서 작성하였는데, 이 과정에서 디버깅이 꽤 오래 걸리기도 하였고, 내용을 완전히 파악하지 않은 상태에서 구현하였는데 점수가 생각보다 낮아서 보니 코드를 바꿔야 하는 부분도 생겨서 시간이 더 걸렸다. 그래서 결국 buddy system까지는 구현해내지 못했다.

buddy system을 구현하지 못한 점은 아쉬웠지만, segregated 방식을 스스로 이해하고 구현했다는 점에서 뿌듯함을 느꼈다. 특히 throughput이 잘 나오지 않아 연산을 줄이기 위해 비트연산을 사용하는 방식을 생각해내고 구현했는데 눈에 띌 정도로 결과가 나아져서 정말 기분이 좋았다.

이번 주차부터는 OS프로젝트에 들어가기에 앞서 C언어를 익히고 ubuntu 환경에서 RBtree와 malloc, 그리고 proxy 서버를 구현한다. 그 첫번째로 Red-Black Tree라는 자료구조를 공부하고 구현하였다.

C언어는 일반적으로 사용하는 프로그래밍 언어 중 가장 기계어수준에 가까운 언어로, 알고리즘 공부에 사용했던 파이썬에 비해 작성이 까다로운 언어이다. 변수를 선언하거나 함수를 작성할때 자료형을 반드시 입력해주어야하는 점이 그러하고, 특히 포인터를 사용한다는 점이 그러하다. 아주 예전에 C를 처음 접했을때 포인터를 잘 이해하지 못했던 기억이 있어서 먼저 포인터에 대해서 확실하게 잡고가려고 노력했다. 그 결과 RBtree 구현 과정에서 어렵지 않게 이해하고 구현할 수 있었으나, 그럼에도 작은 실수들이 있었고 디버깅하는 과정에서 조금씩 더 포인터와 가까워 질 수 있었다.

RBtree를 공부하면서 들었던 생각 중 하나는 스스로 짜임새있는 프로그램을 문제없이 구현하는 것이 너무 어렵다는 점이었다. 실제로 RBtree라는 자료구조와 구현 과정을 공부할때 여러 동영상 강의와 블로그, 알고리즘 서적을 보면서도 이해가 쉽지 않았고 이해하고도 스스로 코드를 작성하기엔 버거워서 pseudo-code를 참고하면서 작성하였는데, pseudo-code가 없었다면 훨씬 더 오랜 시간이 걸렸을 것 같다. 아무래도 이 부분은 아직 지식과 경험이 부족한 이유일 것이라고 생각이 되며, 앞으로 계속 공부하고 많은 코딩 경험을 쌓아가다보면 복잡한 구조도 어렵지 않게 구현할 수 있지 않을까 싶다. 다른 한편으론 pseudo-code가 있어서 코드를 작성할 수 있었기에, 앞으로 직접 무언가를 구현할때에도 스스로 pseudo-code를 작성해서 구현하는 것이 문제가 발생할 확률을 줄이고 의도하는대로 잘 구현하는데 도움이 될 것이란 생각도 든다. 또한 어떤 기능을 구현하기 위해 변수와 함수들을 잘 정의하고 구조화하는 것, 즉 내가 만드는 프로그램이 어떤 방식으로 작동하는지 확실하게 이해하고 구현하는 것이 필수적이라는 생각이 들었는데, 이 또한 pseudo-code를 작성하면 자연스럽게 될 수 있을 것 같다.

아무래도 인생 처음으로 제대로 C를 사용하는 것이다보니 같이 공부하는 동기들도 오류들에 부딪혔고, 같이 머리를 맞대고 디버깅한 시간들이 있었다. 조건을 잘못 작성하거나 포인터를 잘못 쓰는 등 다양한 케이스들이 있었지만, 다른 것보다 변수명을 잘못 작성한 경우가 기억에 남는다. 변수에 오타가 있는 것은 아니지만 변수 자체를 다른 변수와 혼동하여 잘못 적은 경우였는데, 오타가 아니다보니 IDE가 잡아주지 못해 디버깅이 어려웠었다. 다양한 변수를 사용하다보니 헷갈려서 다른 변수를 적게 된 케이스로, 변수명을 지을때 이름이 길어지더라도 가능한 한 한눈에 정체를 알아볼 수 있는 이름으로 변수명을 지을 필요성이 있다는 점을 깨달았다.

C는 기계어 수준에 가까운 언어인 만큼 다루기 어려웠지만, 오히려 그래서 컴퓨터와 코드의 동작에 대해서 더 잘 이해하게 되는 것 같다. 그래서 RBTree도 (물론 어려웠지만) 재밌게 구현할 수 있었고, 다음의 커리큘럼들이 기대가 된다.

이번주에는 알고리즘 마지막 주차로 동적프로그래밍과 그리디 알고리즘을 공부했다.

동적 프로그래밍 (DP. Dynamic Programming)

동적 프로그래밍(이하 DP)이란 '한번 계산한 과정은 다시 계산하지 않는다'는 컨셉이 적용된 알고리즘이다. 재귀 알고리즘 또는 분할 정복법에서 특정한 경우에 동일한 호출이 여러번 발생하게 되는데 이는 경우의 수가 많아질 경우 걸리는 시간이 지수적으로 증가하게 된다. 이러한 경우 DP를 적용할 수 있다. 여기서 특정한 경우란 두가지 조건이 만족하는 경우이다. 먼저 최적부분구조여야 하는데 이는 분할정복이 가능한가 (큰 문제를 작은 문제로 나눌 수 있는가)를 의미한다. 그리고 작은 문제들이 동일한 문제들로써 반복적으로 해결할 수 있는 경우여야 한다. 이를 중복되는 부분문제 라고 한다.

DP는 한번 계산이 진행된 경우 결과값을 배열에 저장했다가 동일한 호출 발생시에 배열의 값을 return 함으로써 구현할 수 있다.

DP를 구현하는 방법에는 두가지가 있다. 첫번째는 하향식으로, 재귀를 이용한 방법이다. 이 경우 계산되지 않은 경우에는 계산을 진행하고, 이미 저장된 값이 있는 경우 그 값을 바로 반환해준다. 이때 계산한 값을 저장해두는 것을 memoization이라고 한다. (memoization은 DP와 별개의 개념이지만, DP를 하향식으로 구현할 경우 사용되는 방법이다.) 두번째는 상향식이며 반복문을 이용한 방법이다. 이는 작은 문제부터 차곡차곡 계산하여 DP table에 저장하는 방식이다.

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 탐욕 알고리즘이라고도 하며 항상 최선의 선택을 하여 최적해를 구하는 방식이다. 그리디 알고리즘은 반드시 최선의 선택만으로도 최적해를 구할 수 있다는 근거가 있는 경우에만 사용가능하다. 따라서 그리디 알고리즘을 고려할때에는 최선의 선택만으로 최적해를 구할 수 있는지부터 고민해야 한다.

회고 및 정리

DP 알고리즘 관련 문제를 해결하는 과정에서 반복적으로 어려움을 겪었다. 진행하다가 막혀서 돌아보면 계속 DP table에 무엇을 저장할 것인지 명확히 정의를 내리지 않고 있었다. 하여 DP를 적용할 경우 DP table을 어떠한 목적으로 사용할 것인지 정의를 명확히 해야겠다고 느꼈다.

이번주차까지해서 4주간의 컴퓨팅사고로의 전환이 마무리되었다. 4주간 진행하면서 느꼈던 점은 해결해야할 문제에 부딪혔을 때 먼저 문제가 어떤 문제인지 잘 정의해야 한다는 점, 어떤 알고리즘을 적용해야할지 아이디어를 생각하고 구체적인 과정을 고민한 후에 차근차근 진행해야 한다는 점이었다.

WEEK05부터는 OS프로젝트에 들어가기 전 3주간 RB트리, malloc, Proxy서버 구현을 진행한다. 두려움보다는 기대감으로 계속 화이팅 해나가야겠다.

3주차에는 그래프 탐색, DFS, BFS, 위상정렬 에 대한 내용들을 공부하였다.

트리(Tree)

노드(Node)와 간선(Edge)으로 구성된 자료구조를 트리 라고 한다. 트리는 Class로 구현할 수 있으며, 간단하게 부모노드를 key, 자식노드를 value로 한 Dict 형태나 부모노드를 index, 자식노드를 value로 한 List 형태로도 구현 가능하다. 일반적으로 노드와 노드의 연결관계를 나타내기 위해 인접리스트 또는 인접행렬을 사용한다.

이진트리란 부모노드에 2개의 자식노드가 붙어있는 형태를 말하며, 이진검색트리란 이진트리 중에서도 특정한 규칙이 있는 트리를 의미하는데, 부모노드를 기준으로 왼쪽트리는 모두 부모노드보다 작고 오른쪽트리는 부모노드보다 큰 규칙을 가진 트리를 말한다.

최소신장트리와 크루스칼 알고리즘

트리에서 노드들이 서로 연결되어 닫힌 구조가 되면 Cycle이 생겼다고 할 수 있는데, 이 싸이클이 없으면서 모든 노드들이 간선으로 연결된 경우 신장트리라고 한다. 그 중에서도, 간선들의 가중치 합이 가장 작은 경우를 최소신장트리라고 한다.

최소신장트리의 가중치 합을 구하는 알고리즘 중의 하나가 크루스칼 알고리즘이다. 크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬한 후 낮은 가중치를 갖는 두 정점(Vertex)부터 확인하며, 두 정점이 Cycle을 형성하지 않는 경우 두 정점을 잇는 과정으로 이루어진다. 두 정점이 Cycle을 형성하는지 확인하고 잇는 과정의 경우 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘은 겹치는 노드가 없는 트리, 즉 서로소인 트리를 찾고 연결하는 알고리즘이다. Find 함수는 한 정점의 부모노드를 반환하며, Union 함수는 Find 함수를 호출하여 두 노드의 부모노드를 알아낸 후 부모노드가 서로 다르다면 두 노드를 합친다. 이 과정에서 잇게되는 가중치에 대해 누적합을 구하면 최소신장트리의 가중치 합을 구할 수 있다.

# 입력
V, E = map(int,input().split())
edges = []
for _ in range(E) :
    A,B,C = map(int,input().split())
    edges.append((C,(A,B)))

# 가중치 기준 오름차순 정렬
edges.sort()

# 최소신장트리의 가중치 합 담는 변수
rst = 0

# 대표 vertex (부모) 저장
parents = [i for i in range(V+1)]

# 대표 vertex 반환 / 평탄화 함수
def find(n) :
    # 부모를 찾고 자기 자신이면 바로 반환, 자기 자신이 아니면 재귀적 호출 후 대표점 반환
    if parents[n] != n :
        parents[n] = find(parents[n])
        return parents[n]
    return parents[n]

# 합치는 함수
def union(a,b) :
    pa = find(a)
    pb = find(b)
    # print("a : %d, b : %d, pa : %d, pb : %d" %(a,b,pa,pb))
    # a와 b의 대표점이 다르면 연결안된 그래프이므로 연결, 같으면 합치지 않음.
    if pa != pb :
        # 실제 가리키는게 중요한게 아니라 연결이 되는게 중요하기 때문에 현재 것들끼리 연결일 필요가 없음. 부모끼리 한 방향으로 연결만 되면 됨.
        parents[pa] = pb
        # print("parents[%d] = %d" %(a,b))
        # print(parents)
        return True
    return False

for edge, vs in edges :
    a, b = vs
    if union(a,b) :
        rst += edge

print(rst)

DFS와 BFS

그래프를 탐색하는 대표적인 방법에는 DFS, BFS 두가지가 있다.

DFS(Depth First Search: 깊이우선탐색) 란 한 노드에 연결된 자식노드들 중 한가지의 노드를 탐색하고, 연결된 노드가 더이상 없을때까지 이 과정을 반복한 뒤에 또 다른 노드를 같은 방법으로 탐색하는 방법이다. 한 노드에서 자식노드로의 탐색하는 과정이 반복되기에 재귀함수로 구현할 수 있으며, 스택과 반복문으로도 구현 가능하다.

# 스택을 활용한 DFS 함수 구현
def DFS(start) :
    stk = [] # 탐색해야할 노드를 임시 저장하는 스택
    visit = [False] * (N+1) # 한번 방문한 곳은 다시 방문하지 않도록 방문처리하는 배열
    stk.append(start)
    while stk : # stk에 노드가 들어있는 동안 반복
        v = stk.pop()
        visit[v] = True # 스택에서 나올때 방문처리
        for i in graph[v] : # 정점에 연결된 노드들에 대하여 반복
            if not visit[i] : # 정점을 방문하지 않았다면
                stk.append(i) # 스택에 저장

BFS(Breadth First Search: 너비우선탐색) 란 한 노드에 연결된 모든 노드에 대해서 우선탐색하는 방법이다. 큐를 사용하여 구현 가능하다.

# 큐를 활용한 BFS 함수 구현
from collections import deque
def BFS(start) :
    que = deque()
    visit = [False] * (N+1)
    que.append(start)
    while que :
        v = que.popleft()
        for i in graph[v] :
            if not visit[i] :
                que.append(i)
                visit[i] = True # 큐에 넣을때 방문처리

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘이란 한 정점으로부터 나머지 정점들까지의 최단거리를 구하는 알고리즘이다. 시작점으로부터 연결된 간선 중 최소거리의 간선을 갖는 정점을 선택하고 이 정점과 연결된 정점을 이으면서 최소값을 갱신해나가는 과정으로 이루어진다. (자세한 설명은 이코테 강의 참고)

# bfs를 활용한 다익스트라 구현
distance = [INF] * (V+1) # 모든 노드로의 거리를 무한대로 초기화
def daijkstra(lv) :
    que = []
    distance[lv] = 0 # 시작점부터 시작점까지의 거리는 0 으로 입력
    heappush(que,(0,lv))
    while que :
        d, s = heappop(que) # 최소값 빼내기
        if d > distance[s] : continue # 이미 확인하여 최소값이 갱신된 경우는 pass
        for w, e in graph[s] :
            cost = d + w
            if cost < distance[e] : # 최소비용이 갱신가능하다면
                distance[e] = cost # 갱신하고
                heappush(que,(cost,e)) # queue에 넣어줌

위상정렬(Topological Sort)

위상정렬이란 방향이 있고 Cycle이 없는 그래프에서 정점들을 순서대로 나열하는 것을 의미한다. 여기서 정렬은 일반적인 정렬과 의미가 다르다. 한 노드에 대해서 들어오는 방향의 개수를 진입차수(Indegree)라고 하며 나가는 방향의 개수를 진출차수(Outdegree)라고 한다. 진입차수가 0인 노드를 queue에 넣는 과정을 반복함으로써 위상정렬을 구현할 수 있다.

# 위상정렬의 기본적인 틀
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1) # 진입차수 0으로 초기화
for _ in range(M) :
    A, B = map(int,input().split())
    graph[A].append(B)
    indegree[B] += 1 # 들어오는 방향에 노드가 있을 때마다 진입차수 1씩 증가

que = deque()

for i in range(1,N+1) :
    if indegree[i] == 0 : # 진입차수가 0이면 큐에 넣기
        que.append(i)

while que :
    v = que.popleft()
    for i in graph[v] :
        indegree[i] -= 1 # 방문할때마다 진입차수 1씩 감소
        if indegree[i] == 0 : # 진입차수가 0이되면
            que.append(i) # 큐에 넣기

이번 2주차에는 이분탐색 분할정복법 스택 큐 우선순위큐 에 대한 내용들을 공부하고 관련 문제들을 풀어보았다. 간단하게 개념 및 구현코드로 정리해보려고 한다.

이분탐색 (Binary Search)

정렬되어있는 리스트에서 원하는 값을 빠르게 찾기 위한 알고리즘으로, 리스트를 절반으로 나누고 중간에 위치한 값과 원하는 값을 비교하여 범위를 좁혀가는 과정으로 진행된다.

# while문 활용
def binary_search(arr, key) :
    left = 0
    right = len(arr) - 1


    while True :
        chk_idx = (left + right) // 2
        if arr[chk_idx] == key :
            return chk_idx
        if arr[chk_idx] > key :
            right = chk_idx-1
        else :
            left = chk_idx+1
        if left > right : return -1


# 재귀 적용
def binary_search_recul(arr, key, left, right) :
    chk_idx = (left + right) // 2
    if arr[chk_idx] == key : return chk_idx
    if arr[chk_idx] > key :
        if left > chk_idx-1 : return -1
        return binary_search_recul(arr, key, left, chk_idx-1)
    else :
        if chk_idx+1 > right : return -1
        return binary_search_recul(arr, key, chk_idx+1, right)

분할정복법 (Devide and Conquer)

문제를 2개 이상의 작은 문제로 분할하고 작은 문제들을 해결함으로써 큰 문제를 정복해내는 방법이다. 대표적인 한가지 예로 A의 N제곱을 구한다고 하면, A의 N/2제곱을 먼저 구한 뒤 이를 제곱함으로써 최종 결과를 얻을 수 있다.

# A의 B제곱을 구하는 함수
def cal(A,B) :
    # B가 1이라면 A 그대로 반환
    if B == 1 :
        return A
    # B가 짝수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱을 반환
    if B%2 == 0 :
        return (cal(A,B//2) ** 2)
    # B가 홀수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱에 A를 곱한 값을 반환
    else :
        return (cal(A,B//2) ** 2) * A

print(cal(A,B,C))

스택 (Stack)

마지막에 저장한 값을 먼저 빼내는 후입선출(LIFO: Last In First Out) 방식의 자료구조이다. 리스트의 append / pop으로 간단하게 구현할 수 있다.

# 리스트의 가장 오른쪽에 데이터를 추가
list.append()
# 리스트의 가장 오른쪽 데이터를 반환하고 제거
list.pop()

큐 (Queue)

먼저 저장한 값을 먼저 꺼내는 선입선출(FIFO: First In First Out) 방식의 자료구조이다. 리스트와 포인터를 사용한 class를 정의하여 구현할 수 있으며, deque 라이브러리를 사용하여 간단하게 구현할 수도 있다.

from collections import deque
que = deque()
# 큐의 오른쪽에 데이터 삽입
que.append(data)
# 큐의 가장 왼쪽에 있는 데이터를 반환하고 제거
que.leftpop()

우선순위큐 (Priority Queue)

가장 크거나 작은 값을 먼저 꺼내는 방식의 자료구조이다. heapq 라이브러리를 사용하여 구현할 수 있다.

import heapq
heapq.heapify(list)
# 데이터를 리스트에 최소힙 방식으로 추가
heapq.heappush(list,data)
# 리스트에서 최소값을 반환 후 제거
heapq.heappop()

heapq는 최소힙으로 구현되어있어 최대힙으로 사용하려면 -를 붙여주면 된다.

# 데이터를 리스트에 최소힙 방식으로 추가 - (-를 넣었기 때문에 pop하고 -를 붙이면 최대힙이 됨)
heapq.heappush(list,-data)
# 리스트에서 최소값을 반환 후 제거
-heapq.heappop()

정리

이번 주차에는 자료구조를 어떻게 잘 활용할 수 있을지 생각해볼 수 있었다. 문제들을 그냥 해결하려고 달려들면 어떤 개념을 어떻게 적용해야할지 감이오질 않았다. 하여 문제를 파악할 때, 어떤 자료구조와 어떤 알고리즘이 필요할지 문제정의를 잘 하고 접근해야겠다고 느꼈다.

1주차부터 4주차까지 총 4주간에는 코드의 성능과 효율을 생각하는 프로그래머로 거듭나기 위한 준비과정으로 알고리즘과 자료구조를 스스로 공부하고 백준 문제를 파이썬을 사용하여 풀면서 컴퓨터에게 일을 시키는 방법을 터득한다.

이번 1주차에는 '정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도' 와 관련된 내용들을 공부하고 다양한 문제를 풀어보았다. 그 중에서도 이해하는데 시간이 걸렸고 그만큼 성장할 수 있었던 '재귀함수'와 '완전탐색' 문제를 정리해보려 한다.

재귀함수 - 백준 9663 n-Queen

재귀함수는 일단 기본적으로 함수 안에서 자기 자신을 호출하는 방식으로 정의되는 함수를 의미한다. 예를들어 수학에서 1부터 N까지의 곱을 N!(N 팩토리얼)로 나타낸다면, 이는 N * (N-1)! 로 나타낼 수 있다. 이를 fact(N) 으로 함수를 정의한다면, 다음과 같은 코드로 정의할 수 있을 것이다.

def fact(N) :
    if N == 0 : return 1 # 재귀함수는 반드시 종결조건을 만들어주어야한다. 그렇지 않으면 무한 루프에 빠질 수 있다.
    return N * fact(N-1)

재귀함수는 학교다닐때 수학시간에 배운 점화식과도 같다. 위의 팩토리얼은 아래와 같은 점화식으로도 표현 가능하다.

- n이 0보다 클 때
a(n) = n * a(n-1)
- n이 0인 경우
a(1) = 1

학생때에는 점화식을 일반식으로 만들어야했지만 코딩할때에는 점화식을 잘 세워주기만 하면 계산은 컴퓨터가 다 해준다. 하지만 이 점화식을 잘 세우는것이 쉽지 않다.

재귀함수의 의미를 이해했다고 생각했지만 문제에 적용하려고하니 어떻게 적용해야할지 생각이 잘 나지 않았다. 특히 n-Queen 문제의 경우에 NxN 크기의 체스판에서 N개의 퀸이 서로를 공격할 수 없도록 배치하는 방법의 수를 구해야하는데, 어떻게해야 2차원의 체스판에서 퀸들이 서로의 위치를 파악하면서 자신의 위치를 찾아갈 수 있을지 감이 오지않아 결국 알고리즘 책을 보고 이해한 뒤에야 구현을 할 수 있었다.

구현한 코드와 설명은 아래와 같다.

# import
from sys import stdin
input = stdin.readline

# 가능한 퀸의 배치수 구하는 재귀함수 구현
def queen(i) :
    # 체스판의 크기 n, 가능한 배치 수 cnt, 열(column)별로 퀸을 배치한 행(row)를 기록하는 배열 c_proc
    # 대각선방향(우상향 ru, 우하향 rd)으로 배치가 가능한지를 체크하는 배열 is_chked_ru/rd
    global n, cnt, c_proc, is_chked_rd, is_chked_ru

    # n만큼 배치가 완료되면 cnt +1
    if i == n :
        cnt += 1
    # 배치 중인 경우
    else :
        for j in range(n) :
            # i열 j 행에 퀸을 놓으려 할때 해당 행에 퀸이 배치되어있진 않읂지, 대각선방향으로 배치 가능한지 확인, 불가능시 다음 j로 이동
            if j in c_proc or is_chked_ru[n-j+i-1] == 1 or is_chked_rd[2 * (n-1) - j - i] == 1 : continue
            # 배치가능할시 배열의 i열에 j행 입력 및 해당 대각선 방향 배치불가 표시
            c_proc.append(j)
            is_chked_ru[n-j+i-1] = 1
            is_chked_rd[2 * (n-1) - j - i] = 1
            # 다음 열 재귀호출
            queen(i+1)
            # i열 j행에 대한 확인 완료시 다음 행 확인 위해 리스트에서 pop 및 대각선방향 원복
            c_proc.pop()
            is_chked_ru[n-j+i-1] = 0
            is_chked_rd[2 * (n-1) - j - i] = 0


n =int(input())
c_proc = []
is_chked_ru = [0] * (2 * n - 1)
is_chked_rd = [0] * (2 * n - 1)


cnt = 0
queen(0)
print(cnt)

완전탐색 - 백준 10971 외판원순회2

완전탐색이란 가능한 모든 경우의 수를 탐색하는 것을 의미한다. 그 중에서도 외판원순회 문제는 굉장히 유명한 문제라고 한다. 완전탐색을 구현할 때 재귀함수가 잘 사용될 수 있는 것 같았다. 재귀함수를 먼저 공부하고 이해한 뒤에 이 문제를 접해서 어렵지 않게 해결할 수 있었던 것 같다.

# import
from sys import stdin
input = stdin.readline

# 0에서 출발, 모든 위치 순회 후 0으로 돌아오면 최소비용(mincost) 갱신하도록 재귀함수 구현
def salesman(v) :
    # 합계 sum, 최소비용 mincost, 방문했는지 확인하는 비트마스크 is_visited
    global sum, mincost, is_visited
    # 0으로 돌아왔고 모든 장소를 방문했을 때 mincost 갱신 (아래에서 mincost보다 sum이 큰 경우엔 추가 진행되지 않도록 선조치했음)
    if v == 0 and all(is_visited) :
        mincost = sum
    else :
        for i in range(n) :
            # i 위치가 이미 방문되었는지, v에서 i로 가는 비용이 0은 아닌지,
            # v에서 i로 가는 비용을 더했을 때 기존의 최소비용보다 비싸지진 않는지 확인
            if (is_visited[i] == 1) or (w[v][i] == 0) or ( mincost < sum + w[v][i] ) : continue
            # 문제없으면 sum에 비용 추가 및 i 위치 방문표시
            sum += w[v][i]
            is_visited[i] = 1
            # i위치 방문으로 후속 재귀호출
            salesman(i)
            # i위치 방문 끝난 후 원복
            sum -= w[v][i]
            is_visited[i] = 0

n = int(input())
w = [list(map(int,input().split())) for _ in range(n)]

is_visited = [0] * n
mincost = pow(10,10)
sum = 0

salesman(0)
print(mincost)

정리

n-Queen 문제에서 어려움을 겪으면서 앞으로의 문제 접근 방향에 대해 한가지 생각해볼 수 있었다.

문제를 뭉텅이로 해결하려고 하지 말고, 낮은 수준으로 잘게 쪼개면서 접근 할 것.

예를 들면, x,y 좌표가 있는 2차원 문제일 때 2차원으로 생각하면 접근하기가 어렵다. 따라서 x,y 따로 1차원으로 분리할 수 있을지 생각해볼 수 있다. n-Queen의 경우, 모든 행과 열에는 퀸을 하나만 놓을 수 있기에, 일단 열 방향으로 진행하면서 하나씩 퀸을 놓음으로써 '모든 열에는 하나씩만 놓을 수 있다'를 해결할 수 있다.

0주차에는 입학시험때 공부한 내용을 바탕으로 간단한 프로젝트를 진행했다. 그 중에서 로그인 구현 및 템플릿을 활용한 SSR(서버사이드 렌더링) 구현을 위해 새롭게 공부한 JWT와 jinja2에 대해 간략하게 WIL(Weekly I Learned)을 작성하려 한다.

JWT

사용자에게 서비스를 개인화하여 제공하기 위해서는 로그인/로그아웃 등의 회원관리 기능이 필요하다. JWT는 이 로그인/로그아웃 기능을 구현하는 방법 중 하나이다.

회원의 로그인 상태를 유지하기 위해서는 일단 Client에서는 로그인 되었다는 정보를 가지고 있어야 하고 Server 또한 이 사용자가 로그인에 성공했다는 정보를 가지고 있어야 한다. 여기서 Client가 가지고 있어야하는 정보는 쿠키에 저장되며, Server가 가지고 있어야하는 정보는 세션으로 저장된다. 즉, 사용자가 로그인 정보(id/pw)를 입력하여 Server로 전달하면 Server는 database에 저장된 회원의 정보와 비교하여 로그인 정보의 유효성을 판단한 후, 유효하다면 해당 정보에 대한 세션을 생성하여 저장하며 Client로 이에 매칭되는 data를 전달한다. Client에서는 이 data를 browser의 쿠키에 저장했다가 Server에 요청을 보낼때마다 쿠키를 다시 전달하고 Server에서 이 쿠키와 세션을 확인하여 로그인상태를 확인하게 된다.

이 쿠키-세션 방식은 사이트의 서버가 1개로 동작할때는 문제가 없지만 사용자가 많아져 서버가 여러개가 되면 로그인 유지에 문제가 발생할 수 있다. A,B,C 서버가 있다고 가정했을때, A서버에서 로그인에 성공하여 세션이 A서버에 생성되었을 경우 이후에 B,C 서버로 접속한다면 세션이 없어 로그인을 다시 해야하는 경우가 생길 수 있는 것이다. 이를 해결하기 위한 여러가지 방법 중 하나가 JWT 인증 방식이다. (추가로 쿠키-세션 방식의 경우 해킹의 위험성도 있다고 한다.)

JWT 인증방식의 경우 로그인 성공시 Client에서 JWT token을 가지고 있게 되며 Server에서는 Secret key를 가지고 있으나 세션 등을 따로 저장하지는 않는다. 로그인 정보가 유효하면 Server에서는 Secret key를 이용하여 JWT token을 생성하고 Client에 전달하며, Client는 이 token을 저장한다. 이후 Server에 요청을 보낼때 token을 전달하면 Server에서 다시 Secret키를 가지고 token을 decode하여 유효성을 확인하게 된다.

Python에서 JWT 인증방식을 구현하기 위해 사용할 수 있는 라이브러리는 pyjwt와 flask_jwt_xtended 가 있는데, 필자는 후자를 사용했다. flask_jwt_extended의 기본적인 사용방법은 아래와 같다. (세팅, 함수 인자 등 자세한 정보는 공식 Docs 참고)

# import
from flask import Flask
from flask_jwt_extended import *

# flask객체 생성
app = Flask(__name__)

# JWT 매니저 활성화
jwt = JWTManager(app)

# secret key 세팅
app.config.update(
    DEBUG=True,
    JWT_SECRET_KEY="JUNGLERSSPORTS",
)

# 로그인 api
@app.route('/login', methods=['POST'])
def user_login() :
    # 로그인 정보 유효성 확인 코드 생략
    # 로그인 정보 유효할 시 token 생성 후 client로 전달
    return jsonify(
                {"result": "success",
                "token": create_access_token(identity=userId, expires_delta= False)}

# 로그인이 필요한 api 접근시
@app.route('/register', methods=['POST'])
@jwt_required()
def register() :
    user = get_jwt_identity() # 로그인 상태 확인 후 user의 identity 정보 return

로그아웃 기능의 경우 쿠키에 저장된 JWT token을 지움으로써 구현하는 방법이 있고, 로그아웃 요청시 들어온 token을 blocklist에 등록하여 구현하는 방법이 있다. 아래는 blocklist에 등록하여 구현하는 코드이다.

# blocklist 생성. 중복 방지 위해 set 자료형 사용
jwt_blocklist = set()

# blocklist 기능 사용을 위한 세팅
@jwt.token_in_blocklist_loader
def check_if_token_is_revoked(jwt_header, jwt_payload) :
    jti = jwt_payload['jti']
    return jti in jwt_blocklist

# 로그아웃 처리 api
@app.route('/logout', methods=['GET'])
@jwt_required()
def user_logout() :
    jti = get_jwt()['jti'] 
    jwt_blocklist.add(jti) # 로그인 user의 jti를 blocklist에 등록

flask_jwt_extended 를 사용하여 로그인이 필요한 api에 적용할 경우 해당 api에 jwt_required 데코레이션을 적용하여 구현 가능했다. 이 경우에는 Client에서 api 요청을 보낼 때 header 부분에 Authorization으로 jwt token을 전달해주어야 한다(참고). 그런데 api로 요청하는 것이 아니라 page에 직접 접속하는 경우에는 header를 입력해 줄 방법이 없다. 공식문서에서는 jwt를 확인할 위치를 header가 아니라 쿠키로 설정해줄 수 있는 것으로 보이나 필자의 경우 적용되지 않았다. (문서를 잘못 이해했거나 쓰는 방법을 잘 모르는 걸수도...) 여기서 애를 많이 썼는데, 결국엔 함수를 추적해서 쿠키에서 token을 가져와 직접 decode 해주는 방식으로 해결했다. (사실 PyJWT를 사용했으면 발생하지 않았을 문제일수도 있다)

# import
from flask_jwt_extended.config import config
from jwt.exceptions import ExpiredSignatureError

@app.route('/mypage')
def show_mypage():
    # 쿠키에서 token 가져오기
    jwtToken = request.cookies.get('jwt-token')
    # token 없을경우 login페이지 rediect
    if jwtToken is None :
        return render_template('login.html')

    #token 만료된 경우 login페이지 rediect
    try:
        # token decode 후 로그아웃여부 확인 위해 jti 저장, user 정보 저장
        jti = decode_token(jwtToken)['jti']
        user = decode_token(jwtToken).get(config.identity_claim_key, None)
    except ExpiredSignatureError: 
        return render_template('login.html')

    #logout된 token의 경우 login페이지 rediect
    logoutCheck = jti in jwt_blocklist
    if logoutCheck :
        return render_template('login.html')

jinja2

웹페이지를 렌더링하는 방식에는 CSR(Client Side Rendering)과 SSR(Server Side Rendering)이 있다.

CSR은 페이지의 변경사항을 Client에서 처리하는 방식으로, 페이지의 정보를 바꾸기 위해서는 페이지를 새로 받아오거나 reload 하지 않고 api 요청으로 data를 받아오고 javascript로 페이지 내용을 변경해주는 SPA(Single Page Application) 방식이다. 이 방식은 페이지의 reload가 거의 발생하지 않아 화면의 번쩍거림 (사라졌다가 다시 나타나는 현상) 이 없어 화면이 빠릿하고 자연스러우나 처음에 한번에 코드를 받아와야한다는 단점이 있다.

반대로 SSR은 페이지의 변경사항을 Server에서 처리하는 방식으로, page를 바꾸기 위해서는 Server로 html 요청이 필요하며 Server에서는 페이지의 내용을 완성한 뒤 html로 내려주는 방식이다. 이는 한번에 코드를 받지 않아도 되어서 속도는 빠를 수 있으나 매번 페이지의 reload가 발생하여 화면이 번쩍거리게 된다.

jinja2는 python에서 SSR을 구현하는 방법 중의 하나이다. flask는 기본적으로 jinja2를 포함하고있어 따로 설치가 필요하지 않다. jinja2가 요구하는 방식으로 html을 작성하고 render_template() 으로 해당 html을 내려주면 된다.

jinja2 입력 방식 - 공식 Docs 참고 변수 : {{ 변수이름 }} 코드(if, for 등) : {% 코드 내용 %}

jinja2를 활용하면 하나의 html 템플릿으로 여러가지의 페이지를 쉽게 만들어줄 수 있어서 편리하다. 예를 들어 회원에 따라 개인화된 my page를 제공하려면 제공하려는 틀을 html로 작성하고 회원의 정보 및 관련 data를 jinja2로 내려주면 된다.

정리

간략하게 정리하려 했으나 쓰다보니 쓸데없이 길어진건 아닌가 싶다. 공식문서나 여러가지 구글링으로 쉽게 찾아볼 수 있는 부분들은 대부분 생략하려 하였고, 개인적으로 이해하기 어렵거나 찾기 어려웠던 부분들은 필자가 이해하거나 구현한 방식으로 자세히 작성해보았다. 이해한 내용을 바탕으로 작성하다보니 틀린부분이 있을지도 모르겠으나 누군가에게 작은 도움이 되었으면 좋겠다.

지난 날의 나는

정말 열심히 살아왔다. 누군가보다 잘 해야한다는 스스로의 압박 속에 항상 주어진 것들에 최선을 다하면서 살아왔다. 하고싶든 하고싶지 않든 주어진 일에 대해서는 항상 잘 하려고 애써왔다. 좋게 말하면 너무나 성실했고 바람직했다. 하지만 힘들었고 재미가 느껴지지 않았다.

열심히 살아온 보상으로 남부럽지 않은 회사에 취업하여 2년여간 일했다. 여기서도 나는, 뒤처지지 않으려고 애쓰며 정말 열심히 일했다. 그러나 언젠가부터 미래에 대한 확신이 들지 않았다. 10년뒤, 20년뒤 나는 이 일을 지속할 수 있을까, 행복할 수 있을까..

나는 어려서부터 컴퓨터를 정말 좋아했다. 무언가를 자동으로 해준다는 것이 신기했고, 그런 컴퓨터를 잘 활용하고 싶었다. 대단했다고 하기엔 부끄럽지만 초등학생때에는 홈페이지를 만들어보고 싶어서 나무(나모?)웹에디터를 사용하고 html을 혼자 공부하기도 하고 메뉴를 만들어보고 싶어서 영상들을 찾아보며 flash로 메뉴를 만들어 넣기도 했다. 중고등학생때는 개발이랑은 조금 거리가 있긴 하지만 포토샵, 프리미어, 애프터이펙트 같은 프로그램들을 배워서 여기저기 써먹기도 했다.

그랬던 나는 (컴퓨터와는 거리가 있는) 화학공학을 전공했고, 반도체 회사에서 일하고 있었다. 열심히 살아왔지만 나는 인생을 만들어가려고 하기보단 '주어진 대로만' 살아왔다. 그렇게 미래에 대한 확신이 흔들릴 무렵, 나는 내 인생을 주체적으로 살고있지 않았으며 어쩌면 스스로에게 좀 무례했던건 아닐까 하는 생각이 들었다.

그때쯤 취미삼아 코딩 공부를 시작했다. 업무에 도움이 될까 싶어 시작했던 엑셀VBA부터 파이썬, 그리고 웹개발. 만들고싶어서 계획하고 코딩한 매크로와 웹이 작동하는 것을 보면서 정말 즐겁고 행복했고, 개발을 제대로 배우고 싶어졌다. 공부하면서 주변에 있는 개발자 친구들과 얘기해보고 긴 시간 고민한 끝에 나는 하고싶은 일을 하기로 결심했다.

개발자.

꿈을 이루기위해 그리고 내 인생을 더 나답게 살기위해 정글에 뛰어들었다.

앞으로의 5개월

내 인생을 더 존중해주기 위해 _좋아하고 하고싶은 일을 하기위해 이 길을 선택한 만큼 뒤돌아보지 말고 나아가기. 나는 나이기에, 다른 사람들과 비교하지 말고 나답게 열심히 살기. 그리고 오늘 열심히 산 나를 칭찬해주기. 두려워하지 말고 오늘에만 집중하기. 아침 일찍 (되도록이면 7~8시) 일어나서 아침운동하고 밥 챙겨먹기 _

실력있는 개발자로 거듭나기 위해 _소중한 동료들과 '함께' 성장하기 내일 더 성장해있도록 매일 공부하기 (일요일은 가급적 쉬기..!) 취업 후에도 계속 성장할 수 있도록 공부습관 만들기 _

정글이 끝나면

5개월간의 정글이 마친 후 나는 서비스 기업으로 취업을 할것이고, 이후로도 실력있는 개발자로 살아가도록 지속적으로 공부를 할 계획이다.

하지만 다른 무엇보다 인생을 주체적으로 살아가는, 자신감있게 나다운 삶을 살아가는 내가 되어있기를 기대한다.