자료구조와 알고리즘

자료구조란?

• 데이터가 어떻게 저장되고, 처리되는지에 대한 구조와 방법

• 가장 기본적인 자료구조는 변수이다.

• 자료구조에 따라 데이터를 처리하는 방법이 달라지며, 코드가 더 효율적이고 간단해질 수 있다.

알고리즘이란?

• 문제를 해결하기 위한 확실한 절차나 방법

• 자료구조를 선택하여 데이터를 저장하고, 이에 맞는 알고리즘을 사용해 데이터를 처리하여 원하는 결과를 얻는다.

시간 복잡도

• 알고리즘이 문제를 해결하는 데 걸리는 시간

• 사용자마다 컴퓨터 사양이 다르므로, 직접적인 시간 측정은 어려운 경우가 많다. 따라서 알고리즘의 성능을 예측하기 위해 시간 복잡도를 사용

• 반복문, 재귀 등에서 성능을 분석

빅오 표기법의 특징

• 입력 크기가 증가할 때 계산량이 어떻게 변화하는지를 나타내는 척도

• n² + 2n + 100 → O(n²)

배열 (Array)

• 장점

  • 읽기/쓰기: O(1) 시간 복잡도

• 단점

  • 크기 예측 어려움: 메모리 낭비 발생 가능

  • 삽입/삭제: 중간에 삽입/삭제되기 때문에 비효율적 (O(n))

     

연결 리스트 (Linked List)

• 특징

  • 동적 크기 조정 가능

  • 삽입/삭제는 효율적 (O(1)), 그러나 특정 노드 검색 시 O(n)

• 배열과의 비교

   

  • 크기: 배열은 고정 크기, 연결 리스트는 동적 크기

  • 주소: 배열은 연속적인 메모리, 연결 리스트는 불연속적

  • 참조 시간: 배열은 O(1), 연결 리스트는 O(n)

  • 삽입/삭제 시간: 배열은 O(n), 연결 리스트는 O(1) (노드 변경 시)

큐 (Queue)

• FIFO(First In First Out), 먼저 들어온 데이터가 먼저 나오는 구조

• 운영체제의 스케줄링에서 사용되는 방식으로, 데이터를 순차적으로 처리한다.

덱 (Deque)

• 양쪽 끝에서 데이터를 삽입하거나 제거할 수 있는 자료구조

• 데이터를 양쪽 끝에서 자유롭게 처리할 수 있다.

해시 테이블 (Hash Table)

• 해시와 테이블을 결합한 자료구조

• 키와 값을 한 쌍으로 저장

• 읽기/삽입/수정/삭제 시 평균적으로 O(1)의 시간 복잡도를 가진다.

• 동일한 인덱스에 여러 데이터를 저장할 때 해시 충돌이 발생할 수 있다. -> 연결 리스트를 사용하여 같은 인덱스에 여러 데이터를 저장

   

• 장점: 빠른 검색, 삽입, 삭제

• 단점: 공간 효율이 좋지 않으며, 좋은 해시 함수 구현이 필수적이다.

셋 (Set)

• 중복된 데이터를 허용하지 않는 자료구조

• 데이터 중복을 자동으로 제거하며, 빠른 검색이 가능

운영체제

CPU(Central Processing Unit) 구조

• 중앙 처리 장치

• 산술논리 연산 장치: 데이터 연산 담당

• 제어 장치: 모든 장치들의 동작을 제어하고 지시 담당

• 레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치(변수라고 생각하면 쉬움)

메모리 종류

RAM(Random Access Memory)

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

• 전력이 끊기면 데이터를 잃어버리기 때문에 메인 메모리로 사용

ROM(Read Only Memory)

• 전력이 끊겨도 데이터 계속 보관 가능

   

• 한 번 쓰면 수정 불가능

• 컴퓨터 부팅과 관련된 바이오스를 저장하는 데 주로 쓰임

인터럽트

• 폴링 방식 주기적으로 CPU를 확인해줘야 해서 성능이 좋지 않음

• 폴링 방식을 해결하는 것이 인터럽트

• CPU가 입출력 관리자에게 명령을 내리고 다른 작업을 수행

   

• 입출력 관리자는 완료되었을 때 CPU에게 신호를 주고 CPU는 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료

• 인터럽트 서비스 루틴은 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수

• 인터럽트는 비동기적으로 수행

• 하드웨어 인터럽트: 입출력 등과 같은 인터럽트

• 소프트웨어 인터럽트: 사용자 프로그램에서 발생하는 인터럽트

프로그램과 프로세스

프로그램

• 하드디스크와 같은 저장 장치에 저장된 명령문의 집합체

• 애플리케이션이나 앱이라고도 불림

프로세스

• 실행 중인 프로그램

• 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 프로세스라고 불림

• 운영체제가 작업을 처리하는 단위

구조

• 코드: 자신을 실행하는 코드

• 데이터: 전역 변수와 static 변수

• 스택: 지역 변수와 함수 호출을 했을 때 필요한 정보

• 힙: 프로그래머가 런타임 시 할당할 수 있는 메모리 공간

컴파일 과정

• 전처리기를 거쳐서 매크로로 정의한 숫자를 치환하고 필요한 파일을 불러옴 -> 파일은 .i가 됨

• 컴파일을 마치면 고수준인 C 언어를 저수준인 어셈블리어로 바꿔준다. ->

  파일은 .s가 됨

• 어셈블러가 어셈블리어를 기계어로 바꿔준다. ->

  파일은 .o가 된다.

• 링커가 링킹(여러가지 라이브러라나 소스코드 연결)을 한다. ->

  파일은 .exe가 된다.

멀티 프로그래밍과 멀티 프로세싱

유니 프로그래밍

• 메모리에 오직 하나의 프로세스만 올라온 것

• I/O 작업은 기다림 → CPU가 쉬는 시간이 발생함

• 하나의 프로세스를 다 끝내야 다른 프로세스를 실행할 수 있음

멀티 프로그래밍

• 메모리에 여러 개의 프로세스가 올라온 것

• I/O 작업을 만나면 해당 프로세스에서 발생한 I/O 작업은 기다리면서 다른 프로세스 실행 → CPU가 쉬는 시간이 없음

• 모든 프로세스를 짧게 실행해 반복해서 동시에 실행되는 것처럼 보임

• CPU가 여러 개 있다면 멀티 프로세서

• 멀티 프로세서로 작업을 처리하는 것을 멀티 프로그래밍

멀티 프로세싱

• 위 두 가지는 메모리 관점으로 정의했다면, 멀티 프로세싱은 CPU 관점으로 정의

• 여러 개의 CPU가 여러 개의 프로세스를 처리하는 것

PCB(Process Control Block)

• 프로세스가 만들어지면 해당 프로세스의 정보를 가진 PCB를 만들고 저장함

• PCB는 연결 리스트로 저장됨

구조

• 포인터: 부모와 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터 등, 프로세스의 한 상태에서 다른 상태로 전환될 때 전환하는 포인터

• 프로세스 상태: 현재 프로세스의 상태(생성, 준비, 실행, 대기, 완료)

   

• 프로세스 ID: 프로세스를 식별하기 위한 숫자

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

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

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

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

프로세스 상태

• CPU는 한 순간에 하나의 프로세스만 처리

• 생성: PCB를 생성하고 메모리에 프로그램 적재를 요청, 승인 받으면 준비 상태로 넘어감

• 준비: CPU를 사용하기 위해 기다리고 있는 상태(CPU 스케줄러에 의해 할당)

• 대기: 프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태

• 특정 프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 CPU를 기다리게 하는건 비효율적

• 해당 프로세스를 대기 상태로 두고 다른 프로세스에게 CPU 할당

• 입출력이 완료되면  CPU 할당 기회를 준다.(준비상태로)

• 실행: 준비 상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태,

• 실행 상태에 있는 프로세스의 수는 CPU의 개수만큼

• 부여된 시간만큼 사용

• 준비된 시간이 지나면 준비 상태로 돌아감

• 완료: 프로세스가 종료된 상태

• 프로세스가 사용했던 데이터를 제거

• PCB도 제거

컨텍스트 스위칭

• 프로세스가 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스를 저장하고 다른 프로세스의 상태 값으로 교체하는 작업

• 컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경

  • 프로세스 상태

  • 프로그램 카운터

  • 레지스터 정보

  • 메모리 관련 정보

• CPU 점유 시간이 다 되거나 I/O 요청이 있거나 다른 종류의 인터럽트가 있을 때 발생

프로세스 생성과 종료

프로세스 생성

• 운영체제는 프로그램의 코드 영역과 데이터 영역을 메모리에 로드하고 빈 스택과 빈 힙을 만듦

• 프로세스를 관리하기 위한 PCB(Process Control Block)를 만들어서 값을 초기화

• 운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 1번만 실행됨

• 나머지는 0번 프로세스를 복사해서 생성 (복사는 fork() 함수 사용).

• 생성하는 것보다 복사하는 것이 더 빠름

• 복사한 프로세스는 자식 프로세스라고 함

• 자식 프로세스는 부모 프로세스의 코드 영역, 데이터 영역, 스택 영역 및 PCB의 내용을 전부 복사

• 자식 프로세스는 부모와 똑같이 실행되지만, exec() 함수를 통해 원하는 프로그램을 실행하면서 부모의 코드를 덮어씀

프로세스 종료

• 부모 프로세스는 자식 프로세스의 종료 상태(exit status)를 확인하고 종료

   

• 부모 프로세스가 먼저 종료되거나 자식 프로세스가 비정상적으로 종료된 경우, 메모리 상에 남아 있는 자식 프로세스를 좀비 프로세스라고 함

쓰레드

• 프로세스 내에 존재하는 작업 단위로 1개 이상의 쓰레드를 가질 수 있음

• 쓰레드는 동일한 프로세스 내에서 코드, 데이터, 힙 영역을 공유하며, 각 쓰레드는 자신만의 스택을 가짐

• 운영체제는 작업을 처리하는 단위로 프로세스 내 쓰레드를 사용

TCB (Thread Control Block)

• 쓰레드를 관리하는 구조체로, 쓰레드의 상태 및 필요한 정보를 담고 있음

CPU 스케줄링 개요

• 프로그램이 실행되면 메모리에서 프로세스가 생성되고, 각 프로세스에는 1개 이상의 쓰레드가 존재

• 프로세스는 CPU를 차지하기 위해 운영체제의 명령을 기다리고 있음

• 운영체제는 CPU를 각 프로세스에 할당/해제하는 작업을 수행하는데, 이를 CPU 스케줄링이라고 함

1. 어떤 프로세스에게 CPU 리소스를 할당할 것인가?

2. CPU를 할당받은 프로세스가 얼마 동안 CPU를 사용할 것인가?

다중큐

• 준비 상태 및 대기 상태는 큐를 사용하여 관리

• 큐에 들어온 프로세스들은 스케줄링에 따라 CPU를 할당받음

스케줄링 목표

• 리소스 사용률 최적화

• 오버헤드 최소화

• 공평성 보장

• 처리량 향상

• 대기 시간 최소화

• 응답 시간 단축

스케줄링 알고리즘

FIFO (First In First Out)

• 큐에 들어온 순서대로 CPU를 할당받는 방식

• 먼저 들어온 프로세스가 완료될 때까지 다른 프로세스는 실행되지 않음

• CPU 사용률이 낮아질 수 있음

   

• I/O 작업이 있는 경우 대기 시간이 길어질 수 있음

SJF (Shortest Job First)

• 가장 짧은 작업(버스트 타임)을 먼저 실행하는 방식

• 프로세스의 종료 시간을 예측하기 어려워서 실제로 구현이 어렵고 비효율적일 수 있음

• 길이가 긴 프로세스는 대기 시간이 길어져 실행되지 않을 수 있음

RR (Round Robin)

• 각 프로세스에 일정 시간(타임 슬라이스)만큼 CPU를 할당하고, 그 후 다른 프로세스로 전환

• 타임 슬라이스를 사용하여 공평하게 CPU를 나눔

• 타임 슬라이스의 크기에 따라 성능이 달라짐

• 크면 FIFO처럼 동작하고, 짧으면 여러 프로세스가 동시에 실행되는 것처럼 느껴짐

• 너무 짧으면 컨텍스트 스위칭이 너무 자주 발생하여 성능 저하가 있을 수 있음

MLFQ (Multi-Level Feedback Queue)

• 가장 일반적으로 사용되는 알고리즘

• 여러 개의 큐를 사용하여 각 큐에 프로세스를 우선순위별로 배치하고, 프로세스가 CPU를 일정 시간 사용하면 우선순위가 낮은 큐로 이동

• RR 알고리즘을 개선하여 I/O 작업이 많은 프로세스와 CPU 사용 시간이 많은 프로세스를 구분할 수 있음

• 적절한 타임 슬라이스를 설정하여 CPU 사용률과 I/O 사용률을 최적화

Reference

• 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

• 그림으로 쉽게 배우는 운영체제