[TIL] Pintos - 가상 메모리 관련 개념 공부2

1. 아침 문제 풀이

1. 10026번 - 적록색약

import sys
from collections import deque

N = int(sys.stdin.readline())
pic = [list(sys.stdin.readline().strip()) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y) :
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue :
        cx, cy = queue.popleft()
        for i in range(4) :
            nx, ny = cx + dx[i], cy + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny < N :
                if not visited[nx][ny] and pic[cx][cy] == pic[nx][ny] :
                    queue.append((nx, ny))
                    visited[nx][ny] = True         

def red_green(x, y) :
    queue = deque() 
    queue.append((x, y))
    rg_visited[x][y] = True

    while queue :
        cx, cy = queue.popleft()
        for i in range(4) :
            nx, ny = cx + dx[i], cy + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny < N :
                if not rg_visited[nx][ny] :
                    if pic[cx][cy] == pic[nx][ny] or (pic[cx][cy] != 'B' and pic[nx][ny] != 'B') :
                        queue.append((nx, ny))
                        rg_visited[nx][ny] = True 

visited = [[False] * N for _ in range(N)]
rg_visited = [[False] * N for _ in range(N)]
count = 0
rg_count = 0
for i in range(N) :
    for j in range(N) :
        if not visited[i][j] :
            bfs(i, j)
            count += 1
        if not rg_visited[i][j] :
            red_green(i, j)
            rg_count += 1
print(count, rg_count)

저번에도 푼 문제로 그때와 거의 동일하게 풀었다.
그 당시보다는 적록색약 탐색시 간단하게 생각하여 구현했다.

다른 사람의 풀이를 보니 같은 탐색함수를 사용하되 적록색약 탐색전에 R, G를 합쳐준다.
1. 함수를 2개 구현
2. 이중 반복문을 한번 더 사용하여 탐색

위의 두가지를 고민해보는 문제였다.

---

2. 기본 코드 분석

1. page struct

//include/vm/vm.h
struct page {
  const struct page_operations *operations;
  void *va;              /* Address in terms of user space */
  struct frame *frame;   /* Back reference for frame */

  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

🗒️ Union

  공용체는 메모리 영역에 다른 유형의 데이터를 저장할 수 있는 특수 데이터 유형

  여러 구성원이 있지만 한 번에 하나의 구성원만 값을 포함

  ✅ 우리 시스템의 페이지가 uninit_page, anon_page, file_page 또는 page_cache가 될 수 있음을 의미

---

2. page_operations struct

//include/vm/vm.h
struct page_operations {
  bool (*swap_in) (struct page *, void *);
  bool (*swap_out) (struct page *);
  void (*destroy) (struct page *);
  enum vm_type type;
};

🗒️ 함수 포인터(Function pointer)

  함수의 시작 주소 또는 메모리 내의 실행 가능한 코드를 가리키는 포인터

void Func(int, int); //함수

void (*ptr_fun) (int, int) = Func; //함수 포인터

함수 포인터의 포인터 타입은 함수의 반환값과 매개변수에 의해 결정

→ 함수의 원형을 알아야만 해당 함수에 맞는 함수 포인터를 만들 수 있다.

 

🔗 http://www.tcpschool.com/cpp/cpp_function_pointer

---

① file일 경우 실행될 함수

// vm/file.c
static const struct page_operations file_ops = {
	.swap_in = file_backed_swap_in,
	.swap_out = file_backed_swap_out,
	.destroy = file_backed_destroy,
	.type = VM_FILE,
};

② 익명 페이지일 경우 실행될 함수

// vm/anon.c
static const struct page_operations anon_ops = {
	.swap_in = anon_swap_in,
	.swap_out = anon_swap_out,
	.destroy = anon_destroy,
	.type = VM_ANON,
};

③ 초기화 되지 않은 페이지일 경우 실행될 함수

// vm/uninit.c
static const struct page_operations uninit_ops = {
	.swap_in = uninit_initialize,
	.swap_out = NULL,
	.destroy = uninit_destroy,
	.type = VM_UNINIT,
};

✅ 함수 포인터를 사용하여 각 타입의 페이지에 알맞는 루틴이 수행된다.

#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy (page)