FAT와 File growth를 구현한 후, 유저 프로그램을 실행하는 테스트 케이스가 계속 실패하였다. 원인은 파일 시스템을 포맷하는 과정에서 루트 디렉토리를 생성하지 않았기 때문이었다. 유저 프로그램을 실행하기 위해서 해당 프로그램의 이름과 disk inode가 어떻게 디렉토리 엔트리에 저장되는지 흐름을 파악해보며 이를 해결하였다. /* Pintos main program. */ int main (void) { ... #ifdef FILESYS /* Initialize file system. */ disk_init (); filesys_init (format_filesys); ... } 핀토스 부팅을 위해 init.c의 main함수가 실행되면, disk_init()과 filesys_init(format..

일부 자원이 여러 프로세스에 의해 사용되고 있다면, 각 프로세스는 충돌이 일어나는 것을 막기 위해 자신만의 자원 복사본을 갖는다. 하지만 자원이 수정되지 않고 읽기 작업만 수행된다면, 물리 메모리에서 여러 개의 복사본을 가지고 있을 필요가 없다. 예를 들어, fork를 통해 새로운 프로세스가 생성되었다고 가정해보자. 자식 프로세스는 부모의 자원을 복사하여 상속받아야 한다. 이를 위해 프레임을 할당하고, 프레임에 데이터를 쓰고, 가상 주소와 물리 주소의 매핑 정보를 페이지 테이블에 추가하는 작업을 수행한다. 이러한 단계들은 시간이 오래 걸릴 수 있다. 더군다나 읽기 작업만을 위한 경우, 이는 비효율적이다. copy on write 기술을 사용하여 이미 물리 메모리 상에 존재하는 프레임을 참조하도록 하여 더..

eager loading 기존의 핀토스는 파일 전체를 메모리에 적재한다. 이는 당장 필요한 자원도 메모리에 적재되어 있지만 당장 필요하지 않은 자원들도 메모리에 적재되어 있음을 의미한다. 물리 메모리의 공간은 한정되어 있기 때문에, 다른 자원을 메모리에 적재하기 위해서는 스왑인과 스왑아웃의 절차를 거쳐야 한다. 이는 오버헤드가 상당히 큰 작업이다. lazy loading 따라서 자원이 실제로 필요한 경우 이를 메모리에 적재하는 lazy loading방식을 채택한다. load segment 함수 안에서 vm_alloc_page_with_initializer 함수를 통해 페이지의 할당과 함께 추후 페이지 폴트가 일어났을 때 프레임에 적재할 파일에 대한 정보를 spt안에 저장한다. 또한 페이지의 타입과 초기화..

Argument Passing PintOS의 process_exec() 함수의 인자를 file name과 argument로 pasing하여 전달해주도록 구현한다. 단순히 방법만을 따라서 구현하다 보니 parsing하여 전달된 인자들이 어떠한 의미를 가지는지 생각해보지 않았다. 따라서 해당 포스팅에서는 실행 가능한 목적파일을 메모리에 적재하고 실행하는 process_exec()와 load()가 어떠한 방식으로 구현되어 있고, 전달된 인자들과 함께 유저 프로그램이 어떻게 실행되는지 알아본다. 목적파일 목적파일에는 다음과 같은 세 가지 형태가 있다. 재배치 가능 목적파일(Relocatable object file) 실행 가능 목적파일을 생성하기 위해, 컴파일 할 때 다른 재배치 가능 목적파일과 결합될 수 있는..

Alarm Clock - Timer Interrupt Alarm Alarm은 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수이다. Pintos에서는 알람 기능이 Busy waiting 방식으로 구현되어 있다. 해당 알람 기능을 sleep/wake up 방식으로 수정하여 다시 구현한다. Alarm Clock 기능을 구현할 때, ticks에 대한 이해가 미흡했기 때문에 어려움을 겪었었다. 아래 코드는 next_tick_to_awake가 제대로 갱신되지 않고, thread_awake의 argument가 잘못된 경우이다. /* 최소 틱을 가진 스레드 저장 */ void update_next_tick_to_awake(int64_t ticks) { // 만약 ticks가 next_tick_to_a..

다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 이는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다. 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 다이나믹 프로그래밍에서는 메모이제이션(Memoization)이 사용된다. 이는 이미 계산한 결과를 배열에 저장하여 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순..

백준 21606번 : 아침 산책 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 주어진 조건을 만족하는 서로 다른 산책 경로의 개수를 찾는 문제이다. 문제 조건을 요약하면 다음과 같다. 시작점과 끝점은 모두 실내 장소 산책 경로 위에 시작점과 끝점을 제외하고 실내 장소가 있으면 안됨 실내 → 실외 → 실내로 이동하는 경우와 실내 → 실내로 이동하는 경우 두 가지를 고려해야 한다. 실내 → 실외 → 실내 먼저 하나의 실외 노드에 4개의 실내 노드가 인접해 있다고 가정해보자. 산책 경로의 수는 ..

백준 5639 이진 검색 트리 이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력하는 프로그램을 만드는 문제이다. 이진 검색 트리의 조건은 다음과 같으며, 이를 이용해 문제를 풀 수 있다. 이진 검색 트리(binary search tree)는 모든 노드가 다음 조건을 만족해야 한다. 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다. 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다. 처음에는 전위 순회 결과를 토대로 트리를 복구한 다음, 후위 순회 결과를 출력하는 방식으로 풀이를 시도 했으나, 시간 초과와 메모리 초과가 발생하였다. 전위 순회 결과의 첫번째 요소는 이진 검색 트리의 루트 노드이다. 이를 시작점으로 하여 각 노드들과의 대소 관계 비교를 통해 트리의..