24.04.01 운영체제, PintOS, 백준

아니 벌써 4월임..ㄷㄷ 이거 신기한거시와요 하와와

어느새 4월이 왔슴니다.. 어느새 2분기가 시작했다구욧!! 시ㅣㄴ나기한거시에요…

운영체제

34. 분산시스템

• 웹브라우저가 지구상 어딘가에 있는 웹 서버에 접속하면 클라이언트/서버 분산 시스템이라는 구조에 한 구성원이 된다.
• 분산 시스템의 핵심 사안은 실패와 고장의 극복이다. 개별 구성요소들은 자주 고장나지만 기계들은 고장없는 시스템처럼 보이도록 만들 수가 있다.
• 또 다른 중요한 문제가 있다. 시스템 성넝은 매우 중요한 요소이다. 분산된 시스템들을 연결하는 네트워크에서는 시스템 설계자들은 주어진 목적을 달성하는데 많은 신경을 써야한다.
• 마지막으로 보안 역시 매우 중요한 요소이다. 원격 사이트를 접속할 때, 접속한 사이트가 진짜 원했던 사이트인지를 확신할 수 있는지도 중요한 문제이다.

34.1 통신의 기본

• 최신 네트워킹의 핵심 가정은 통신은 신뢰할 수 없다는 것이다. 종류에 상관 없이 패킷들은 정기적으로 손실되거나, 손상되었거나, 목적지에 도착하지 못할 수도 있다.
• 패킷 손실이나 손상에는 많은 이유가 있다. 그 중 좀 더 중요한 원인은 네트워크 스위치, 라우터 또는 연결의 종단점에서 충분히 버퍼링 할 수 없기 때문이다. 라우터에 패킷이 도착한다고 할 때 패킷이 처리되려면 라우터 내부 어딘가에 존재하는 메모리에 저장되어야 한다. 한 번에 많은 패킷들이 도착한다면 라우터의 메모리가 그 모든 패킷들을 다 수용할 수 없을 수 있다. 그 시점에 라우터가 내릴 수 있는 선택은 패킷을 포기(drop)하는 것이다.

34.2 신뢰할 수 없는 통신 계층

• 간단한 방법은 아무런 조치도 취하지 않는 것이다. 어떤 응용 프로그램들은 패킷 손실시 대응 방법을 가지고 있기 때문에 메시지 계층과 직접 통신하도록 하는 것이 이로울 때도 있다. 신뢰할 수 없는 계층에 대한 좋은 예 중 하나는 거의 모든 현대 시스템에 존재하는 UDP/IP 네트워크 스택을 들 수 있다. UDP를 사용하기 위해서는 소켓 API를 이용하여 통신지점을 생성한다. 다른 편 기계의 프로세스들은 UDP 데이터 그램을 원래의 프로세스로 전송한다.
• 패킷을 잃어버리는, 메시지가 목적지에 도달하지 못하는 상황이 발생하더라도 발신측은 손실에 대해서 전혀 알 수가 없다. 하지만 모든 실패에 대해서 전혀 대비를 못한다는 것은 아니고 UDP는 체크섬을 포함하고 있기 때문에 일부 패킷 손상은 검출할 수 있다.

34.3 신뢰할 수 있는 통신 계층

• 신뢰할 수 있는 통신 계층을 만들기 위해서는 패킷 손실에 대응할 수 있는 새로운 메커니즘과 기술이 필요하다. 발신자는 수신자가 메시지를 수신했다는 것을 알 수 있는 방법이 필요하다.
• 우리가 사용할 기술은 확인(acknowledgement) 또는 짧게 ack라고 하는 것이다. 개념은 간단하다. 발신자는 메시지를 수신자에게 보낸다. 수신자는 받았다는 것을 알리기 위해서 짧은 메시지를 다시 보낸다.
• 발신자가 메시지가 도착했다는 ack를 받으면 수신자가 메시지를 잘 받았다는것을 확신할 수 있다.
• 이와 같은 경우를 다루기 위해서 타임아웃이라고 하는 추가적인 장치가 필요하다. 발신자가 메시지를 보낼 때 발신자는 타이머를 설정하여 일정시간이 흐른 후에는 종료되도록 한다. 만약 그 시간안에 ack를 받지 못한다면, 발신자는 메시지를 잃어버렸다고 판단한다. 발신자는 이번엔 전달되겠지 하는 희망을 갖고 똑같은 메시지를 잃어버렸다고 판단한다. 발신자는 이번엔 전달되겠지 하는 희망을 갖고 똑같은 메시지의 전송을 재시도 한다. 이것이 제대로 동작하려면 발신자는 재전송에 대비하여 메시지의 사본을 갖고 있어야 한다. 이 방법을 타임아웃/재시도 방식이라고 부른다.
• 불행하게도, 현재 상태의 타임아웃/재시도 로는 충분하지가 않다. 원래의 메시지가 손실되는 것이 아니라 ack메시지가 손실되는 경우 발신자 측에서 본다면 ack를 못 받는 상황과 마찬가지이기 때문에 타임아웃과 재시도 방식이 제대로 동작하는 것처럼 보인다. 하지만 수신자측에서는 그렇지 않다. 수신자의 경우 메세지를 두 번 받게된다. 그러므로 신뢰성 있는 메시지 계층을 목표로 한다면 수신측도 각 메시지를 정확히 한 번만 받는다는 보장이 필요하다.
• 수신자가 중복된 메시지를 검출할 수 있으려면 발신자가 각 메시지를 구분해서 전송해야 하며 수신자는 각 메시지를 이전에도 받은적이 있는지 파악할 수 있는 방법이 필요하다.
• 중복된 메시지를 검출하는 방법 중 적은 양의 메모리를 사용하면서 이 문제를 해결하는 좀 더 간단한 방법은 순서 카운터(sequence counter)라고 하는 방법이다. 순서 카운터를 사용하기 위해서 발신자와 수신자가 양쪽에서 관리할 어떤 시작값에 서로 동의한다. 메시지를 보내면서 현재의 카운터 값을 함께 전송한다. 이 카운터 값은 메시지의 ID 역할을 한다. 메시지가 전송된 후에 발신자는 값을 증가시킨다.
• 수신자는 이 카운터 값을 발신자 측으로부터 도착하는 메시지의 예상 ID값으로 사용한다. 만약 수신한 메시지의 ID가 수신자의 카운터와 동일하다면 메시지에 대해 ack를 보내고 메시지를 응용 프로그램에 전달한다. 이 경우에 수신자는 이 메시지가 처음 받은 것이라고 결론을 내린다. 수신자는 이후에 카운터를 증가시키고 다음 메시지를 기다린다.
• ack이 손실된 경우 발신자는 타임아웃으로 인해 메시지 N을 재전송할 것이다. 이번에는 수신자의 카운터가 더 크기 때문에 발신자는 메시지를 이미 받았었다는 것을 안다. 그러므로 메시지에 대해서 ack를 전송하지만 메시지를 응용 프로그램에게 전달하지는 않는다. 이런 간단한 방식의 순서 카운터를 사용하여 중복수신을 피할 수 있다.

34.4 통신 추상화

• 분산 공유 메모리(DSM : distributed shared memory) 시스템은 하나의 프로세스가 서로 다른 기계들 위에서 커다란 가상주소 공간을 공유할 수 있도록 한다. 이 과정을 통해 분산된 연산이 마치 멀티쓰레드 응용프로그램처럼 보이도록 만들었다.
• 대부분의 DSM 시스템은 운영체제의 가상메모리 시스템 기반으로 동작한다. 페이지가 접근 되었을 두 가지 경우가 일어날 수 있다. 첫 번째(최선)는 페이지가 이미 기계내에 있어서 빠르게 데이터를 가져올 수 있는 경우다. 두 번째는 페이지가 현재 다른 기계에 있는 경우다. 이때는 페이지 폴트가 발생한다. 페이지 폴트 핸들러는 다른 기계에게 메시지를 보내 페이지를 달라고 요청하고, 그 결과를 프로세스의 페이지 테이블에 삽입한 후 실행을 계속한다.
• DSM은 실패를 처리하는 방식과 성능의 문제로 대중적으로 사용하지 않는다.

34.5 Remote Procedure Call(RPC)

• RPC는 간단한 목표를 가지고 있다. 원격 기계에서의 코드실행을 로컬 내의 함수를 부리는 것처럼 간단하게 복잡하지 않게 만드는 것이다. 클라이언트는 프로시저 호출을 하고 잠시 후에 결과를 리턴받는다. 서버는 공지할(export) 루틴을 정의한다. 나머지는 RPC 시스템이 두 부분으로 나누어 담당한다. 바로 스텁생성기(stub generator)와 런타임 라이브러리(run-time library)이다.

스텁 생성기

• 함수의 인자들을 묶는 불편함을 없애고 자동적으로 메시지를 만드는 것이 스텁생성기의 일이다. 많은 장점들이 있다. 수작업으로 그런 코드를 작성할 경우 발생할 수 있는 작은 실수들을 막아주며, 더 나아가 스텁 컴파일러가 그런 코드를 최적화 할 수도 있기 때문에 성능을 개선할 수도 있다.
• 서버가 클라이언트에게 공지할 프로시저들의 집합을 컴파일러에게 입력으로 전달한다.
• 스텁 생성기는 이런 종류의 인터페이스를 사용하여 몇 개의 다른 코드를 생성해낸다. 클라이언트용으로 인터페이스에 명시된 함수들로 구성된 클라이언트 스텁을 생성한다. 클라이언트 프로그램이 RPC 서비스를 이용하기 원하면 클라이언트 스텁을 생성하여 호출한다. 클라이언트 스텁의 각각의 함수들이 원격 프로시저 호출을 위한 일을 처리한다. 클라이언트 스텁의 func1() 코드는 다음과 같은 일을 한다.
  • 메시지 버퍼 생성
  • 메시지 버퍼에 필요 정보를 병합 : 버퍼에 이 정보를 담는 과정을 인자들 합병하기(marshaling) 또는 메시지를 직렬화(serialization)라고 표현하기도 한다.
  • RPC 서버에 메시지 전송
  • 응답 대기 : 함수 호출은 대부분 동기식(synchronous)이기 때문에 완료가 될 때까지 대기한다.
  • 리턴 코드와 인자풀기 : 스텁의 내용들을 풀기 때문에 합병 해제하기 또는 역직렬화라고 부른다.
  • 호출자에게 리턴하기
• 서버용 코드도 생성된다. 서버측에서 수행되는 과정은 다음과 같다.
  • 메시지 풀기 : 도착하는 메시지에서 합병해제하기 또는 역직렬화를 통해 정보를 추출한다. 함수 식별자와 인자들이 추출된다.
  • 실제 함수 호출하기
  • 결과를 통합
  • 응답 전송하기
• 스텁 컴파일러에서 고려해야 할 몇 가지 중요한 문제들이 있다. 첫 번째는 복잡한 구조의 인자나 다수의 인자를 전달하는 문제이다. 즉, 복잡한 자료구조를 어떻게 패키지화 해서 전송할 것이가. 일반적으로 잘 알려진 데이터 형을 사용하거나 자료구조에 해석하는 방법에 대한 내용을 추가하여 컴파일러가 바이트의 어떤 부분을 직렬화 할지 알 수 있도록 한다.
• 또 다른 문제는 병행성을 고려하여 서버를 구성하는 것이다. 단순한 서버는 간단한 반복문에서 요청을 대기하면 한번에 한 요청씩 처리한다. 하지만 엄청나게 비효율적일 수 있다. 그래서 서버들은 병행성은 이용하여 구성된다. 흔한 구성 방식은 쓰레드 풀을 사용하는 것이다. 이 구성 방식은 서버를 시작할 때 정해진 수의 쓰레드들을 생성한다. RPC 호출이 도착하면 메인 쓰레드가 워커 쓰레드로 보낸다. 메인 쓰레드는 계속 PRC 호출을 받기 위해 대기한다. 또 다른 요청이 도착하면, 다시 다른 워커 쓰레드에게 전달한다. 이와 같은 방식으로 서버내에서 병행 실행을 활용하여 활용률을 높일 수 있다. RPC 서버를 구성하는 데 필요한 프로그래밍 복잡도가 약간 늘어난다. RPC 호출의 올바른 동작을 위해 락이나 기타 동기화 기법들을 써야 하기 때문이다.

런타임 라이브러리

• 성능과 신뢰성에 관한 대부분의 문제들을 처리하고 있다. 런타임 계층을 구현하는데 필요한 핵심 사안 몇 가지를 다루도록 한다.
• 극복해야 하는 첫 번째 도전거리 중에 하나는 원격 서비스의 위츠를 찾는 문제이다. 이름(naming)에 관한 이 문제는 분산 시스템에서는 흔한 것이고 또 어떤 면에서는 현재 논의 주제에서 벗어난 것일 수도 있다. 가장 간단한 방법은 기존의 시스템을 활용하는 것이다.(현재의 인터넷 프로토콜이 사용하는 호스트의 이름과 포트번호를 활용한다) 그런 시스템에서 클라이언트는 RPC 서비스를 실행하기를 원하는 기계의 호스트 이름 또는 IP주소 그리고 포트 번호를 반드시 기록한다.(포트번호는 기계에서 일어나는 통신작업을 구별할 수 있는 방법이며, 이를 통해 여러개의 통신 작업들이 동시에 진행될 수 있다.) 그 다음, 패킷이 특정 주소로부터 시스템에 있는 임의의 다른 기계로 전달될 수 있는 메커니즘을 제공해야 한다.
• 클라이언트가 원격지의 서비스를 위해 어떤 서버와 소통할지 알아냈다면 그 다음의 질문은 RPC를 어떤 전송 계층 프로토콜 위에 만들지를 결정해야 한다. 신뢰할 수 있는 TCP/IP와 같은 것을 사용할 것이냐. 아니면 UDP/IP 같은 신뢰할 수 없는 통신 계층 위에 만들것이냐

PintOS

STACK_GROWTH구현을 성공하고, MMAP, MUNMAP 구현을 시작했다.

그 과정에서 우리가 전에 page나 frame을 사용할 때, 사용하던 palloc을 malloc으로 바꾸는 과정을 거쳤다. 페이지와 관련된 테스트 케이스의 경우 굉장히 큰 페이지를 할당받으려고 하는데, 그런 경우 palloc을 사용하면 하나의 페이지만 처음에 할당을 했기 때문에 pass하지 못하고 fail만 나왔다.

malloc의 경우 큰 메모리를 할당하기 때문에 malloc을 써서 통과했다.

int read(int fd, void *buffer, unsigned size)
{
	...
	if (p && !p->writable)
	...
}

file에 대한 read,write 시스템 콜을 활용하는 test가 있었다. 그 경우 동적 할당을 하지 않고 정적 변수로 사용했기 때문에 페이지 테이블에 존재하지 않았고, spt 테이블에서 찾으려고 하니 계속 NULL을 반환했다. 그래서 exit(-1) 조건을 삭제하고, 버퍼에 관한 쓰기 권한을 체크해줬다.

백준

14502 연구소

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

const int mxN = 8, dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
int n, m, a[mxN][mxN];
int tmp[mxN][mxN];
int ans = 0;
bool vis[mxN][mxN];

void copy(int tmp[mxN][mxN], int a[mxN][mxN]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmp[i][j] = a[i][j];
		}
	}
}
void bfs()
{
	int after[8][8];
	copy(after, tmp);

	queue<pair<int, int>> q;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (after[i][j] == 2)
				q.push({ i,j });
		}
	}
	while (q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; ++k)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (after[nx][ny] == 0)
			{
				after[nx][ny] = 2;
				q.push({ nx,ny });
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (after[i][j] == 0)
				++cnt;
		}
	}
	ans = max(ans, cnt);
}

void wall(int cur)
{
	if (cur == 3)
	{
		bfs();
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (tmp[i][j] == 0)
			{
				tmp[i][j] = 1;
				wall(cur + 1);
				tmp[i][j] = 0;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (a[i][j] == 0)
			{
				memset(vis, 0, sizeof(vis));
				copy(tmp, a);
				tmp[i][j] = 1;
				wall(1);
				tmp[i][j] = 0;
			}
		}
	}
	cout << ans;
}

• 바이러스가 상하좌우로 퍼지기 때문에 BFS를 사용했다.
• 벽을 3개 세울 수 있기 때문에 모든 빈칸중 벽을 건설해 안전 영역을 구해야한다.
• 원본 그래프를 복사하며 사용한다.