인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <첫째 주 발자국>
[Day 01]
Data Structure
자료구조란
데이터가 어떤 구조로 저장되고, 어떻게 사용되는지 나타낸 것.실행 속도가 빠르고, 메모리 차지가 적으며, 유지보수가 쉬워야 좋은 자료구조.
시간복잡도(Time Complexity)컴퓨터 프로그램의 입력값과 연산 수행 횟수의 상관관계를 나타내는 추상적 성능 척도.
알고리즘의 대략적 성능 증가/감소 경향성을 판단을 목표로 하므로 부가 사항은 배제함.
배제 요소: 시스템 연산 성능 및 연산 1회당 연산량, 최고차항 외 항 등.
점근적 표기법(Asymptotic Notation)
함수를 단순화하여 함수의 증가율을 다른 함수와의 비교로 표현하는 방법으로, 다음 세 가지 표기법이 존재함.
종류
Big-O Notation
알고리즘의 점근적 상한(Asymptotic Upper Bound)을 표시하는 표기법.
"이 표기법은 최악의 경우를 고려할 때만 사용한다." -> X
무슨 일이 벌어질지 모를 현실 세계에서 가장 많이 고려되는 표기법임.
Big-Θ Notation
알고리즘의 점근적 상한/하한(Asymptotic Tight Bound)을 동시에 표시할 수 있는 표기법.
Big-Ω Notation
알고리즘의 점근적 하한(Asymptotic Lower Bound)을 표시하는 표기법.
현실의 문제 해결적 목적보다는 알고리즘 이론과 성능의 본질적 한계 분석 및 입증, 즉 개선 한계 분석의 중요한 근거가 된다는 데 의의가 있음. (by ChatGPT 4.5)
Algorithm
알고리즘이란
어떤 문제를 해결하기 위한 확실한 방법.데이터의 개수나 반복 횟수 등이 달라져도 같은 조건이면 동일하게 적용되는 것이 좋은 알고리즘.
Operating System
OS는 프로세스(Process), 메모리(Memory), 하드웨어(Hardware), 파일 시스템(File System)을 관리함.
겁나 비싼 CPU를 최대한 뽑아먹기(?) 위해 Single-stream Batch System -> 시분할(Time Sharing)로 발전함(참고).
응용 프로그램은 (보통의 경우) 표준 API를 통해 시스템 콜에 접근함(안전성, 편의성 Up)(참고:
우리가 흔히 보는 플러그 앤 플레이는 커널에 연결한 장치의 드라이버가 내장되어 있어서임.
컴퓨터 구조 관련
대표적인 컴퓨터 설계
폰 노이만 구조(von Neumann Architecture) (참고: 1, 2) (여담: 1, 2)
John von Neumann이 1945년에 설계한 프로그램 내장(Stored Program) 방식 컴퓨터 아키텍쳐로, 더 이상 물리 회로 변경 없이 CPU 명령어를 전환할 수 있게 됨.
von Neumann Model, Princeton Architecture라고도 함.
CPU, Bus, Memory, I/O Device로 이루어져 있음.
메모리 내부에 명령어와 데이터를 동시에 저장하므로 병목현상(Bottleneck)(=메모리 속박 문제)이 발생할 수 있음.
명령어 병렬 처리 방식(SMP, MPP 등)을 쓰거나 아예 새로운 하버드 구조로 해결 가능함.
하버드 구조(Harvard Architecture) (참고: 1, 2, 3)
폰 노이만 구조에서의 단일 Bus를 명령어용/데이터용 Bus로 물리적으로 분리하여 명령어와 데이터에 동시에 접근할 수 있도록 설계된 컴퓨터 아키텍처.
ARM9, Xscale, RISC 마이크로 프로세서, DSP 등이 여기 속함.
초기 하버드 구조는 명령어용 메모리와 데이터용 메모리를 분리했으나, MHA에서는 CPU와 RAM 사이에 캐시 메모리를 두어 병목을 개선함.
컴퓨터 발전에 따라 CPU와 I/O 장치 간 처리 속도 차가 심해졌고, 그 간극을 메우고자 CPU에 인터럽트 컨트롤러를 추가해 I/O 장치의 인터럽트 신호를 받아 비동기적으로 처리할 수 있게 됨.
참고3: CPU는 어떻게 작동할까?
[Day 02]
Data Structure
배열(Array): 메모리의 특정 크기의 연속된 공간을 미리 할당받는 자료구조.특징은?
위 내용 보고 생각해 보기!JS의 배열은 정확히는 배열이 아니라, 객체(Object)의 한 형태(idx가 키!).
Python의 List는 동적 배열(Dynamic Array)로, 새 배열 생성 없이 데이터 추가 O.
연결 리스트(Linked List): 각 노드(Node)에 각 데이터를, 불연속적인 메모리 위치에 저장하고 이들을 포인터(Pointer)로 연결한 자료구조.특징은?
위 내용 보고 생각해 보기!자료구조 구현 시 추상 자료형(Abstract Data Type) 구현 후 그걸 코드화한다고 생각하면 쉬움.
이거 완전 Pseudocode랑 비슷하지 않나?
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done)
세 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
프로그램은 수동적(=자기 코드가 실행되기를 기다림), 프로세스가 되면 능동적(=리소스를 주도적으로 활용함)임!
프로그램이 실행되어 메모리에 올라가 프로세스로 바뀌는 과정을 인스턴스화(Instantiation)라고도 함.
메모리 용량이 작던 과거엔 유니프로그래밍을 활용할 수밖에 없었는데, 이때 스와핑(Swapping)을 통해 멀티프로세싱을 간접적으로 활용했음.
OS는 멀티태스킹 처리의 안정성을 담보하기 위해 생성된 프로세스를 연결 리스트 형태인 PCB(Process Control Block)로 커널 영역(Kernel Space)에 저장함(참고: 1, 2).
프로세스 상태(Process State)
프로세스는 시분할(Time-Sharing) 처리를 위해 New(생성), Ready(준비), Waiting(대기), Running(실행), Terminated(완료) 상태를 가짐.
[Day 03]
Data Structure
스택(Stack): FILO 원칙을 따르는 자료구조로, 후입선출이기만 하면 자료 형태는 상관 없음.ex) Undo 기능, Syntax Checker, 재귀 알고리즘 등
Redo는 어떻게 구현하는 걸까? -> Undo한 작업을 Redo 스택에 저장해두었다가 다시 실행할 수 있도록 함.
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
큐(Queue): FIFO 원칙을 따르는 자료구조로, 선입선출이기만 하면 자료 형태는 상관 없음.ex) 메세지 큐(Message Queue), FIFO 스케줄링, 프린터 스풀러(Printer Spooler)
등
큐를 Linked List 기반으로 구현할 때는 양방향 연결 리스트 기반으로 구현해야 빠름!
참고: 오늘의 영어단어 - queue
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
Line 72~74를 왜 Line 56 조건에 넣지 않고 뺀 걸까? 새 노드를 테일 노드 뒤에 넣으면 무조건 새 노드를 테일로 만들어야 하는데.
여기서 답변을 주셨지만 사실 저걸 봐도 이해가 안 된다...ㅎ
변수 할당할 땐 뒤에서부터 앞으로 생각하는 게 편한 것 같다!
ex)
this.tail.next = newNode;--> newNode를 테일 다음 노드에!
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
덱(Deque): FILO / FIFO를 자유자재로 선택 가능한 자료구조로, Double-ended queue의 약자임.ex) 토마토, 웹 브라우저 히스토리, A-Steal(Job-Steal) 알고리즘 등
구현하기
첫 번째 구현: 강의 보며 구현
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
Context Switching: 프로세스 전환을 위해 프로세스 상태값 저장, 불러오기하는 것.시분할(Time-Sharing) 시스템에서 멀티태스킹을 안정적으로 수행하기 위해 필요한 필수 과정.
인터럽트 -> CPU 레지스터 PCB A에 저장 -> PCB B의 레지스터 값 CPU에 적용 -> 프로세스 B 상태 전환순서로 진행됨.Time Slice가 너무 짧아 C.S이 너무 자주 일어나면 Context Switching Overhead가 발생할 수 있음(
프로세스 생성 및 종료
부팅 후 첫 프로그램 실행 시 부모 프로세스가 생성되며, 자식 프로세스는 이를 복제(fork)하여 생성됨.
프로그램의 코드 영역과 데이터 영역을 메모리에 로드->빈 힙과 스택 생성->PCB init강의에서 나온 fork()는 UNIX 계열(Linux)의 생성 방식이며, Windows 환경에서는 부모 프로세스 복사 없이 CreateProcess() 함수를 통해 독립적으로 생성함.
exec() 함수로 자식 프로세스의 코드/데이터 영역을 덮어씀으로써 독립된 프로세스로 동작함.
부모 프로세스는 자식 프로세스가 exit() 신호를 보내기 전에는 C.S이 일어나도 CPU를 할당받지 않음.
부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어(예: 부모의 조기 종료, 부모의 wait() 누락 등) 메모리에서 제거되지 않은 프로세스를 좀비 프로세스(Zombie Process)라고 함.
(일반적으로는) Windows 환경에선 부모와 자식이 독립적이므로, 부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어도 커널이 해당 프로세스를 완전히 제거함.
프로세스 내의 단일 시퀀스 스트림(A single sequence stream)으로, 코드/데이터 영역과 힙을 공유함(스택은 독립 할당).
쓰레드에게 할당된 독립 공간은 스택도 있지만 TLS(Thread Local Storage)도 있음.
OS는 TCB(Thread Control Block) 내 각 쓰레드의 ID를 통해 각 쓰레드를 개별적으로 관리함.
메모리 소모가 적고, 쓰레드 간 통신 속도가 빠르다는 장점과 안정성이 낮다는 단점이 있음.
[Day 04]
Data Structure
해시 테이블(Hash Table): 해시 함수(Hash Function)를 통해 데이터를 Key, Value 형태로 저장하는 자료구조.해시 충돌(Hash Collision)이 나면 Chaining, Open Addressing 등을 통해 해결할 수 있음.
해시 함수를 통과한 데이터는 특정 범위에 속한 정수(=해시)로 변환하며, 이를 키(=인덱스)로 데이터를 할당함.
하지만, 해시 테이블 이외 상황에서는 해시 함수 통과 시(=해싱) 고정된 길이의 데이터로 변환됨.
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
CPU 스케줄링(CPU Scheduling)
개요
프로세스 상태 전이(Process State Transition) (참고: 1, 2, 3, 4)
승인(Admit)
인스턴스화된 프로그램, 즉 프로세스가 New 상태에서 Ready 상태로 전환되는 것.
빈 Code, Data, Heap, Stack 영역과 Thread 1개, 그리고 PCB가 생성되어 커널에 저장됨.
디스패칭(Dispatching)
Ready 상태 프로세스의 PCB가 Ready Queue에 있다가 우선순위에 따라 CPU 스케줄러(=OS)에 의해 실행 상태로 전환되는 것.
Deadlock Avoidence의 은행원 알고리즘(Banker's Algorithm)이 여기서 작동함(Day 07 참고).
깨우기(Wake-up)
Waiting 상태의 프로세스가 Ready 상태가 되고, 해당 PCB도 커널의 Ready Queue로 이동함.
Device Queue 내 I/O 작업 종류별로 우선순위가 결정됨.
대표적인 CPU 스케줄링 알고리즘
FIFO Scheduling (※ FCFS(First Comes, First Served) Algorithm이라고도 함)
스케줄링 큐에 들어온 순서대로(FIFO), 프로세스를 하나씩 실행하는 최악의 알고리즘.
프로세스 간 우선순위에 따라(Burst Time이 긴 게 먼저 vs. 짧은 게 먼저) 평균 대기 시간 차이가 확 남.
FIFO Scheduling은 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling)에 해당하므로,
Convoy Effect(호위 효과)가 발생할 수 있음.
[Day 05]
Data Structure
셋(Set): 데이터의 중복을 허용하지 않는 자료구조.구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
SJF(Shortest Job First) Scheduling: Burst Time이 짧은 프로세스를 우선 실행하는 알고리즘.각 프로세스의 Burst Time 예측 불가능성, Burst Time이 긴 프로세스는 영영 실행되지 못할 수도 있는 점(=Starvation) 때문에 RR로 빠르게 대체됨.
RR(Round Robin): FIFO 스케줄링에 Time Slice(Time Quantum)를 추가한 알고리즘.FIFO랑 다름 없거나, C.S에 의한 오버헤드가 너무 크지 않도록 최적의 TS(TQ)를 찾는 것이 매우 중요함!
참고: Scheduling Algorithms - Round Robin Scheduling
MLFQ(Multi Level Feedback Queue): 프로세스마다 최적의 TS(TQ)를 할당해 최적의 리소스 사용률 및 응답 속도를 보장하는 알고리즘.인터럽트가 일어난 프로세스의 TS는 낮추고, 스케줄링이 일어난 프로세스의 TS는 높임.
답변 0