전체 글

OS가 관리하는 부분을 배운다 지금 필요하지 않는 페이지는 disk(swap area)에 저장 CPU가 요청한 페이지가 물리 메모리에 없다면 page fault -> 디스크에서 불러오는 I/O 작업 필요 현대 시스템은 page fault 비율이 0.1 이하 정도로 낮다 디스크에서 페이지를 불러올 때 물리 메모리에 자리가 없다면 page fault가 최대한 덜 나타나도록 자리를 만든다 reference string: 페이지에 번호를 매겨 참조된 순서대로 기록한 것 victim이 수정되었다면 반영하여 backing store에 저장, 아니라면 그냥 삭제 미래에 참조될 페이지를 안다고 가정하는 알고리즘 -> offline -> 비현실적인 최대 효율 알고리즘 LRU는 연결 리스트로 구현하여 맨 위 페이지 추출하..

힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..

트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트 이진 트리: 가장 널리 사용되는 트리 자료구조 m-ary 트리(..

일반적으로 segment 개수가 훨씬 적기 때문에 테이블이 차지하는 용량이 비교적 매우 적다 shared segment: code, private segment: data segment로 나눈후 각 segment를 다시 page로 나누는 기법 -> 물리 메모리에는 page 단위로 올라감(hole 없음) 공유와 보안은 segment 차원에서 처리하여 두 방법의 장점을 모두 가지고 있다 지금까지 배운 주소변환 과정에서 운영체제의 역할은 없었다 (모두 하드웨어의 도움) CPU가 주소변환을 통해 메모리에 접근할 때마다 OS에 넘어갔다가 다시 사용자 프로세스에 넘어오지 않는다 I/O 접근을 할 때 역할이 있다 출처: https://core.ewha.ac.kr/publicview/C010102014050914293..

다단계 페이지 테이블을 사용해도 TLB 사용 비율이 높다면 오버헤드가 그렇게 크지 않다 page table은 주소 공간의 전체 용량만큼의 엔트리가 생성되므로, 페이지 개수가 부족한 프로세스도 있다 각 페이지가 code, data, stack 중 일부를 가지고 있는데, 어떤 연산 권한을 가지고 있는지 알려준다 예: code부분은 바뀌면 안되기 때문에 read-only, data/stack은 읽고 쓰기 다 가능 해당 프로세스의 논리 주소가 page table의 몇번째 엔트리에 있는지 확인 후 물리 메모리에도 같은 인덱스로 접근 공간 효율을 높이기 위한 방법이지만 시간 오버헤드가 매우 크다 associative register: 순차적인 탐색이 아닌 동시에 모든 엔트리 탐색 예: 동일한 워드 프로그램 3개 실..

프로세스마다 page table을 가지고 있다 인덱스로 접근하면 물리 주소를 바로 알 수 있다 (table = array) 32 bit로 2^32 byte의 주소 공간을 처리할 수 있고, 이는 4kb 크기의 page를 1M개 담고 있다 메모리는 byte 단위로 주소가 매겨진다 4kb의 page들은 각각 4byte의 엔트리를 1k개 보유하고 있다 사용되지 않는 주소 공간이 많아 만들어지지 않는 inner page table이 많으므로 공간을 더 효율적으로 사용 1계층 테이블은 모든 페이지에 대한 정보가 모두 들어가고 물리 메모리에 저장되므로 비효율적 d: 4kb = 2^12byte = 12bit p2: 1kb = 2^10byte = 10bit p1: 32bit - (12bit + 10bit) = 10bit..

프로세스 최초 실행 시 논리 주소 생성되고 필요한 부분만 실제 물리 주소에 올라가서 실행된다 물리 메모리의 어떤 주소에 올라갈지 결정하는 주소 바인딩 과정이 필요하다 프로그래머 입장에서는 심볼로 된 주소를 사용하고 컴파일되면 숫자 주소로 바뀐다 실행파일의 인스트럭션이 가리키는 주소는 논리 주소이기 때문에 CPU도 논리 주소를 참조한다 따라서 CPU가 요청하는 논리 주소에 대응되는 물리 메모리의 주소를 매번 제공받아야 한다(주소 변환) relocation register(base register): 물리 메모리 주소의 시작지점 저장 -> 요청받은 논리 주소에 이 값을 더해 변환 limit register: 해당 프로세스의 최대 주소 번지 저장 -> 악성 프로세스 필터링(다른 프로그램 침범 방지) 현대의 메..

P0가 A를 하나만 요청해도(어떤 요청을 해도) 받아들이지 않고, P1이 필요자원 내에 어떤 요청을 해도 받아들임 즉, 항상 safe 상태를 지향하는 매우 보수적인 알고리즘이다 deadlock은 매우 드문 현상이므로 위 알고리즘은 매우 비효율적(할당되지 않는 자원이 많다) deadlock을 일단 허용하기 때문에 최대 필요 자원을 조사하지 않음 그래프에서는 사이클이 있는지 확인 테이블에서는 낙관적으로 요청 자원이 없는 프로세스는 사용중인 자원을 반납할 것이라는 예상을 기반으로 한다 만약 P2가 자원 C를 하나 요청한 상황이라면 deadlock 상태 출처: https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f

request edge: 해당 프로세서가 가리킨 자원을 요청한다는 의미 (할당 전) assignment edge: 해당 자원이 가리킨 프로세서에 할당되어 있다는 의미 왼쪽 예제부터 deadlock (X), deadlock (O), deadlock (X) 현대에는 대부분 OS가 deadlock을 책임지지 않고 사용자에게 맡긴다 deadlock이 그렇게 자주 발생하지 않기 때문에 이를 미연에 방지하기 위해 하는 작업의 오버헤드 때문 두번째 그래프에서 자원2를 프로세스2에 할당하면 생길 위험한 상황을 미리 방지하고자 프로세스2에 할당 X 현재 available 자원으로 need 자원이 충족되는 프로세스를 우선으로 할당해준다 이후 자원을 다 활용하고 반납하여 available 자원이 늘어나면 또 그에 맞는 프로..

= concurrency control 모니터는 공유 데이터와 그 데이터에 접근할 수 있게 하는 코드를 한 곳에 넣고 한번에 한 프로세스만 코드 수행하도록 하여 프로그래머의 부담을 덜어준다 active한 프로세스가 코드 수행을 마치거나, 특정 조건을 불만족하여 잠들게 되어야 다른 프로세스가 모니터로 들어와 active해질 수 있다 empty: 빈 버퍼를 기다리는 프로세서 줄 full: 자원을 기다리는 프로세서 줄 lock 관련 변수가 불필요함 semaphore 변수는 값을 가지고 프로세서가 코드를 수행하면서 그 값이 바뀐다 출처: https://core.ewha.ac.kr/publicview/C0101020140411143154161543?vmode=f