기록공간

앞서 봤던 페이징은 상당한 성능 저하를 가져올 수 있다. 큰 메모리 공간이 요구되며 작업은 엄청난 성능 저하를 유발한다. 운영체제의 실행 속도를 개선하려면, 도움이 필요하다. 대부분의 경우 하드웨어로부터 도움을 받는다. 주소 변환을 빠르게 하기 위해서 변환-색인 버퍼(Translation-lookaside buffer) 또는 TLB 부르는 것을 도입한다. TLB는 칩의 메모리 관리부(MMU)의 일부다. 자주 참조되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시이다. 주소-변환 캐시(Address-translation cache)가 좀 더 적합한 명칭이다. 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 있다면 페이지 테이블을 통하지 않고 변환을 빠르게..

우리는 앞에서 공간 관리 문제를 해결하기 위해 세그멘테이션을 이용하여, 가변 크기의 조각들로 분할하는 방법을 사용한다는 것을 살펴봤다. 하지만 이것은 태생적인 문제를 가지고 있다. 공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화(Fragmented) 될 수 있고, 할당은 점점 더 어려워진다. 이러한 문제점을 해결하기 위해서 공간을 동일한 크기의 조각으로 분할하는 것을 고려해 볼 필요가 있다. 가상 메모리에서 이를 페이징(Paging)이라 부른다. 프로세스의 주소 공간을 몇개의 가변 크기의 논리 세그멘트(힙, 스택, 코드)로 나누는 것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(Page)라고 부른다. 물리 메모리도 페이지 프레임(Page frame)이라고 불리는 고..

이 장에서는 구체적으로 빈 공간 관리에 관련된 문제를 논의할 것이다. 빈 공간 관리가 어려운 이유는 관리하는 공간이 변할 수 있는 가변적인 특성을 가진다는 점이다. malloc() 과 free() 에서처럼 사용자 수준 메모리 할당 라이브러리나 세그멘테이션으로 물리 메모리를 관리하는 운영체제가 이런 특성을 가지는 대표적인 예이다. 빈공간은 다양한 크기의 작은 조각으로 분할되어 결국 단편화된다. 빈 공간들의 전체 크기가 요청된 것보다 크더라도 하나의 연속된 영역이 존재하지 않으면 요청을 실패할 수 있다. 다음 그림은 이러한 문제의 예를 보여 준다. 이 경우 빈 공간의 전체 크기는 20바이트이다. 불행히도, 10바이트 짜리 두 조각으로 나누어져 있다. 그 결과, 20바이트의 빈 공간이 있지만 15바이트의 요청..

동적 계획법을 사용하는 문제였다. 가장 긴 증가하는 부분 수열은 LIS라고 하며 이전에 자세하게 언급한 적이 있으므로 해당 게시글을 참조하길 바란다. https://lipcoder.tistory.com/50?category=843242 최장증가수열 - LIS(Longest Increasing Subsequence) LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들수 있다. 이 때 만들어진 부분수열 중 오름차.. lipcoder.tistory.com 하지만 위와 다른 점이 있다면 위 문제의 경우는 중복되는 숫자가 있다는 점이다. 그것을 감안하고 풀면 되겠다. 코드는 다음과 같다. #includ..

동적 계획법을 이용하는 문제였다. 이전 문제였던 2xn 타일링과 비슷해 보이지만 2x2 타일이 추가되었다. 우선 2x2 타일을 추가하지 않은 경우 타일을 채우는 방법의 수를 점화식으로 표현하면 다음과 같다. 2xn 타일을 채울 방법의수 DP 테이블 배열 DP[N]이 있는 경우 DP[N] = DP[N - 1] + DP[N - 2] 하지만 2x2 타일이 추가되었기 때문에 세가지 사항을 고려해야 된다. 1. N - 1번째에서 2x1짜리 타일 한 개 붙이는 경우 2. N - 2번째에서 1x2짜리 타일 두 개 붙이는 경우 2. N - 2번째에서 2x2짜리 타일 한 개 붙이는 경우 그러므로 점화식은 DP[N] = DP[N-1] + 2 * DP[N-2]가 된다. 이는 DP[3]부터 적용되므로 그 밑의 값 DP[1],..

동적 계획법을 이용하여 해결하는 문제였다. 점화식을 찾기 위해 1부터 차례대로 구해보자. N = 1일 때는 1부터 9까지 모두 계단 수이다. (0은 계단 수가 아니라는 것을 명시했기 때문에 제외해야 한다) => 1, 2, 3, 4, 5, 6, ...., 9 이므로 N = 2일 때에는 계단 수는 다음과 같다. => 10, 21, 12, 32, 23, 43, 34, ...., 89 N = 2일 경우 계단 수에서 마지막 수를 잘 살펴보면 0 ~ 9까지 차례대로 나온다는 것을 알수 있고, 그 앞자리에는 +-1이 온다는 것을 알 수 있다. N = 2에서 마지막 수가 3일 경우 X3 (X에는 2와 4가 오기 때문에 N = 1에서 2와 4가 오면 된다.) 그러므로 23, 43이 계단수로 온다. N = 3에서 마지막 ..

동적 계획법을 사용하여 해결하는 문제였다. N번째에서 최대가 되는 연속합은 두가지 경우가 있다. 1. N-1번째의 연속합과 N번째 값을 더한 것 2. N번째 값 (N번째 부터 연속합을 구하는 경우) 이 두가지 경우를 점화식으로 만들면 다음과 같다. N번째의 연속합을 기록할 DP테이블 배열 DP[N+1](인덱스 접근시 0부터 시작하므로)과 해당 번째의정수를 기록할 배열 num[N+1]이 있다고 했을때, 첫번째 경우는 DP[N] = DP[N-1] + num[N]이고, 두번째 경우는 DP[N] = num[N]이 된다. 이 둘중 가장 큰 값이 DP[N]에 알맞는 연속합 값이 된다. 1번째 부터 마지막 번째 까지 알맞는 DP값을 기록한 후 DP 배열 중 가장 큰 값이 이 문제의 결과값이 된다. 주의할 점은 음수가..

동적 계획법을 사용하여 해결하는 문제이다. 연속으로 놓여있는 3잔을 마실 수 없기 때문에 세가지 경우가 도출된다. N개의 와인잔이 있다고 가정했을때, 처음부터 N번째 까지 차례대로 최대로 마신 양을 기록한다고 하자. N번째 와인잔에서는... 1. 해당 번째 와인을 마시지 않는 경우 : 그러면 이전 와인에서 최대로 마신 양이 된다. 2. 해당 번째 와인을 마시고 이전이전 와인을 마시는 경우 : 그러면 이전이전 와인에서 최대로 마신 양과 N번째 와인의 양의 합이다. 3. 해당 와인을 마시고 이전 와인을 마시고, 3잔 이상인 경우, 연속으로 놓여있는 3잔을 마실 수 없기 때문에 이전이전이전 와인을 마신다 : 이전이전이전 와인에서 최대로 마신 양과 이전 와인와 양 그리고 N번째 와인의 양를 모두 더한다. 이제 ..