이누의 개발성장기

페이지 대치가 일어날 때는 앞으로 page fault가 최대한 일어나지 않도록 최선의 페이지를 대치시켜야한다. 그를 위한 다양한 알고리즘들이 존재한다. 최적알고리즘과 최악알고리즘 최적 대치 알고리즘 : 앞으로 오랫동안 사용되지 않을 페이지를 찾아서 교체하는 것이 최적일 것이다. 이러한 최적 대치 알고리즘은 벨러디알고리즘 또는 BO 알고리즘이라고 불린다. 하지만 해당 알고리즘은 오랫동안 사용되지 않을 페이지를 미리 아는 방법이 없기 때문에 사실상 실현이 어렵다. (cf. 이렇게 미래를 미리 예측하는 알고리즘은 lookahead 알고리즘이라고 불린다.) 실현은 어렵지만 해당 알고리즘이 가지는 의미는 크다. 해당 알고리즘이 있어 이에 근접한 알고리즘을 연구할 수 있고, 이를 능가하는 알고리즘은 존재할 수 없기..

한 프로그램이 수행되기 위해 정말 프로그램 '전체'가 메인메모리에 탑재되어야 할까? 프로그램 일부만 탑재되어도 수행 가능하도록 하는 방법이 있다. 이러한 생각을 바탕으로 구현된 메모리 경영기법이 가상메모리 기법이다. 가상 메모리 기법의 개요 분할방법과 페이징은 전체 프로그램을 적재해야 하지만, 가상 메모리 기법은 일부만 적재하고도 프로그램 수행이 가능하다. 사상 단위는 페이지테이블을 사용하는 페이징 기법과 똑같이 페이지이다. 프로그램의 일부만 적재되는 만큼 논리공간의 크기보다 실제 필요 물리공간의 크기가 작다. 프로그램은 적은 수의 프레임을 번갈아가면서 이용하기 때문에 '프로그램 오버레이'가 가능해지고, 메모리 활용도도 증대된다. 가상 메모리 기법의 개념 각 페이지가 메인메모리의 프레임 중 적절한 곳에 ..

세그먼테이션 페이징 기법의 핵심은 메모리 공간을 동일한 크기로 나누는 것이다. (논리공간은 페이지, 물리공간은 프레임) 하지만 실제로 사용자(개발자)는 자신의 프로그램을 동일한 크기의 페이지 모음으로 인식하기보단, 함수는 함수대로, 자료구조는 자료구조대로 각각 단위 별로 메모리 상에 존재하는 것으로 인식한다. 이러한 것을 '세그먼트'라고 부른다. 세그먼트를 그대로 물리 메모리 운영에 반영해주는 기법을 '세그멘테이션'이라고 한다. 이러한 세그멘테이션은 주소 결속 방식이 페이징과 유사하지만 다르다. 페이지 테이블 대신 세그먼트 테이블을 활용해 해당 테이블에 각 세그먼트의 시작주소와 크기정보를 수록한다. 크기정보는 세그먼트가 페이지처럼 고정적인 크기가 아니라서 추가된 정보이다. 세그먼트를 활용하면 세그먼트 간..

페이지 테이블의 구조 32비트 주소체계를 사용하는 경우 컴퓨터가 있다고 할 때, 주소 공간의 크기는 2의 32승이다. 페이지 하나의 크기가 4KB라면 이는 약 2^12이다. 페이지 테이블에 2^20개(2^32/2^12)의 정보가 저장되어야 하고, 항목 당 4바이트가 사용된다면 각 프로세스는 2의 22승, 즉 4MB의 페이지 테이블 공간을 물리메모리에 필요로 하게 된다. 애초에 페이징이라는 것이 연속된 메모리에 공간을 할당하는 것이 불합리해서 그 문제를 해결하기 위해 고안된 것인데, 페이지 테이블 때문에 4MB라는 공간을 연속해서 사용해야 한다는 모순이 발생한다. 따라서 페이지 테이블 구조를 개선해야 한다. 페이지 테이블 자체도 더 작은 단위로 쪼개서 메인메모리에 탑재한다. 이를 구현하기 위해 계층적 페이..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Skip List 링크드 리스트에서 중간으로 향하는 포인터를 두고 이를 활용해 이진탐색처럼 활용할 수 있도록 구성한 리스트 하지만 insert, delete 등의 기능을 사용하면서도 이러한 조건을 유지하기란 쉽지 않다. 데이터가 바뀌지 않을 때만 한정적으로 사용하기에도 적절치 않다. 배열이 더 효율적이다. 더 좋은 자료구조가 없을까? Binary Search Tree (BST) class Node { int k; // key값 Node *l, *r; // child 노드 정보 트리의 ..

페이징 단편화 문제를 압축방식으로 해결하려 했지만, 이 또한 비용이 발생한다. 좀 더 근본적인 해결책을 찾다가 발견한 것이 '페이징'이다. 단편화가 문제가 되는 이유는 프로그램을 연속된 메모리공간에 탑재해야만 하기 때문이다. 이러한 '연속적'이라는 조건을 없어지도록 하는 것이 페이징 기법이다. 즉, 페이징 기법은 연속된 물리공간을 필요로 하지 않으면서도, 실행시간 및 주소결속 등 프로그램 수행에는 문제가 없도록 하는 방식이다. 프레임, 페이지, 페이지테이블 3개로 이루어진다. 전체 물리적 공간을 같은 '프레임' 단위로 나누어놓고, 논리적 공간도 프레임과 같은 크기의 '페이지' 단위로 나눈다. 그리고 '페이지 테이블'을 통해 페이지를 프레임에 매핑시킨다. 즉 페이지 테이블은 일종의 주소 변환 테이블의 역할..

분할(Partition) 방법 여러 개의 프로그램을 적재하기 위해 메모리 공간을 여러개로 분할한다. 분할의 수가 다중 프로그래밍 가능의 정도가 된다. 이는 다시 고정분할 방법과 가변 분할 방법으로 나뉜다. 고정분할 방법 고정분할 방법은 분할의 단위가 되는 'Partition'의 크기가 고정된 것이다. 따라서 분할의 수도 고정된다. 이 경우 주소결속 방법이 간단하다.상한 레지스터와 하한 레지스터를 두고,상한 레지스터에는 영역의 크기가, 하한 레지스터에는 영역의 시작주소가 기록된다. CPU가 논리주소로 메모리를 접근하려 하면 먼저 그 논리주소값이 상한 레지스터에 기록된 영역의 크기값을 초과하는지 확인한다. 만약 초과한다면 이를 진행시킬 경우 다른 영역을 침범하게 될 것이므로 에러처리한다. 이러한 문제가 없다..

시분할 시스템에서는 여러 프로세스들이 동시에 수행된다. 즉, 여러 프로세스들이 메인메모리 상에 공존하고 있어야 한다. 제한된 용량의 메인메모리에서 이를 제대로 실현시켜 주어야 각 프로세스들의 성능도 저하되지 않고 CPU의 이용률도 올라가게 된다. 이런 맥락에서 이번 장부터는 메인메모리를 관리하는 다양한 기법들을 알아볼 것이다. 분할기법, 페이징기법, 세그먼테이션 기법 등이 그 예이다. 더 중요하다고 할 수 있는 가상 메모리 기법은 다음 파트에서 다룰 것이다. 다양한 기법들을 공부하기 전에 먼저 컴퓨터 시스템의 주소체계에 대한 이해가 필요하다. 따라서, 이와 관련된 개념들인 논리주소, 물리주소, 주소결속 등에 대하여 알아볼 것이다. 프로그램이 돌아가는 과정 int g_a; main() { … g_a++; ..

교착상태 처리 방법 교착상태가 발생하지 않도록 하는 방법과 교착상태를 방치하고 이를 탐지하여 복구하는 방법이 있다. 이에 따라 예방, 회피 / 탐지, 복구로 나뉘어 진다. 교착상태 예방 교착상태 발생의 4가지 필요충분조건 중 한가지만 일어나지 않아도 예방이 된다. "상호 배제" 조건 부정 : 상호배제 조건을 부정하는 것은 사실상 불가능하다. 자원자체가 상호배제를 요구하는 것을 전제로 했기 때문이다. "점유 대기" 조건 부정 : 모든 자원을 실행 전에 미리 확보하도록 한다. 이렇게 되면 대기 자체가 필요없어져 교착상태를 예방할 수 있다. 하지만 자원을 바로 사용하지 않고도 장시간 점유를 해야하기 때문에 다른 프로세스에 악영향을 줄 수 있다. 또한 하나의 프로세스가 자원들을 독점하여 자원의 활용도가 낮아진다..

교착상태 한 프로그램에 공유자원은 여러개이다. 이에 따라 임계구역도 여러곳에 존재한다. 이런 경우 자원의 소유와 대기에 있어 물고 물리는 관계가 되면서 프로그램의 수행이 정지할 수 있다. 이를 '데드락' 혹은 '교착상태'라고 한다. 교착상태는 즉, 서로에게 필요한 자원을 서로 요구하는 경우이다. 각 프로그램이 지켜야할 프로토콜을 설정하여 해결할 수 있다. 예를 들면 반대쪽의 프로그램이 실행중임을 확인하면 한쪽편의 프로그램은 대기하고 있는 것이다. 그러나 이 역시 반대쪽에서 계속해서 프로그램이 등장하면 한쪽편은 기아상태가 발생할 수 있다. (이는 에이징 등의 기법으로 해결한다.) 교착상태의 예 : 세마포어 // T0 P(A); P(B); V(A); // T1 P(B); P(A); V(B); 세마포어에서 각..