Computer Science

가상 메모리(Virtual Memory) 하나의 프로그램을 실행시킬 때 해당 프로그램 전체를 실제 메모리에 올렸었다. 하지만 가상 메모리(Virtual Memory)를 사용한다면 당장 실행에 필요한 부분만 실제 메모리에 올려서 실행하게 된다. 즉, 가상 메모리는 프로그램 전체가 아닌 필요한 일부분만 실제 메모리에 올리는 방식을 사용한다. 1) 실행에 있어서 사용되는 프로그램의 일부만 메모리에 올린다. 2) 논리적 주소 공간은 물리적 주소 공간보다 더 커질 수있다. 3) 몇몇의 프로세스는 주소 공간에 공유되어진 것을 허락한다. 4) 프로세스 생성을 더욱 효과적으로 할 수 있다. 5) 필요로 한다면 페이지는 swapped in/out 이 된다. 요구 페이징(Demand Paging) 요구 페이징은 가상 메모..

outline Background Binding of Data to Memory MMU contiguous allocation paging TLB Background 메모리는 기본적으로 주소와 데이터로 구성되어 있다. CPU와 메모리는 양방향으로 주소와 데이터를 주고받는다. CPU는 주소를 가지고 메인 메모리에 데이터를 요청을 하고 해당 주소에 계산 결과를 통해서 메모리에 요구하는 실제 주소에 저장되어 있는 데이터를 CPU에 전달한다. 소스 파일(Source file) : 고수 준언어 또는 어셈블리어 (ex. c) 목적 파일(Object file) : 컴파일 또는 어셈블 결과 (ex. o) 실행파일(Executable file) : 링크 결과 (ex. exe) 소스파일은 컴파일러에 의해 수행 결과로 목적..

깊이 우선 탐색 너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색(DFS, depth, first search)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다. 시간 복잡도 : O(V+E) DFS는 대체로 시작 정점에서 멀이 있는 정점을 찾을 때 적합하다. DFS는 최단 경로를 보장하지 않는다. DFS에 의해 생성된 검색 트리는 길고 좁은 편이며, 상대적으로 적은 메모리를 필요로 한다. 깊이 우선 탐색 관련 문제 [프로그래머스] [level2] 타..

너비 우선 탐색 너비 우선 탐색(BFS, Breadth, First Search)은 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성된다. 그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다. 다음에 나오는 그림을 보면서 BFS 동작에 대해 짐작하면 좋다. 시간 복잡도 : O(V+E) BFS는 시작 정점에서 가까운 정점을 찾는데 적합하다. BFS에서 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장한다. BFS는 현재 경계에 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며 많은 메모리를 필요로 합니다. 너비 우선 탐색 관련 문제 [프로그래머스] 2021.08.10 - [컴도리돌이 전공 공부/C++] ..

outline Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem Monitors 전통적 동기화 문제들(Classical Problems of Synchronization) 1. 유한 버퍼 문제(Bounded-Buffer Problem), 소비-생산자 문제(Producer-Consumer Problem) 생산자(Producer)는 데이터를 생성하고, 소비자(Consumer)는 데이터를 소비한다. 생산한 데이터는 중간의 버퍼(buffer)라는 저장 공간에 저장해 두고, 소비자는 버퍼에서 필요한 만큼 가져간다. 버퍼의 크기는 유한하다. 버퍼의 공간이 가..

outline Critical Section Requirements for the Solution Alogrithm Synchronization Hardware TestAndSet and Swap Semaphores Critical Section of n Processes Block/ Wakeup Implementation 프로세스 동기화(Process Synchronization) 프로세스는 독립 프로세스(Independent Process)와 협력 프로세스(Cooperating Process)로 나눠진다. 협력 프로세스는 다른 프로세스에 의해 영향을 주고받을 수 있는 프로세스이다. 반대로 다른 프로세스에게 영향을 미치지 않고 독립적인 프로세스를 독립 프로세스라고 한다. 현대 컴퓨터 환경에서는 협력 프..

outline CPU Scheduler Scheduling Criteria Dispatcher Scheduling Algorithms FCFS(First-Come First-Served) SJF(Shortest-Job-First) SRTF(Shortest-Remaining-Time-First) Priority Scheduling RR(Round Robin) Multilevel Queue Multilevel Feedback Queue CPU 스케줄러(CPU Scheduler) CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 다음 프로세스가 어느 프로세스인지를 선택하는 알고리즘을 'CPU Scheduling' 알고리즘이라고 한다. CPU 스케줄링은 크게 두 가지의 특징으로 나눌 ..

outline Process Concept Process State Process Control Block-PCB Process Scheduling Queues Schedulers Threads Process creation and terminated Context Switch User and Kernel Threads Issue 프로세스(Process) 프로세스란 실제 메모리에 적재되어 프로세서에 의해 실행되고 있는 프로그램을 의미한다. 즉, 프로그램을 구동하였을 때, 프로그램 자체와 상태가 메모리 상에서 실행되는 작업의 단위를 지칭한다. 실행 중인 프로그램, 프로그램이 실행되는데 필요한 모든 것들을 저장하는 자료구조의 실체. 1) 메모리의 프로세스(Process in Memory) 텍스트(text s..