SW Jungle/TIL (Today I Learned)
-
[WEEK13] Pintos에서의 FAT 구현 (Pintos PROJECT4 : FILE SYSTEM)SW Jungle/TIL (Today I Learned) 2022. 12. 20. 05:51
발표자료 슬라이드를 바탕으로, FAT이 어떤 것이며 Pintos에서 어떻게 구현되어 있는지를 간략하게 살펴보자. FAT이란, File Allocation Table의 약자이다. 말 그대로 파일의 할당 정보를 표현한 테이블이라고 할 수 있다. MS-DOS 시절부터 쓰여 왔는데, Windows에 들어서면서 FAT형식의 파일시스템 자체를 가리키는 용어가 되었다. FAT area와 FAT filesystem의 혼동을 주의하여야 한다. PROJECT3까지 PINTOS에서 사용하던 파일 시스템은 Free-map 방식이었다. 이는 한 덩어리를 연속된 디스크 공간에 한번에 할당하는 방식이다. 이렇게 하면 외부 단편화가 심해진다. 위의 그림처럼, 주황색 블럭 두 개를 저장할 빈 공간이 남아 있음에도 불구하고 할당할 수 ..
-
[WEEK12] Lazy Loading (Pintos PROJECT3 : VIRTUAL MEMORY)SW Jungle/TIL (Today I Learned) 2022. 12. 13. 04:28
Lazy loading이라는 개념이 있다. 우리말로 옮기면 지연 로딩 정도로 말할 수 있는데, 이 Lazy loading은 어떤 개념이며 왜 사용하는 것일까? Lazy loading은 운영체제가 메모리를 할당하는 기법이라고 할 수 있다. 찾아보니 web이나 java (JPA) 쪽에서도 사용하는 용어라고 한다. 하지만 이 글에서는 운영체제 측면에 한해 다루겠다. 앞선 글에서, 가상메모리와 관련된 페이징 개념을 다뤘다. 페이징을 활용해서 연속적이지 않은 공간에 파일을 로드함으로써 공간을 효율적으로 사용할 수 있었다. 여기에 더해 Lazy loading을 활용하면 추가적인 공간적 이점과 더불어 시간적인 이점도 가져올 수 있다. Lazy 라는 말만 들으면 뭔가 더 지연될 것 같은데, 어떻게 시간적으로도 이점이 ..
-
[WEEK11] 페이징은 왜 하는걸까 (Pintos PROJECT3 : VIRTUAL MEMORY)SW Jungle/TIL (Today I Learned) 2022. 12. 6. 10:59
운영체제의 Memory Management를 구현하면서, 페이징이라는 개념이 왜 쓰이는지 궁금해졌다. 이번 글에서는 페이징이란 무엇이고, 운영체제가 페이징을 왜 하는지에 대해 알아볼 예정이다. 페이징은 메모리를 관리하는 방법이다. 페이징의 기본 아이디어는, 물리 메모리 공간과 가상 메모리 공간을 일정 크기로 나누어 매핑시켜 운영체제가 관리의 주체가 됨으로써, 물리 메모리 공간이 연속적으로 할당되지 않아도 되게끔 만드는 것이다. 질문 1. 왜 가상 메모리 공간이라는 것이 필요한 걸까? 만약 물리 메모리에서 프로그램들을 돌린다고 가정해보자. 돌려야 하는 프로그램이 하나라면, 굳이 가상메모리가 필요하지 않을 수 있다. 어차피 혼자서 메모리 공간을 다 써도 되기 때문에, 프로그램이 주어진 공간을 자유롭게 활용하..
-
[WEEK09~10] syscall wait()의 구현 - 구조 설계를 중점으로 (Pintos PROJECT2 : USER PROGRAMS)SW Jungle/TIL (Today I Learned) 2022. 11. 29. 16:15
복잡한 기능을 구현하려고 하면 막막하다는 느낌을 받을 때가 많다. 고려해야 할 요소들이 너무 많아서, 머릿속에서 마구 섞이기 때문이다. 무엇을 먼저 고려해야 구현이 쉬울까? 구현을 하는데는 다양한 방법이 있을 것이고, 각자 자기에게 맞는 방법이 있을 테니 나의 방식만이 옳다고 할 수는 없다. 하지만 아예 감조차 잡지 못하는 분들을 위해 조금이라도 도움이 되길 바라면서, 이번 Pintos Project 2 - User Programs를 구현할 때 내가 썼던 방식을 공유하려고 한다. 구현한 여러 System Call 중, wait() 기능을 구현할 때의 경험을 바탕으로 설명하겠다. 아래 이미지들은 SW정글에서 발표할 때 썼던 장표들이다. wait 함수가 올바르게 작동하기 위해서는 위와 같은 조건들을 만족해야..
-
[WEEK08] Pintos PROJECT1 : THREADSSW Jungle/TIL (Today I Learned) 2022. 11. 17. 06:41
SW정글 8주차 과정인 "Pintos PROJECT1 : THREADS"를 수행하며, 배운 내용을 정리하려 한다. Project 1 : Threads에서 구현하는 기능은 다음과 같다. - Alarm Clock - Priority Scheduling 이 글에서는 Alarm Clock만 다룰 예정이다. Alarm Clock /* 처음에 제공된 timer_sleep() 함수 */ /* Suspends execution for approximately TICKS timer ticks. */ void timer_sleep (int64_t ticks) { int64_t start = timer_ticks (); ASSERT (intr_get_level () == INTR_ON); while (timer_elapse..
-
[WEEK07] C언어에서 문자열 다루기. 근데 이제 포인터와 파싱(parsing)을 곁들인SW Jungle/TIL (Today I Learned) 2022. 11. 10. 22:36
SW정글에서 7주차 과제인 웹 프록시 서버를 만들며, HTTP 통신의 기초를 공부하게 되었다. 여기서는 HTTP 통신에 대해서는 다루지 않고, 전달된 값을 분석하는 과정인 문자열 파싱(parsing)을 다뤄보려 한다. 1. C언어에서의 문자와 문자열 가. 문자열의 선언 기본적으로 C에서는 문자를 아스키 코드값으로 다룬다. 아스키 코드가 127까지 있으므로, 문자 하나는 char 자료형 (1 Byte) 크기에 담을 수 있다. 그래서 일반적으로 문자열은 char 배열로 선언한다. 문자열의 맨 마지막에는 널 문자가 들어가기 때문에, 문자열 배열의 크기는 문자열의 길이 + 1 로 설정해 주어야 한다. * 널 문자 == 숫자 0 == '\0' == NULL * 문자 '0'은 널 문자가 아님에 주의하라. ✚ 한글은..
-
[WEEK06] Malloc Lab 설명서 번역 (CS:APP)SW Jungle/TIL (Today I Learned) 2022. 10. 28. 01:32
http://csapp.cs.cmu.edu/3e/malloclab.pdf 이 글은 CSAPP (Computer Systems : A Programmer's Perspective) 교재의 참고자료 중 하나인 Malloc Lab 설명서를 번역한 글입니다. 오역이 있을 수 있으며, 특정 부분은 이해를 쉽게 하기 위해 의역하였음을 밝힙니다. 번역이 잘못된 부분은 댓글로 지적해주시면 감사하겠습니다. 수정1. 2022.10.28 - 전체적으로 문장을 매끄럽게 하고, 틀린 부분을 수정했으며 빠진 부분을 보충했습니다. (thanks to YJ) Malloc Lab : Dynamic Storage Allocator(동적 메모리 할당기) 만들기 1. 소개 이번 실습에서는 C언어로 동적 메모리 할당기(dynamic stor..
-
[WEEK05] C언어로 구현하는 레드-블랙 트리 (Red-Black Tree)SW Jungle/TIL (Today I Learned) 2022. 10. 27. 01:08
스스로 생각을 정리하기 위해 적은 글입니다. 초심자가 읽기를 권하지 않습니다! 정보에 오류가 있을 수 있습니다! 목차 레드-블랙 트리란? 레드-블랙 트리의 규칙 경계 노드(Sentinel Node)를 갖는 레드-블랙 트리 트리 수정 시 위반되는 레드-블랙 특성 복구를 위한 회전(Rotate) 레드-블랙 트리의 삽입 레드-블랙 트리의 삭제 코드 보기 레드-블랙 트리란? 레드-블랙 트리는 스스로 균형을 잡는(self-balancing) 이진 탐색 트리이다. 스스로 균형을 잡는다는 말은, 트리에 원소가 삽입 또는 삭제될 때 어느 한 쪽에 편중되지 않도록 스스로 조정한다는 말이다. 균형잡힌 트리는 실행 시간이 우수하다는 장점이 있다. (시간복잡도가 낮음) 트리에 n개의 원소가 있을 때, $O(logN)$의 시간..