24.02.28 운영체제, 백준

운영체제

2. 프로세스

• 프로세스는 실행 중인 프로그램으로 정의한다.
• 운영체제는 CPU를 가상화시켜 환상을 만들어 낸다.
• 시분할(time sharing)이라고 불리는 이 기법은 원하는 수 만큼 프로세스를 동시에 실행 할 수 있게 한다. 시분할 기법은 CPU를 공유하기 때문에 각 프로세스의 성능은 낮아진다.
• 운영체제의 지능은 정책(Policy)의 형태로 표현된다. 정책이란 운영체제에서 어떤 결정을 내리는데 사용되는 알고리즘이다. 다수의 실행 가능한 프로그램이 있을 때 운영체제의 스케줄링 정책(Scheduling Policy)이 이러한 결정을 내린다.

2.1 프로세스의 개념

• 운영체제는 실행 중인 프로그램의 개념을 제공하는데, 이를 프로세스라 한다. 프로세스의 구성요소를 이해하기 위해 하드웨어 상태(machine state)를 이해해야 한다.
• 프로세스의 하드웨어 상태 중 가장 중요한 구성요소는 메모리다. 명령어는 메모리에 저장된다. 실행 프로그램이 읽고 쓰는 데이터 역시 메모리에 저장된다. 프로세스가 접근할 수 있는 메모리는 프로세스를 구성하는 요소이다.
• 레지스터도 프로세스의 하드웨어 상태를 구성하는 요소 중 하나이다. 많은 명령어들이 레지스터를 읽거나 갱신한다. 레지스터 중 특별한 레지스터들이 존재한다. 프로그램 카운터(PC : Program Counter)는 프로그램의 어느 명령어가 실행 중인지 알려준다. 프로그램 카운터는 명령어 포인터(IP : Instruction Pointer) 라고도 불린다. 스택 포인터(Stack Pointer)와 프레임 포인터(Frame Pointer)는 함수의 변수와 리턴 주소를 저장하는 스택을 관리할 때 사용하는 레지스터이다.

2.2 프로세스 API

• 생성(Create) : 운영체제는 새로운 프로세스를 생성할 수 있는 방법을 제공해야 한다.
• 제거(Destroy) : 운영체제는 프로세스를 가엦로 제거할 수 있는 인터페이스를 제공해야 한다.
• 대기(Wait) : 때론 어떤 프로세스의 실행 중지를 기다릴 필요가 있다.
• 각종 제어(Miscellaneous Control) : 여러가지 제어기능이 제공된다. 대부분의 운영체제는 프로세스를 일시정지하거나 재개하는 기능을 제공한다.
• 상태(Status) : 프로세스 상태정보를 얻어내는 인터페이스도 제공된다.

2.3 프로세스 생성 : 좀 더 자세하게

• 프로그램 실행을 위하여 운영체제가 하는 첫 번째 작업은 프로그램 코드와 정적 테이터(static data, 초기값을 가지는 변수)를 메모리, 프로세스의 주소공간에 탑재(Load)한다.
• 코드와 정적데이터가 메모리로 탑재된 후, 특정 크기의 메모리 공간이 프로그램에 스택 용도로 할당 되어야 한다. 운영체제는 스택을 주어진 인자로 초기화 한다. 특히 main() 함수의 인자인 argc와 argv 벡터를 사용하여 스택을 초기화 한다.
• 운영체제는 프로그램의 힙(heap)을 위한 메모리 영역을 할당한다. 힙은 동적으로 할당된 데이터를 저장하기 위해 사용된다.
• 운영체제는 또 입출력과 관계된 초기화 작업을 수행한다. 예를 들어, Unix 시스템에서 각 프로세스는 기본적으로 표준입력, 표준출력, 표준에러 장치에 해당하는 세 개의 파일 디스크립터를 갖는다.
• 이후 main() 루틴으로 분기함으로써, 운영체제는 CPU를 새로 생성된 프로세스에게 넘기게 되고 프로그램 실행이 시작된다.

2.4 프로세스 상태

• 실행(Running) : 프로세스는 프로세서에게 실행중이다. 즉 명령어를 실행하고 있다.
• 준비(Ready) : 프로세스는 실행할 준비가 되어있지만 운영체제가 다른 프로세스를 실행하고 있는 등의 이유로 대기중이다.
• 대기(Blocked) : 프로세스가 다른 사건을 기다리는 동안 프로세스의 수행을 중단시키는 연산이다.
• 프로세스는 운영체제의 스케줄링 정책에 따라 스케줄 되면 준비상태에서 실행상태로 전이한다. 실행상태에서 준비상태로의 전이는 프로세스가 나중에 다시 스케줄 될 수 있는 상태가 되었다는 것을 의미한다. 프로세스가 입출력 요청 등의 이유로 대기 상태가 되면 요청 완료등의 이벤트가 발생할 때까지 대기 상태로 유지된다. 이벤트가 발생하면 프로세스는 다시 준비 상태로 전이되고 운영체제의 결정에 따라 다시 실행될 수 도 있다.

2.5 자료구조

• 운영체제도 일종의 프로그램이다. 다른 프로그램들과 같이 다양한 정보를 유지하기 위한 자료구조를 가지고 있다. 프로세스 상태를 파악하기 위해 준비 상태의 프로세스들을 위한 프로세스 리스트와 같은 자료구조를 유지한다.
• 레지스터 문맥(register context) 자료구조는 프로세스가 중단 되었을 때 해당 프로세스의 레지스터 값들을 저장한다. 이 레지스터 값들을 복원하여 운영체제는 프로세스 실행을 재개한다.
• 이 상태 외에도 초기(initial) 상태를 가지는 시스템도 있다. 프로세스가 완전히 생성되기 전까지의 상태를 나타낸다. 프로세스는 종료됐지만 해당 프로세스가 사용하던 각종 자원들이 아직 완전히 반납되지 않은 상태인 최종(final) 상태도 있다(unix-기반 시스템에서 좀비라고 한다.) 이 상태는 하나의 프로세스가 (보통은 부모 프로세스) 다른 프로세스가 성공적으로 실행을 마쳤는지를 파악하는데 유용하게 사용된다. 이를 위해서 프로세스마다 정의된 최종상태를 활용한다.(unix - 기반 시스템에서는 프로세스가 성공적으로 종료되면 0을, 그렇지 않으면 0이 아닌 값을 반환한다. 부모 프로세스는 자식 프로세스의 종료를 대기하는 시스템콜을 호출(wait()) 한다. 이 호출은 종료된 프로세스와 관련된 자원을 정리할 수 있다고 운영체제에 알린다.

3. 프로세스 API

3.1 fork() 시스템콜

• 프로세스 생성에 fork() 시스템 콜이 사용된다.
• 자식 프로세스는 부모 프로세스와 완전히 동일하지는 않다. 자식 프로세스는 자신의 주소공간, 레지스터, PC값을 갖는다 매우 중요한 차이점이 있다. fork() t시스템콜의 반환값이 서로 다르다. fork()로 부터 부모 프로세스는 생성된 자식 프로세스의 PID를 반환 받고, 자식 프로세스는 0을 반환 받는다.
• CPU 스케줄러는 실행할 프로세스를 선택한다.

3.2 wait() 시스템콜

• wait() 시스템콜은 자식 프로세스 종료 시점까지 자신의 실행을 잠시 중지 시킨다.

3.3 exec() 시스템콜

• 자기 자신이 아닌 다른 프로그램을 실행해야 할 때 사용한다.
• 실행파일의 이름과 약간의 인자가 주어지면 해당 실행 파일의 코드와 정적데이터를 읽어들여 현재 실행중인 프로세스의 코드 세그멘트와 정적 데이터 부분을 덮어쓴다. 힙과 스택 및 프로그램이 다른 주소공간 새로운 프로그램의 실행을 위해 다시 초기화 된다. 그런 다음 운영체제는 프로세스의 argv와 같은 인자를 전달하여 프로그램을 실행시킨다.
• 자식 프로세스가 부모와의 연관성을 완전히 끊어서 새로운 프로그램을 실행할 수 있도록 한다.

3.4 프로세스 제어와 사용자

• kill() 시스템콜은 프로세스에게 멈추거나 끝내기와 같이 시그널을 보내는데 사용된다.
• 시그널이라는 운영체제의 메커니즘은 외부 사건을 프로세스에게 전달하는 토대이다. 개별적인 프로세스 단위 또는 프로세스 그룹 단위로 시그널을 받거나 처리할 수 있다.
• 일반적으로, 우리가 사용하는 시스템은 동시에 여러 사용자가 접속할 수 있다. 사용자는 자기 프로세스들에 한해서 제어권을 가지고 있다. 운영체제는 CPU, 메모리와 디스크 같은 자원을 각 사용자와 프로세스들에 할당하여 전체적인 시스템의 목적에 도달하도록 만드는 역할을 한다.

백준

1260 DFS와 BFS

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

vector<int> adj[10002];
vector<int> result_bfs;
vector<int> result_dfs;
bool visited[1002];

void dfs(int x)
{
	visited[x] = true;
	result_dfs.push_back(x);
	for (int i = 0; i < adj[x].size(); ++i)
	{
		if (!visited[adj[x][i]])
			dfs(adj[x][i]);
	}
}

void bfs(int x)
{
	queue<int> q;
	q.push(x);
	visited[x] = true;
	while (!q.empty())
	{
		int tmp = q.front();
		q.pop();
		result_bfs.push_back(tmp);
		for (int i = 0; i < adj[tmp].size(); ++i)
		{
			if (!visited[adj[tmp][i]])
			{
				q.push(adj[tmp][i]);
				visited[adj[tmp][i]] = true;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, start;
	cin >> node >> edge >> start;
	for (int i = 0; i < edge; ++i)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= node; ++i)
	{
		sort(adj[i].begin(), adj[i].end());
	}
	bfs(start);
	memset(visited, false, sizeof(visited));
	dfs(start);
	for (auto i : result_dfs)
		cout << i << " ";
	cout << "\\n";
	for (auto i : result_bfs)
		cout << i << " ";
	
	return 0;
}

• DFS , BFS를 구현하는 문제.
• 전에 파이썬으로 풀었음에도 시간이 지나서 많이 애먹었다.
• 코드를 외운다기 보다는 개념을 숙지하고 그 개념을 토대로 코드를 짠다면 조금 더 편하게 다가갈 수 있지 않을까 생각한다.