인프런 워밍업 클럽 - CS Day 3
그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)
Array
배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다. → O(1)의 성능을 갖는다.
삽입, 삭제의 성능이 좋지 않다. → 데이터를 추가, 제거하려면 내부적으로 필요한 단계가 많다.
데이터 추가, 제거 시 내부적으로 수행해야 하는 단계
연속된 메모리 할당
배열은 메모리상에 연속적으로 저장되어 있다.
→ 중간에 요소를 삽입하거나 삭제할 때 문제가 발생
요소 이동 필요
배열의 중간에 새로운 요소를 삽입하거나 기존 요소를 삭제할 경우, 해당 위치 이후의 모든 요소들을 이동시켜야 한다.
→ 오버헤드가 발생한다.
고정된 크기
정적 배열의 경우 크기가 고정되어 있어, 삽입 시 공간이 부족하면 새로운 더 큰 배열을 생성하고 모든 요소를 복사해야 한다.
삽입/삭제 위치에 따른 성능 차이
배열의 끝에서 삽입/삭제하는 경우는 O(1)로 빠르지만, 최악의 경우(배열의 시작 부분에서 삽입/삭제) O(n)의 시간이 소요된다.
메모리 재할당
동적 배열의 경우, 크기를 늘릴 때 새로운 메모리 공간을 할당하고 기존 데이터를 복사해야 하므로 추가적인 시간이 소요된다.
JS의 Array
상황에 따라서 연속적, 불연속적으로 메모리를 할당한다.
일반적으로 불연속적으로 할당한다.
불연속적으로 할당된 메모리는 내부적으로 연결해서 사용자에게는 배열처럼 느껴진다.
Linked List
배열의 단점인 삽입, 삭제의 성능을 보완하기 위한 자료구조
저장하려는 데이터들을 메모리(힙 영역)에 분산하여 할당하고, 해당 데이터를 서로 연결한다.
노드를 사용하여 데이터들을 저장하고, 각 노드가 다음 노드를 가리키도록 한다.
첫 노드의 주소만 알고 있으면 그 이후의 모든 노드에 접근할 수 있다.
장점
데이터 추가 및 삭제
빈 메모리 공간 아무 곳에 데이터를 생성하고, 연결만 해주면 데이터 추가가 완료된다.
중간에 데이터가 삽입/삭제 된다고 한다면 배열은 해당 데이터 이후의 모든 데이터들을 이동시켜야 하지만 연결리스트는 해당 데이터와 그 이전, 이후의 데이터만 수정하면 된다.
단점
특정 데이터를 찾고 싶다면 노드를 순회해야 한다. → O(n)의 성능을 갖는다.
Array vs Linked List
데이터의 참조가 많은 경우 ⇒ Array 사용
데이터의 삽입과 삭제가 많은 경우 ⇒ Linked List 사용
추상 자료형(ADT, Abstract Data Type)
어떠한 데이터와 그 데이터에 대한 연산을 표기하는 방법
→ 데이터의 논리적인 동작을 정의한다.구현 방법을 명시하지 않고, 자료구조의 특성과 연산만을 설명한다.
데이터의 타입과 해당 타입에 수행할 수 있는 연산들만을 정의한다.
내부 구현 세부사항은 숨기고 인터페이스만을 제공한다.
Linked List의 ADT
모든 데이터 출력 → printAll()
모든 데이터 제거 → clear()
인덱스 삽입 → insertAt(index, data)
마지막 위치에 데이터 삽입 → insertLast(data)
원하는 인덱스의 데이터 삭제 → deleteAt(index)
마지막 데이터 삭제 → deleteLast()
특정 인덱스 데이터 읽기 → getNodeAt(index)
그림으로 쉽게 배우는 운영체제
Program(= Application, App)
저장장치에 저장된 명령문의 집합체
Windows에서는
.exe의 형식저장 장치만 사용하는 수동적인 존재
Process
실행중인 프로그램
저장장치에 저장된 프로그램이 메모리에 올라갔을 때 프로세스라고 한다.
메모리, CPU, I/O 작업을 수행하는 능동적인 존재
구조
Code
자신을 실행하는 코드가 저장되어 있는 영역
Data
전역 변수와 Static 변수가 저장되어 있는 영역
Stack
지역 변수와 함추 호출을 했을 때 필요한 정보들이 저장되는 영역
함수 호출시 매개변수와 돌아갈 주소가 저장된다.
Heap
프로그래머가 동적으로 메모리를 할당하는 데 사용되는 영역
→ 프로그래머가 런타임시 할당할 수 있는 메모리 공간
Program → Process가 되는 과정(C 언어 기준)
전처리기를 거쳐서 매크로로 정의한 숫자를 치환하고 필요한 파일을 불러온다.
전처리기를 거치면 파일의 확장자는
.i가 된다.컴파일러가 컴파일 수행
고수준인 C언어를 저수준인 Assembly어로 치환해준다.
파일의 확장자는
.s가 된다.어셈블러가 어셈블리어를 기계어로 치환한다.
파일의 확장자는
.o가 된다.링커가 링킹을 수행하여 여러 가지 라이브러리나 다른 소스 코드를 연결한다.
파일의 확장자는
.exe가 된다.저장장치에 저장된
.exe파일을 실행하면 메모리에 올라가게 된다.
→ 프로세스가 된다.프로세스는 운영체제에 의해 관리된다.
Uni-Programming
메모리에 오직 하나의 프로세스가 올라온 상태
메모리 관점으로 정의
Multi-Programming
메모리에 여러개의 프로세스가 올라온 상태
메모리 관점으로 정의
Multi-Processing
CPU 관점으로 정의
CPU가 여러 개의 프로세스를 처리하는 것을 의미한다.
Swapping
메모리에 있는 데이터를 다른 저장장치로 보내고 다른 저장장치에서 데이터를 메모리로 올리는 방법
PCB(Process Control Block)
프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장한다.
PCB들은 연결리스트라는 자료구조로 저장된다.
OS는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.
구조
Pointer
부모와 자식 프로세스에 대한 포인터
할당된 자원에 대한 포인터
프로세스의 한 상태에서 다른 상태로 전환될때 저장하는 포인터
Process Status
현재 프로세스의 5가지 상태를 의미
생성, 준비, 실행, 대기, 완료
Process ID : 프로세스를 식별하기 위한 숫자
Program Counter
다음에 실행될 명령어의 주소를 포함한다.
특정 프로세스가 CPU를 사용하다가 다른 프로세스에게 CPU를 반납하고 다시 CPU를 사용할 때 이전 상태의 명령어가 실행되어야 하기 때문에 반드시 필요하다.
Register Info
프로세스가 실행될 때 사용했던 레지스터의 정보
PC와 마찬가지로 CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도로 사용
Memory Info
프로세스가 메모리에 있는 위치 정보
경계 레지스터 값이 저장
CPU Scheduling Info
CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간등이 저장된다.
Process Status
시분할 처리를 위한 5가지 상태값
New(생성)
PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태
메모리에 프로그램 적재를 승인받으면 준비상태로 넘어간다.
Ready(준비)
CPU를 사용하기 위해 대기하고 있는 상태
CPU 스케줄러에 의해 CPU가 할당된다.
Waiting(대기)
프로세스가 I/O 요청을 하면, I/O가 완료될때까지 기다리는 상태
I/O 작업은 무거운 작업이기 때문에 I/O 작업이 완료될 때까지 CPU를 놀리는 것은 비효율적
→ I/O 요청을 한 프로세스는 I/O 작업이 완료될 때까지 대기 상태로 두고 다른 프로세스에게 CPU를 할당한다.
→ I/O 작업이 완료되면 대기 상태에 있던 프로세스에게 CPU 할당 기회를 준다.
Running(실행)
준비상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 부여된 시간만큼 할당받아 실행되는 상태
실행상태에 있는 프로세스의 수는 CPU의 개수이다.
부여된 시간이 종료되면 CPU 스케줄러가 강제로 CPU를 빼앗는다.
→ 준비 상태로 돌아간다.
Terminated(완료)
프로세스가 종료된 상태
프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거한다.
댓글을 작성해보세요.
