[인프런 워밍업클럽 CS 2기] 1주차 발자국
1주차 학습 내용
'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2
'그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4)
'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2
Section 1. 개요
자료구조와 알고리즘이란?
자료구조
데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄(ex, 변수, 배열)
자료구조에 따라 처리 방법이 달라짐, 코드가 달라질 수 있음
알고리즘
어떤 문제를 해결하기 위한 확실한 방법
한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있음 (ex, 표현방법에 따라) → 더 좋은 알고리즘을 사용
시간 복잡도
더 좋은 알고리즘이란?
메모리 사용이 적은 것, 속도가 더 빠른 것 등 사용자에 따라 달라짐
일반적으로 알고리즘의 속도를 성능의 척도로 사용 → 시간복잡도
시간 복잡도란, 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말함
그러나 사용자마다 컴퓨터 사양이 다르기 때문에 시간을 측정하는 방식이 아닌, 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측함 → 반복문을 보고 성능 평가함
표현 방법
Big-Ω : 최선의 경우 한 번에 찾음
Big-O : 최악의 경우 배열의 길이만큼 걸림
Big-Θ : 평균의 경우 배열의 길이 중간 만큼 걸림
Section 2. 자료구조
배열
일반적으로 배열은 생성하게 되면 운영체제에서 배열의 크기만큼 메모리를 잡게 됨
운영체제는 배열의 시작 주소만 기억하고, 배열의 index에 따라 한번에 접근하게됨
배열의 참조 성능은 좋지만, 데이터의 삽입, 삭제 성능은 좋지 않음
데이터 삽입 시 → 초기에 잡은 메모리 크기보다 큰 크기가 필요할 때, 그만큼의 연속된 메모리 공간을 또다시 찾아야 함. 또 기존 데이터를 복사도 해줘야 함.
데이터 삭제 시 → 공간 낭비됨
자바스크립트는 다른 프로그래밍 언어와 달리 배열이 연결리스트 형태로 되어 있어서 배열 생성 시 메모리가 연속적으로 있어야하는 단점을 해결함
연결리스트
저장하려는 데이터들을 메모리 공간에 분산해 할당하고, 이 데이터들을 서로 연결해줌 → Node를 만들어서 사용
Node의 구조
데이터를 담는 변수
다음 노드를 가리키는 변수
장점
빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야 하는 단점이 없음
중간에 데이터 삽입 시, 연속된 공간 확보 필요 없이 앞, 뒤 노드의 다음을 가리키는 노드만 바꿔주면 됨
단점
기존 배열은 시작 주소만 알면 index에 따른 데이터의 접근이 쉽지만(O(1)), 연결리스트는 연결된 노드를 따라 접근해야함(O(n))
스택(Stack)
FILO(First In Last Out)
데이터 삽입을 무조건 첫 번째 인덱스에 하고, 삭제 또한 첫번째 인덱스에서 함
일상생활 예시
엘리베이터 - 일찍타는 사람이 늦게 내리게 됨
포토샵 - 작업 되돌리기 작업
문법 에러 체크 시
큐(Queue)
First In First Out
데이터 삽입을 첫 번째 인덱스에 하고, 삭제는 뒤에서부터 제거 함
문제점
기존 연결리스트에서 구현한 구조로는 맨 뒤의 인덱스에 접근을 하기 위해 O(n) 성능이 나옴.
따라서 맨 뒤 인덱스를 가리키는 tail을 만들고, 노드에 이전 노드를 가리키는 변수를 추가해서 이중연결리스트를 만듦.
O(1)의 성능으로 삭제를 할 수 있게 함
일상생활 예시
마트에서 줄 순서대로 계산
운영체제 프로세스 처리 (FIFO 스케줄링)
맛집, 놀이공원 줄
덱(Deque)
데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있는 자료구조
특성에 따라 스택과 큐 모두 구현할 수 있음
해시테이블(Hash)
프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리라고도 불림
배열의 공간 낭비를 줄이기 위해 어떤 계산을 거쳐 특정 공간 인덱스에 데이터를 저장하는 방법을 사용 → 어떤 계산 - 해시 함수 (ex, 선수 등번호 % 10)
해시 함수에서의 충돌을 해결하기 위해 인덱스를 연결리스트로 구성해 데이터들을 연결함
좋은 해시 함수는 데이터를 골고루 분배시켜주는 함수
장점
빠른 데이터 읽기, 삽입, 삭제 가능
단점
메모리를 많이 차지함
해시 함수에 따라 메모리를 많이 차지할 수도 아닐 수도 있음
셋(Set)
데이터의 중복을 허용하지 않는 자료구조
해시테이블을 사용해 Hash Set이라고 불리기도 함
테이블의 value값은 사용하지 않고, key만 사용해서 구현함
'그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4)
Section 1. 운영체제 들어가기
운영체제 개요
운영체제들
개인용 컴퓨터 - Windows, MacOS
대형 컴퓨터, 서버용 - 유닉스, 리눅스
스마트폰, 테블릿 - iOS, Android
스마트워치, 세탁기, 냉장고 - 임베디드 운영체제
컴퓨터는 운영체제가 있어야 하는가?
No, 그러나 원래 설계된대로만 쓸 수 있기에 기능을 추가할 수 있음 (ex, 예전 유선 전화기 vs 스마트폰)
운영체제가 하는 일
프로세스 관리 : 하나의 프로그램이 CPU를 독차지 하지 않고, 여러프로그램이 동시에 실행될 수 있도록 함
메모리 관리 : 여러 프로그램을 메모리에서 관리함
하드웨어를 관리 : 사용자의 하드웨어에 대한 직접적인 접근을 막음
파일 시스템 관리 : 하드디스크에 많은 파일들의 효율적인 저장과 관리를 함
운영체제 역사
비싼 CPU를 더 많이 사용하려고 고민했었고, 오퍼레이터와 프로그래머 사이의 낭비되는 시간을 줄이려함
→ CPU 사용률과 비용절감을 위한 노력으로 오늘날의 운영체제가 탄생함연도별 운영체제 발전
애니악 출현 (1940년대)
펜실베니아 대학교에서 미사일 탄도계산을 위해 개발된 컴퓨터 (세계에서 가장 큰 스케일의 전자디지털 계산기)
스위치와 배선을 사람이 직접 연결함
하드웨어의 비용이 비싸기 때문에 CPU를 최대한 많이 사용할 수 있는 방법에 대해 연구하게 됨
직접회로(IC) 개발 (1950년도)
진공관과 전선으로 만들어진 논리회로를 아주 작은 크기로 만듦 → 현대적인 컴퓨터의 모습
CPU, 메모리는 있지만, 키보드와 마우스는 없음 → 프로그래머가 펀치 카드에 구멍을 뚫어서 프로그래밍을 함
오퍼레이터가 직접 컴퓨터에 카드를 넣고 결과가 나오면 프로그래머에게 전달함
싱글스트림 배치시스템 (1950년대 중후반)
오퍼레이터 오버헤드가 커서 이를 해결하기 위해 프로그래머가 여러개의 펀치카드를 전달하고, 이를 CPU가 순서대로 처리해서 결과도 한번에 확인할 수 있도록 개발함 → CPU 사용률이 올라감
I/O 디바이스 컨트롤러 개발(인터럽트) - 입출력 중에도 CPU가 계산할 수 있도록 만들어서 CPU 사용률을 더욱 높임
그러나 입력의 경우 어쩔 수 없이 입력이 끝날 때까지 기다려야하기 때문에 CPU 사용률이 떨어지게 됨 → 싱글스트림 배치시스템 한계점
시분할 시스템 (1960년대)
메모리에 여러 프로그램을 올려놓고 시간을 나누어서 빠르게 돌아가며 실행시킴 → CPU 사용률 증가
컴퓨터가 비싸기에 사용자가 여러개의 터미널을 두고 하나의 컴퓨터에 접근해서 사용 → 여러 사용자가 각자의 프로그램을 각각 사용 가능하게 됨 → 개인 컴퓨터같아져서 개인 파일을 저장하게 되면서 파일 시스템 개념이 생겨남 (AT&T 벨 연구소 - UNIX)
문제점 생김
메모리에 여러 프로그램이 올라와서 작업을 실행함에 따라 메모리 침범 이슈 생김
여러 프로그램이 실행됨에 따라 프로그램의 메모리 위치가 변동됨 → 하드웨어적으로 베이스 레지스터를 추가하게 됨
개인용 컴퓨터의 시대 (1970년대)
애플 매킨토시(GUI 사용), 마이크로소프트 MS-DOS
운영체제 구조
커널
프로세스, 메모리, 저장장치를 관리함
사용자는 커널에 직접 접근할 수 없고, 인터페이스를 통해 접근 가능함
인터페이스는 GUI, CLI가 있음
어플리케이션은 시스템 콜을 이용해서 커널에 접근 가능 → 시스템 콜을 통해 안전하게 하드디스크 빈공간에 데이터를 저장하게 됨
하드웨어는 드라이버를 이용해서 커널에 접근 가능 → 그래픽카드나 타블렛 같은 복잡한 장치들은 디바이스 드라이버를 설채해서 사용해야함
컴퓨터 하드웨어와 구조
폰 노이만 구조 - 프로그램 내장 방식 (프로그램을 메모리에 내장함)
애니악 시절 사람이 직접 스위치와 배선을 매번 조정하던 불편함을 해결하기 위해 CPU와 메모리 사이를 버스로 연결하는 방법으로 데이터를 전달하도록 함
메모리에 올라간 프로그램은 명령에 따라 처리되고, 소프트웨어만 바꿔주면 됨
오늘날의 컴퓨터 하드웨어
메인보드 - 다른 하드웨어 연결하는 장치
CPU, 메모리, 하드디스크, 그래픽카드, 모니터, 마우스, 키보드, 스피커 등 연결
CPU(Central Processing Unit)
산술논리 연산장치, 제어 장치, 레지스터로 구성
메모리
RAM(Random Access Memory), ROM(Read Only Memory)로 구성
RAM
랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음
전력이 끊기면 데이터를 잃어버림
메인메모리로 사용됨
ROM
전력이 끊겨도 데이터를 계속 보관할 수 있음
데이터를 한 번 쓰면 수정 불가능 → 따라서 컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임
컴퓨터의 부팅과정
전원 켬 → 바이오스 실행 (주요 하드웨어에 이상 여부 체크) → 이상 없을 시, 하드디스크의 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행 → 운영체제 선택 → 컴퓨터 바탕화면 보임 → 실행되는 모든 프로그램은 메모리에 올라와서 운영체제가 관리함
인터럽트
CPU 관점에서 입출력 완료 여부를 알 수 없기에 주기적으로 계속 체크함(Polling 방식) → 주기적으로 CPU가 체크해야하기 때문에 성능이 좋지 않음
인터럽트
Polling 방식의 단점을 해결한 방식
입출력 관리자가 입출력이 완료되었을 때 CPU에게 신호를 주고, CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료 함
인터럽트 서비스 루틴(ISR) - 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수
인터럽트는 비동기적으로 동작하기 때문에 성능에 이점이 있음
인터럽트 방식
하드웨어 방식 - ex, 입출력
소프트웨어 방식 - ex, 사용자 프로그램에서 발생한 인터럽트 (유효하지 않은 메모리 접근, 0으로 나누는 명령어)
Section 2. 프로세스와 쓰레드
프로그램과 프로세스
프로그램
하드디스크등과 같은 저장장치에 저장된 명령문의 집합체 (ex, 앱, .exe파일 등)
컴퓨터 관점에서 저장장치만 사용하는 수동적인 존재
프로세스
실행중인 프로그램
하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행중인 프로그램 → 프로세스라고 불림
컴퓨터 관점에서 메모리, 운영체제의 CPU스케줄링 알고리즘에 따라 CPU 사용, 필요에 따라 입출력도 하기에 능동적인 존재
프로세스의 구조
Code, Data, Heap, Stack으로 나눠짐
Code - 자신을 실행하는 코드 저장
Data - 전역 변수, Static 변수 저장
Stack - 지역 변수, 함수 호출 시 필요한 정보들이 저장
Heap - 프로그래머가 동적으로 메모리를 할당하는 데 쓰임
코드가 프로세스가 되는 과정
코드(ex, C언어) → test.c → 전처리기 → test.i → 컴파일러 → test.s → 어셈블러 → test.o → 링커 → test.exe → 메모리에 올라감 → 프로세스(운영체제에 의해 관리됨)
멀티프로그래밍과 멀티프로세싱
유니프로그래밍 - 메모리에 오직 하나의 프로세스가 올라온 것(메모리 관점)
멀티프로그래밍 - 메모리에 여러개의 프로세스가 올라온 것(메모리 관점)
멀티프로세싱 - CPU가 여러개의 프로세스를 처리하는 것(CPU의 관점)
오늘날의 OS는 멀티프로그래밍과 멀티프로세싱이 공존함
예전에는 메모리의의 크기가 작았기 때문에 유니프로그래밍으로 멀티프로세싱 기법(메모리, 저장장치 데이터 스와핑)을 사용함
PCB(Process Control Block)
프로세스 생성 시, 프로세스의 정보를 가지고 있는 PCB를 만들고 저장함
PCB들은 연결리스트로 저장됨
운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거함
PCB 구조
포인터 - 부모와 자식 프로세스에 대한 포인터, 할당된 자원에 대한 포인터, 프로세스의 한 상태에서 다른 상태로 전환될 때 저장하는 포인터 가짐
프로세스 상태 - 생성, 준비, 실행, 대기, 완료 나타냄
프로세스 ID - 프로세스를 식별하기 위한 숫자 저장
프로그램 카운터 - 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장(시분할처리로 여러 프로세스를 번갈아 실행시키기에 필요하게 됨)
레지스터 정보 - 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨(프로그램 카운터와 마찬가지로 시분할처리에 필요)
메모리 관련 정보 - 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기위한 경계레지스터 값 등 저장
CPU 스케줄링 정보 - CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장
프로세스 상태
프로세스는 시분할 처리를 위한 다섯가지 상태를 가짐 : 생성, 준비, 실행, 대기, 완료
생성 상태(New)
PCB를 생성하고, 메모리에 프로그램 적재를 요청한 상태
준비 상태(Ready)
메모리에 프로그램 적재를 승인받으면 넘어오게 됨
CPU를 사용하기위해 기다리고 있는 상태
CPU스케줄러에 의해 CPU가 할당됨
실행 상태(Running)
준비상태에 있는 프로세스가 CPU스케줄러에 의해 CPU를 할당받아 실행되는 상태
실행상태에 있는 프로세스의 수는 CPU의 개수만큼임
부여된 시간만큼 CPU 사용 가능 → 시간이 초과되면 다시 준비상태로 돌아감
대기 상태(Waiting)
프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태
완료 상태(Terminated)
프로세스가 종료된 상태
프로세스가 사용했던 데이터를 메모리에서 제거하고, 생성된 PCB도 제거함
컨텍스트 스위칭(Context Switching)
프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업
PCB의 내용이 변경됨 - 실행중인 프로세스의 작업내용을 PCB에 저장하고, 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨
컨텍스트 스위칭이 일어날 때, 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됨
컨텍스트 스위칭이 발생하는 이유
CPU 점유시간이 다 됨
I/O 요청이 있음
다른 종류의 인터럽트가 있을 때
프로세스 생성과 종료
프로세스 생성 방법
.exe 파일 실행 → 운영체제가 코드영역, 데이터영역을 메모리에 로드 → 빈 스택, 빈 힙을 만들어 공간 확보 → PCB 생성 및 값 초기화 (운영체제 부팅 후 0번 프로세스가 생성될 때 한 번 실행됨) → 부모 프로세스
나머지 프로세스는 0번 프로세스를 복사하게 됨 (fork() 함수 이용) → 새로 생성하는 것보다 복사가 빠르기 때문 → 자식 프로세스
자식 프로세스는 부모 프로세스의 코드, 데이터, 스택, PCB 내용 모두 복사함
fork() → exex() 실행 시, 자식 프로세스의 코드, 데이터 영역을 원하는 값으로 덮어쓰게 됨 → 부모 프로세스와 다르게 동작함
exit() → 자식 프로세스가 부모 프로세스에게 정상 종료를 알림 → 부모 프로세스가 자식 프로세스를 정리함
좀비 프로세스 - 부모 프로세스가 먼저 종료되거나, 자식 프로세스가 exit()를 주지못해서 메모리에 계속 살아있는 상태
쓰레드
프로세스가 많아지면 PCB, 코드, 데이터, 스택, 힙영역도 만들어줘야하기 때문에 무거워짐 → 메모리 많이 차지함 → 쓰레드 고안
쓰레드는 프로세스 내에 존재하는 것으로, 1개 이상 있을 수 있음
PCB, 코드, 데이터, 힙영역을 공유함
스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음
쓰레드를 구분하기 위한 쓰레드ID, TCB(Thread Control Block) 생성
프로세스, 쓰레드 장단점
안정성 - 프로세스는 독립되어 있기에 다른 프로세스 문제에 영향을 받지 않음, 프로세스는 영향을 받음
속도, 자원 - 프로세스는 각자 코드, 데이터, 힙, 스택을 가지고 있고 프로세스간 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림, 프로세스는 스택영역을 제외한 영역은 모두 공유하기 때문에 오버헤드가 작음. 그러나 공유되는 공간에서 문제가 생길 수도 있음
Section 3. CPU 스케줄링 - (Unit 1~4)
CPU스케줄링 개요
컴퓨터 자원
필수 장치 - CPU, 메모리
주변 장치 - HDD, 키보드, 마우스
CPU스케줄링
운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것
CPU가 스케줄링에서 고려할 사항
어떤 프로세스에게 CPU 리소스를 줄 것인가?
CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?
CPU Burst
CPU를 할당받아 실행하는 작업
I/O Burst
입출력 작업
다중큐
프로세스 상태에서 준비상태, 대기상태는 큐(Queue)라는 자료구조로 관리됨
실행 → 준비 상태가 될 때, 운영체제는 그에 맞는 준비 큐에 넣음
실행 → 대기 상태가 될 때, I/O 작업 종류에 따라서 분류된 큐에 들어가게 됨 (ex, 하드디스크 작업 → HDD 큐)
정확히는 프로세스 정보를 가지고 있는 PCB가 들어가게 됨
스케줄링 목표
리소스 사용률
CPU 사용률 높이기, I/O 디바이스의 사용률 높이기 등등
오버헤드 최소화
스케줄링을 하기 위한 계산이 너무 복잡해지거나, 컨텍스트 스위칭을 너무 자주하지 않도록
공평성
모든 프로세스에게 공평하게 CPU가 할당되어야 함
공평의 의미는 시스템에 따라 달라질 수 있음
처리량
같은 시간 내에 더 많은 처리를 할 수 있는 방법
대기 시간
작업을 요청하고 실제 작업이 이루어지기 전까지 대기 시간이 짧은 것을 목표로 함
응답 시간
대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하기 때문에 응답시간이 짧은 것을 목표로 함
목표간에 서로 상반되는 상황이 있는데, 이 때는 사용자가 사용하는 시스템에 따라 목표를 다르게 설정하게 됨 (ex, 터치스크린 → 응답시간 짧도록, 과학 계산 → 처리량이 높도록 초점 맞춤)
FIFO(First In First Out)
스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식
먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음
장점
단순하고 직관적
단점
한 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함
I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됨
스케줄링의 성능 → 평균 대기 시간으로 평가함
프로세스의 실행 순서만 바꿔도 평균 대기 시간의 차이가 많이 남
FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고, 일괄처리시스템에 쓰임
회고
일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점
칭찬하고 싶은 점 : 바쁜 일정 중에도 이번주 범위를 전체적으로 두 번 반복해서 강의를 들으면서 놓친 부분은 없는지 확인했던 점입니다.
아쉬웠던 점 : 강의를 듣고 잘 이해했다고 생각했는데, 내 스타일로 아직 명확하게 정리가 되지 않아서 미션 수행 시 조금 당황했던 점입니다.
보완하고 싶은 점 : 강의를 듣고 강의 내용에 대해 머릿속으로 정리해보는 시간을 좀 더 가지면 좋을 것 같습니다.
다음주에는 어떤 식으로 학습하겠다는 스스로의 목표
다음주에는 오늘 범위의 강의를 듣기 전에 어제 범위의 강의를 머릿속으로 다시 생각하고 정리하는 시간을 갖겠습니다.
댓글을 작성해보세요.