오래 못 할 짓 하지 않기

https://min-h-study-review.tistory.com/259Background Physical memory보다 큰 프로그램을 실행시켜야 한다면프로그램 전체를 가져올 필요가 없다. 실행할 때 당장 필요한 것들만 가져오면 되고,그렇지 않은 것들은 가상의 메모리에 저장해두면 된다.● Virtual MemoryLogical mem을 Physical mem으로부터 분리시킨 공간.= Logical address space는 physical address space보다 훨씬 크다. 여러 Process간에 address space도 공유할 수 있게 한다. 요약하면 물리 메모리보다 더 많은 것을 저장할 수 있게 해주는 메모리라고 생각하면 된다.    Demand Paging: 요구되는 page만  loa..

: Sort에서 Divide and Conquer 를 사용하는 알고리즘  구간을 정하고 그 안에서 sort한다. sort의 기준은 Pivot임. 이번에는 Pivot을 배열의 가장 마지막 원소로 지정한다.  x 가 pivot이라고 했을 때,왼쪽은 x이하    오른쪽은 x이상 으로 분류한다.  옛날에 배웠던 건 Pivot element가 pivot이거나 , 처음 중간 끝 값 중에 가운데를 pivot으로 했다. A = arrayp = 첫번째 인덱스r = 마지막 인덱스 이번에는 가장 오른쪽에 있는 element를 pivot으로 정한다.검사는 → 이렇게 한 방향으로만 한다. 3번째 줄 : 그럼 처음부터 r-1까지만 검사하면 된다.  4,5,6번째 줄 : 만약 현재 Index의 값이 Pivot보다 작으면,     ..

만약 Paging 해야하는 게 엄청 많아지면 어떻게 처리해야 할까? Memory가 엄청 크고 우리가 고려해야하는 프로세스들이 많아지면page table이 엄청 커지지 않을까? 이를 처리하는 방법에는 3가지가 있다. ● Hierarchical Paging● Hashed Page Tables● Inverted Page Tables   ● Hierarchical Paging: Logical address space 를 여러 Table로 나눈다.즉 Page를 위한 Page라고 생각하면 됨.ex) 윙의 윙  그림을 보면 Outer page table이 있다. Page table들을 모아두는 page table들이 있는 것이다. 이런 구조라고 생각하면 된다. 만약에 더 큰 Logical address space가 ..

외부 단편화의 이유: 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되어서   ▶ 모든 크기가 같았으면 발생하지 않음       = 그럼 같게 해주자 ● 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고                                     [ 프로세스 공간 → 페이지 ] ● 메모리의 물리 주소 공간을 프레임이(frame)라는 페이지와 동일,일정한 단위로 자른 뒤       [  메모리의 공간 → 프레임 ]페이지와 프레임 사이에서 매핑하는 걸 도와주는 Page Table이 있다.  : Physical address의 공간이 연속적이지 않아도 되고, frame은 모두 같은 크기이므로● 효과 : 외부 단편화 문제를 해결한다!   page = logical ..

Floyd Algorithm: All Pairs Shortest Path 를 구하기 위한 알고리즘이다. From all to all   Dense graph는, Edge의 개수 = O(V^2)인 경우의 graph이다.E에 V^2를 대입하면 과 같다  ● Floyd Algorithm 사용 조건 - Negative Edge 는 가능 - 하지만 Negative Weight cycle은 안 된다. - DP로 구현한다. = Optimal Substructure 적용 가능   알아야 하는 개념- Intermediate Vertex  : i에서 k까지 가는 path에 포함되는 Vertex    단, 한 번만 나올 수 있다. DP로 생각해보면 1 ~ ... k-1까지 가는 최단 경로를 찾았다면 k까지 갈 땐 k-1까지..

이제는 CPU가 하는 일보다는, 메모리에 관련된 작업은 어떻게 이루어지는지 알아보자. ● 배경 지식 Process = 실행되고 있는 Program = 이 Program은 Instruction의 집합체 이고,    이들은 Main memory 안에 있다.  - Memory는▶ 많은 양의 Byte로 된 Array로 이루어져 있고,    이는 각각의 address가 있다. ▶ 따라서 CPU는 Memory에서 PC에 따라 이 Instruction들을 Fetch하여 사용한다.   메모리 보호  : Process가 들어갈 수 있는 크기가 있다.      그걸 정해주는 Register 한 쌍 : Base register / Limit register       Process 하나가 메모리에 들어가는 크기 = Limi..

Dijkstra Algorithm ( From all to all )● 조건:  Negative weight인 edge가 없다면,   Bellman-Ford보다 성능이 좋다.  ● 구현법- Queue에 담긴 Vertex 를 하나씩 꺼내면서 Tree를 키운다.- Queue는 , d[v] 가 낮은 순서대로 Prioirity queue를 만든다. Minimum shortest path인 것을 select한다.u라는 vertex를 S에 넣은 뒤 , u와 인접한 모든 node를 Relaxation 시킨다. 1 : 초기화2,3 : set을 비우고, Q에 vertex들을 넣는다. 4 ~ 8:  Q에 vertex가 비어있지 않았다면,             vertex하나를 꺼내고, 그걸 S에 넣는다.    7~8 : ..

Deadlock Preventionhttps://min-h-study-review.tistory.com/252 저번 강의에서 배웠던 Deadlock 이 발생하는 조건 중에하나만이라도 충족시키지 못하게 만들면 Deadlock을 예방할 수 있지 않은가 하는 아이디어 = 교착상태 발생 조건 중 하나를 제거하기  ● Mutual exclusion: 상호 배제를 없앴다면, 모든 자원을 공유하게 한다.  하지만, 현실적으로 모든 자원을 공유하는 건 불가능하다. ● Hold and wait: 점유와 대기를 없앤다.자원을 점유한 상태에서 다른 자원을 기다리는 것을 못하게 한다. = 특정 프로세스에게 자원을 모두 할당 or 아예 할당 X 배고픈 철학자 문제에 적용해보면, 포크 기다릴 거면 왼쪽 포크는 내려놓고 기다려라 ..

u에서 v까지 가는 Shortest path의 Weight은 [ Path가 존재한다면 ]u → v까지의 path의 weight의 최솟값을 구한다. [ Path가 존재하지 않는다면 ]무한대  길 찾기의 유형 1. Single source shortest path   : 하나의 Vertex에서 다른 모든 Vertex로 가는데 가능한 최단 경로 (이거 먼저 배울거임)  ● 알고리즘 Bellman-Ford AlgorithmIn DAGDijkstra's Algorithm 2. All- Pair shortest path   : 모든 Vertex에서 모든 vertex까지 가는데 가능한 최단 경로 ● 알고리즘 Floyd - Warshall Algorithm (다음 장에서 배움)    Shortest path  ● 특징..

참고https://min-h-study-review.tistory.com/54Minimum Spanning Tree 조건: Connected + Undirected + Non-Cycled + Weighted graph  이 중에서도 우리는 모든 Vertex를 지나고 , Total Weight가 최소인 Tree를 구할 것이다.   ● 특징 )1. n개의 vertex / n-1개의 Edge2. MST 가 Unique하지 않을 수도 있음.(a)에 대한 MST는 b,c 두 개가 있다.  ● MST를 찾는 알고리즘 :1. Kruskal Algorithm ( 가장 Weight이 낮은 Edge부터 하나하나 가져옴 )  2. Prim Algorithm ( root Vertex 에서부터 인접한 Edge중에서 Weight..