24.01.30 퀴즈, CSAPP 9.8 - 9.9.3, 백준

퀴즈

• 꼬리 재귀 최적화라는 새로운 알고리즘을 들었다. 뭔가 CSAPP책에서 놓친 것이 있었나하고 아차 내가 읽었던것을 까먹었던가 빼놓고 읽었구나 라고 생각했다. 하지만 다행? 다행일까? 새로운 부분이 나온걸 보아하니 그런건 아니구라 라고 생각도 한번씩하고, 하지만 내가 지금까지 알았던걸로 충분히 유추해서 풀 수 있었던 것을 생각하면 아쉽기도 한것같다.
• 그리고 내 지식의 구멍을 좀 느낄 수 있었다. 제대로 공부했다면 퀴즈라고 많은 시간을 소모하는 게 아니라 간단하게 복습하는것으로 기억을 되살려 문제를 풀 것이라고 생각하면 아직은 많이 모자란 것 같다.
• 그럼 이제 다시 배우거나 애매하게 있었던 것 레쓰꼬!

1. 스택과 레지스터가 어떤 것인지 설명하고, 용도와 장점을 설명하세요.

• 스택(stack)은 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간이다. 선언되는 순서와 반대로 메모리가 해제되는 LIFO(Last In First Out) 구조를 가지고 있다.
  • 용도
    • 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다.
    • 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다.
  • 장점
    • 동적으로 메모리를 할당하고 해제할 수 있다.
    • 구현이 간단하며, 메모리 관리 overhead가 낮다.
• 레지스터(register)는 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다.
  • 용도
    • 중간 연산 결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용된다.
    • 빠른 데이터 접근 : 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용된다.
  • 장점
    • 매우 높은 데이터 접근 속도를 제공한다.
    • 데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가한다.

2. 꼬리 재귀 최적화(Tail Recursion Optimization)을 호출 스택(Call stack)의 관점에서 설명하세요.

• 꼬리 재귀 최적화는 재귀 함수 호출 시 호출 스택 사용을 최적화하는 기법이다. 재귀 함수가 호출될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 된다. 꼬리 재귀 최적화는 재귀 함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거한다. 이를 통해 함수가 반환될 때 호출 스택을 재사용할 수 있다.
• 구체적으로, 꼬리 재귀 함수는 반환값을 바로 return하기 보다는 파라미터로 전달한다. 이렇게 하면 호출 스택에 쌓이지 않고 후속 호출로 이동된다.
• 마지막 호출에서 스택 프레임을 재활용하므로, 메모리 사용량이 일정하게 유지된다.
• C언어 factorial을 꼬리 재귀 최적화를 통한 구현

int factorial_tail(int n int acc){
	if (n == 1){
		return acc;
}
	return factorial_tail(n-1, a*acc);
}

int factorial(int n){
	return factorial_tail(n,1);
}

4. 그리디 알고리즘과 동적 프로그래밍의 정의를 각각 쓰시고, 동적 프로그래밍에서 상향식, 하향식 차이에 대해 설명해 보세요.

• 그리디 알고리즘(Greedy Algorithm)
  • 정의
    • 매 순간마다 가장 좋아 보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대한다.
  • 특징
    • 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식이다. 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않는다.
• 동적 프로그래밍(Dynamic Programming)
  • 정의
    • 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘이다.
  • 특징
    • 중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높인다.
    • 메모이제이션(Memoization) 또는 테블레이션(Tabulation) 기법을 사용한다.
  • 하위 유형
    • 상향식(Bottom-Up) : 작은 문제부터 차례대로 해결해 나가면서 큰 문제의 해결책을 구한다. 테블레이션 사
    • 하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결해간다. 필요할 때 하위 문제를 해결한다. 재귀사용, 메모이제이션 사용

CSAPP

9.8 메모리 매핑

• 리눅스는 가상 메모리 영역의 내용을 디스크의 객체에 연결해서 초기화 한다. 이 과정은 메모리 매핑이라고 알려져 있다. 영역들은 다음 두 종류의 객체 중의 하나로 매핑 될 수 있다.
  1. 리눅스 파일 시스템 내의 일반파일 : 한 영역은 실행 가능 목적파일과 같은 일반 디스크 파일의 연속적인 섹션으로 매핑 될 수 있다. 파일 섹션은 페이지 크기의 조각들로 나누어지고, 이들은 각각 가상페이지의 초기 내용을 포함하고 있다. 요구 페이징 때문에 CPU가 처음 페이지에 접근할 때(즉, 페이지의 주소공간의 영역내에 들어가는 가상주소를 만들어 내는)까지는 이 가상 페이지들 중 아무것도 실제로 물리 메모리로 스왑되어 들어오지 않는다. 만일 이 영역이 파일섹션보다 더 크다면, 이 영역은 0으로 패딩된다.
  2. 무기명 파일 : 한 영역은 또한 무기명 파일로 매핑 될 수 있다. 이 파일은 커널이 만든 것이며, 모두 이진수0을 포함한다. CPU가 이 영역의 가상페이지에 처음으로 접근할 때, 커널은 물리메모리 내에서 적당한 희생자 페이지를 찾아내고, 만일 이것이 dirty하다면 희생자 페이지를 스왑 아웃하고, 희생자 페이지를 이진수 0으로 덮어쓰고, 이 페이지가 존재한다고 표시하기 위해 페이지 테이블을 갱신한다. 어떤 데이터도 실제로는 디스크와 메모리 사이에 이동하지 않았다는 점에 유의해야한다. 이 이유 때문에 무기명 파일로 매핑된 영역 내의 페이지들은 때로 무요구(demand-zero)페이지라고 불린다.
• 어떤 경우든지, 일단 가상페이지가 초기화된 후에는 커널이 관리하는 특별한 스왑 파일 사이에서 스왑인 되었다가 아웃되었다가 한다. 또한 스왑 파일은 스왑공간 또는 스왑영역이라고 알려져있다. 인식해야 하는 중요한 점은 시간상의 어느 시점에, 스왑 공간이 동시에 실행되고 있는 프로세스들에 의해 할당된 전체 가상페이지의 양을 제한 한다는 것이다.

9.8.1 다시보는 공유객체

• 프로세스의 개념은 각 프로세스에 자신만의 가상 주소공간을 제공하며, 이것은 다른 프로세스들에 의해 잘못된 쓰기와 읽기 작업이 발생하는 것을 막아준다. 그렇지만 많은 프로세스들은 동일한 읽기-허용 코드 영역을 가지고 있다.
• 많은 프로그램들은 동일한 읽기-허용 런타임 라이브러리 코드에 접근할 필요가 있다. 예를 들어, 모든 C 프로그램들은 printf 같은 표준 C라이브러리 함수를 필요로 한다. 각각의 프로세스를 위해 물리메모리 상에 이와 같이 공통으로 사용하는 코드를 중복해서 두는것은 매우 낭비다. 메모리 매핑을 통해서 어떻게 객체들이 다수의 프로세스들에 의해 공유될 수 있는지를 제어하는 깔끔한 매커니즘을 가지게 됐다.
• 객체는 공유 가상 메모리 영역으로 공유객체 또는 사적(private) 객체로 매핑될 수 있다. 만일 공유객체를 자신의 공유주소공간으로 매핑한다면, 이 프로세스가 이 영역에 쓰는 모든 내용은 자신의 공유 메모리 내로 객체를 매핑한 다른 프로세스들도 볼 수 있게 된다. 나아가서 이런 변경된 내용은 디스크상의 원래의 객체에도 반영된다.
• 반면에, 사적 객체에 매핑된 영역에 가한 수정사항들은 다른 프로세스들은 볼 수 없으며, 이 영역에서 프로세스가 수행하는 모든 쓰기 작업들은 디스크상의 객체에는 반영되지 않는다. 공유된 객체가 매핑된 가상메모리 영역은 종종 공유 영역이라고 불린다. 사적영역과 비슷하게 정의된다.
• 객체가 여러 공유 영역에 복수로 매핑된 경우에도 단 한 개의 공유객체만이 물리 메모리에 저장된다.
• 사적객체들은 copy-on-write 라고 알려진 영리한 기법을 사용해서 가상 메모리에 매핑된다. 사적객체는 공유객체와 똑같은 방법으로 만들어지며, 물리메모리에 단 한 개의 사적객체만이 저장된다. 사적객체를 매핑하는 각 프로세스에 대해서 대응되는 사적영역에 대한 페이지 테이블 엔트리들은 읽기-허용으로 표시되어 있으며, 영역 구조체는 사적 copy-on-write로 표시되어있다. 두 프로세스 모두 자신의 사적영역에 쓰려고 하지 않는 한, 이들은 물리 메모리내에 단 한 개의 객체 사본을 계속 공유한다. 그렇지만, 한 프로세스가 사적영역내의 일부 페이지에 쓰려고 하는 순간 쓰기 작업은 보호 오류를 유발한다.
• 오류 핸들러가 어떤 페이지를 사적 copy-on-write 영역에 쓰려고 하는 프로세스에 의해서 보호 예외가 발생했다고 알릴 때, 핸들러는 이 페이지의 새로운 사본을 물리 페이지 내에 만들고, 페이지 테이블을 갱신해서 새로운 사본을 가리키게 하며, 그 후에 이 페이지에 대한 쓰기 허가를 복원한다. 오류 핸들러가 리턴 할 때, CPU는 이 쓰기작업을 재 실행 하고, 이것은 이제 새롭게 만들어진 페이지에서 정상적으로 진행한다.
• copy-on-write는 마지막 가능한 순간까지 사적 객체 내에서 페이지를 복사 하는 것을 지연시켜서 부족한 메모리를 가장 효율적으로 사용한다.

9.8.2 다시보는 fork 함수

• 프로세스가 fork 함수를 호출하면, 커널은 이 새로운 프로세스를 위한 여러가지 자료구조를 생성하고, 여기에 고유한 PID를 부여한다. 새 프로세스를 위한 가상 메모리를 생성하기 위해서 현재 프로세스의 mm_struct, 영역 구조체, 페이지 테이블과 동일한 사본을 만든다. 두 프로세스의 모든 페이지들을 읽기-허용으로 표시하고, 두 프로세스의 영역 구조체들은 사적 copy-on-write로 표시한다.
• fork 프로세스가 새 프로세스를 리턴할 때, 새 프로세스는 이제 fork가 호출되었을 때 존재하던 가상메모리와 똑같은 사본을 가진다.이 두 프로세스 중 한 프로세스가 이후에 쓰기 작업을 수행하면 copy-on-write 메커니즘은 새 페이지를 생성하고, 따라서 각 프로세스에 대해 사적 주소공간 개념을 유지하게 된다.

9.8.3 다시보는 execve 함수

• evecve 함수는 현재 프로세스 내에서 현재 프로그램을 효과적으로 교체하면서 실행 목적파일 a.out에 포함된 프로그램을 실행하고 로드한다. a.out을 로드하고 실행하는 것은 다음 단계를 필요로 한다.

(그림 9.31)

1. 기존 사용자 영역을 제거한다. 현재 프로세스의 가상주소의 사용자 부분에 있는 기존 영역 구조체들을 삭제한다.
2. 사적 영역을 매핑한다. 새 프로그램의 코드, 데이터, bss, 스택을 위한 새로운 영역 구조체를 만든다. 이 모든 새로운 영역들은 사적 copy-on-write 형식을 사용한다. 코드와 데이터 영역은 a.out파일의 .text와 .data섹션들에 매핑된다. .bss영역은 무요구 형식으로, 크기가 a.out에 들어 있는 무기명 파일에 대응된다. 스택과 힙 영역 또한 무요구 형식으로, 처음에는 길이가 0이다.
3. 공유 영역을 매핑한다. 만일 a.out 프로그램이 표준 C라이브러리 libc.so같은 공유 객체들과 연결 되었다면 이 객체들은 프로그램에 동적으로 링크되며, 그 후에 사용자의 가상 주소공간의 공유 영역으로 매핑된다.
4. 프로그램 카운터(PC)를 설정한다. 현재 프로세스 컨텍스트 내에 있는 프로그램 카운터를 코드 내 엔트리 포인트를 가리키도록 설정하는 것이다.

• 다음번에 이 프로세스가 스케줄되고, 이것은 엔트리 포인트로부터 실행하기 시작할 것이다. 리눅스는 필요할 때에 코드와 데이터를 스왑해서 들어온다.

9.8.4 함수를 이용한 사용자 수준 메모리 매핑

• 리눅스 프로세스들은 함수를 이용해서 가상메모리의 새로운 영역들을 만들 수 있으며, 객체들을 이 영역으로 매핑할 수 있다.
• *mmap 함수는 커널에 새 가상 메모리 영역을 생성해 줄 것을 요청하며, 이때 start주소에서 시작하는 영역을 선호하고, 새 영역을 가리키는 파일 식별자 fd로 명시된 연속된 객체들을 매핑해 줄것을 요청한다.

9.9 동적 메모리 할당

• 동적 메모리 할당기는 힙heap 이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 자세한 내용은 시스템마다 다르지만, 일반화의 오류를 범하지 않는 한도에서 힙이 미초기화된 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정할 것이다. 각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk(break라고 발음)을 사용한다.
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당 되었거나 가용한 가상 메모리의 연속적인 묶음이다. 할당된 블록은 응용하기 위해 명시적으로 보존되었다. 각용한 free 블록은 할당을 위해 사용할 수 있다. 가용 블록은 응용이 명시적으로 할당할 때까지 가용한 상태로 남아있다. 할당된 블록은 응용에 의해 명시적으로 또는 메모리 할당기 자신에 의해 묵시적으로 반환될 때 까지 할당된 채로 남아있다.
• 할당기의 두 개의 기본 유형
  • 명시적 할당기 : 응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. 예를 들어, C표준 라이브러리는 malloc패키지 라고 하는 명시적 할당기를 제공한다. C프로그램은 malloc 함수를 호출해서 블록을 할당하며 free함수를 호출해서 블록을 반환한다.
  • 묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을것을 요구한다. 묵시적 할당기는 가비지컬렉터(garbage collector)라고 알려져 있으며, 자동으로 사용하지 않는 할당된 블록을 반환 시켜주는 작업을 가비지 컬렉션이라고 부른다.

9.9.1 malloc과 free함수

• C표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공한다. 프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당 받는다.
• malloc 함수는 블록 내에 포함 될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size바이트를 갖는 메모리 블록의 포인터를 리턴한다. 실제 구현에서 정렬은 코드가 32비트, 64비트 모드에서 동작하도록 컴파일 되어 있는지 여부에 따라 다르다. 32비트 모드에서는 malloc주소가 8의 배수 블록을 리턴하고, 64비트에서는 16의 배수를 리턴한다.
• malloc은 프로그램이 가용한 가상메모리 보다 더 큰 크기의 메모리 블록을 요청 받으면 널을 리턴하고 errno를 설정한다. malloc은 리턴하는 메모리를 초기화 하지 않는다. 초기화한 동적 메모리를 원하는 응용들은 calloc을 사용할 수 있는데, 이것은 할당된 메모리를 0으로 초기화하는 calloc 함수 주위의 얇은 래퍼 함수다. 이전에 할당된 블록의 크기를 변경하려는 응용은 realloc 함수를 사용할 수 있다.
• malloc 같은 동적 메모리 할당기는 mmap와 munmap 함수를 사용해서 명시적으로 힙 메모리를 할당하거나 반환하며, 또는 sbrk 함수를 사용할 수 있다.
• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk값을 리턴하고, 아니면 -1을 리턴하고 errno를 ENOMEM으로 설정한다. 만일 incr이 0이면 sbrk는 현재의 brk를 리턴한다. sbrk를 음수 incr로 호출하면 합법적이지만, 리턴값(이전 brk값) 이 새로운 힙의 탑을 지나서 abs(incr)바이트를 가리키기에 복잡해진다.
• 프로그램은 할당된 힙 블록을 free 함수를 호출해서 반환한다.
• ptr인자는 malloc, calloc, realloc에서 획득한 할당된 블록을 가져야 한다. 그렇지 않다면 free 동작은 정의되지 않는다. 더 나쁜것은 아무것도 리턴하지 않기 때문에 free는 응용에게 뭔가 잘못 되었다는 것을 알릴 수 없다는 점이다. 이것은 혼란스러운 런타임 에러를 유발한다.

9.9.2 왜 동적 메모리 할당인가?

• 프로그램을 실제 실행하기 전에는 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다.
• 배열을 정해진 최대 배열 크기를 갖는 정적 배열로 사용해서 할당하는 것은 종종 나쁜 방법이 된다. 사용자가 더 큰 파일을 읽으려고 한다면, 가능한 유일한 대책은 프로그램을 더 큰 값을 사용해서 다시 컴파일 하는 것이다.
• 더 나은 방법은 n값을 알 수 있을 때, 배열을 런타임에 동적으로 할당하는 것이다. 이 방법으로, 배열의 최대 크기는 가용한 가상 메모리의 양에 의해서만 제한된다.

9.9.3 할당기의 요구사항과 목표

• 명시적 할당기는 다소 엄격한 제한 내에서 동작해야한다.
  • 임의의 요청 순서 처리하기 : 응용 프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응 되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환 요청을 할 수 있다. 그래서 할당기는 할당과 반환 요청의 순서에 대해서는 아무 가정도 할 수 없다.
  • 요청에 즉시 응답하기 : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
  • 힙만 사용하기 : 확장성을 갖기 위해서는 할당기가 사용하는 비확정성 자료구조들은 힙 자체에 저장 되어야 한다.
  • 블록 정렬하기(정렬요건) : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬 해야한다.
  • 할당된 블록을 수정하지 않기 : 할당기는 가용블록을 조작하거나 변경할 수만 있다. 특히, 일단 블록이 할당되면 이들은 수정하거나 이동하지 않는다. 그래서 할당된 블록을 압축하는 것 같은 기법들은 허용되지 않는다.
• 이러한 제한 사항들을 가지고 작업하기 위해서 할당기 개발자는 처리량과 메모리 이용도를 최대화 하려는 종종 상충되는 성능 목표를 달성하기 위해 노력한다.
• 목표1. 처리량 극대화 하기 : 할당기의 처리량을 최대화하려고 하며, 이것은 단위 시간 당 완료되는 요청의 수로 정의된다. 일반적으로, 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화 한다. 할당 요청의 최악 실행시간이 가용 블록의 수에 비례하고, 반환 요청의 실행시간이 상수인 적당히 좋은 성능의 할당기를 만드는 것은 그리 어렵지 않다.
• 목표 2. 메모리 이용도를 최대화 하기 : 한 시스템에서 몬든 프로세스에 의해 할당된 가상 메모리의양은 디스크 내의 스왑 공간의 양에 의해 제한된다. 할당기가 힙을 얼마나 효율적으로 사용하는지를 규정하는 많은 방법이 있다. 가장 유용한 단위는 최고 이용도(peak utilzation)이다.

백준

12865 평범한 배낭

• knapsack 문제

import sys

n, k = list(map(int,sys.stdin.readline().split()))
item_list = [[0,0]]

knap = [[0 for i in range(k+1)]for i in range(n+1)]

for i in range(n):
	item_list.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,n+1):
	for j in range(1, k+1):
		weight = item_list[i][0]
		value = item_list[i][1]

		if j < weight:
			knap[i][j] = knap[i-1][j]
		else:
			knap[i][j] = max(value + knap[i-1][j-weight],knap[i-1][j])

print(knap[-1][-1])

11053 가장 긴 증가하는 부분 수열

import sys

n = int(sys.stdin.readline())

_arr = list(map(int,sys.stdin.readline().split()))

dp = [1] * n

for i in range(1,n):
	for j in range(i):
		if _arr[i] > _arr[j]:
			dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))