투투

프로세스가 실행되기 위해서는 CPU, 메모리, 파일 등과 같은 여러가지 자원이 필요하다. 이 중 하나의 자원만 부족해도 프로세스가 실행되지 못한다. 따라서 운영체제는 이러한 자원을 관리하여 프로세스에게 적절히 배분해줘야 한다. 이때 교착상태가 일어나는데 교착상태의 개념과 교착상태의 원인, 해결법을 알아보자. 교착상태란? 입구가 두 개이고 한 명만 지나갈 수 있는 골목이 있다. 이 때 양쪽의 입구에서 사람들이 골목을 지나가려고 한다. 하지만 서로 반대편 사람이 먼저 지나가는 것을 기다리고 있어 아무도 골목을 들어서지 못하고 있다. 이처럼 두 개 이상의 서로 다른 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리고 있어 어떠한 프로세스도 완료되지 못하는 것을 교착상태라 한다. 프로세스 A와 B가 있을 때 ..

이진 트리는 루트 노드를 기준으로 두 개의 서브트리로 나뉘어 진다. 또한 서브트리도 최대 두 개의 서브트리로 나뉘어지는 것을 이진 트리라 한다. 이진 탐색 트리는 정해진 규칙에 의해 이진 트리의 노드에 데이터를 저장하는 기법이다. 이진 탐색 트리를 통해 데이터를 저장하면 원하는 데이터를 찾을 때 효율적으로 찾을 수 있다. 이진 탐색 트리의 원리 이진 탐색 트리는 정해진 규칙에 따라 이진 트리에 데이터를 저장한 트리이다. 아래는 이진 탐색 트리를 가장 잘 표현한 것 같아서 첨부한다. 루트 노드를 기준으로 큰 값이 들어오면 오른쪽으로, 작은 값이 들어온다면 왼쪽으로 보내진다. 이를 통해 루트 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 저장된다. 이제 데이터를 찾아야 한다면 아래와 같은 과정을 거치게..

프림과 크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 알고리즘이다. 먼저 최소 신장 트리가 무엇인지 알아본 후에 유니온 파인드를 적용시킨 크루스칼 알고리즘을 알아본다. 최소 신장 트리 N개의 노드로 이루어진 그래프가 있다. 이 그래프에는 다양한 부분 그래프가 존재할 수 있다. 이때 부분 그래프를 신장 트리라하며 N개의 노드글 N-1개의 간선으로 연결하고 순환되지 않는 구조를 가져야만 신장 트리라 할 수 있다. 이러한 신장 트리 중에서 연결하는데 가장 적은 비용이 드는 신장 트리를 최소 신장 트리라 한다. 개념 크루스칼 알고리즘은 유니온 파인드와 그리디 알고리즘의 개념을 활용하였다. 먼저 신장 트리가 되기 위해서는 N-1개의 간선으로 N개의 노드를 연결해야 하며 순환되지 않는 구조를 가져야 한다. ..

운영체제는 커널 모드와 사용자 모드로 나뉘어 운영된다. 프로그램에서 파일 읽기, 파일 쓰기 등은 커널 모드를 통해 동작한다. 이때 시스템 콜은 커널 영역의 기능을 사용자 모드에서 사용할 수 있도록 한다. 시스템 콜의 개념과 동작 과정을 알아보자. 개념 시스템 콜은 응용 프로그램에서 커널이 제공하는 기능을 사용하기 위한 인터페이스다. 이를 통해 프로세스가 하드웨어에 직접 접근하여 디스크에 저장되어 있는 파일을 읽는 등의 기능을 수행할 수 있다. 프로그램은 고유의 주소를 갖고 있으며 함수 호출이 발생하면 해당 주소 내에서 접근하여 함수를 실행할 수 있다. 하지만 프로그램의 주소를 벗어난 공간에 접근하기 위해서는(커널 영역) 시스템 콜을 사용할 수 있다. 시스템 콜의 동작 과정 프로그램에서 디스크에 저장되어 ..

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 즉 {1, 2}와 {3, 4}는 서로소 집합이지만 {1, 2}와 {2, 4}는 서로소 집합이 아니다. 이러한 서로소 집합을 구할 때 유니온 파인드 알고리즘을 사용할 수 있다. 유니온 파인드의 개념을 알아보고 코드를 통해 구현해보자. 또한 유니온 파인드 알고리즘을 활용한 또 다른 알고리즘을 소개한다. 개념 유니온 파인드 알고리즘은 서로소 집합을 찾기위해 사용되는 알고리즘이다. 유니온 파인드는 Find과 Union라고 불리는 두 가지 연산으로 이루어져 있다. Find: 원소 x가 어느 집합에 포함되어 있는지 찾는다. Union: 원소 x가 포함된 집합과 원소 y가 포함된 집합을 합친다. 위의 연산을 통해 그래프 내에서 부분집합을 쉽게 구할 수 있다. 이제..

스택을 활용하여 후위표기법을 구현할 수 있다. 후위표기법의 개념과 스택으로 후위표기법을 구현해보자. 후위표기법이란? 우리가 일반적으로 알고있는 5+3x2와 같은 수식은 중위 표기법으로 작성된 것이다. 이를 후위표기법으로 변환하면 532x+가 된다. 먼저 중위 표기법으로 작성된 수식을 후위 표기법으로 변환하는 방법과 후위 표기법으로 표현된 수식을 계산하는 방법을 알아보자. 후위 표기법으로 변환 5+3x2라는 수식을 보자. 숫자가 나오면 바로 옮겨 적는다. "x" 또는 "÷"가 나오면 나온 순서대로 다른 곳에 기록해둔다. "+" 또는 "-"가 나오면 다른 곳에 기록해둔 "x"와 "÷"를 늦게 적은 순서대로 후위 표기식에 옮겨 적는다. 모두 옮겨 적었다면 "+" 또는 "-"를 다른 곳에 기록해둔다. 모두 적었..

합병 정렬은 분할 정복 알고리즘을 활용한 정렬 방법이다. 먼저 원소들을 반으로 나누고 두 개의 부분 배열을 비교하여 정렬된 상태로 만들어 가는 것이다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 N//2를 기준으로 원소들을 반으로 나눈 값을 인덱스로 하고 위에서 구한 인덱스를 기준으로 리스트를 반으로 나눈다. 반으로 나눈 리스트를 또 다시 반으로 나누고 리스트 원소의 개수가 1일 때 해당 원소를 반환한다. 이렇게 반으로 나눈 원소들을 합쳐 나간다. 초기에 1개의 원소들로 이루어진 리스트를 비교하여 정렬 후에 2개의 원소를 갖는 리스트로 만든다. 이후에는 2개의 원소를 갖는 리스트끼리 비교하여 정렬하여 4개의 원소를 갖는 리스트로 만든다. 위의 과정을 반복하는 것이 합병 정렬이다. 구현 me..

TCP와 UDP는 OSI 7 계층의 전송 계층에서 사용되는 프로토콜이다. TCP와 UDP는 데이터를 전달하는데 사용되지만 정확성을 추구하는 TCP와 신속성을 추구하는 UDP는 각각 방식이 다르다. 이번에 TCP와 UDP의 차이를 알아보고 UDP가 어디에 사용되는지 알아보자. TCP TCP는 클라이언트와 서버가 연결된 상태에서 데이터를 주고받는 연결 지향적 프로토콜이다. 연결을 위해서 3-way handshake를 사용하며 클라이언트가 연결 요청을 하면 서버는 연결을 수락한다. 서버가 연결을 수락했다면 고정적인 통신 선로가 생기고 이를 통해 데이터를 주고받을 수 있다. 이를 통해 TCP는 1:1 통신만 가능하다는 것을 알 수 있다. TCP는 신뢰성있는 데이터 전송을 하기 때문에 클라이언트가 전송하는 모든 ..

인터럽트는 끼어들기라고 생각하면 쉽게 이해할 수 있다. 이미 진행하고 있는 일을 중간에 끼어들어 가로채서 다른 사람이 그 일을 진행하는 것이라고 일단 생각해보자. 그리고 인터럽트의 정의와 종류, 처리 과정을 알아보면서 이해해보자. 개념 CPU는 매번 프로그램 카운터가 가리키는 곳의 명령을 수행한 후에 다음 명령을 수행하기 직전에 인터럽트 라인을 확인한다. 이때 인터럽트 라인에 인터럽트가 발생했을 때는 지금까지 수행하던 일을 PCB에 저장하고 인터럽트를 수행한다. 만약 인터럽트를 처리하는 중에 또 다른 인터럽트가 들어온다면 어떻게 할까? 결론적으로 인터럽트 처리 중에 다른 인터럽트를 허용하지 않는다. 왜냐하면 A라는 인터럽트가 어떤 데이터를 변경을 하고 있는데 B라는 인터럽트가 들어왔다고 가정해보자. B라..

슬라이딩 윈도우는 어떠한 배열에서 일정 범위의 값을 비교할 때 유용하게 사용될 수 있는 방법이다. 투 포인터와 비슷하다고 생각할 수 있지만 투 포인터는 정렬된 배열 내에서 가변적인 범위를 탐색하는 반면 슬라이딩 윈도우는 정렬의 유무와 상관없이 고정적인 범위를 탐색한다는 것에 차이가 있다. 개념 슬라이딩 윈도우는 어떠한 배열에서 고정된 크기의 범위를 탐색할 때 유용하게 사용된다. 아래의 그림과 같은 배열을 예시로 확인해보자. 아래의 배열 중에서 연속된 세개의 수를 선택하여 그 합이 최대가 되는 구간이 어디인지 구하려고 한다. 이를 위해 아래의 그림처럼 처음부터 세개의 수를 선택하여 합을 구할 수 있을 것이다. 순서대로 (3 - 1 + 8)을 계산하고 (-1 + 8 - 2)를 계산하면서 진행하는데 (-1 +..