페이지교체와 프레임할당 물리 메모리보다 더 큰 프로세스를 실행할 수 있지만, 그럼에도 물리 메모리의 크기는 한정되어있다. 그렇기 때문에 운영체제는, 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고(=페이지 교체알고리즘), 프로세스들에게 적절한 수의 프레임을 할당(=프레임할당)해야한다. 요구페이징 요구되는 페이지만 적재하는 기법으로, 아래 순서대로 실행된다. cpu가 특정 페이지에 접근하는 명령어를 실행한다. 해당 페이지가 현재 메모리에 있을경우(=유효비트가 1일경우), cpu는 페이지가 적재된 프레임에 접근한다. 해당 페이지가 현재 메모리에 없을경우(=유효비트가 0일경우), page fault 인터럽트가 발생한다. page fault처리루틴은 해당 페이지를 메모리로 적재하고 유효비트를 1로..

페이징을 통한 가상 메모리 관리 연속 메모리 할당의 두가지 문제점 외부 단편화의 문제 (=프로세스를 할당하기 어려운 만큼 작은 빈 공간들로 인해 메모리가 낭비되는 현상) 물리 메모리보다 더 큰 프로세스 실행이 불가능하다. 가상메모리 관리 실행하고자 하는 프로세스를 일부만 메모리에 적재하여, 실제 물리메모리보다 더 큰 프로세스를 실행시키는 기술을 의미한다. 가상메모리관리를 해결하기 위한 기술로 페이징, 세그멘테이션 등이 있다. 페이징 외부 단편화가 발생했던 근본적인 문제는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문 페이징은 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당한다. 즉, 페이징은 프로세스의 논리 주소공간(=cpu가 바라보는 주소공간)을 페이지라는 일정단위로 ..

연속메모리 할당의 개념과 방식 이에 따른 문제점 연속 메모리 할당 : 프로세스에 연속적으로 메모리공간을 할당하는 것을 의미 swapping (swap out, swap in, cf: 중기스케줄러) swapping 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 쫓아낸 빈 공간에 새 프로세스를 적재하는 것을 의미한다. 장점 여러 프로세스들이 요구하는 메모리 공간의 크기가 실제 RAM메모리의 크키보다 큰 경우에도, 동시에 실행 가능하다. swap영역의 크기는 free, top명령어로 확인가능하다. 연속 메모리 할당 3가지 방식 (cf: first-fit, best-fit, worst-fit) first-fit (=최초적합) 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가, 적재할..

인덱스로 BTree계열이 자주 사용되는 이유 BTree, AVL Tree, Red-Black-Tree 시간복잡도 BTree Binary Search Tree(BST)를 일반화한 트리 Self-Balancing BST BST중에서 한쪽으로 치우치는 것이 있는데, 이를 보완하기 위해 스스로 규형을 잡는 트리인 AVL트리, RedBlackTree가 있다. 세개 모두 시간복잡도가 O(logN)인데 왜 굳이 BTree를 DB INDEX로 자주 쓰일까? 위를 이해하기 앞서, computer system을 이해할 필요가 있다. computer system computer system에는 총 3가지로 나눠서 설명할 수 있다. cpu 프로그램 코드가 실제로 실행되는 곳 main memory(RAM) 실행 중인 프로그램의..

monitor 실행 순서를 위한 동기화 및 상호 배제를 위한 동기화에 대해 모두 제공한다. mutual exclusion을 보장한다. 조건에 따라 스레드가 대기(waiting)상태로 전환 가능하다. monitor에는 두개의 큐가 존재한다. entry queue : critical section에서 진입을 기다리는 큐로서, mutex에 의해 관리된다. waiting queue : 조건이 충족되길 기다리는 큐로서, condition variable에 의해 관리된다. 프로그래밍 언어 레벨에서 지원하는 것임! 구성요소 mutex critical section에서 mutual exclusion을 보장하는 장치로 critical section에 진입하려면 mutex lock을 취득해야한다. mutex lock을 취..

Deadlock 위 오른쪽 그림이 deadlock임을 말할 수 있다. 숫자 1, 2, 3, 4가 리소스이고, 자동차가 프로세스라고 생각해보자. 각 차들은 직진하기 위해 2개의 리소스를 점유해야한다. 각 차들이 마음이 급해 자원을 하나 점유는 하였으나, 그 외에 리소스들은 각 다른 차량들이 점유하고 있어 교착상태에 빠지게 되어 계속 하염없이 기다리게 되었다. (=deadlock) 즉, 두 개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태를 의미한다. Deadlock이 발생하기 위한 4가지 조건, 4가지 조건이 모두 만족해야 deadlock이 발생한다. Mutual Exclusion 리소스를 공유해서 사용할 수 없다. Hold and Wait 프로세스가 이미 하나 이상의 리소스를 취득(h..