이누의 개발성장기

머신러닝 개요 인간이 직접 데이터를 분석해 규칙을 유도, 모델을 구축하는 '기호주의 방식' 머신러닝은 데이터를 이해하는 알고리즘의 과학이자 하나의 어플리케이션이다. 머신러닝은 데이터를 지식으로 바꿀 수 있다. 머신러닝을 활용해 더 효율적으로 지식을 추출할 수 있다. 머신러닝 분류 : 지도학습 지도학습 : 레이블 된 훈련 데이터를 활용해 모델을 학습시켜, 본 적 없는 가까운 미래 데이터에 대한 예측값을 출력하는 것. 분류 : 지도학습의 하위 카테고리. 과거의 관측을 기반으로 새로운 샘플의 범주형 클래스 레이블 예측이 목적. 클래스 레이블은 이 때 클래스를 구분하는 규칙을 점선으로 표현하기도 하는데, 이는 '결정경계'라고 불리기도 한다. (클래스 레이블, 불연속적인 일종의 데이터가 속한 그룹) 대표적인 예로..

쓰레싱(Thrashing) 프레임이 충분히 할당되지 않은 프로세스는 page fault가 발생할 가능성이 높다. page fault가 발생할 때마다 페이지 교체가 필요하게 되지만, 나머지 프레임들도 이미 활발하게 사용중이므로 어떤 페이지가 교체되든 바로 다시 필요해질 것이다. 결과적으로 계속 반복하여 page fault가 발생하게 되는 악순환이 생긴다. 이렇게 과도한 페이징 작업을 쓰레싱이라고 부른다. 즉, 어떤 프로세스가 실제 실행보다 페이징에 더 많은 시간을 사용할 경우 쓰레싱이 발생했다고 한다. 이러한 쓰레싱 현상은 CPU 스케줄러에 의해 야기되기도 한다. 운영체제는 CPU의 이용률을 감시하면서 이용률이 떨어지는 것을 확인하면 이용률을 높이기 위해 새로운 프로세스를 추가해 다중 프로그래밍의 정도를 ..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. tree에 대한 Lemma 한 서브트리의 모든 값들은 전체를 sorting 해놓은 리스트에서 연속적이다. 수학적 귀납법으로 증명 가능 Base : 루트에서는 무조건 성립한다. Step : 특정 노드 X에서 성립한다고 가정하면, 해당 서브트리인 L과 R은 각각 왼쪽과 오른쪽으로 갈린다. 따라서 무조건 성립하게 된다. AVL Tree 균형잡힌 Tree라고 할 수 있다. 전체를 lotation 처리한 결과이다. 각 노드의 Lable에 L/R을 추가한다. L : Height of Left s..

페이지 부재율은 일반적으로 프로세스에 할당된 프레임의 개수와 역비례 관계이다. 즉, 할당된 프레임이 많을 수록 page fault rate가 줄어든다. 물론 페이지 대치 알고리즘에 따라서 일시적으로 이 역비례관계가 깨지는 '벨러디 변이'가 일어날 수는 있다. 이런 성질에 따라 각 프로세스에 적절한 프레임 개수를 할당해주어야만 할 것이다. 프레임 할당 모든 프로세스가 할당 받을 최소의 프레임 개수는 CPU 명령어의 구조에 의해 결정된다. 하나의 명령어가 참조하는 모든 페이지가 동시에 메모리에 올라와야 명령어 수행 완료가 가능하기 때문이다. 예를 들어 어떤 명령어가 간접주소를 사용한다고 하면 '명령어 페이지', '오퍼랜드 주소 페이지', '주소 내용이 가리키는 페이지' 총 3개의 페이지가 담길 프레임이 필요..

페이지 대치가 일어날 때는 앞으로 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개로 이루어진다. 전체 물리적 공간을 같은 '프레임' 단위로 나누어놓고, 논리적 공간도 프레임과 같은 크기의 '페이지' 단위로 나눈다. 그리고 '페이지 테이블'을 통해 페이지를 프레임에 매핑시킨다. 즉 페이지 테이블은 일종의 주소 변환 테이블의 역할..