CS 1주차 발자국

운영 체제

운영체제 개요

• 컴퓨터는 운영체제가 없어도 동작이 가능

• 예전 전화기는 통화만 되지만 최신 휴대전화는 어플등 다양한 기능이 가능

• 운영체제의 일

  • 프로세스 관리

  • 메모리 관리

  • 하드웨어 관리

  • 파일 시스템 관리

운영체제의 역사

• 1943 애니악

• 1950

  • 초반 직접회로 개발

  • 후반 싱글 스트림 배치시스템

• 1960

  • 시분할 시스템

    • 싱글 스트림 배치 시스템 한계 극복

    • 프로그램을 순서대로 실행하는 것이 아닌 메모리에 여러 프로그램을 올려 놓고 시간을 나누어서 빠르게 돌아가며 실행

  • UNIX

    • 멀티 프로그래밍

    • 다중 사용자

    • 파일 시스템

• 1970

  • 개인용 컴퓨터의 시대

  • 매킨토시, ms-dos

  •  

운영체제의 구조

• 커널

  • 프로세스와 메모리, 저장 장치를 관리하는 기능

  • 사용자는 인터페이스를 통해 접속

• 사용자는 GUI, CLI로 커널 제어

• 어플리케이션과 커널의 인터페이스는 시스템 콜을 사용

• 하드웨어와 커널의 인터페이스는 드라이버를 사용

컴퓨터 하드웨어와 구조

• 폰 노이만 구조

• CPU와 메모리 사이에 버스로 연결.

• 메인보드

  • 다른 하드웨어를 연결하는 장치

  • cpu와 메모리가 필수

• CPU(중앙처리 장치)

  • 산술 논리 연산장치, 제어장치, 레지스터의 구조

• 메모리 종류

  • ram

    • 전원을 끄면 메모리가 휘발

  • ROM(Read Only Memory)

    • 전월을 꺼도 메모리가 보존.

    • 바이오스 등 수정되지 않는 데이터를 저장

부팅 과정

• ROM에 저장된 바이오스 실행

• 부트 오더

인터럽트

• cpu는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령

• 주기적으로 장치들에게 확인

  → polling 방식. 효율이 좋지 않음

• polling방식의 단점을 보완한게 인터럽트

  • 입출력 명령을 내리고 입출력 관리자는 입출력이 발생하면 cpu에게 전달

  • cpu는 isr실행시켜 작업 완료.

• 하드웨어 인터럽트

• 소프트웨어 인터럽트

프로그램

• 하드디스크 등과 저장장치에 저장된 명령문의 집합체

• 저장 장치만 사용하는 수동적인 존재

프로세스

• 실행중인 프로그램

• 하드디스크에 저장되어 있는 프로그램이 메모리에 올라가있는 상태

• 메모리도 사용하고 운영체제의 cpu 스케줄링 알고르즘도 사용, 출력와 입력도 하는 능동적인 존재

프로세스 구조

• code, data, heap, stack 영역으로 구조

• code

  • 실행하는 코드가 저장

• data

  • 전역 변수와 static(정적) 변수가 저장

• heap

  • 동적으로 메모리를 할당하는데 사용.

• stack

  • 지역 변수와 함수를 호출했을때 필요한 정보들이 저장

프로세스가 되는 과정

• 컴파일 과정

• 전처리기 → 컴파일러 → 어셈블러 → 링커(링킹)

유니프로그래밍

• 메모리에 오직 하나의 프로세스가 올라와 처리하는 것

• cpu는 프로세스를 실행하다가 i/o 작업을 만나면 기다렸다가 완료되면 작업을 처리

• 하나의 프로세스를 다 끝내야 다른 프로세스를 실행하는 단점이 존재.

멀티 프로그래밍

• 메모리에 여러개의 프로세스를 올려서 실행

• cpu가 프로세스를 실행하다가 I/O 작업을 만나면 기다리면서 다른 프로세스를 실행

• cpu 쉬는시간이 줄어들어 효율적

• 여러개의 프로세스를 돌아가면서 짧은시간동안 작업을 진행하여 모든 프로세스를 동시에 실행시키는 것처럼 느끼게 하는 기술

  → 멀티태스킹

• cpu를 한개가 아니라 여러개를 이용

  → 멀티 프로세서

• 멀티 프로세서로 작업을 처리하는 방식을 멀티 프로세싱이라 칭함.

PCB(Process Control Block)

• 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장.

• PCB들은 연결리스트라는 자료 구조로 저장.

• 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거.

  • 연결 리스트의 구조는 유지

PCB 구조

• 포인터

  • 부모와 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터를 저장

• 프로세스 상태

  • 현재 프로세스의 5가지 상태를 나타냄

  • 생성, 준비, 실행, 대기, 완료

• 프로세스 ID

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

• 프로그램 카운터

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

• 레지스터 정보

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

• 메모리 관련 정보

  • 메모리에 있는 위치정보, 경계레지스터 값 등이 저장

• CPU 스케쥴링 정보

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

프로세스 상태

• 시분할 시스템을 사용하는 운영체제는 여러개의 프로세스를 돌아가면서 실행

• cpu가 여러개의 프로세스를 동시에 실행하는 것이 아니라 한 순간에는 하나의 프로세스밖에 처리하지 못함

  • 속도가 빨라 사람이 보기엔 동시에 처리로 보임.

• 생성 상태

  • PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태

• 준비 상태

  • CPU를 사용하기 위해 준비하고 있는 상태

  • CPU 스케쥴러에 의해 CPU가 할당됨.

  • 대부분의 프로세스 상태

• 실행 상태

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

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

  • 부여된 시간만큼만 사용이 가능

  • 시간이 완료되면 다시 준비 상태로 변경

• 대기 상태

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

• 완료 상태

  • 프로세스가 종료된 상태

  • 데이터를 메모리에서 제거하고 생성된 PCB제거

컨텍스트 스위칭

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

• 실행중인 프로세스의 작업 내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨.

• PCB에 변경되는 값들은 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등

• 컨텍스트 스위칭이 발생하는 이유

  • CPU 점유 시간이 다 된 경우

  • I/O 요청이 있는 경우

  • 다른 종류의 인터럽트가 있는 경우

프로세스 생성과 종료

• .exe 파일 실행시 운영체제는 포로그램의 코드영역과 데이터 영역을 메모리에 로드하고 빈스택과 빈 힙을 만들어 공간을 확보

• 프로세스를 관리하기 위한 pcb를 만들어 값을 초기화

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

  • 나머지 모든 프로세스는 새로 생성하지 않고 0번 프로세스를 복사해서 사용

  • 복사는 fork()함수를 사용

  • 새로 생성하는 것보다 복사하는게 빠르기 때문

  • 복사한 프로세스는 자식 프로세스

  • 0번 프로세스는 부모 프로세스

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

  • 그럼 복사하면 0번 프로세스가 똑같이 실행되는거 아닌가?

    • 맞음. 그대로 복사하니 당연한 결과

    • 자기가 원하는 코드는 exec() 함수를 이용하여 실행.

    • 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 겂으로 덮어쓰게됨.

    • 자식프로세스는 부모 프로세스와 다르게 동작

• 부모 프로세스와 자식 프로세스는 cpu 스케줄링에 따라 실행되는데 순서는 운영체제 따라 결정.

• 부모 프로세스가 먼저 실행되는 경우

  • pid 값을1 받으면 17번째 줄 함수 실행

  • 자식 프로세스의 exit 실행될때까지 대기.

  • 자식 프로세스 실행

  • 12번 함수 실행 후 13번 함수를 통해 프로세스 종료를 부모 프로세스에게 전달

  • 대기하고 있던 부모 프로세서는 자식 프로세스의 종료 신호를 받고 18번 함수 19번 함수를 실행하고 종료

• 만약 부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적인 종료가 되어서 exit신호를 주지 못해 ExitStatus를 읽어오지 못하여 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 함

쓰레드

• 운영체제가 작업을 처리하는 단위는 프로세스

• 프로세스를 생성하면 pcb가 생성되고 프로세스 수만큼 pcb, 코드, 데이터, 스택, 힙 영역도 만들어줘야 하기 때문에 너무 무거워짐.

• 그래서 프로세스가 많아질수록 메모리를 많이 차지 하게 됨.

  ⇒ 쓰레드 고안

• 쓰레드는 프로세스 안에 있고 한개 또는 여러개가 존재하게 됨.

• 쓰레드들은 프로세스의 pcb, code, data, heap영역을 공유. 단 stack은 쓰레드마다 하나씩 갖고 있음.

   

• 쓰레드들에게 id를 부여하고, 쓰레드를 관리하기 위한 TCB(Thread Control Blcok)이 생성.

  • 운영체제 관점에서 쓰레드들도 구분이 가능해짐.

• 브라우저에서 탭을 하나 추가로 생성하면, 프로세스가 생성되는 것이 아니라 쓰레드가 하나 더 생성됨.

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

• 안정성

  • 프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제 있어도 다른 프로세스는 영향을 받지 않는다.

  • 쓰레드는 하나의 프로세스 안에 존재하기 때문에 프로세스에 문제가 생기면 쓰레드에게도 문제가 생긴다.

  • 프로세스 방식이 쓰레드 보다 우수

• 속도와 자원

  • 각각의 프로세스는 서로 고유한 자원을 갖고 있음. code, data, heap, stack영역을 전부 따로 두고 있고, 프로세스간 통신을 하려면 IPC를 이용해야 해서 오버헤드가 크고 속도가 느림.

  • 쓰레드는 한 프로세스 내에서 stack 영역을 제외한 영역을 공유하므로 오버헤드가 작음. 쓰레드 간의 통신은 데이터를 공유할 수 있으니 쉽지만, 공유되는 공간에서 문제가 생길 수 있음.

CPU 스케쥴링 개요

• 운영체제는 모든 프로세스에게 cpu를 할당/해제 하는데 이를 cpu 스케쥴링이라 함.

• 스케줄러(운영체제)의 고려사항

  1. 어떤 프로세스에게 cpu리소스를 주어야 하는가.

  2. cpu를 할당 받은 프로세스가 얼마나 cpu를 사용해야 하는가.

     • 시분할 처리 방식으로 여러 프로세스에 짧은 시간동안 돌아가면서 Cpu를 할당.

  → 컴퓨터의 성능에 영향을 많이 미침.

  • cpu를 할당받아 처리하는 작업을 CPU Burst. 입출력 작업을 I/O Burst.

다중 큐

• 큐

  • 먼저 들어온걸 먼저 처리하고, 나중에 들어온걸 나중에 처리하는 구조.

• 프로세스가 실행상태에서 준비 상태로 돌아갈때

  • 운영체제는 해당 프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음.

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

• 프로세스가 실행상태에서 i/o 요청을 받아 대기상태로 오면

  • i/o 작업 종류에 따라서 분류된 큐에 들어가게 됨.

  • hdd, lan, 키보드 큐

• 큐에 들어가는건 프로세스의 정보를 갖고 있는 PCB가 들어감.

• 프로세스 정보를 담고 있는 PCB는 준비상태의 다중큐에 들어가서 준비되길 기다리며, CPU스케쥴러에 의해 실행 상태로 전환.

• CPU스케쥴러는 준비상태의 다중큐를 참조하여 어떤 프로세스를 실행시킬지 결정

• I/O 작업도 종류별로 나누어진 큐에 들어가고 CPU스케쥴러는 이를 참조해 스케쥴링을 진행.

스케쥴링 목표

1. 리소스 사용률

   • CPU사용률을 높이는것을 또는 I/O 사용률을 높이는것을 목표로 할 수 있음.

2. 오버헤드 최소화

   • 스케줄링을 하기 위한 계산이 복잡하거나 컨텍스트 스위칭을 자주하면 배보다 배꼽이 커지는 상황이 발생.

   • 스케줄러는 이런 오버헤드를 최소화 하는것을 목표

3. 공평성

   • 모든 프로세스에게 공평하게 CPU가 할당되어야 함.

   • 공평의 의미는 시스템에 따라 달라질 수 있음.

4. 처리량

   1. 같은 시간내에 더 많은 처리를 할 수 있는 방법을 목표로 함.

5. 대기시간

   • 작업을 요청하고 실제 작업이 이뤄지기 전까지 대기하는 시간이 짧은 것을 목표로 함.

6. 응답시간

   • 대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하므로 응답시간이 짧은것을 목표로 함.

• 모든 목표를 최고 수준으로 유지하기는 힘듬.

• 서로 상반된 목표가 있기 때문.

  • 처리량을 높이기 위해서는 하나의 프로세스에 cpu를 오래 할당해야함.

  • 응답시간을 줄이기 위해서는 여러 프로세스에 cpu를 골고루 할당해야함.

  → 처리량과 응답시간의 목표를 같이 달성할 수 없음.

  → 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정.

스케쥴링 알고리즘

FIFO(First In First Out)

• 먼저 들어온 작업이 먼저 나감.

• 스케쥴링 큐에 들어온 순서대로 cpu를 할당하는 방식.

• 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행 됨.

• 장점

  • 단순하고 직관적

• 단점

  • 한 프로세스가 완전히 끝나야 다음 프로세스가 실행되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함.

  • 또한 I/O작업이 있다면 cpu가 i/o작업이 끝날때까지 기다리기때문에 cpu 사용률이 떨어짐.

• 스케줄링의 성능은 평균 대기 시간으로 평가

  • 평균 대기 시간은 프로세스가 여러개 실행될때 이 프로세스가 모두 실행될때까지 대기 시간의 평균.

  • 프로세스 1의 burst는 25초, 프로세스2는 5초 프로세스3은 4초.

    • 프로세스1이 먼저 도착했으므로 대기시은 0초.

    • 프로세스2는 프로세스1이 실행되고 실행 하므로 대기시간은 25초.

    • 프로세스 3은 프로세스1과 프로세스2가 실행되고 실행 하므로 대기시간은 30초.

    • 평균 대기시간은 18.3초.

  • 순서가 바뀌면

    • 프로세스3은 바로 시작 되었으므로 대기시간은 0초.

    • 프로세스2이 실행되고 프로세스2가 실행. 대기시간은 4초.

    • 프로세스1은 프로세스 3,2 실행 시간만큼 기다려서 대기시간은 9초.

    • 평균 대기시간은 4.3초.

  ⇒ FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나서 현대 운영체제에서는 잘 쓰이지 않고 일괄 처리 시스템에 사용됨.

SJF(Shortest Job First)

• FIFO의 단점을 보완.

• 이론적으로 FIFO보다 성능이 좋음.

• 하지만 문제점 발생

  1. 어떤 프로세스가 얼마나 실행될 지 예측이 힘듦.

  2. BurstTime이 긴 프로세스는 아주 오래동안 실행되지 않을 수 있음.

  → 이러한 문제때문에 SJF알고리즘은 사용되지 않음.

RR(Round Robin)

• FIFO알고리즘은 일괄처리 시스템엔 적절하지만 시분할 처리 시스템엔 부적절

• SJF알고리즘의 단점은 프로세스의 종료 시간을 예측하기 힘듦.

• FIFO 알고리즘의 단점을 해결

  • 한 프로세스에게 일정 시간만큼 cpu를 할당하고, 할당시간이 지나면 강제로 다른 프로세스에게 일정 시간만큼 cpu를 할당.

  • 강제로 cpu를 빼앗긴 프로세스는 큐의 마지막으로 이당.

• 프로세스에게 할당하는 일정 시간은 타임 슬라이스 또는 타임 퀀텀이라고 부름.

• 평균 대기시간 측정

  • 타임슬라이스: 10s

  • P1의 BursTime은 25초 / P2는 4초 / P3는 10초

  • P1은 큐에 들어오자마 실행. 대기시간은 0초

    • 25초중 타임 슬라이스 값인 10초만 실행되고 나머지 시간은 큐의 제일 뒤로 이동.

    • P2(4s) / P3(10s) / P1(15s)

  • p2는 10초동안 기다림. 대기시간은 10초

    • BurstTime인 4초만 실행하고 종료.

    • P3(10s) / P1(15s)

  • p3은 14초동안 기다림. 대기시간은 14초

    • BurstTime인 10초만 실행하고 종료

    • P1(15s)

  • p1은 p2, p3의 실행 시가만큼 기다림. 대기시간은 14초.

    • BurstTime이 타임 슬라이스 값보다 크므로 10초만 실행.

    • 남은 작업시간은 큐의 맨 뒤로 생성

    • P1(5s)

  • 다시 P1의 남은 작업을 실행. 큐에 생성되자마자 실행 되므로 대기시간은 0초.

  → 평균 대기시간은 12.67s

• RR방식과 FIFO방식의 평균 대기시간이 비슷할 수 있음.

  • 평균 대기시간이 비슷하면 RR방식이 비효율적

    → 컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문.

    → RR 알고리즘의 성능은 타임슬라이스 값에 따라 크게 달라짐.

• 타임 슬라이스가 무제한인 경우 FIFO와 같음.

• 타임 슬라이스가 작은경우에는 컨텍스트 스위칭이 너무 자주 발생함.

  • 타임 슬라이스에서 실행되는 프로세스의 처리 양보다 컨텍스트 스위칭을 처리하는 양이커져서 오버헤드가 너무 커지는 상황 발생.

• 최적의 타임슬라이스를 설정하는 방법은 사용자가 느끼기에 여러 프로세스가 버벅 거리지 않고 동시에 실행된다고 느끼면서 오버헤드가 너무 크지 않는 값을 찾아야 함.

  • 윈도우는 20ms, Unix는 100ms

MLFQ(Multi Level Feedback Queue)

• 가장 일반적으로 쓰이는 cpu 스케쥴링 기법

• 탄생 배경

  • RR의 업그레이드 된 알고리즘

  • P1은 I/O 작업 없이 CPU연사만 하는 프로세스, P2는 1초 CPU 연산을 하고 10초 동안 I/O 작업.

  • P1 → Cpu Bound Process // P2 → I/O Bound Process

  • Cpu Bound Process는 Cpu 사용률과 처리량을 중요하게 여김.

  • I/O Bound Process는 응답 속도를 중요하게 여김

  • 타임 슬라이스 값에 따른 효율 분석. (P2가 먼저 시작된다고 가정)

    • 타임 슬라이스가 100초인 경우

      • I/O 요청이 발생하고 P1이 100초동안 실행됨.

         

    • 타임 슬라이스가 1초인 경우

      • I/O요청이 발생하고 P1이 10번 실행되면 P2의 작업이 끝나 인터럽트가 발생되고, P2는 큐에 들어감.

      • P2는 다시 1초 실행 되고 다시 I/O 작업을 기다림.

      • 이후 계속 반속

         

    • 상황 비교

      • CPU는 쉬지 않고 일해서 CPU사용률은 100%

      • I/O 사용률을 보면 P1이 실행되는 동안 P2의 I/O 작업이 완료된 시점부터 기다리는 시간이 발생하기 때문에 10%밖에 되지 않음.

      • 타임 슬라이스가 작기 때문에 P2가 첫번째 상황처럼 기다리며 낭비되는 시간이 거의 없음. 90%정도 나오게 됨.

         

• CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임슬라이스를 선택

• 그리고 CPU Boud Process 타임 슬라이스를 크게 설정.

• 운영체제 입장에서 CPU Boud Process와 I/O Bound Process 구분하는 기준

  • CPU를 실행하는 프로세스가 스스로 CPU를 반납하면 CPU사용량이 적은거니 I/O Bound Process일 가능성이 큼.

  • 반대로 CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏기는 상황이면 CPU Boud Process일 확률이 높음.

• 우선 순위를 가진 큐를 여러가지 준비.

  • 우선순위가 높으면 타임 슬라이스가 낮고 우선순위가 낮을 수록 타임 슬라이스 크기가 커짐.

  • 타임 슬라이스 크기를 오버해서 강제로 Cpu를 뺏기면 원래있던 순위보다 우선순위가 낮은 큐로 이동.

자료구조

자료구조

• 데이터가 어떻게 저장되고 어떻게 사용되는지 나타냄.

• 가장 간단한 자료구조는 변수, 배열

알고리즘

• 어떤 문제를 해결하기 위한 확실한 방법

• 자료구조가 바뀌면 알고리즘도 바뀐다

시간복잡도

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

• 시간을 측정하는 시간이 아닌 실행시간을 예측

• 반복문이 많아지면 시간이 늘어난다.

• 최선의 경우 - $\varOmega$

• 최악의 경우 배열의 길이만큼 - Big-O

• 평균의 경우 - $\Theta$

배열

• 기본적으로 제공하는 자료구조

• 일반적인 프로그래밍 언어는 배열을 선언할때 배열의 크기를 선언.

  • 운영체제는 메모리에서 해당 크기만큼 연속된 빈공간을 찾아서 값을 할당.

  • 할당하지 않은 부분은 의미없는 쓰레기 값을 전달하고, 운영체제는 배열의 시작 주소만 기억.

• 배열의 인덱스 참조는 크기에 상관없이 한번에 찾아와서 O(1)의 성능을 갖는다.

• 하지만, 데이터 삽입, 삭제의 성능은 좋지 않음.

  • 배열의 데이터는 메모리에 연속된 공간에 할당하고 있음.

  • 배열 크기를 넘어서 할당하게 되면 문제가 발생.

  • 배열의 끝에는 다른 데이터가 있을경우 운영체제는 다시 연속적인 크기의 메모리를 찾아서 다시 할당하고. 기존의 데이터를 복사까지 해주어야함.

  • 그렇다고 배열의 크기를 처음부터 크게 할당하면 일시적으로 해결된것 처럼 보이지만, 처음부터 공간을 크게 할당하면 배열하나의 메모리양이 커지고, 다 사용하지 않으면 공간의 낭비이다.

• JS의 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분 불연속적으로 할당.

  • 메모리는 내부적으로 연결하여 사용자에게는 연속적처럼 느껴지게함.

• 장점

  • 읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가진다

• 단점

  • 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.

  • 데이터 삽입, 삭제가 비효율적이다.

연결리스트(Linked List)

• 배열의 단점을 보완.

• 저장하는 데이터들을 메모리에 분산해서 할당하고 데이터들을 서로 연결.

• Node라는 것을 만들어서 수행

• Node의 구조

  • 데이터를 담는 변수

  • 다음 노드를 가리키는 변수

• 연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있음.

• 연결이라는 특성 때문에 배열과 다른 장단점을 갖고 있음.

• 장점

  • 중간에 데이터를 삽입(삭제)하게 되는 경우 다음 노드의 정보만 바꿔주면 되므로 간단.

• 단점

  • 특정 인덱스의 데이터에 바로 접근이 힘듦. 첫번째 노드에서 부터 순서대로 원하는 인덱스까지 이동해야 하므로 데이터 참조는 O(n)의 성능을 가짐.

• 배열과의 비교

  • 크기

    • 배열은 고정

    • 연결리스트는 노드를 만들어 연결해주므로 동적

  • 주소

    • 배열은 연속적으로 할당

    • 연결 리스트는 불연속적인 공간에 할당

  • 데이터 참조

    • 배열은 메모리 접근이 빠름(O(1)

    • 연결리스트는 앞에서부터 해당 노드에 접근해야 하므로 느림(O(n))

  • 삽입과 삭제

    • 배열은 모든 데이터를 옮겨야해서 O(n)의 성능

    • 연결리스트는 삽입하려는 노드까지 계속 노드를 타고가야 하므로 O(n)의 성능

스택(Stack)

• First In Last Out(FIFO)

• 먼저 들어온 데이터가 마지막에, 가장 늦게 나온 데이터가 제일 앞에 있는 데이터 구조.

큐(Queue)

• First In First Out

덱(Deque)

• 덱은 데이터를 tail, head에 삽입과 삭제가 자유로운 자료 구조

해시 테이블(Hash Table)

• 해시, 맵, 해시맵, 딕셔너리로 언어마다 다른 이름을 갖고 있음.

• 장점

  • 빠른 데이터 읽기

  • 삽입, 삭제

• 단점

  • 메모리를 많이 차지함.

  • 좋은 해시 함수의 구현이 필수정

Set

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

• 해시 테이블을 사용. HashSet이라고 불리기도 함.