분류 전체보기 (15) 썸네일형 리스트형 [PintOS-KAIST]Project3: Virtual Memory preview 이번 핀토스 프로젝트 3의 주제인 가상메모리 구현에 앞서 알아야 할 몇가지 사전 지식들을 정리하려고 한다. 가상 메모리가상 메모리는 물리 메모리(실제 메모리)의 크기와 상관없이 메모리를 이용할 수 있도록 지원하는 기술이다. 프로그래머는 가상 메모리 덕분에 물리 메모리의 크기에 구애받지 않고 작업할 수 있는 커다란 공간을 얻게 되는 셈이다. 즉, 가상 메모리(virtual memory)는 크기가 다른 물리 메모리에서 일관되게 프로세스를 실행할 수 있는 기술이다.가상 메모리를 사용하면서 실제 물리 메모리에 연결하는과정이 필요한데,이러한 작업을 동적 주소 변환(Dynamic Address Translation, DAT)라고 한다. 동적 주소 변환을 거치면 프로세스가 아무 제약 없이 사용자의 데이터를 물리 메모.. [PintOS-KAIST]Project2: SYSTEMCALL(1) project2의 핵심내용인 systemcall에 대해서 작성을 해보도록 하겠다. systemcall이란 운영체제의 커널이 제공하는 서비스에 대해, 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스이다. 보통 c나 c++과 같은 고급 언어로 작성된 프로그램들은 직접 시스템 호출을 사용할 수 없기 때문에 고급 API를 통해 시스템 호출에 접근하게 하는 방법이다. 즉, 운영체제 서비스에 접근하기 위한 유일한 수단인 소리이다. 그럼 이러한 systemcall이 필요한 이유는 무엇일까?사용자가 직접적으로 하드웨어 장치를 제어한다면 큰 문제가 발생할 수 있다. 따라서 사용자 어플리케이션은 System Call 을 통해 직접적인 H/W 요청이나 중요한 시스템 요청을 하는 것이다.우리가 일반적으로 사용하는.. [PintOS-KAIST]Project1:preview 본격적으로 project1을 하기 위한 전반적인 코드 분석 및 flow 이해를 하기위한 포스트이다.pintos의 경우 굉장히 많은양의 코드(대략 기본 코드가 2만줄이라고한다,,,)와 많은 파일들이 있기에 전반적이 flow 이해와 더불어 구현해야할 부분에 대한 코드분석이 우선이라고 생각했다.실제로 2일동안은 코드 한줄 작성하지 않고 코드분석과 flow이해를 위한 기본적인 개념공부와 더불어 gdb를 이용해 test를 돌려보면서 한줄 한줄 뜯어보면서 확인했다.(alarm-multiple)확인하는 방법은 main()에서 thread_start()에 breakpoint를 찍고 한줄한줄 step over,into,out을 반복하며 확인했다.(실제로 into를 깊게 들어가면 어셈블리어까지 있다.... 이론적으로 공부.. [PintOS-KAIST]Loading PintOS의 project 과제를 수행하기전에 PintOS가 어떻게 구동되는가를 먼저 확인하겠다.로딩은 PintOS의 Loader 실행과 Kernel의 초기화 작업을 한다.여기서 Loading이란 os 실행시 진행되는 부팅과정이다. 부팅은 컴퓨터가 구동하여 기초적인 초기화 작업 진행 후 운영체제를 읽어오는 과정이다.부트 섹터는 방금 언급한 기초적인 초기화 작업과 운영 체제를 읽어서 메모리에 올리고 수행시키는 작업에 대한 코드가 작성된 프로그램이 기록된 섹터로 장치의 첫 번째 트랙의 첫 번째 섹터이다.Loader는 부팅을 진행하는 프로그램으로 Disk의 첫번째 Track의 첫번째 Sector에 저장되어있다. 1.BIOS가 컴퓨터 구동후 첫번째 Sector를 탐색하여 부팅 가능한지 검사(첫번째 Sector.. [Algorithm05] 이진탐색 전 시간에는 백트래킹을 문제에 적용하는 법을 배웠다. 백트래킹은 완전탐색에서 탐색 시간을 줄이기 위해 다음 노드 탐색 전 유망조건을 체킹하여 탐색하는 방법이었다. 그럼 문제에서 주어진 조건에 부합하는 답을 찾는데 시간을 줄일 수 있는 다른 방법이 뭐가 있을까라는 고민을 해볼 수 있다. 오늘의 주제는 그와 관련된 알고리즘 중 이진 탐색 혹은 이분 탐색 알고리즘을 문제에 적용시키는 방법에 대해 이야기해볼까 한다. 이 블로그는 특정한 알고리즘에 대해 깊게 공부하는것이 아닌 문제를 접근하는법과 해당문제의 답을 찾는 과정에서 다양한 알고리즘을 적용시켜 문제 푸는 법에 대해 이야기하는중이니 특정 알고리즘에 대해 따로 공부할 사람은 다른 글을 찾아 보는것이 더 도움 될것이다. 자 그럼 이진 탐색이란 무엇일까 이진탐색.. [Algorithm04] 백트래킹 전 시간인 완전탐색의 기본에 대해서 공부했다. 오늘의 백트래킹에 대해 공부하기 전에 짧게 복습하면 완전탐색은 근본적으로 반복문과 조건문을 활용하여 문제에서 주어진 조건에 부합하는 가능한 모든 경우의 수를 탐색하는 것이다. 오늘 공부할 백트래킹은 완전탐색 중(우리는 dfs기본을 이용하여 완전탐색을 진행했다) 문제에서 주어진 조건을 활용하여 경우의 수를 끝까지 탐색하기 전에 미리 체킹 하여 불필요한 탐색 시간을 줄이는 방법이다. 그럼 어떻게 불필요한 탐색 시간을 줄일 수 있는지 알아보자 백트래킹 백트래킹이란 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 여기서 지금의 경로가 해가 될 거 같지 않으면을 체크하는것을 유망조건을 확인한다라고.. [Algorithm03] 완전 탐색 우리는 전 시간에 순열과 조합을 dfs(재귀적 접근)를 이용해서 공부했다. 계속 순열과 조합의 기본을 강조하는 이유가 어떤 문제든 탐색을 진행할 집합이 그래프화(배열이나 리스트 등)할 수 있다면 순열과 조합의 기본을 이용하여 모두 풀 수 있기 때문이다. 다만 못 푸는 경우도 존재하는데 이것은 정답을 찾을 수 없다가 아니라 문제를 풀 때 제한조건을 만족하지 못해서이다. 즉, 시간복잡도나 공간복잡도를 줄여야 하는 문제이기 때문이다. 이러한 시간복잡도와 공간복잡도를 줄이기 위해서 다양한 알고리즘들이 존재한다. 하지만 기본적인 완전탐색을 하지 못하는데 시간복잡도와 공간복잡도를 줄이기 위한 다른 알고리즘을 먼저 공부하는 것은 아니라고 생각한다. 본인만의 문제 접근법 풀이법이 정립이 되지 않았는데, 이 문제는 이 .. [Algorithm02] 순열과 조합 이번 시간에는 순열과 조합에 대해 이야기하겠다. 순열과 조합은 알고리즘 중 탐색과 관련하여 가장 기초 중의 기초이다. 기본적으로 어떠한 조건에 따른 탐색의 결과는 조합과 순열을 이용하여 결과를 내는 것이다. 전 시간에 재귀를 이용한 n개 중에서 k개를 뽑는 방법을 예시로 들었는데, 이번 시간에는 조건에 따른 순열과 조합의 구현에 대해 이야기해보겠다. 순열과 조합의 차이는 순서를 고려하느냐의 차이이다. 순열은 순서 고려, 조합은 순서 고려 X ([a, b]와 [b, a]를 다르게 취급하면 순서를 고려하는 것) 재귀(DFS)를 이용한 순열 조합을 구현하는 방법에 대해 이야기하겠다.(DFS는 추가적으로 뒤에서 자세하게 다룰 예정이니 DFS의 기초를 다룬다고 생각하자. 탐색방법 중 하나의 알고리즘인데, 탐색의 .. 이전 1 2 다음
