[OSTEP] 스터디 7주차 - 메모리 가상화 3 - 숙제

1.먼저 -n 10 -H 0 -p BEST -s 0 플래그로 실행하여 몇 개의 무작위 할당과 해제를 생성하세요. alloc()/free()가 무엇을 반환할지 예측할 수 있나요? 각 요청 후에 프리 리스트의 상태를 추측할 수 있나요? 시간이 지남에 따라 프리 리스트에서 무엇을 알 수 있나요?

A : 풀이 방법

[1000..............................................................1099]
Free List: [ addr:1000 sz:100 ]Free(ptr[0]) : 병합 없음, 반환 값 0

1) Alloc(3)

1. 프리 리스트에서 “3B를 담을 수 있는 가장 작은” 블록 찾기
   → 후보는 [1000,100] 하나뿐 → 선택
2. 선택한 블록을 앞에서 3B 잘라서 주고, 나머지(97B) 를 프리로 남김

• 반환 포인터: 1000
• 새 프리 리스트: [1003,97]

[1000 1001 1002][1003.................................1099]
  ^^^ alloc 3B      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ free 97B
Free List: [ addr:1003 sz:97 ]

2) Free(1000, size=3)

• 병합이 꺼져 있어서, 그냥 “주소 순(ADDRSORT)”으로 끼워 넣기만 함
• 반환값: 0

프리 리스트(주소순):

[1000,3] [1003,97]

그림:

[1000 1001 1002][1003.................................1099]
  ^^^ free 3B        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ free 97B
Free List: [1000,3] [1003,97]

정답

ptr[0] = Alloc(3) returned 1000 (searched 1 elements)
Free List [ Size 1 ]: [ addr:1003 sz:97 ]

Free(ptr[0])
returned 0
Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1003 sz:97 ]

ptr[1] = Alloc(5) returned 1003 (searched 2 elements)
Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1008 sz:92 ]

Free(ptr[1])
returned 0
Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:92 ]

ptr[2] = Alloc(8) returned 1008 (searched 3 elements)
Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]

Free(ptr[2])
returned 0
Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]

ptr[3] = Alloc(8) returned 1008 (searched 4 elements)
Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]

Free(ptr[3])
returned 0
Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]

ptr[4] = Alloc(2) returned 1000 (searched 4 elements)
Free List [ Size 4 ]: [ addr:1002 sz:1 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]

ptr[5] = Alloc(7) returned 1008 (searched 4 elements)
Free List [ Size 4 ]: [ addr:1002 sz:1 ][ addr:1003 sz:5 ][ addr:1015 sz:1 ][ addr:1016 sz:84 ]

2. 프리 리스트를 검색할 때 최악 적합(Worst-fit) 정책(-p WORST)을 사용하면 결과가 어떻게 달라지나요? 무엇이 바뀌나요?

A : Best Fit에서는 필요한 크기에 가장 맞는 블록을 고른다. 그래서 작은 블록을 먼저 소모한다. Worst Fit에서는 가장 큰 블록을 고른다. 그래서 작은 블록은 그대로 남기고 큰 블록에서 잘라간다.

3. 최선 적합(First-fit) 정책(-p FIRST)은 어떤가요? 최선 적합을 사용하면 무엇이 빨라지나요?

A : 평균 탐색 길이가 감소한다. 왜냐하면 가장 처음 맞는 곳에서 바로 블록을 사용하기 때문이다. 구현이 단순하다.

4. 위의 질문들에서, 리스트를 어떤 순서로 유지하느냐에 따라 일부 정책의 자유 블록 탐색 시간이 달라질 수 있습니다. 다양한 프리 리스트 순서(-l ADDRSORT,-l SIZESORT+,-l SIZESORT-)를 사용하여 정책과 리스트 순서가 어떻게 상호작용하는지 확인하세요.

A :

리스트 순서 (-l) \ 정책 (-p)	FIRST (처음 맞는 곳)	BEST (가장 작은 적합)	WORST (가장 큰 적합)
ADDRSORT (주소 오름차순)	짧음: 앞쪽에서 종종 멈춤	김: 최솟값 찾으려면 보통 전수 스캔	김: 최댓값 찾으려면 보통 전수 스캔
SIZESORT+ (크기 오름차순)	짧음: 작은 것부터 보니 첫 적합이 빠름 → 거의 BEST처럼	짧음: 처음 만나는 적합 = 베스트핏 → 초기 정지	김: 끝쪽(큰 블록)을 찾아가야 해서 전수에 가깝게
SIZESORT- (크기 내림차순)	짧음: 큰 것부터 보니 첫 적합이 빠름 → 거의 WORST처럼	김: 끝쪽(작은 적합)을 찾아야 해서 전수에 가깝게	짧음: 처음 만나는 적합 = 워스트핏 → 초기 정지

5. 프리 리스트의 병합(Coalescing)은 매우 중요할 수 있습니다. 무작위 할당 수를 늘려보세요(예: -n 1000). 시간이 지남에 따라 큰 할당 요청에는 어떤 일이 일어나나요? 병합 없이(즉, -C 플래그 없이) 그리고 병합과 함께 실행해 보세요. 결과에 어떤 차이가 있나요? 각 경우에 시간에 따른 프리 리스트의 크기는 어떻게 되나요? 이 경우 리스트의 순서가 중요한가요?

A : 큰 할당을 오래 성공시키려면 병합(-C ON) 이 필수이고, 탐색 속도는 정책×리스트 정렬(BEST↔SIZESORT+, WORST↔SIZESORT-, FIRST는 대체로 짧음) 로 최적화하되, 병합이 꺼지면 시간이 갈수록 조각화로 큰 요청 실패가 급증한다.

6. 할당된 블록의 비율을 나타내는 -P를 50 이상으로 변경하면 어떻게 되나요? 이 비율이 100에 가까워지면 할당은 어떻게 되나요? 0에 가까워지면요?

A:

• P > 50 (할당 위주)
  • 라이브 블록이 계속 늘어남 → 프리 리스트가 줄고, 큰 덩어리부터 잘려나감.
  • 시간이 갈수록 큰 요청 실패가 늘어남(특히 -C OFF일 때).
  • searched k는 초반엔 짧다가, 남은 자유공간이 잘게 쪼개질수록 점점 길어질 수 있음.
• P → 100 (거의 전부 할당)
  • 해제가 거의 없어 언젠가 힙 고갈 → 이후 Alloc은 연속 실패.
  • -C 유무나 정책/정렬의 차이가 거의 영향 없음(풀릴 메모리가 없으니까).
• P < 50 (해제 위주)
  • 라이브 블록이 줄어 프리 리스트가 커짐.
  • -C ON이면 큰 블록으로 재결합되어 큰 요청 성공률↑ / searched↓.
  • -C OFF면 프리 리스트 길이만 길어지고(작은 구멍 증가) → searched↑, 큰 요청은 조각화 때문에 실패할 수 있음.

 

7. 고도로 단편화된 프리 공간을 생성하려면 어떤 종류의 특정 요청을 만들 수 있나요? -A 플래그를 사용하여 단편화된 프리 리스트를 생성하고, 다양한 정책과 옵션이 프리 리스트의 구성을 어떻게 변경하는지 확인하세요.

A: -A로 교차 해제 + 살짝 작은 재할당을 반복하면 초미세 조각(1B)들이 누적되어 고단편화가 잘 생기고, 이때 BEST/FIRST+ADDRSORT는 슬리버를 양산, WORST+SIZESORT-는 큰 덩어리를 깎아 중형 조각을 확산시킵니다; 코얼레싱(-C ON) 을 켜면 인접 해제들이 즉시 합쳐져 큰 요청 생존성이 크게 개선됩니다.