* 운영체제
- TLB 와 Data Cache 중 TLB가 일반적으로 hit rate이 더 높은데, 그 이유는?
- FFS(Fast File System)과 LFS(Log File System)의 차이를 설명하라
* 컴퓨터구조
- 64KiB의 4-way Set Associative Cache가 있고, 캐쉬 블럭이 16바이트, Physical Address로 32비트를 사용한다고 할 때 Cache Tag는 몇 비트인가?
- Cache의 Cold Miss의 개념은 무엇이고, Cold Miss를 줄이는 방법은 무엇인가?
=> 데이터를 첫 번째 참조할 때 발생하는 miss이며, 줄이는 방법은 없다.
- x86-IA32 머신에서 page fault, data cache miss, tlb miss 가 동시에 발생할 수 있는가? 있다면 발생 순서대로 설명해보라. (instruction miss는 고려하지 않음)
=> 1. Virtual Address를 Physical Address로 변환하는 과정에서 TLB Miss 발생 가능
2. 변환된 Physical Address를 참조할 때 캐쉬에 없는 경우 Cache Miss 발생 가능
3. 캐쉬에 데이터를 로드하기 위해 메모리를 참조하는 과정에서 Page Fault 발생 가능
- Multi-Core 환경에서 Cache를 사용할 때 발생할 수 있는 문제점은 무엇인가?
=> L1 Cache는 보통 코어 내부에 포함되기 때문에 CPU Scheduling을 통해 서로 다른 코어에서 프로세스가 실행될 경우 Miss Rate이 올라갈 수 있음
* 자료구조
(그래프 그림)
- 위 그래프에서 Prim's Algorithm으로 노드 a에서 출발하여 Minimum Spanning Tree를 구하는 과정을 설명하라.
=> 노드 a부터 edge weight이 가장 적은 edge를 하나씩 선택하여 MST를 확장
- 위 그래프에서 Dijkstra's Algorithm으로 노드 a에서 출발하여 각 노드로 향하는 Shortest Path를 구하는 과정을 설명하라
=> 노드 a부터 전체 노드까지의 거리를 무한대로 설정해놓고, 아직 방문하지 않은 노드 중 a로부터의 거리가 가장 짧은 노드를 방문하고 방문한 노드의 주변 노드의 거리를 갱신함.
- 위 두 알고리즘의 유사한 점은 무엇인가? 다른점은 무엇인가?
=> Local Optimal을 구해서 확장하면 전체의 Optimal한 해를 얻는다는 공통점, MST는 인접한 노드간의 edge weight만 고려한다면 SP는 출발 노드로부터의 거리를 고려한다는 점이 다름