인프런 워밍업 클럽 스터디 3기 - CS 전공 지식<3월 첫째주 발자국>

1주차 학습 내용

시간복잡도란?
- "특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간"
- 주로 사용하는 측정 기법은 Big-O 이다. Big-O란 데이터가 늘어남에 따라 계산량이 얼마나 늘어나는지를 최악의 경우 기준으로 평가하는 방법이다.
- O(n) 선형시간 알고리즘이다. 데이터가 많아질수록 계산량(n)이 증가한다.
- O(1) 상수시간 알고리즘이다. 데이터의 크기와 상관없이 상수의 시간이 걸린다.

배열: 연속된 메모리에 데이터를 저장하여 인덱스 접근이 O(1)로 빠르지만, 삽입/삭제 시 성능 저하 발생.

연결 리스트: 임의의 메모리 위치에 데이터를 저장하며 삽입/삭제가 O(1)로 빠르지만, 조회 성능이 O(n)로 낮음.

스택 : 마지막에 추가된 요소가 먼저 제거됨. 후입선출

큐: 먼저 추가된 요소가 먼저 제거됨. 선입선출

덱: 양쪽에서 삽입과 삭제가 가능한 자료구조

해시테이블: 키 - 값 구조를 가지고 조회에 O(1) 성능을 가진다. 대신 메모리를 많이 차지함.

파이썬의 딕셔너리 구조를 말하는거 같다.

set: 중복되지 않는 요소의 집합. 요소의 존재 여부를 빠르게 파악

폰노이만 구조는 메모리에 프로그램을 저장하고, 버스를 통해 데이터를 전송해서 CPU에서 처리하는 방식이다.

메모리 종류

부팅 과정: 부팅할 때 BIOS가 실행되고, 하드웨어에 이상이 없는지 체크한다.

인터럽트: 인터럽트는 CPU가 작업을 잠시 멈추고, 중요한 작업을 먼저 처리하는 방식이다.

프로세스: 프로세스는 실행 중인 프로그램이다.

멀티프로그래밍: 멀티프로그래밍은 메모리 내에서 여러 개의 프로세스를 동시에 관리하는 방식이다.

멀티프로세싱: 멀티프로세싱은 여러 개의 CPU로 작업을 병렬 처리하는 방식이다.

생성 → 준비 → 실행 → (대기) → 완료

프로그램을 중복해서 실행 할 경우 프로세스의 복사도 같이 일어난다.(크롬탭10개 생성 시 프로세스도 10개 실행)

이럴 때 메모리의 부하를 막기위해 나온 것이 쓰레드다. 쓰레드는 프로세스 내에 존재하고 1개 이상이 있을 수 있다.

쓰레드는 PCB, 코드, 데이터, 힙영역을 공유한다. 단 스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있다.

FIFO (First In First Out): 먼저 들어온 순서대로 실행. 실행 시간이 긴 프로세스가 앞에 있으면 전체 대기 시간이 길어질 수 있어 현대 운영체제에서는 잘 쓰이지 않음.
SJF (Shortest Job First): 실행 시간이 짧은 순서대로 실행. 평균 대기 시간을 줄일 수 있지만, 실행 시간이 긴 프로세스는 계속 뒤로 밀려나는 스타베이션(기아) 문제가 발생할 수 있어 잘 사용되지 않음.
RR (Round Robin): 각 프로세스에 타임슬라이스(정해진 시간)를 할당해 순환하며 실행.
- 타임슬라이스가 너무 크면 여러 프로세스가 실행될 때 응답성이 떨어지고,
- 너무 작으면 컨텍스트 스위칭 비용이 증가해 성능이 저하됨.
MLFQ (Multi-Level Feedback Queue): 현대 운영체제에서 많이 사용하는 CPU 스케줄링 기법.
- 여러 개의 우선순위 큐를 사용해 CPU 실행시간에 따라 우선순위를 조정.
- CPU Bound 프로세스는 점점 낮은 우선순위 큐로 이동하며 타임슬라이스가 커짐.
- I/O Bound 프로세스는 높은 우선순위를 유지해 빠르게 실행됨.
- FIFO, SJF, RR의 장점을 조합한 방식으로, 효율적인 CPU 자원 관리를 가능하게 함.