인프런 워밍업 클럽 3기 CS - 1주차 발자국
[강의 내용]
운영체제
폴링과 인터럽트
폴링 : CPU가 입출력 명령이 완료되었는지 주기적으로 확인하는 방식
CPU가 주기적으로 확인해줘야 하기 때문에 성능이 좋지 않음
인터럽트 : 입출력 명령이 완료되면 CPU에게 신호를 주고 CPU는 신호를 받아 인터럽트 서비스 루틴을 실행시켜 작업을 완료하는 방식
비동기적으로 동작하기 때문에 성능에 이점이 있음
인터럽트는 하드웨어 인터럽트와 소프트웨어 인터럽트가 존재
프로그램과 프로세스
프로그램 : 하드디스크에 저장되어 있는 실행파일(.exe 파일)
프로세스 : 프로그램을 실행하여 해당 프로그램이 하드디스크에서 메모리로 올려져서 실행 중인 프로그램
멀티 프로그래밍과 멀티 프로세싱
멀티 프로그래밍 : 하나의 CPU에서 여러 개의 프로세스를 메모리에 올려서 처리하는 기술
멀티 프로세싱 : 여러 개의 CPU를 이용하여 프로세스를 처리하는 기술
PCB(Process Control Block)
프로세스를 관리할 필요가 있는 정보를 포함하는 운영체제 커널의 자료구
PCB들은 연결 리스트 자료구조로 저장
프로세스 상태
생성(new) : PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태
준비(ready) : 프로세스가 CPU를 사용 위해 기다리는 상태
실행(running) : 프로세스가 CPU를 할당 받아 실행 중인 상태
대기(waiting) : 프로세스가 특정 이벤트를 기다리는 상태
완료(terminated) : 프로세스가 종료된 상태
컨텍스트 스위칭
프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업
쓰레드
프로세스 내부에 존재하는 운영체제가 실행하는 단
쓰레드는 프로세스의 PCB, 코드, 데이터, 스택, 힙을 공유
프로세스에 문제가 생기면 프로세스를 공유하는 모든 쓰레드에 문제가 발생
스케쥴링
프로세스에게 CPU를 할당/해제하는 알고리듬
어떤 프로세스에게 얼마의 시간 동안 CPU를 할당할지에 따라 스케쥴링이 결정됨
FIFO(First In First Out)
먼저 들어온 프로세스가 먼저 처리하는 방식
프로세스가 끝나지 않으면 다음 프로세스를 실행할 수 없음
SJF(Shortest Job First)
버스트 타임이 가장 짧은 프로세스를 먼저 실행하는 방식
어떤 프로세스가 얼마나 실행될지 예측할 수 없기 때문에 실제로는 구현되지 못한 스케쥴링
버스트 타임이 짧은 프로세스가 계속 들어오면 버스트 타임이 긴 프로세스는 계속 실행할 수 없는 기아 상태가 발생하게 됨
RR(Round Robin)
프로세스에게 CPU를 할당하고 일정 시간이 지나면 현재 프로세스의 CPU를 다른 프로세스에게 할당하는 방식
타임 슬라이스가 크면 먼저 들어온 프로세스를 먼저 처리하는 FIFO 스케쥴링과 같아짐
타임 슬라이스가 작으면 프로세스의 처리량보다 컨텍스트 스위칭의 처리량이 커짐
MLFQ(Multi Level Feedback Queue)
여러 개의 우선순위를 가진 큐를 사용
높은 우선순위를 가진 큐는 타임 슬라이스가 작고 낮은 우선순위를 가진 큐는 타임 슬라이스가 큼
프로세스가 스스로 CPU를 반납하면 CPU 사용이 적다는 의미로 I/O 바운드 프로세스일 가능성이 높음
프로세스가 타임 슬라이스를 오버하여 CPU를 강제로 뺏기면 CPU 사용이 많다는 의미로 CPU 바운드 프로세스일 가능성이 높음
자료구조와 알고리듬
자료구조
데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타내는 용어
가장 간단한 자료구조는 변수
변수를 어떤 규칙에 따라 생성하고 사용하는지에 따라서 배열, 스택, 큐 등의 다양한 자료구조가 됨
시간 복잡도
알고리듬의 성능을 측정하는 척도
실제 성능을 측정하지 않고 연산의 횟수를 계산하여 대략적인 성능을 측정
알고리듬에서 성능에 가장 큰 영향을 주는 연산은 반복문
표기법
빅 오(Big-O) 표기법은 함수의 상한을 표기
빅 오메가(Big-Ω) 표기법은 함수의 하한을 표기
빅 세타(Big-θ) 표기법은 함수의 평균을 표기
배열(Array)
프로그래머가 요청한 크기만큼 메모리에 연속된 공간을 할당
프로그래머가 처음 요청한 크기의 공간을 변경하기 어려움
필요한 메모리 공간의 크기를 몰라서 처음부터 많은 메모리 공간을 할당하는 경우가 많아 메모리 낭비가 심함
배열은 데이터를 탐색할 때 인덱스를 사용하여 데이터에 바로 접근할 수 있기 때문에 탐색 성능은 O(1)의 성능을 가짐
배열은 데이터를 삽입, 삭제할 때 삽입, 삭제하는 데이터의 인덱스 위치 이후에 있는 모든 데이터를 이동 시켜야 하기 때문에 삽입, 삭제 성능은 O(n)의 성능을 가짐
연결 리스트(Linked List)
각 노드가 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수로 이루어진 자료구조
다음 노드를 가리키는 변수가 있어 필요할 때 새로운 노드를 생성하여 연결해줄 수 있음
연결 리스트의 첫 번째 노드의 주소만 알고 있으면 다른 모든 노드로 접근이 가능
연결 리스트는 데이터를 탐색할 때 첫 번째 노드부터 단계적으로 탐색해야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐
연결 리스트는 새로운 노드를 삽입, 삭제할 때 노드를 탐색 후 새로운 노드를 삽입, 삭제만 하면 되기 때문에 삽입, 삭제 성능은 O(1)의 성능을 가짐
스택(Stack)
가장 최근에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 방식의 자료구조
스택은 데이터를 탐색할 때 모든 데이터를 삭제하면서 읽고 삭제한 데이터를 다시 스택에 넣어줘야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐
스택은 데이터를 삽입할 때 스택의 맨 위에 데이터를 삽입하기 때문에 삽입 성능은 O(1)의 성능을 가짐
스택은 데이터를 삭제할 때 스택의 맨 위에 있는 데이터를 삭제하기 때문에 삭제 성능은 O(1)의 성능을 가짐
큐(Queue)
가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO(First In First Out) 방식의 자료구조
큐도 스택처럼 데이터를 탐색할 때 모든 데이터를 삭제하면서 읽고 삭제한 데이터를 다시 큐에 넣어줘야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐
큐는 데이터를 삽입할 때 큐의 맨 뒤에 데이터를 삽입하기 때문에 삽입 성능은 O(1)의 성능을 가짐
큐는 데이터를 삭제할 때 큐의 맨 앞에 있는 데이터를 삭제하기 때문에 삭제 성능은 O(1)의 성능을 가짐
덱(Deque)
덱은 double-ended queue로 데이터를 head, tail 양쪽 방향에서 삽입, 삭제가 가능한 자료구조
스택과 큐의 특징을 모두 가짐
해시 테이블(Hash Table)
Key-Value를 한 쌍으로 데이터를 저장하는 자료구조
배열 안에 연결 리스트를 생성하여 같은 인덱스를 갖는 데이터를 연결하는 방식으로 데이터를 저장
해시 함수를 이용하여 Key 값을 인덱스로 변경하여 해시 테이블에 골고루 퍼지게 저장하는 것이 성능의 핵심
따라서 해시 함수의 성능이 매우 중요
해시 테이블은 데이터를 탐색할 때 Key 값만 알면 데이터에 바로 접근할 수 있기 때문에 탐색 성능은 O(1)의 성능을 가짐
해시 테이블은 데이터를 삽입, 삭제할 때 Key 값을 이용하여 데이터를 바로 삽입, 삭제하기 때문에 삽입, 삭제 성능은 O(1)의 성능을 가짐
해시 셋(Hash Set)
Key 값만 사용하여 해시 테이블에 저장하는 자료구조
Key 값이 Key이면서 Value가 됨
Key와 Value가 같기 때문에 중복된 데이터를 저장할 수 없음
1주차 강의 회고
발자국의 내용 요약을 작성할 때 진짜로 내용을 요약한 것이 아닌 알고 있는 내용을 나열한 것 같아서 다음 작성할 때는 좀 더 핵심 내용만 작성해 볼 것
다음 주에는 강의 내용 이외의 내용들을 더 세세하게 찾아보면서 강의를 학습하며 1주차의 강의를 복습해 나갈 것
[미션]
미션을 해결하는 과정
일단 미션의 내용을 보고 알고 있는 내용을 전부 작성한 후 미션의 내용과 맞는 강의 내용을 찾아보면서 미션을 해결
1주차 미션 회고
미션을 해결할 때 강의 내용을 찾아보기 전에 이미 알고 있는 내용을 좀 더 생각해서 나열해 보고 해결 방법을 찾는 것이 좋을 것 같음
답변 0