jjj

컴퓨터는 바이트 단위로 메모리 주소를 부여한다. 32비트 주소체계를 사용하면 2^32 바이트만큼의 메모리 공간에 서로 다른 주소를 할당할 수 있다. 일반적인 주소도 행정 구역을 나누어 게층적으로 관리하듯이 컴퓨터 상의 주소도 32비트를 그대로 사용하지 않고 효율적인 운영을 위해 연속된 일련의 영역을 행정 구역처럼 묶어서 사용한다. 보통 4KB 단위로 묶어서 페이지라는 하나의 행정 구역을 만들게 된다. 따라서 32비트의 주소 중 하위 12비트는 페이지 내에서의 주소를 나타내는 것이다. 주소 바인딩가상 주소 ( 논리적 주소)프로그램이 실행을 위해 메모리에 적재되면 그 프로세스를 위한 독자적인 주소 공간이 생성된다. 이 것이 가상 주소이다. 0 번지 부터 시작된다.물리적 주소물리적 메모리에 실제 올라가는 위치..

CPU는 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치이다.프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. 그러면 CPU는 프로그램 카운터가 기리키는 주소의 기계어 명령을 하나씩 수행하게 된다.I/O 버스트I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업CPU 버스트I/O를 한번 수행한후 다음 I/O를 수행하기까지 적접 CPU를 가지고 명령을 수행하는 일련의 작업시스템 내에서 수행되는 프로세스들의 CPU버스트를 분석해보면 대부분 짧은 CPU버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 가진다.주로 대화형 작업이 CPU 버스트가 짧다. 이러한 작업은 빠른 ..

프로세스의 개념프로세스란 실행 중인 프로그램이다.문맥 (Context)프로세스가 현재 어떤 상태에서 수행되고 있는지를 정확히 규명하기 위해 필요한 정보프로세스의 주소 공간 ( 코드, 데이터, 스택)을 비롯한 레지스터에 어떤 값을 가지고 있었는지와 시스템 콜 등을 통해 커널에서 수행한 일의 상태, PCB 등을 포함한다.프로세스 제어 블록 (PCB)운영체제가 시스템내의 프로세스들을 관리하기 위해 프로세스당 유지하는 정보들을 담는 커널 내의 자료구조구성요소프로세스의 상태 (Process State)CPU를 할당해도 되는지 여부를 결정하기 위해 필요프로그램 카운터값 (Program Counter)다음에 수행할 명령의 위치CPU 레지스터 (CPU Register)CPU 연산을 위해 현 시점에 레지스터가 어떤 값을..

프로그램 구조와 인터럽트컴퓨터 프로그램은 그 내부적인 구조는 함수들로 구성된다. 프로그램이 CPU에게 명령을 수행하려면 수행하려는 주소 영역이 메모리에 올라가 있어야 한다. 이 때 프로그램의 주소 영역은 크게 코드, 데이터, 스택 영역으로 구분된다.코드우리가 작성한 프로그램 함수들의 코드가 기계어 명령으로 변환되어 저장되는 부분데이터전역 변수들 프로그램이 사용하는 데이터를 저장하는 부분스택함수가 호출될 때 호출된 함수의 수행을 마치고 복귀할 주소 및 데이터를 임시로 저장하는데 사용되는 공간이다.예를들어 X라는 함수가 수행중에 Y라는 함수를 호출한 경우 X함수에서 Y함수를 호출한 지점을 스택에 저장해 놓았다가 Y함수가 수행된 후 스택에서 저장된 주소위치로 돌아와 코드를 계속 수행한다.인터럽트의 동작 원리도..

이분 매칭 두 그룹 A와 B는 서로 연결될 수 있는 두 그래프이다. 이러한 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게 이분 매칭이라고 한다. // A 와 B의 정점의 개수 int n, m; bool adj[MAX_N][MAX_M]; vector aMatch, bMatch; vector visited; int dfs(int a) { if (visited[a]) return false; visited[a] = true; for (int b = 0; b < m; b++) { if (adj[a][b]) { // 만약 b가 매칭되지 않았을때 // or 매칭이 되었을 경우 b와 매칭된 A그룹의 정점이 // 다른 B 그룹의 정점과 연결이 가능한지 파악 // 가능하다면 그 점과 연결한 후 a 와 b 매칭 if ..

포드 풀커슨 알고리즘은 네트워크 유량을 구하기 위한 문제이다. 특정 시작점에서 특정 끝점까지 한번에 보낼 수 최대 유량값을 찾는 문제이다. 구현 방법 bfs를 이용하여 시작점에서 끝점까지 탐색 ( 그 과정에서 자신으로 들어오는 부모 정점 저장 ) 끝점부터 시작하여 해당 경로를 통해 옮길 수 있는 유량을 확인 ( 경로 중 가장 작은 값) 찾은 유량 값을 갱신 ( 반대 방향은 음수로 갱신) 이 것을 끝점에 닿는 증가경로가 없을 때까지 반복 const int INF = 99999999; int V; // capacity[u][v] : u에서 v로 보낼 수 있는 용량 // flow[u][v] : u에서 v로 보낸 유량 ( 반대 방향일 경우 음수 ) int capacity[MAX_V][MAX_V]; int flo..

크루스칼 알고리즘은 프림 알고리즘과 함께 최소 스패닝 트리를 찾는 알고리즘이다. 스패닝 트리는 모든 정점에 대해 사이클이 없는 그래프이다. 즉 트리 형태이지만 부모- 자식의 형태로 이어질 필요는 없다. 크루스칼 알고리즘은 간선을 정렬한 후 사이클이 존재하지 않게 순서대로 간선을 붙이는 방식으로 구현된다. 사이클이 존재하지 않기 위해서는 두 정점이 같은 컴포넌트로 속해져 있지 않으면 되고, 같은 컴포넌트에 에 속하지 않는 것을 확인하기 위해 상호배타적 조합 ( 유니온 파인드라고 많이 부른다)을 사용한다. #include #include using namespace std; struct DisjointSet { vector parent, rank; DisjointSet(int n) { parent = vec..

플로이드 워셜은 모든 점에서 다른 모든 점까지의 최소 거리를 구하는 알고리즘이다. k라는 정점을 정해놓고 모든 점이 그 점을 경유했을 때 다른 모든 점까지의 최소값을 갱신하면서 모든 점 사이의 최소값을 구하는 방법이다. k를 모든 정점에 대해서 수행한다. 만약 i 정점에서 k까지 이어져 있지 않다면 j for문을 뛰어넘어도 상관이 없을 것이다. const int MAX_V = 1000; // 정점의 개수 int V; // 간선이 없으면 아주 큰 값을 넣는다. int adj[MAX_V][MAX_V]; void floyd() { for (int i = 0; i < V; i++) { adj[i][i] = 0; } for (int k = 0; k < V; k++) { for (int i = 0; i < V; i..