기술 블로그

Physical memory는 자원에 limit이 있기 때문에 한계가 있습니다. 실행하고자 하는 프로세스, 페이지가 적재가 되는데 프로그램이 하드디스크에 있는 실행이 되면 SWAP 영역에 페이지 단위로 쪼개져서 실행이 되면 CPU가 보는 메모리는 프로세스가 0번지부터 High 까지 높은 번째로 존재하는 것이 페이지 단위로 쪼개져서 존재합니다. 페이지가 Physical memory에 적재가 됩니다. 하드디스크의 프로그램이 실행이 되면 페이지 단위로 쪼개집니다. 페이지 단위로 쪼개져서 CPU 단위로 봤을 때 메모리에 적재가 되어 있는데 CPU가 보는 프로세스는 연속적으로 접해있다라고 보고 Logical Memory를 통해서 접근을 합니다. 실제로는 SWAP 영역에 있는 페이지가 Physical memo..

global - datalocal - stack SWAP 연산의 IO 연산은 하드디스크의 IO 연산보다 조금 빠릅니다. 그래서 하드디스크에 있는 프로그램에 있는 컴파일 바이너리 이미지가 이것을 더블클릭을 통해서 실행하면 전체가 스왑영역에 갑니다. CPU가 Address를 메인메모리에 요청하면 CPU에 보는 나의 메모리는 무한대입니다. Address를 요청하면 OS가 보고서 무슨 값을 요청하는구나 봅니다. 해당 프로세스의 페이지를 프레임에 적재를 하고 적재를 하고 있는 주소 Physical memory에서 읽어다가 CPU에 전달해주는 것입니다. 어쨋든 Logical Address와 Physical Address를 Mapping 시키는 거는 Memory Management Unit을 통해 하는 것이고 운..

가상메모리라고 하는 것은 virtual 메모리입니다. 가상이라는 단어가 굉장히 중요합니다. 가상이라고 하는 것은 cpu가 보는 메모리를 가상메모리라고 합니다. CPU가 보는 메모리입니다. 이게 가상이라는 것인데 메인메모리의 크기는 하드디스크보다 굉장히 작습니다. 메인메모리의 크기를 16기가에서 2기가로 줄여도 동작을 합니다. 그에반해서 실행시키는 웹브라우저 같은 프로세스는 다양한 프로그램들을 실행시킵니다. 현재 동작시키고 있는 프로세스들이 하드디스크에 있는 이미지의 크기가 훨씬 큽니다. 현재 실행하고 있는 프로세스들의 크기가 여러분의 메인ㅁ네모리보다 훨씬 큼에도 불구하고 동작을 합니다. 왜냐하면 CPU는 가상메모리라는 것을 통해서 여러 프로세스들을 동시에 실행합니다. 그래서 가상메모리라고 하는 것은..

CPU가 프로세스를 실행시킬 때, Text section에 있는 CPU가 메인메모리에게 Address를 보냅니다. 명령어를 메인메모리에 보내줍니다. ADD 48269, 1 이렇게 되어있다고 가정한다면 48269라고 하는 메모리에 있는 값을 읽어서 1을 더한 다음 저장하라는 뜻입니다. 그러면 메인메모리에 있는 특정한 위치의 메인메모리에 Address를 보냈더니 명령에 Address를 통해서 받았을 때 명령어와 주소, 이는 Data Section에 있는 것 혹은 Stack에 있는 것입니다. Address를 메인메모리에 연결했을 때 page값을 운영체제가 보다가 mmu를 통해서 확인합니다. CPU가 적재를 하고 MMU를 통해서 해당 정보를 가져옵니다. CPU가 Address를 메인메모리에 보냅니다. 그럼..

CPU가 볼 때는 페이지 단위로 되어있지만 실제로는 page 사이즈와 frame 사이즈는 같습니다. 그러면 Page와 Frame을 관련시켜주는 것을 MMU라고 볼 수 있습니다. Logical 주소를 physical 주소로 바꿔주는 것이 MMU라고 배웠습니다. 이렇게 Physical 메모리는 조금밖에 되지 않는데 큰 프로그램을 어떻게 실행시키는지에 대한 고민을 해결하는 것입니다. 작은 physical 공간에 큰 사이즈 프로그램을 어떻게 작은 사이즈의 메모리에서 실행하는지에 관한 것입니다. CPU가 볼때는 자기가 선택한 프로그램은 모두 다 메인메모리에 적재가 되어 있다라는 것입니다. 즉 가상세계에 살고 있는 것이고 Virtual memory즉 가상메모리라고 합니다. 프로그램을 실행했을 때 태초에는 ..

CPU가 보는 프로그램은 책처럼 생겼습니다. 하드디스크를 컴파일로 실행하면 프로그램으로 만들면 더블클릭해서 메인메모리로 올라갈 것입니다. 적재가 되면 프로세스 형식으로 적재됩니다. CPU가 보는 프로세스는 0번지부터 시작하고 Continuious하게 존재하는 것처럼 보이지만 실제 view를 보면 여러군데 막 쪼개져 있는 구조입니다. 또한 어디에 올라가있는지 모릅니다. 그래서 dynamic loading하는 방법에서 필요한 코드만 메인메모리에 올립니다. CPU가 볼때는 모든 프로세스가 메인메모리에 올라와있는 것처럼 보입니다. OS는 컴파일된 프로그램을 책처럼 쪼갭니다. 하드디스크에서 램으로 적재할 때 필요한 부분만 적재하기 때문에 다 적재된 것처럼 보이는 것이 가상메모리입니다. 페이징이 무엇이냐면 프..

base와 base + limit를 도입해서 read base + 20read base + 10 이렇게 저장 되어있다가 프로세스로 변환되면 read ~ 되는 것입니다. 주소를 읽어와서 연산이 가능한 것입니다. 프로그램의 역할이 데이터를 읽어오고 데이터를 쓰는 것인데 이 주소가 필요한데 컴파일은 이것이 다 symbol로 저장됩니다. read base + 20read base + 10이런 상대주소로 되며 램에 적재해서 실행하게 되면 base에 그때 램의 상황에 따라서 바뀐 base를 받게 되는 것입니다. 실행을 하게 되면 base 값은 1024 번지야 그러면 이 안에 있는 것들이 1044 이렇게 바뀌는 것입니다. Logical address space : 프로그램에 의해서 생성된 logical addr..

1번a) 인접 행렬의 경우 n x n의 배열이 필요해서 시간복잡도가 o(n^2) 입니다.하지만 인접리스트의 경우 각 노드의 연결된 부분만 저장하므로 o(n+m) 입니다. 따라서 간선이 적은 sparce graph의 경우 인접리스트가 더 효율적입니다. b) 인접행렬의 경우, 각 정점에서 다른 모든 정점을 확인해야 하므로 o(n^2)의 시간이 걸립니다. 인접리스트는 각 노드의 실제 연결된 간선만 확인하믈 o(n+m)의 시간에 탐색이 가능하기에 DFS/BFS 알고리즘의 일반적인 시간복잡도입니다. c) 인접행렬은 n x n 배열을 재할당해야 하므로 정점 추가가 어렵고 비용이 크지만 인접리스트는 단순히 리스트에 빈 항목을 추가하면 되므로 정점 추가가 간편합니다. 2번무방향 단순그래프란?무방향 : 간선에 방향이 없..

Floyd-Warshall Algorithm가중치 방향 그래프 G=(V,E) V={1,2, ..., n}모든 노드 쌍들간의 최단경로의 길이를 구함d^k[i,j]중간에 노드 집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로 길이i.j 사이 어떤 노드도 경유하지 않고 가는 것은 무한대이다 라고 표시합니다. edge가 있으면 edge의 weight로 아니면 무한대로 표시합니다. 노드 i에서 j까지 가는데 1에서부터 n사이의 노드를 지날 수 있고 이것은 i에서 j까지 가는데 어떤 노드를 지나도 상관이 없다라는 것이고 이것이 i에서 j까지 가는 최단경로입니다. i^n[i, j] = 최단경로의 길이다 모든 i.j를 보는 것입니다. wij 자체가 만약 i에서 j로가는 edge가 있..

노드들을 반복해서 bellman-ford를 만들 수 있는 것에서 아무 에지나 릴렉스하지 않고 특별한 조건을 만족하는 relax에만 만족합니다. 그것이 dijkstra 알고리즘입니다. 초기화는 똑같습니다. 출발 노드만 distance estimator가 0이고 출발을 해서 첫번째 round에서 relax 할 때 distance 값이 최소인 노드를 찾습니다. 최소인 노드로부터 나가는 edge들만 relax합니다. 두번째 round에서는 다시 distance가 최소인 애를 찾는데 dijkstra 알고리즘은 이미 이전 round에서 선택이 되어서 edge들을 두번 선택할 필요는 없습니다. 이 노드의 최단 경로는 현재 노드가 가지고 있는 d[s] = 델타[s,s]입니다.dijkstra는 s만 0이고 나머지는 무한..