https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 생각해보기 M개의 블루레이를 기준으로 블루레이의 최소 크기를 찾는 이분탐색 문제이다. 각 강의의 길이는 오름차순으로 정렬되어 있지 않고, 순서가 변경되어선 안된다. 따라서 start는 배열의 max, end는 배열의 합으로 정한다. 처음에는 각 블루레이의 크기를 배열에 저장했으나 이는 불필요한 연산이었을 뿐 아니라, 연산을 끝까지 했을 때 올바른 결과를 저장하고 있지 않았다. 블루레이의 개수인 cnt를 ..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 생각해보기 매 시행마다 세 가지 연산 중 하나를 수행하며, S개의 이모티콘을 만드는데 걸리는 최소 시간을 구한다. 이모티콘의 개수와 클립보드 둘 다 고려해야 한다. BFS로 어떻게 탐색하게 할 것인가? 방문 체크를 세 가지 연산과 함께 고려한다. 풀이 1) 방문 체크를 2차원 배열로 하기 import sys from collections import deque input = sys.stdin.rea..

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)이 사용된다. 이는 이미 계산한 결과를 배열에 저장하여 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순..