[인프런 워밍업 클럽 스터디 3기] 1주차 발자국

1주차 학습 내용

운영체제

운영체제의 역사

50년대 이전

(출처: IBM - The punched card)

시대별 발전

• 1940s: ENIAC - 최초의 범용 컴퓨터, 펀치카드 사용

   

• 1950s: 스위치 배선작업, 배치 시스템, CPU-입출력 분리

• 1960s: 멀티프로그래밍, 파일시스템, 터미널, UNIX 등장

• 1970s: 개인용 컴퓨터, Apple/MS-DOS, GUI 도입

기본 구조

하드웨어

• 폰 노이만 구조: 메모리에 프로그램 내장

   

• 메인보드: 하드웨어 연결 허브

• CPU: 연산장치, 제어장치, 레지스터로 구성

• 메모리: RAM(휘발성), ROM(비휘발성)

운영체제

• 커널: 프로세스/메모리/저장장치 관리

• 인터페이스: CLI, GUI

주요 개념

• 부팅: ROM(BIOS) → 하드웨어 점검 → 부트로더 → OS 실행

• 인터럽트: CPU 대기 없이 입출력 처리

프로세스와 쓰레드

컨텍스트 스위칭

• 프로세스를 실행하는 중에 다른 프로세스를 실행하려고 교체하는 작업

• PCB의 내용이 변경 됨

  • 다시 이전작업으로 돌아갈 수 있도록 값을 저장해야 함!

• 입출력 요청 / 너무 오래 CPU를 점유 / 기타 인터럽트가 발생했을 때 생김

쓰레드

• 원래는 프로세스만 있었는데 작업을 처리할 때마다 프로세스를 생성하니까 성능 이슈로 인해 생겨남

• 프로세스 안에 있는 처리 단위로 프로세스의 CODE, DATA, HEAP을 공유함

   

CPU 스케줄링

운영체제가 프로세스들에게 CPU를 할당했다가 해제했다가 하는 행위

어떻게 하면 최대한 효율적으로 이를 할 수 있는지를 고민한 것이 스케줄링

스케줄링 알고리즘에는 FIFO , SJF , RR , MLFQ 등이 있고 현대에는 MLFQ 를 가장 많이 사용한다.

자료구조와 알고리즘

• 자료구조: 데이터가 어떤 구조로 저장되고 사용되는지

• 알고리즘: 어떤 문제를 해결하기 위한 확실한 방법

• 자료구조에 따라서 필요한 알고리즘도 달라지며 한가지 자료구조에 따라서도 알고리즘은 여러가지가 있을 수 있다

시간복잡도

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

실제로 시간을 재는 것이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 예측한 것

이 많은 영향을 주는 부분 == 반복문

• 빅 오메가 (Big-Ω):

  최선의 경우 (Best Case)

• 빅 오 (Big-O):

  최악의 경우 (Worst Case)

• 빅 세타 (Big-Θ):

  평균의 경우 (Average Case)

빅오를 가장 많이 사용

(출처: https://qc-at-davis.github.io/QCC/Classical-Computation/Computational-Complexity/big-O-chart.png)

• 초록색 (Excellent): O(1), O(log n) - 가장 효율적

• 연두색 (Good): O(n) - 좋은 효율성

• 노란색 (Fair): O(n log n) - 보통 효율성

• 주황색 (Bad): O(n²) - 나쁜 효율성

• 빨간색 (Horrible): O(2ⁿ), O(n!) - 최악의 효율성

자료구조

스택

First In Last Out

계속 쌓인다고 생각하면 됨 (수직으로)

연결리스트에서 무조건 첫번째 인덱스에 인서트

큐

First In First Out

먼저 줄을 선 손님이 먼저 계산 → 큐!

운영체제 프로세스의 작업요청 → 큐! (CPU가 순서대로 꺼내서 처리 → FIFO 스케줄링)

연결리스트에 head에다가 인서트

제거할때는 가장 뒤에서부터 하면됨

덱

데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조

덱을 이용하면 스택과 큐를 다 구현할 수 있음

해시테이블

Hash / Map / HashMap / Dictionary

해시함수로 테이블의 인덱스를 새로 만드니까 해시테이블

Key만 알면 Value에 O(1)의 성능으로 할 수 있음

해시함수 로직에 따라 충돌이 날 수 있음

→ 연결리스트로 구성해서 데이터들을 연결

이렇게 연결리스트로 연결되어있을때는 O(n)의 성능 (처음부터 찾아가야 하니깐)

해시함수의 성능이 매우 중요

→ 데이터들을 골고루 분산 시켜줄 수 있는 함수가 좋은 함수

셋

중복을 허용하지 않는 자료구조 / HashSet

회고

👏 칭찬하고 싶은 점

꾸준히 점심시간과 퇴근시간 이후를 사용하여 강의를 듣고 구현을 직접 해봤다.

😅 아쉬웠던 점

구현을 할 때 직접 생각보다는 따라쓰고 그 후에 이해하기 바빴던 것 같다.

🔄 보완하고 싶은 점

앞으로는 구현을 할 때는 먼저 생각해서 구현을 해보고 다음에 강의를 들으면서 확인하고 수정하는 방향으로 하면 좋을 것 같다.

🎯 다음주의 목표

• 밀리지 않고 지금처럼 강의를 듣고 정리하기

• 스스로 구현 해보면서 깨닫기