[Day 01]

Data Structure

• 자료구조란 데이터가 어떤 구조로 저장되고, 어떻게 사용되는지 나타낸 것.

• 실행 속도가 빠르고, 메모리 차지가 적으며, 유지보수가 쉬워야 좋은 자료구조.

• 시간복잡도(Time Complexity)

  • 컴퓨터 프로그램의 입력값과 연산 수행 횟수의 상관관계를 나타내는 추상적 성능 척도.

  • 알고리즘의 대략적 성능 증가/감소 경향성을 판단을 목표로 하므로 부가 사항은 배제함.

    • 배제 요소: 시스템 연산 성능 및 연산 1회당 연산량, 최고차항 외 항 등.

  • 점근적 표기법(Asymptotic Notation)

    • 함수를 단순화하여 함수의 증가율을 다른 함수와의 비교로 표현하는 방법으로, 다음 세 가지 표기법이 존재함.

    • 종류

      • Big-O Notation

        • 알고리즘의 점근적 상한(Asymptotic Upper Bound)을 표시하는 표기법.

        • "이 표기법은 최악의 경우를 고려할 때만 사용한다." -> X

          • 알고리즘 성능 평가의 목적 및 프로젝트 실행 환경에 따라 적합한 표기법을 취사 선택하는 것이 중요!

        • 무슨 일이 벌어질지 모를 현실 세계에서 가장 많이 고려되는 표기법임.

      • Big-Θ Notation

        • 알고리즘의 점근적 상한/하한(Asymptotic Tight Bound)을 동시에 표시할 수 있는 표기법.

        • 어떤 케이스에도 상한과 하한이 동일할 때 사용할 수 있음.

          • ex) 순차 탐색(Linear Search), 이진 탐색(Binary Search) 등

      • 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)(참고:

  1, 2)

• 우리가 흔히 보는 플러그 앤 플레이는 커널에 연결한 장치의 드라이버가 내장되어 있어서임.

• 컴퓨터 구조 관련

  • 대표적인 컴퓨터 설계

    • 폰 노이만 구조(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 장치의 인터럽트 신호를 받아 비동기적으로 처리할 수 있게 됨.

    • 참고1: 인터럽트 컨트롤러가 최초로 추가된 컴퓨터 UNIVAC 1103A(위키피디아, 사진).

    • 참고2: Polling vs. Interrupt in Super Mario

    • 참고3: CPU는 어떻게 작동할까?

    • 참고4: 인터럽트 서비스 루틴(ISR, Interrupt Service Routine)

[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)라고도 함.

  • 프로세스는 Code, Data, Heap, Stack 영역으로 이루어져 있음(참고: 1, 2).

  • 메모리 용량이 작던 과거엔 유니프로그래밍을 활용할 수밖에 없었는데, 이때 스와핑(Swapping)을 통해 멀티프로세싱을 간접적으로 활용했음.

    • 스와핑을 통한 멀티프로세싱은 동시에 여러 개를 처리하는 것처럼 보일 뿐이지, 멀티프로세싱이라 할 수 없지 않나?

      • 강의가 틀렸었다! 강의에서 설명한 건 멀티태스킹(Multitasking)이었다.

        • 발전 순서: 멀티프로그래밍 -> 멀티태스킹 -> 멀티프로세싱임(참고: 1, 2).

  • 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가 발생할 수 있음(

      참고: 1, 2).

  • 프로세스 생성 및 종료

    • 부팅 후 첫 프로그램 실행 시 부모 프로세스가 생성되며, 자식 프로세스는 이를 복제(fork)하여 생성됨.

      • 프로그램의 코드 영역과 데이터 영역을 메모리에 로드 -> 빈 힙과 스택 생성 -> PCB init

      • 강의에서 나온 fork()는 UNIX 계열(Linux)의 생성 방식이며, Windows 환경에서는 부모 프로세스 복사 없이 CreateProcess() 함수를 통해 독립적으로 생성함.

    • exec() 함수로 자식 프로세스의 코드/데이터 영역을 덮어씀으로써 독립된 프로세스로 동작함.

    • 부모 프로세스는 자식 프로세스가 exit() 신호를 보내기 전에는 C.S이 일어나도 CPU를 할당받지 않음.

      • 부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어(예: 부모의 조기 종료, 부모의 wait() 누락 등) 메모리에서 제거되지 않은 프로세스를 좀비 프로세스(Zombie Process)라고 함.

        • (일반적으로는) Windows 환경에선 부모와 자식이 독립적이므로, 부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어도 커널이 해당 프로세스를 완전히 제거함.

  • 쓰레드(Thread) (참고: 1, 2)

    • 프로세스 내의 단일 시퀀스 스트림(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)

    • 개요

      • 특정 프로세스에게 CPU 리소스를 할당/제거하는 OS(=스케줄러)의 역할.

      • 리소스 사용률 향상, 오버헤드 최소화, 공평성 극대화, 처리량 증대, 대기·응답시간 최소화 등을 목표로 함.

        • 모든 목표를 동시에 달성할 순 없으므로, 현대 컴퓨팅 환경에서는 OS의 지향점에 따라 여러 스케줄링 알고리즘을 바꿔가면서, 또는 복합적으로 사용함(예).

    • 프로세스 상태 전이(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는 높임.