24.01.31 CSAPP 9.9.4, 백준

아니 세상에 마상에나 벌써 1월의 마지막이다.

내가 점점 발전을 하고 있다는 생각은 들지만 음.. 빠른가? 라고 누군가 물어본다면 그거에 대해서 확실하게 대답은 못할 것 같다.

그럼에도 그렇게 불안에 떨지 않는건 나는 잘할 것이라는걸 알기 때문이 아닐까?

더 어려워도 뭐 사람이 하는거고 앞 선배들이 해왔던건데 불가능한 것을 내놓진 않겠지 라는 마인드로 살아가고 있다.

내일 WIL 회고에다가 적을말을 TIL에 적고 있는 것 같은데, 아무튼!!!

나는 하루하루 성장하고 있다. 곧 초사이어인의 반열에 오를지도..

CSAPP

9.9.4 단편화

• 나븐 힙 이용도의 주요 이유는 단편화라고 알려진 현상이다. 이것은 가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다. 단편화에는 두 종류의 단편화가 있다.
  • 내부 단편화
    • 할당된 블록이 데이터 자체보다 더 클때 일어난다. 이것은 여러가지 이유로 일어날 수 있다. 예를 들어, 할당기의 구현이 요청한 데이터 보다 더 큰 할당된 블록들에 최소 크기를 부여할 수도 있다. 할당기는 정렬 제한사항을 만족시키기 위해서 블록의 크기를 증가시킬 수도 있다.
    • 내부 단편화는 정량화 시키기가 간단하다 이것은 단순히 할당된 블록의 크기와 이들의 데이터 차이의 합이다. 그래서 시간 상 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.
  • 외부 단편화
    • 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
    • 외부 단편화는 내부 단편화보다 훨씬 더 측정하기 어려운데, 그것은 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문이다.
    • 외부 단편화가 측정하기 어렵고 예측하기 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용 블록들보다는 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택한다.

9.9.5 구현이슈

• 가장 간단히 상상할 수 있는 할당기는 힙을 하나의 커다란 바이트의 배열과 이 배열 첫번째 바이트를 가리키는 포인터P로 구성할 수 있다. size 바이트를 할당하기 위해서 malloc은 현재 p값을 스택에 저장하고, p를 size만큼 증가시키고, p의 이전 값을 호출자에게 리턴한다. free는 아무것도 하지 않고 단순히 호출자에게 리턴한다.
• 이 초보적인 할당기는 디자인 공간에서 극단점에 해당한다. 각 malloc과 free가 적은 수의 인스트럭션들을 실행하기 때문에 처리량은 매우 좋다. 그렇지만, 할당기는 블록들을 하나도 재사용하지 않기 때문에 메모리 이용도는 매우 나쁠 것 이다. 처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈를 고려해야 한다.
  • 가용블록 구성 : 어떻게 가용블록을 지속적으로 추적하는가?
  • 배치 : 새롭게 할당된 블록을 배치하기 위한 가용블록은 어떻게 선택하는가?
  • 분할 : 새롭게 할당된 블록을 가용블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
  • 연결 : 방금 반환한 블록으로 무엇을 할 것인가?

9.9.6 묵시적 가용 리스트

• 모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.

• 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성한다. 헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당 되었는지 가용상태인지를 인코딩한다. 만일 더블 워드 정렬 제한 조건을 부과한다면 블록 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다. 그래서 블록 크기의 상위 29비트만 저장 할 필요가 있으며, 나머지 3비트는 다른 정보를 인코드 하기 위해 남겨둔다. 이 경우 블록이 할당 되었는지 가용 상태인지를 나타내기 위해 최소 중요 비트(할당된 비트)를 사용하고 있다.
• 헤더 다음에는 응용이 malloc을 불렀을 때 요구한 데이터가 따라온다. 데이터 다음에는 사용하지 않은 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다. 패딩을 해야하는 이유는 여러가지가 있다. 외부 단편화를 극복하기 위한 할당기 전략의 일부분일 수도 있다. 또는 정렬 요구사항을 만족하기 위해 필요할 수 있다.
• 이러한 구조를 묵시적 리스트라고 부르는데, 그것은 가용블록이 헤더 내 필드에 의해서 묵시적으로 연결 되기 때문이다. 할당기는 간접적으로 가용블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문 할 수 있다. 어떤 특별히 표시한 마지막 블록이 필요하다는 점에 유의하자.
• 장점
  • 단순성
• 중요한 단점
  • 할당된 블록을 배치하는 것과 같은 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당 된 블록과 가용 블록의 수에 비례한다는 것이다.
• 시스템의 정렬 요구 조건과 할당기의 블록 포맷 선택이 할당기에 최소 블록 크기를 결정한다는 것을 깨닫는 것이 중요하다. 할당되거나 반환된 블록 모두는 이 최소 값보다 작을 수 없다.

9.9.7 할당한 블록의 배치

• 어플리케이션이 k바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다. 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해서 결정된다. first fit, next fit, best fit이 주로 사용된다.
• First fit 은 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택한다. Next fit은 first fit 과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다. Best fit은 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다.
• First fit의 장점은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 점이다. 단점은 리스트의 앞 부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다는 것이다. Next fit은 first fit에 대한 대안으로, 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다. Next fit은 first fit에 비해서 매우 빠른 속도를 갖는데, 리스트의 앞 부분이 많은 작은 크기의 조각들로 구성되면 특히 더 이런 성향을 보인다. 그렇지만 일부 연구 결과에 의하면 Next fit이 first fit보다 최악의 메모리 이용도를 갖는것으로 밝혀졌다. 연구결과는 best fit이 일반적으로 first fit이나 next fit보다는 더 좋은 메모리 이용도를 갖는다는 것을 밝혀냈다. 그렇지만 묵시적 가용 리스트 같은 단순한 가용 리스트 구성을 사용해서는 best fit을 사용하는 단점은 힙을 완전히 다 검색해야 한다는 점이다.

백준

1931 회의실 배정

import sys

n = int(sys.stdin.readline())
time_table = []
for i in range(n):
	a, b = list(map(int,sys.stdin.readline().split()))
	time_table.append((a,b))
time_table.sort(key = lambda x : (x[1],x[0]))
end_time = 0
ans = 0

for newstart,newend in time_table:
	if newstart >= end_time:
		ans += 1
		end_time = newend

1946 신입 사원

import sys

test_case = int(sys.stdin.readline())
for i in range(test_case):
	app = []
	top = 0
	ans = 0
	n = int(sys.stdin.readline())
	for j in range(n):
		a, b = list(map(int,sys.stdin.readline().split()))
		app.append((a,b))
	app.sort()
	for j in (1,len(app)):
		if app[j][1] < app[top][1]:
			top = j
			ans += 1
	print(ans)