뜌릅

개념 분할정복의 한 방법으로서, 평균적으로 매우 빠른 알고리즘에 속합니다. 우리가 라이브러리에서 사용하는 대부분의 정렬 함수는 퀵 정렬을 변형한 것입니다. 분할정복 답게 문제를 분리하여 각각 해결하고 합쳐서 해결하는 방식입니다. 배열안에 있는 요소를 선택합니다. 이렇게 고른 원소를 피봇이라고 합니다. 피봇을 기준으로 피봇보다 작은 원소들은 왼쪽으로 큰 원소들은 오른쪽으로 옮깁니다. 피봇을 제외한 왼쪽 배열과 오른쪽 배열을 각각 순환 호출을 통하여 피봇을 설정하고 왼쪽 오른쪽으로 나눕니다. 배열이 더이상 분할이 불가능할 때까지 반복합니다. 즉 피봇을 기준으로 분할하고 분할된 배열들을 합하여 정렬된 배열이 되게 하는 알고리즘입니다. 분할 정복기준으로 단계를 나누면 아래와 같습니다. Divide: 입력 배열을..

삽입정렬이란 삽입정렬은 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다. 최선의 경우: 이미 정렬이 완료되어있는 배열, 이 경우에는 삽입할 위치를 지정할 필요없이 O(N)으로 끝이 납니다. Worst Case: 내림차순으로 정렬이 된 배열, 이 경우에는 삽입할 위치를 찾기 위해 탐색하기 때문에, 시간복잡도는 O(N^2)입니다. 예제 8,5,6,2,4를 오름차순으로 정렬해 봅시다. 코드 예시 void insertion_sort(vector &arr) { int n = arr.size(); int i = 0, j = 0; for (i = 1; i < n; i++) { int key = arr[i]; // ..

Bubble Sort 가장 간단한 정렬 알고리즘 거품 정렬 즉 Bubble Sort는 가장 기초적인 정렬 알고리즘이다. 서로 인접한 2가지 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 알고리즘 입니다. 2중 포문으로 구성되어 있으며, 첫번째 포문의 1번째때, 첫번재와 두번째원소를 비교하고, 두번째와 세번째 원소를 비교하고 마지막-1번째와 마지막번째를 비교하는 식으로 구성됩니다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다. void bubbleSort(int[] arr) { in..

파일 시스템이란 파일을 다루는 시스템을 의미한다. 파일 시스템이 무엇인지에 대해 설명하기에 앞서 파일이 무엇인지 알아보는게 좋을 듯 싶다. 파일이란 파일이란? 데이터나 프로그램을 담는 그릇입니다( 파일시스템은 그 그릇들을 관리하는 것이다). 정확히 말하자면 데이터나 프로그램을 저장하는 연속적인 논리적 공간입니다. 파일의 젤 앞부분을 offset 0 라고 하며, 여기서부터 데이터가 연속적으로 담기게 된다. 데이터의 타입은 바이너리일수도, 일반 정수일수도 Char타입일수도 있습니다. 파일의 구조는 어떨까? 파일의 구조는 OS나 프로그램이 정합니다. None: 연속적인 바이트 구조 Simple Record: 레코드의 한줄이 구조가 되는 것이다. 길이는 가변적일수도 고정적일수도 있습니다. Complex: Doc..

메모리는 전통적으로 한정적이었습니다. 운영체제는 이 메모리를 효율적으로 운용하기 위해서 적절한 관리방법이 필요했고, 크게 나누어보면 가상메모리와 물리 메모리 2가지로 나누어 볼 수 있습니다. 모든 프로그램이 실행될려면 메모리에 탑재가 되어야 합니다. 이는 CPU가 메모리와 레지스터에만 접근이 가능하기 때문입니다. CPU는 메메모리 주소를 기반으로 작동을 하며, 우리가 아는 HDD나 SDD는 Block Device로 Block단위로 디바이스를 통하여 IO가 발생합니다. (NAND 메모리(RAM)는 PAGE단위로 NOR 메모리(Register)는 바이트 단위로 IO가 가능합니다.) 하지만 실제 모든 프로세스가 메모리의 0번지에서 시작하지는 않습니다.(커널메모리나 기타 등등) 따라서 이를 위해서 가상메모리가 ..

스케줄러는 왜 필요할까? CPU에서는 프로세스를 수행하는데, 최대 효율과 반응성을 높여야 한다는 목표가 있습니다. 이를 위해서는 스케줄링을 잘해야 합니다. 프로세스의 비용을 추상화 하면, Process Cost = CPU Brust + IO Brust 라는 식이 나옵니다. 여기서 Brust는 실행을 의미합니다. CPU Brust는 CPU가 직접 계산하는 Cost을 의미하고, IO Brust는 인터럽트 발생 Cost을 의미합니다. 어떤 프로세스는 CPU Brust가 클것이고 어떤 프로세스는 IO Brust 부분이 더 클 것입니다. 운영체제는 프로세스의 이러한 점을 고려하여 스케줄링을 행해야 합니다. CPU Brust가 큰 프로세스는 CPU Bounded Process라고 부르고, IO Brust가 큰 부분..

IPC란 Inter Process Communication의 줄임말입니다. 프로세스는 독립적으로 사용이 됩니다. 독립적이라는 것은 다른 프로세스에게 영향을 받지 않는 다는 말입니다. 이러한 독립적인 프로세스이더라도 프로세스간에 통신을 해야할 상황이 존재할 것입니다. 이를 가능하게 하는 것이 IPC 통신입니다. 이러한 IPC의 설비는 커널이 제공합니다. IPC 설비는 보통 2가지로 서비스를 제공합니다. 아래의 그림처럼, 커널을 통해 통신하는 방식이 존재하며, 커널을 통하지 않고 공유메모리를 사용하여 통신하는 방식이 존재합니다. 1. 메시지 전달(Message Sending) 커널이 제공하는 API를 이용해서 커널 공간을 통해 통신합니다. 메시지 큐(Mesage Queue)를 사용하여 송신 프로세스는 큐에 ..

CPU의 여러 기능중 하나는 Process Management입니다. 단순히 Process Scheduling뿐만 아니라, Process을 수행하고 변경하는 등의 여러가지 일을 할 줄 알아야 합니다. CPU가 프로세스를 처리할줄 알려면, 프로세스에 대한 데이터(메타 데이터)가 있어야 합니다. 프로세스를 제어하기 위한 메타 데이터들을 저장하는 곳이 PCB Process Control Block입니다. PCB PCB의 구성은 아래와 같습니다. Process Metadata Process ID Process State Process Priority CPU Registers Owner CPU Usage Memeory Usage PCB는 프로세스가 생성 상태에서 생성이 이루어집니다. PCB는 프로세스 테이블 안에..

인터럽트란? OS에서 인터럽트란 매우 중요합니다. 우리가 마우스를 움직이거나 키보드로 타자를 칠때, 컴퓨터는 이를 즉각 수용하여 모니터 화면에 띄어 주어야 합니다. 이런 즉각적인 일을 하기 위해서는 기존의 하던일을 중단하고 IO로 들어온 요청을 수행해야 한다.(놀고있는 CPU 코어가 있다면 그 친구가 할수도 있긴합니다. 하지만 OS는 멀티프로그래밍을 지향하기 때문에 어떠한 일을 수행하고 있을 가능성이 큽니다.) 이러한 인터럽트는 CPU의 사용성을 증대시키는 방안으로 활용되었습니다. 예를들어 작업중에 DISK에서 새로운 데이터를 가져와야 하는 경우, 운영체제의 특성상 CPU가 직접 접근을 못하므로 IO 컨트롤러에게 대리로 시키게 됩니다. 그동안 작업은 대개 중단됩니다. 디스크 IO 컨트롤러(윈도우에서 작업..

운영체제(Operating System)는 컴퓨터 시스템의 자원들을 효율적으로 관리하며,, 운영체제는 컴퓨터 사용자와 컴퓨터 하드웨어 간의 인터페이스로서 동작하는 시스템 소프트웨어의 일종으로, 다른 응용프로그램이 유용한 작업을 할 수 있도록 환경을 제공해 줍니다. 또 사용자입장에서 운영체제는 편리성을 제공해 주는데, 이는 사용자가 건드려서는 안될것을 건드리는 것을 예방하거나, 보기편한 GUI, 인터페이스등을 제공해줍니다. 프로세스 관리 프로세스에 대해 설명하기 전에 커널에 대해 설명을 간단하게 해야 합니다. 커널은 사용자 인터페이스, 어플리케이션 등등과 시스템 소프트웨어 등을 분리하는 역할을 합니다. 사용자가 하드웨어 제어를 하고 싶을 때에는 커널을 통해서만 조작이 가능합니다. 이러한 기능을 제공하는 이..