자료구조와 알고리즘

자료구조(Data Structure)란 효율적인 데이터의 사용을 위해 데이터를 특정 방식으로 저장, 구성하는 방식이다.

알고리즘(algorithm)이란 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다.

자료구조와 알고리즘을 함께 공부하는 이유는, 자료구조에 따라 알고리즘이 달라지기 때문이다. 즉, 어떤 방식으로 데이터를 저장하고 구성했냐에 따라 문제를 해결하는 방식이 달라진다. 또한 같은 자료구조일지라도 알고리즘은 여러가지가 될 수 있다.
개발자라면 문제 해결을 위한 가장 좋은 알고리즘을 선택할 수 있어야 하며 가장 좋은 알고리즘을 위해 어떤 자료구조를 사용할지 결정할 수 있어야 한다.

그렇다면, 좋은 알고리즘이란 무엇일까?
일반적으로 알고리즘의 속도를 성능의 척도로 사용하여 문제를 해결하는 속도가 빠를수록 좋은 알고리즘이라고 할 수 있다. 속도는 어떻게 측정할까?

시간복잡도

시간복잡도(Time Complexity)란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 뜻한다. 이 때의 시간은 초, 분을 뜻하는 것이 아니라 '문제해결을 위해 같은 방식을 몇 번이나 반복했는지'와 같은 반복 횟수를 뜻한다. 알고리즘에 대해 다음 세 가지 경우로 나누어 성능을 평가한다.

• 최선의 경우: Big-Ω(빅-오메가).
  한 번에 데이터를 찾는 경우

• 최악의 경우: Big-O(빅-오).
  마지막에 데이터를 찾는 경우

• 평균의 경우: Big-Θ(빅-세타).
  배열 길이의 중간만큼 시간이 걸리는 경우

가장 많이 사용하는 방법은 Big-O로, 앞으로 이야기하는 시간복잡도는 특정 알고리즘을 사용해 문제를 해결할 때 가장 오래걸리는 시간이다.

시간 복잡도에는 여러가지가 있는데, 입력량(데이터의 양)이 증가할수록 계산량도 비례하여 증가하는 일차함수의 모양을 띠는 O(n), 가장 성능이 좋은 O(1) 등이 있다.

자료구조

배열(Array)

프로그래밍 언어에서 기본적으로 제공하는 자료구조로, 연속된 메모리 공간을 찾은 뒤 순서대로 데이터를 할당하고, 나머지 공간에 의미 없는 쓰레기 값을 저장한다.

장점

• 참조에 있어 O(1)의 좋은 성능을 보인다.

단점

• 데이터 삽입과 삭제에 대해 비효율적이다.

연결 리스트(LinkedList)

저장하려는 데이터들을 메모리 공간에 분산해 할당한 뒤 이 데이터들을 노드로 연결하는 자료구조
노드는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있어 다음 노드와 연결이 가능하다.
연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능하다.

장점

• 데이터의 삽입, 삭제에 유리

단점

• 참조에 있어 O(n)의 성능을 보여 비효율적이다.

데이터의 참조가 자주 발생한다면 배열을, 삭제 또는 삽입이 자주 발생한다면 연결 리스트를 쓰는 것이 효율적이다.

스택(Stack)

First In Last Out(FILO) 즉, 가장 먼저 삽입된 데이터가 가장 나중에 나오는 특징을 가지는 자료구조이다.

우리가 자주 사용하는 Ctrl+z(이전으로 되돌리기) 기능도 스택으로 구현된 것이다.

큐(Queue)

First In First Out(FIFO) 즉, 먼저 들어간 데이터가 먼저 나오는 특징을 가지는 자료구조이다.

FIFO 스케줄링에서 운영체제는 프로세스를 큐에 들어온 순서대로 넣고 CPU는 먼저 들어온 순서대로 프로세스를 처리한다.

덱(Deque)

데이터의 삽입과 삭제를 head와 tail 두 군데에서 자유롭게 진행 가능한 자료구조이다.

해시 테이블(Hash Table)

프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리 등 다양한 이름으로 불린다. 해시와 테이블이 합쳐진 것으로, 특정 해시 함수에 따라 테이블의 Key와 Value에 매치된다.

장점

• Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다.

• 삽입, 수정, 삭제 또한 O(1)의 성능을 보인다.

단점

• 이미 어떤 Key에 대한 Value가 존재할 경우, 해당 Key에 대한 다른 데이터가 생성될 때 충돌이(Collision) 발생하는데, 이 충돌을 해결하기 위해 이전에 있던 Value와 새로 들어간 Value를 연결 리스트로 연결한다. 이후에 저장된 데이터에 접근하기 위해선 원래 있던 데이터에 먼저 접근 후 연결 리스트를 통해 다음 데이터로 접근한다. 이 때의 참조 성능은 O(n)이 된다. 그렇기 때문에 같은 Key에 여러 Value가 존재하지 않도록 데이터를 골고루 분산 시킬 수 있는 해시 함수의 선정이 중요하다.

• 공간이 많이 필요해 메모리를 많이 차지한다.

셋(Set)

데이터의 중복을 허용하지 않는 자료구조로, 해시 테이블을 이용해 구현할 수 있어 해시 셋(Hash set)이라고도 한다.

해시 테이블의 Value값을 사용하지 않고 Key만 사용하여 구현한다. 즉, Key가 key이자 데이터가 되는 것이다.

운영체제(Operating System)

운영체제(Operating System)란 응용프로그램 또는 사용자가 컴퓨터 하드웨어를 편리하고 효율적으로 사용하게 하기 위하여 시스템 자원(메모리, 프로세서 등)을 관리하고 여러가지 프로그램이 필요로 하는 공통적인 서비스를 제공하는 소프트웨어이다.

운영체제의 역할

• 프로세스 관리:

  여러가지 애플리케이션을 동시에 실행할 수 있도록 한다.

• 메모리 관리: 여러가지 애플리케이션을 실행할 때 메모리를 관리한다.

• 하드웨어 관리: 중요한 데이터를 보호하기 위해

  사용자의 하드웨어에 대한 직접적인 접근을 막는다.

   

• 파일 시스템 관리: 하드디스크에 파일들을 효율적으로 저장, 관리한다.

운영체제의 구조

커널: 프로세스와 메모리, 저장장치를 관리하는 운영체제의 핵심 부분. 사용자는 커널에 직접 접근하지 못하고, 인터페이스를 통해 접근 가능

인터페이스: 사용자의 명령을 전달하고 실행 결과를 사용자에게 알려주는 역할

시스템 콜: 사용자로부터 커널을 보호하기 위한 인터페이스. 하드웨어에 데이터 저장시 Write 함수를 통해 하드디스크의 빈 공간에 데이터를 저장해, 다른 데이터를 덮어쓰거나 침범하지 않도록 한다.

드라이버: 하드웨어와 커널의 인터페이스. 운영체제는 많은 종류의 하드웨어를 지원하해야 하는데 마우스와 키보드같은 간단한 하드웨어 프로그램은 커널이 가지고 있기도 하지만, 보통 하드웨어는 그 하드웨어의 제조사가 드라이버를 만들어 제공한다. 사용자는 이런 디바이스 드라이버를 설치해서 사용을 할 수 있다.

컴퓨터와 하드웨어 구조

오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조.

메인보드: 다른 하드웨어를 연결하는 장치.

CPU(Central Processing Unit, 중앙처리장치)

CPU의 구성

• 산술논리 연산장치(Arithmetic and Logic Unit, ALU): 데이터 연산

• 제어 장치(Control Unit): 모든 장치들의 동작 지시, 제어

• 레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치

메모리

• RAM(Random Access Memory)

랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.

전력이 끊기면 데이터를 읽어버린다. 메인 메모리로 사용

• ROM(Read Only Memory)

전력이 끊겨도 데이터를 보관할 수 있지만 데이터를 한 번 쓰면 수정 불가

컴퓨터 부팅과 관련된 BIOS 저장에 주로 쓰인다.

CPU와 입출력 장치의 통신 방식

• 폴링 방식: 입출력이 완료되는 시점을 몰라 주기적으로 확인해야 해 성능이 낮다.

• 인터럽트: 폴링 방식의 단점을 해결하기 위한 방식. 입출력 관리자에게 입출력 명령을 내린 뒤 CPU는 다른 작업을 진행하고 입출력 완료 시 입출력 관리자가 CPU에게 신호를 주면 신호를 받은 CPU는 인터럽트 서비스 루틴(ISP)을 실행시켜 작업을 완료한다.

프로세스와 쓰레드

프로그램(Program): 애플리케이션 또는 앱이라고도 불리며, 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체

프로세스(Process): 실행 중인 프로그램, 즉 하드디스크에 저장된 프로그램이 메모리(RAM)에 올라갔을 때

프로세스의 구조

Code: 자신을 실행하는 코드 저장

Data: 전역 변수와 Static(정적) 변수가 저장

Heap: 프로그래머가 동적으로 메모리를 할당할 수 있는 메모리 공간(malloc(), free())

Stack: 지역 변수와 함수 호출을 했을 때 필요한 정보들 저장

PCB(Process Control Block)

운영체제가 여러 개의 프로세스를 체계적으로 관리하기 위해 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 생성, 저장한다. 이 PCB는 연결 리스트 자료구조로 저장된다.

PCB의 구조

포인터: 프로세스의 한 상태에서 다른 상태로 전환될 때 저장

프로세스 상태: 현재 프로세스의 다섯 가지 상태(생성, 준비, 실행, 대기, 완료) 표시

프로세스 ID: 프로세스 식별 숫자 저장

프로그램 카운터: 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장

레지스터 정보: 프로세스가 실행될 때 사용했던 레지스터 값 저장

메모리 관련 정보: 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등 저장

CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행 시간, CPU 점유 시간 등 저장

프로세스 상태

오늘날 운영체제는 시분할 프로세스로 여러 개의 프로세스를 돌아가며 실행하며, 이를 위해 다섯 가지 상태를 가진다.

• 생성(New): PCB 생성 및 메모리에 프로그램 적재 요청. 요청 승인 시 준비 상태로 전이

• 준비(Ready): CPU를 사용하기 위해 기다림. CPU 할당

• 대기(Waiting): 실행 중이던 프로세스가 입출력 요청을 하면 CPU는 입출력이 완료될 때까지 기다리지 않고 이 프로세스를 대기 상태로 놓은 채 다른 프로세스를 가져와 실행한다. 대기 상태의 프로세스의 입출력 작업이 완료되면 다시 CPU 할당 기회를 주기 위해 준비 상태로 보낸다.

• 실행(Running): 준비상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태. 실행상태의 프로세스 개수는 CPU의 개수와 같다. 실행상태에 있는 프로세스도 부여된 시간 초과시 할당된 CPU를 빼앗긴다. 이 때 프로세스는 다시 준비 상태로 돌아간다.

• 완료(Terminated): 프로세스가 종료된 상태. 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거

   

컨텍스트 스위칭(Context Switching)

프로세스 실행 중 다른 프로세스를 싱행하기 위해 실행중이던 프로세스를 저장하고 다른 프로세스의 상태값으로 교체하는 작업. CPU 점유시간 초과, I/O 요청, 다른 종류의 인터럽트 발생 시 컨텍스트 스위칭이 발생한다.

쓰레드(Thread)

운영체제가 작업을 처리하는 단위는 프로세스로, 여러 작업을 요구할수록 프로세스 증가, PCB 증가 및 메모리에 각각의 코드, 데이터, 스택, 힙 영역 생성으로 컴퓨터가 느려지며 비용이 증가한다.

한 개 이상의 쓰레드가 프로세스 내에 존재하며 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유하며 스택은 각 쓰레드가 가지고 있다.

작동 원리

1. 쓰레드 ID를 부여 및 Thread Control Block(TCB) 생성

2. 운영체제가 작업을 처리하는 단위가 프로세스에서 프로세스 내 쓰레드로 변경

3. 이제 여러 작업을 할 때 프로세스를 복사하는 것이 아닌 쓰레드를 생성

프로세스와 쓰레드의 장단점

• 안정성: 프로세스는 서로 독립적이기 때문에 하나의 프로세스에 이상이 생기더라도 다른 프로세스에는 영향이 없다. 반면 쓰레드는 자신이 속한 프로세스에 이상이 생기면 그 안에 있는 모든 쓰레드에도 문제가 생긴다.

• 속도, 자원: 각각의 프로세스는 서로 고유한 자원을 소유(코드,데이터, 힙, 스택)하며 프로세스 간 통신을 할 때 IPC를 이용해야해 오버헤드가 크고 속도가 느리다. 반면 쓰레드는 스택을 제외한 자원을 공유하기 때문에 오버헤드가 적고 쓰레드 간 통신을 할 때 데이터를 공유할 수 있어 통신이 쉽지만 공유되는 공간에서 문제가 발생할 수 있다.

CPU 스케줄링

CPU 스케줄링이란 운영체제(스케줄러)가 다음의 사항을 고려해 특정 방식으로 모든 프로세스에게 CPU를 할당/해제하는 작업이다.

1. 어떤 프로세스에 CPU 리소스를 줄 것인가

2. CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야 하는가

CPU 스케줄링 과정

프로세스 실행 과정을 프로세스의 상태에 따라 조금 더 자세히 알아 보자.

그 전에 먼저 이 과정에서 준비/대기 상태는 큐(Queue) 자료구조로 관리된다는 것을 인지하고 넘어가자. 큐(Queue) 자료구조는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In Fist Out) 방식의 자료구조이다.

1. 프로그램을 실행해 프로세스와 프로세스의 정보를 담고 있는 PCB가 생성(New)되면 PBC는 준비(Ready) 상태의 다중큐에 들어가 실행되기를 기다린다.

2. CPU 스케줄러는 준비 상태의 다중큐에 들어있는 프로세스 중 적당한 프로세스를 선택해 실행상태로 전환한다.

3-1. 실행을 마치고 종료 시 프로세스는 완료(Terminated)된다.

3-2. 하지만 프로세스가 CPU를 할당받아 실행되던 중 I/O 요청이 들어오면 대기(Waiting) 상태로 진입하는데, 이 때 I/O 작업 종류에 따라 분류된 큐(HDD, LAN, 키보드 등)로 들어가게 된다. 이 때 운영체제는 준비(Ready) 상태에 있던 다른 프로세스에 CPU를 할당해 실행시켜 CPU가 계속 일할 수 있도록 한다.

4. I/O 작업 완료시 해당 큐에서 PCB를 꺼내 다시 준비(Ready) 상태의 다중큐에 위치시킨다. 이후 2번의 과정부터 다시 반복한다.

스케줄링 목표

• 리소스 사용률: CPU 사용률 또는 I/O 디바이스 사용률 상승

• 오버헤드 최소화

• 공평성: 모든 프로세스에 공평하게 CPU 할당

• 처리량: 같은 시간 내 더 많은 처리량 가지도록 함

• 대기시간: 작업 요청 후 실제 작업 실행 전까지 대기 시간이 짧을 수 있도록

• 응답시간: 대화형 시스템에서 사용자의 요청에 대해 빠른 응답

목표 간 서로 상반되어 같이 달성할 수 없는 상황도 존재하기 때문에 사용하는 시스템에 따라 적절히 목표를 설정하여 스케줄링 한다.

회고

생각보다 하루에 이해해야 할 양이 많았고, 구현 부분에서 시간이 많이 소요된다고 느꼈다. 하지만 이전까지 자료구조는 단순한 개념 중 하나라고만 생각했는데 구현을 해보니 조금 더 실체적으로 다가왔던 것 같다. 어렵다고도 생각했지만 그림과 함께 설명을 들으니 그래도 이해가 더 쉽고 빠르게 가능했다.

공부한 내용을 정리해 블로그에도 올리고, 깃헙 잔디도 심는 방식으로 발자취를 남긴 부분에서는 나 자신을 칭찬한다. 다만 지금까지는 구현할 때 알려주는 대로 따라 가고, 따라 치기만 했는데 다음에 그런 기회가 온다면 스스로 미리 구현해본다면 좋겠다고 생각했다.