24.03.26 퀴즈, 운영체제, PintOS, 백준

퀴즈

1. 페이지 테이블 접근 시 TLB가 어떻게 페이지 테이블의 성능을 향상시키는지 설명하고, TLB miss가 발생하면 시스템이 어떤 과정을 거쳐 메모리에 접근하는지 설명하세요.

• TLB는 자주 사용되는 주소 변환 정보를 빠르게 참조할 수 있도록 하는 캐시 메모리이다. TLB에 원하는 주소 변환 정보가 있으면, 페이지 테이블을 참조하지 않고 바로 물리적 주소를 얻을 수 있어 성능이 향상된다.
• TLB miss일 대 시스템은 페이지 테이블을 조회하여 물리적 주소를 찾고, 이 정보를 TLB에 업데이트 한다.

2. 페이징 기법을 사용하는 메모리 관리 시스템에서, 페이지 프레임 수를 늘리는데도 page fault가 발생하는 빈도가 오히려 늘어나는 경우가 있습니다. 이를 Belady의 역설이라고 하는데, 이런 현상이 발생하는 원인과 이를 방지하는 해결 방법에 대해 설명하세요.

• Belady’s Anomaly는 특히 FIFO 페이지 교체 알고리즘에서 관찰된다. 페이지 프레임의 수가 증가함에도 불구하고, FIFO 알고리즘은 새로운 페이지가 오래된 페이지보다 덜 필요할 수 있는 상황을 고려하지 않는다. 이로 인해, 실제로는 자주 사용되는 페이지가 교체도리 수 있고, 그 결과 페이지 폴트가 더 자주 발생한다.
• 이를 해결하기 위한 방법으로는 더 진보된 페이지 교체 알고리즘을 사용하는 것이다. LRU, LFU등의 알고리즘들은 페이지를 교체할 때 단순히 페이ㅣ지의 로드 시간뿐만 아니라 사용 빈도나 최근 사용 기록을 고려한다. 즉, Locality 개념에 기반한 제약을 가미하고, 교체/할당 정책을 보완하는 것이 해결방안이 될 수 있다.

3. 스레싱(Thrashing) 현상에 대해서 설명하세요

• 스레싱은 프로세스가 너무 자주 페이지를 교체하여 실제 유용한 작업보다 페이지 교체에 더 많은 시간을 소비하는 현상이다. 이는 일반적으로 메모리가 포화 상태이고, 멀티태스킹 환경에서 너무 많은 프로세스가 동시에 실행될 때 발생한다.

4. 운영체제가 anonymous page를 0으로 초기화하는 이유는 무엇인가요.

• anonymous page는 프로세스에 의해 동적으로 할당되는 메모리 페이지로, 이전에 다른 프로세스에 의해 사용되었을 가능성이 있다. 이러한 페이지를 0으로 초기화하지 않으면, 새로운 프로세스가 이전 프로세스의 데이터에 접근할 수 있는 보안 취약점이 발생할 수 있다.
• 0으로 초기화하는 과정은 새로운 프로세스가 페이지를 처음 사용할 때 ‘깨끗한’ 상태, 즉 어떠한 이전 데이토도 포함하지 않는 상태로 시작할 수 있도록 보장한다.

운영체제

28. 하드 디스크 드라이브

28.1 인터페이스

• 드라이브는 읽고 쓸 수 있는 매우 많은 수의 섹터(512 byte블록)들로 이루어져 있다. 디스크 위의 n개의 섹터들은 0부터 n-1까지의 이름이 붙어있다. 그렇기 때문에 디스크를 섹터들의 배열로 볼 수 있으며 0부터 n-1이 드라이브의 주소 공간이 된다.
• 멀티 섹터 작업도 가능하다. 사실 많은 파일 시스템들이 한번에 4KB(또는 그 이상)을 읽거나 쓴다. 하지만 드라이브 제조사는 하나의 512byte 쓰기만 원자성을 보장한다. 그러므로 갑작스럽게 전력 손실이 발생한다면 대량의 쓰기 중에 일부만 완료될 수 있다.(때로는 이런 현상을 찢어쓰기(torn write)라고 부른다).
• 디스크 드라이브는 드라이브의 주소공간에서 가깝게 배치되어 있는 두 개의 블록을 접근하는 것은 멀리 떨어져 있는 두 개의 블록을 접근하는 것보다 빠르다고 가정한다. 또 다른 가정은 연속적인 청크의 블록을 접근하는 것이 가장 빠르며 어떤 랜덤 접근 패턴보다 매우 빠르다는 것이다.

28.2 기본 구조

• 원형의 딱딱한 표면을 갖고 있는 플래터(Platter)에 자기적 성질을 변형하여 데이터를 지속시킨다. 디스크는 하나 또는 그 이상의 플래터를 가지고 있으며 각각은 2개의 표면(surface)을 갖고있다. 이런 플래터는 대체로 단단한 물질로 만들어지며 드라이브의 전원이 나가더라도 비트를 드라이브에 영구적으로 저장하기 위해 얇은 자성층이 입혀져 있다.
• 플래터들은 회전 축(spindle)이라는 것으로 고정되어 있는데, 이 축은 모터와 연결이 되어있어서 플래터를 일정한 속도로 회전시킨다.
• 각 표면에 동심원을 따라 배치되어있는 섹터들 위에 데이터가 부호화된다. 이때 동심원 하나를 트랙(track)이라고 한다.
• 표면 위를 읽거나 쓸 때에는 디스크의 자기적 패턴을 감지하거나(읽거나) 변형을 유도하는(쓰는) 기계적 장치가 필요하다. 읽기와 쓰기 동작은 디스크 헤드(disk head)라는 것을 통해 할 수 있으며 각 표면마다 그런 헤드가 하나씩 존재한다. 디스크 헤드는 디스크 암(disk arm)에 연결되어 있으며 이것을 통해서 헤드가 원하는 트랙 위에 위치하도록 이동시킬 수 있다.

28.3 간단한 디스크 드라이브

단일 트랙 지연 시간 : 회전지연

• 디스크는 디스크 헤드 아래에 원하는 섹터가 위치하기를 기다린다. 이러한 기다림은 현대 드라이브에서도 흔하게 발생하며 I/O 서비스 시간에서 중요한 요소이기 때문에 회전형 지연(rotational delay)이라는 특별한 이름을 갖고있다.

멀티 트랙 탐색 시간

• 현대 디스크들은 수백만개의 트랙을 갖고있다. 디스크가 멀리 떨어져 있는 섹터에 대한 요청을 받았을 때, 이 요청을 처리하기 위해 드라이브는 디스크 암을 올바른 트랙 위에 위치시킨다. 이 과정을 탐색(seek)이라고 한다. 회전과 더불어서 탐색은 가장 비싼 디스크 동작 중 하나이다.
• 탐색은 여러 단계로 되어있다.
• 첫 번째는 가속 단계로 디스크의 암이 움직이기 시작한다. 디스크 암이 최고속도로 움직이는 활주 단계를 지나고, 디스크 암이 속도가 줄어드는 감속 단계 이후에 안정화 단계에서 정확한 트랙위에 헤드가 조심스럽게 위치하게 된다. 드라이브가 정확한 트랙위에 확실히 위치해야 하기 때문에 안정화 시간(settling time)은 매우 중요하며 0.5에서 2msec 정도로 오래 걸린다.
• 탐색 이후 디스크 암은 올바른 트랙 위에 헤드를 위치시킨다.
• 탐색 과정에서 암이 원하는 트랙위로 이동을 하는 동안에 당연하게 플래터 역시 회전한다. 섹터가 디스크 헤드 아래로 막 지나가고 있기 때문에 약간의 회전 지연 후에 전송을 완료할 수 있다.
• 섹터가 디스크 헤드를 지나가게 되면 I/O의 마지막 단계인 전송이 이루어져 표면 위의 데이터를 읽거나 쓰게 된다.

그 외의 세부사항

• 많은 드라이브는 트랙 비틀림(track skew)이라 불리는 기술을 채용하여 트랙의 경계를 지나서 순차적으로 존재하는 섹터들을 올바르게 읽을 수 있게 한다.
• 한 트랙에서 다른 트랙으로 전환하는 경우에, 바로 인접한 트랙으로 전환되는 경우에도, 디스크의 헤드를 다시 위치시키기 위한 시간이 필요하다. 이와 같은 비틀림이 없다면 헤드가 다음 트랙으로 넘어갔을때 다음에 읽어야 하는 블럭이 이미 헤드를 지나쳤을 수도 있기 때문에 다음 블럭을 접근하기 위해 거의 한 바퀴에 해당하는 회전지연을 감수해야 한다.
• 또 바깥측에 공간이 많다는 구조적인 이유 때문에 바깥 측 트랙에 더 많은 섹터들이 있다. 이러한 트랙들을 흔히 멀티 구역(multi zoned) 디스크 드라이브라고 부른다. 디스크들은 여러 구역으로 나뉘어 있으며 한 구역은 표면 위에 연속적으로 존재하는 트랙들의 집합이다. 각 구역내의 트랙은 같은 수의 섹터들을 포함하고 있으며 바깥측 구역에는 더 많은 수의 섹터를 갖고 있다.
• 현대 디스크 드라이브의 가장 중요한 부분은 캐시(cache)로서, 역사적인 이유로 때로는 트랙 버퍼(track buffer)라고도 부른다. 이 캐시는 드라이브가 디스크에서 읽거나 쓴 데이터를 보관하는데 사용한다.
• 쓰기 요청 완료 보고의 경우 드라이브의 선택지는 두 개가 있다.
  • write-back : 메모리에 데이터가 기록된 시점에 쓰기가 완료를 보고한다.
  • write-through : 디스크에 실제로 기록되었을 대 완료되었다고 보고한다.
  • 만일 파일 시스템이나 응용 프로그램이 정확함을 위해 특정 순서로 디스크에 기록해야 한다고 할때 write-back을 사용하면 문제가 될 수 있다.

28.4 디스크 스케줄링

• 각 작업의 길이가 얼마나 될지 알 수 없는 작업 스케줄링과 다르게 디스크 스케줄링의 경우, 디스크 요청 작업이 얼마나 길지를 꽤 정확히 예측할 수 있다. 요청의 탐색과 회전 지연의 정도를 예측하면 각 요청이 얼마나 오래 걸릴지 디스크 스케줄러가 알 수 있기 때문에 처리할 수 있는 가장 빠른 요청을 선택할 수 있다. 이와 같이 디스크는 SJF(shortest job first, 짧은 작업 우선)의 원칙을 따르려고 노력한다.

SSTF : 최단 탐색 시간 우선(shortest-seek-time-first)

• SSTF는 트랙을 기준으로 I/O 요청 큐를 정렬하여 가장 가까운 트랙의 요청이 우선 처리되도록 한다.
• 문제점이 있는데 드라이브의 구조는 호스트 운영체제에게 공개되어 있지 않으며 운영체제는 그저 블록들의 배열로만 인식한다. 운영체제는 SSTF 대신 NBF(Nearest-block-first, 가장 가까운 블록 우선) 방식을 사용해서 이 문제를 해결한다. 이 방식은 가장 가까운 블록 주소에 접근하는 요청을 다음에 처리하도록 스케줄한다.
• 두 번째는 기아(Starvation)에 대한 문제이다

엘리베이터(SCAN 또는 C-SCAN)

• 기아 문제는 SCAN을 통해 해결했다. 이 알고리즘은 트랙의 순서에 따라 디스크를 앞 뒤로 가로지르며 요청을 서비스한다. 디스크를 가로지르는 것을 스위프(sweep)라고 부른다. 따라서 어떤 요청이 이번 스위프에 이미 지나간 트랙에 대해 들어온다면 바로 처리되지 않고 다음 번 스위프(반대방향)에 처리되도록 큐에서 대기한다.
• C-SCAN은 Circular SCAN의 약자이다. 디스크를 양방향으로 스위프하는 대신 밖에서 안으로만 스위프한다. 그리고 한번 스위프하면 다시 밖으로 돌아간다. 이런식으로 동작하면 밖과 안쪽 트랙에 대한 요청이 더 공정하게 처리된다. SCAN은 안팎으로 가로지르면서 중간 트랙을 우대하는 방식이기 때문이다.
• SCAN이 현재 위치와 가까운 층 위조로 이동하는 것이 아니라 위 또는 아래로 이동해서 엘리베이터 알고리즘이라 불린다.
• 회전을 무시하기에 최고의 스케줄링 기술을 의미하지는 않는다.

SPTF : 최단 위치 잡기 우선

• 탐색 시간이 회전 지연보다 더 크다면 SSTF는 잘 동작한다. 하지만 탐색이 회전보다 훨씬 빠르다면 더 먼 탐색을 통해 바깥 트랙에 있는 요청을 먼저 처리하는 것이 짧게 탐색하여 가까운 중간의 트랙으로 이동해서 요청을 처리하는 것보다 낫다.
• 현대 드라이브들은 앞서 본 것과 같이 탐색과 회전이 거의 비슷하고 따라서 SPTF가 유용하고 성능을 개선 시킬 수 있다. 하지만 트랙의 경계가 어디인지 현재 디스크 헤드가 어디에 있는지(회전의 관점에서)를 정확히 알 수 없기 때문에 운영체제에서 이것을 구현하기는 매우 어렵다. 그러므로 SPTF는 드라이브 내부에서 실행된다.

다른 스케줄링 쟁점들

• 디스크 스케줄러가 수행하는 중요한 관련 작업은 I/O병합(I/O merging)이다. 연속된 블록을 읽는 요청이 있는 경우 스케줄러는 블록 요청을 병합하여 두 블록 길이의 요청으로 만든다. 병합된 요청을 반영하기 위하여 스케줄러는 해당 요청들을 재배치한다. 디스크로 내려보내는 요청의 개수를 줄이면 오버헤드를 줄일 수 있기 때문에 운영체제에서 병합은 특히 중요하다.
• 현대 스케줄러가 해결해야하는 마지막 문제는 다음과 같다. 디스크로 I/O를 내려보내기 전에 시스템은 얼마나 기다려야 하는가? 단 하나의 I/O만 있더라도 디스크로 즉시 내려보내야 한다고 순진하게 생각할 수도 있다. 이와 같은 방식은 처리할 요청이 있는 한 디스크는 유휴 상태가 되지 않도록 하는 작업보전(work-conserving) 방식이다. 하지만 예측 디스크 스케줄링(anticipactory disk scheduling) 연구에 따르면 때로는 잠시 기다리는 것이 더 좋다는 것을 보였으며, 이를 작업 비보전(non-work-conserving)방식 이라고 부른다. 기다리다보면 새로운 좀 더 좋은 요청이 디스크에 도달할 수 있으므로 전체적인 효율이 좋아지게 된다.

PintOS

깃북을 보면서 pair programming으로 anonymous page 까지 일단 구현을 해보았다.

하지만 but.. 문제 발생!

load쪽에서 문제가 발생했고, 처음에는 set up stack에서 발생했겠거니 생각했었는데, 계속 찾아보고 printf를 찍어본 결과 load_segment에서 터진다는 것을 발견했다.

일단 내일.. 아니 오늘의 나에게 디버깅을 넘긴다

무섭다 vm 넘모링 넘모링 어렵당..

백준

1504 특정한 최단 경로

#include <bits/stdc++.h>
using namespace std;

int INF = 98765432;
vector<pair<int, int>> vec[802];
int dist[803];
void bfs(int a)
{
    memset(dist, INF, sizeof(dist));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    queue.push(make_pair(0, a));
    dist[a] = 0;
    while (!queue.empty())
    {
        int sum_distance = queue.top().first;
        int x = queue.top().second;
        queue.pop();
        
        if (dist[x] < sum_distance)
            continue;
        for (int i = 0; i<vec[x].size(); ++i)
        {
            int nx = vec[x][i].first;
            int ncost = sum_distance + vec[x][i].second;
            if (dist[nx] > ncost)
            {
                queue.push({ ncost,nx });
                dist[nx] = ncost;
            }
        }
    }
}

int compare_ab(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

int main() 
{
    int node, edge, result;
    cin >> node >> edge;
    for (int i = 0; i < edge; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        vec[a].push_back({ b,c });
        vec[b].push_back({ a,c });
    }
    int dest1, dest2;
    cin >> dest1 >> dest2;
    
    bfs(1);
    int to_dest1 = dist[dest1];
    int to_dest2 = dist[dest2];

    bfs(dest1);
    int dest1_to_dest2 = dist[dest2];
    int dest1_to_node = dist[node];

    bfs(dest2);
    int dest2_to_node = dist[node];

    result = compare_ab(INF, to_dest1 + dest1_to_dest2 + dest2_to_node);
    result = compare_ab(result, to_dest2 + dest1_to_dest2 + dest1_to_node);
    if (result >= INF)
        cout << -1;
    else
        cout << result;

}

• 다익스트라를 활용해서 푸는 문제이다.
• 다익스트라를 이용해서 무조건 거쳐야하는 정점까지 최단 거리를 구하고, 다시 그 정점부터 node정점까지 최단거리를 구해주면 쉽게 해결할 수 있다. 즉, 다익스트라를 3번 써야한다.
• a-b-c, b-a-c를 구해서 비교해 답을 제출해야 한다.