[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 49회차 미션

환급미션 49일째..

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 가상 메모리 개념

소프트웨어 베이직 - 자료구조와 알고리즘 - 그래프 - 깊이 우선 탐색

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 가상 메모리 개념

 

 

- 가상 메모리 (Virtual Memory System)

 

 

실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기에 한계가 있다.

가령, Linux os에서는 하나의 프로세스가 4GB를 차지하는데

일반적으로 사용되는 컴퓨터의 메모리 용량은 8~16GB 정도를 사용한다.

또한 폰 노이만 구조를 기반으로 하기 때문에 코드는 반드시 메모리 안에 있어야 한다.

-> 이러한 문제점을 해결하기 위해 가상 메모리의 개념이 필요한 것이다.

 

 

** 가상 메모리 기술은 운영체제에서 큰 부분을 차지하고,

프로세스 관련 기술과도 관련이 있기 때문에 두 주제가 서로의 이해를 돕게 될 것이다.

 

 

 

 

 

- 가상 메모리의 필요성

 

 

 

* 하나의 프로세스만 실행 가능한 시스템 ex) batch system

 

프로그램을 메모리로 로드

프로세스 실행

프로세스 종료(메모리 해제)

 

 

* 여러 프로세스 동시 실행 시스템

 

메모리 용량 부족 이슈

프로세스 메모리 영역 간에 침범 이슈

 

 

 

 

 

가상 메모리는 실제 메모리보다 많아 보이게 하는 기술로

실제 사용되는 메모리는 작다는 점에서 시작된 기술이며,

프로세스 간 공간을 분리하여 

프로세스 이슈가 전체 시스템에 영향을 주지 않을 수 있다.

 

 

앞서 다루었던 스레드의 개념과는 조금 다르다.

 

-> 메인 메모리에 실제 각 프로세스의 데이터가 조각으로 씌여있다.

 

 

 

 

 

 

 

* 기본 아이디어

 

프로세스는 가상 주소를 사용, 실제 해당 주소에서 데이터 읽기/쓰기를 할 때만 물리 주소로 바꾼다.

virtual address( 가상주소) : 프로세스가 참조하는 주소

physical address (물리주소) : 실제 메모리 주소

 

 

 

* MMU (memory management unit)

 

 

cpu에서 코드를 실행할 때, 가상 주소 메모리 접근이 필요할 때

해당 주소를 물리 주소 값으로 변환하는 하드웨어 장치를 뜻한다.

 

 

 

 

 

 

------------------

 

가상 메모리의 개념의 이해를 위해

복습 차원에서 프로세스 개념을 다시 살펴보았다.

 

 

 

 

* 실제 프로세스 : 리눅스 예시

 

(실제 물리 메모리의 공간과는 다른 가상메모리 주소를 사용한다. 앞선 내용들에서도 모두 마찬가지)

 

프로세스 간 공간은 완전히 분리되어 있고,

위의 예제에서는 0~3Gb : 실제 프로그램이 쓰는 공간, 3~4Gb 운영체제 코드가 들어가는 공간으로 부여되었다.

사용자 모드에서는 커널 공간에 접근이 불가능하다.

 

 

커널 공간은 공유하게 된다.

구체적인 내용은 가상 메모리 강의시간에 다루게 될 예정

 

 

 

 

 

 

* 다양한 IPC 기법

 

1. file 사용 - 실시간성이 떨어지고, 저장매체를 통하기 때문에 시간이 오래 걸림

 

2. Message Queue

3. Shared Memory

4. Pipe

5. Signal

6. Semaphore

7. Socket

...

 

2번부터는 모두 커널 공간을 사용한다. (핵심내용)

(커널 공간은 실제 물리 메모리 공간을 사용)

 

 

 

 

 

 

정리

 

여러 프로세스 동시 실행을 통한 성능 개선, 복잡한 프로그램을 위해 프로세스 간 통신이 필요

프로세스 간 공간이 완전히 분리되어있다.

프로세스 간 통신을 위한 특별한 기법 필요 - IPC(InterProcess Communication)

대부분의 IPC 기법은 결국 커널 공간을 활용하는 것 ( 커널 공간은 공유하기 때문 )

 

 

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 17. 그래프 - 깊이 우선 탐색

 

 

 

- 깊이 우선 탐색 (Depth First Search)

 

 

깊은 것을 우선적으로 탐색하는 알고리즘

스택(Stack) 자료구조를 기반으로 한다.

 

빠르게 모든 경우의 수를 탐색하려 할 때 쉽게 사용할 수 있다는 장점이 있다.

 

---------

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.

2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리를 한다.

방문하지 않은 인접 노드가 없는 경우, 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.

----------

 

 

 

 

위의 그림에서 1부터 출발,

방문 순서 : 1->2->7->6->8->3->4->5

 

 

Stack 자료구조에 기초하므로 구현이 간단하며, 

실제로는 스택을 사용하지 않아도 재귀함수를 사용해 스택과 비슷하게 동작한다는 점에서 

간단하게 구현 가능하다는 장점이 있다.

또한 O(N)의 시간복잡도를 갖는다.

 

 

 

 

- 깊이 우선 탐색 구현하기

 

 

 

* 깊이 우선 탐색 - 연결 리스트 정의

 

 

 

* 깊이 우선 탐색 - 연결 리스트 삽입함수

 

 

 

* 깊이 우선 탐색 - 깊이 우선 탐색 함수

 

 

 

 

* 깊이 우선 탐색 이용해보기

 

 

 

위의 코드를 실행하고,

node 3, edge 3

1-2

1-3

2-3

을 각각 연결시켰을 때

깊이 우선 탐색 함수를 실행시켰을 때

원하던 결과값이 나오는 것을 확인할 수 있다.

 

 

 

 

 

위의 코드 예제는 단순히 방문할 수 있는 기준에 대해 명시하지 않았다고 한다.

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE