이누의 개발성장기

디스크의 구성 중심에는 스핀들(spindle)이 있어 시계방향으로 돌아간다. 용량이 큰 서버용 디스크는 면이 여러개이다. 여기서 면은 플래터(platter)라고 부른다. 이러한 플래터 상에는 섹터(sector)들이 모여 하나의 원을 형성하고, 이 원을 트랙(track)이라고 한다. 트랙이 안 쪽에 있든 바깥쪽에 있든 한 트랙의 섹터 수는 동일하다. 각 플래터 상의 동일한 트랙들을 통합해 실린더(cylinder)라고 부른다. 디스크가 입출력을 하는 단위는 섹터이다. 디스크에 읽기와 쓰기를 실행하는 헤드가 목표하는 섹터를 찾아가기 위해 디스크 암은 해당 트랙을 찾아가주고, 스핀들은 디스크를 회전시킨다. 일반적으로 하드디스크의 한 섹터 크기는 512바이트이다. 헤드를 움직여 특정 트랙의 특정 섹터를 찾아가 읽..

디스크 공간할당 프로그램 파일, 데이터 파일, 디렉토리 파일 모두 파일이며, 파일은 저장장치에 블록 단위로 산재되어 저장된다. 이를 최대한 효율적으로 저장해야 파일 입출력의 속도를 높일 수 있다. 이처럼 디스크에 파일을 저장할 때 파일의 블록들의 배치를 결정하는 것이 디스크 공간할당이다. 디스크 공간할당은 연속 할당과 불연속 할당으로 나누어진다. 연속 할당 : 임의의 한 파일을 위해 디스크 내에 선형적으로 연속된 블록을 할당. 불연속 할당 : 임의의 한 파일을 위해 디스크 내에 산재된 블록을 연결해 할당, 블록이 디스크 내 어디에 있어도 액세스 가능. 불연속 할당을 구현하는 방법으로는 연결 할당, 색인 할당, 간접 색인이 있다. 간접 색인도 멀티레벨 색인과 혹합 색인으로 나누어진다. 연속 할당 연속할당 ..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Minimum Sparsing Tree 주어진 그래프에서 엣지들의 subset을 찾고 그 결과로 엣지 cost의 합이 최소인 '연결된' 그래프를 찾아라. 해당 그래프는 자연스럽게 트리가 된다. 이는 사이클이 없다. 싸이클이 있다고 가정하면 '엣지 cost 합 최소' 조건이 성립이 안되기 대문이다. 엣지는 '노드개수 - 1'일 것이다. 해당 질문에 대한 답은 그래프 형태에 따라 여러개일 수 있다. (유일하다는 것을 증명하기 위해서는 edge w..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Traversal Traversal : 모든 노드를 특정 순서로 방문하는 것 여기서 '방문'이란 단순히 거치는 것을 넘어서 해당 노드에서 특정한 작업을 수행하는 것이다. Traverse (Node *D) { if (D==Null) return; // Visit(D); => Preorder traversal Traverse(D->Left); // Visit(D); => Inorder traversal Traverse(D->Right); // Visit(D); => Post..

파일의 개념 파일 : 정보의 집합체. 정보란 비트, 바이트, 행, 레코드 등을 모두 포함한다. 파일 작성자나 사용자가 해당 정보를 정의한다. 파일은 보조기억장치에 저장되어 있고, 주로 프로그램파일 혹은 데이터 파일이다. 프로그램 파일 : 원시 프로그램(C,C++), 오브젝트(바이너리) 프로그램 데이터 파일 : 수를 포함해 문자 또는 ASCII 코드로 된 문자 혹은 숫자로 구성되어 있다. 내용 면에서는 텍스트 파일처럼 비정형화된 자유형식일 수도 있고, 데이터베이스처럼 엄격히 정형화된 형태일 수도 있다. 또한 동영상, 이미지, 소리 등 정해진 포멧을 따르고 있을 수도 있다. 어떤 파일이든 하드디스크와 같은 저장장치에 저장될 때 섹터 단위로 저장된다. 즉, 하나의 파일이 디스크 내 여러개의 섹터로 구성되는 것..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Priority Queue 내부 item들이 우선순위를 가진다. 보통 우선순위는 여러 기준이 있지만 최대한 Simple하게 설정해놓는 것이 학습에 용이하다. Queue에서 가장 우선순위가 높은 것이 나온다. (우선순위 변동은 없다.) 우선순위에 의해 정렬되어 있으면 : Del는 빠르지만, Insert는 느리다. 우선순위에 의해 정렬되어 있지 않으면 : Del은 느리지만, Insert는 빠르다. 어떤 자료구조를 활용해 구현할까 기본 BST를 제외한 AVL, 2-3, 2-3-4, Red-..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. 2-3-4 Tree 2-3 트리의 확장판이다. Node key 값의 공간이 커진다. 모든 leaf가 같은 거리에 있다. 2-3-4 트리에 N개의 key가 있을 때 Height는 O(logN)이다. 해당 트리는 2-3 트리와 달리 새로운 key값이 들어오지 않아도 key 값이 3개인 상태에서 split이 가능하다. 트리에서는 새로운 키 값이 추가될 때 [노드내부 작업 - 링크 따라가기 - 새로운 노드 및 링크 생성]의 과정이 필요했다. 이 때 각 작업의 비용은 현재 작업이 어디에서 진행..

쓰레싱(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개의 페이지가 담길 프레임이 필요..