[워밍업클럽3기] CS전공지식 1주차
그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)Section01. 개요자료구조var (variable, 변수)arr (Array, 배열)index를 이용하여 해당 data에 접근함자료 구조에 따라 배열을 사용하는 것이 편할 수 있음. Algorithm.확실한 방법을 의미함시키는대로 했을 때 답이 나와야함.모호한 방법은 안됨자료구조에 따라 알고리즘이 달라짐특정 자료구조 =/= 하나의 알고리즘시간복잡도더 좋은 알고리즘이란?사용자의 니즈에 따라 다름depend on the memory size, speed or both일반적으로 알고리즘 속도 = 성능속도 = 시간 복잡도시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간사용자마다 컴퓨터 사양이 다르기 때문에 실행시간이 무조건 같지는 않음.알고리즘의 평가는 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 것임.코드에서 성능에 많은 영향을 주는 부분 = 반복문빅오 표기법 빅오 표기법이 성능을 정확하게 표현하지 못하는 이유: 단순히 해당알고리즘의 입력이 늘어날 때, 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문O(n) : 선형시간 알고리즘O(1): 상수시간 알고리즘O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)계산에 가장 많이 영향을 미치는 차수만 표시함Section02. 자료구조배열 [array]기본적으로 제공하는 자료구조일반적인 배열: 선언시 배열의 크기를 알려줌읽기/쓰기/참조에서 좋은 성능을 보임삽입/ 삭제에서 좋지 않은 성능을 보임이유: 이미 연속된 메모리공간을 선언하였기 때문에 배열의 끝에 새로운 메모리로의 추가가 어렵기 때문에 새로운 사이즈의 배열을 추가할 수 있는 메모리를 찾아야함. (삭제도 같은 이유)배열을 너무 크게할경우, 일시적으로 해결 되는 것처럼 보이지만, 결국 제한적이고 배열의 크기와 메모리의 크기가 비례하기 때문에, 너무 큰 배열은 너무 많은 메모리를 차지하게됨.연결리스트 [linked list]배열의 단점을 해결해줌연결은 노드를 이용함node는 data의 위치 + next node number위와 같은 이유로 node = linked list장점열의 초기 크기를 알아야하는 단점이 없음.삽입과 삭제가 용의함단점데이터들이 떨어져 있어서(노드번호에 따라 위치가 다름) 특정 순서의 데이터로 바로 갈 수 없음.각 노드의 다음노드를 무조건 알아야 하기때문에 O(n)의 성능을 가짐.array의 성능은 O(1)데이터의 참조가 많이 일어나는 경우에는 배열이,데이터의 삽입과 삭제가 많이 일어나는 경우에는 연결리스트가 도움이 됨.스택(Stack)Stack의 사전적의미: 더미, 무더기 인것처럼 무작정 쌓는 개념FILO(First in Last Out)그냥 물건 쌓아두는 개념선입선출과 반대됨 큐(Queue)FIFO (First In First Out)선입선출의 개념임질서를 위해 서는 줄head에 삽입, 제거연결리스트로 구현함.O(n)의 성능이 나옴그렇기 때문에 head는 가장 앞의 노드, tail은 가장 뒤의 노드로 tail 변수추가로 O(1)의 성능이 나오게함일반 연결리스트 아닌 이중 연결리스트 사용. (양방향 연결리스트임)tail의 이전노드를 할당함.enqueue : insert datadequeue : delete datafront : 데이터 참조isEmpty : 비어있는가 확인스택은 위로 쌓아 올려서 위에서 꺼내는 느낌이면큐의 경우 왼쪽에서 데이터 넣고 오른쪽에서 데이터 빼내는 느낌?덱(Deque)삽입과 제거를 head와 tail모두에서 가능하기 때문에 스텍과 큐의 형태 모두 구현가능추상자료형printAll: 모든 데이터 출력addFirst: head에 데이터 삽입removeFirst: head에서 데이터 제거addLast: tail에 데이터 삽입removeLast: tail에서 데이터 제거isEmpty: 리스트가 비어있는지 확인해시테이블(hash Table)해시테이블 (hash table)hash, map, hashmap, dictionary라고도 불림표를 저장하는 가장쉬운방법 = array에 저장index로 접근하다보니 빈공간이 많아지고, 낭비되는 공간이있음메모리 절약을 위해 어떠한 계산을 거쳐 인덱스로 치환함: 어떠한 계산이 해시함수임삽입, 수정, 삭제까지 O(1)의 성능을 가짐문제: 충돌이 발생하기도함해당인덱스를 연결리스트로 구현해 저장함: O(n)의 성능을 가짐이렇기 때문에 해시테이블은 해시함수의 선정이 매우 중요함.장점: 빠른 데이터 읽기, 삽입, 삭제단점: 메모리를 많이 차지함.셋(Set)데이터의 중복을 허용하지 않는 자료구조해시테이블을 이용함hash set이라고도 부름hash table의 key만 사용추상자료형add(data) 데이터 삽입isContain(data) 데이터 체크(boolean)remove(data) 데이터 제거clear() 셋비우기isEmpty() 셋이 비었는지 체크printAll() 모든 데이터 출력 그림으로 쉽게 배우는 운영체제Section1. 운영체제 들어가기운영체제가 하는일프로세스관리멀테가가능하게해줌예시) 게임하는중, 백그라운드로 노래나 인터넷 브라우저를 틀어놓을 수 있음메모리 관리모든 프로그램은 메모리를 사용하드웨어관리운영체제가 판단하여 적절한데 저장하드디스크에 중요한 것이 저장 될 수 있기 때문파일 시스템 관리하드디스크의 효율적인 저장과 관리를 위함운영체제의 구조커널: 프로레스와 메모리, 저장장치를 관리하는 핵심적인 기능사용자는 인터페이스를 통해서만 접근가능함GUI (Graphic user interface)ex. window더블클릭으로 디렉토리 이동 CLI (Command-Line Interface)ex. 리눅스텍스트로 입력해야지만 이동 어플리케이션은 시스템콜을 이용해서 커널에 접근가능하드웨어와 커널의 인터페이스는 드라이버임각각의 하드웨어에 맞는 프로그램을 커널이 다 가질수 없기 때문에, 복잡한 장치는 디바이스 드라이버를 설치해야 사용가능함. 인터럽트입출력작업이 들어오면 관리자에게 오더함주기적으로 확인해야함: polling방식주기적인 확인으로 성능이 좋지 않음cpu가 명령내리고, 입출력 관리자가 다 되었을 때 cpu에 알려줌: 인터럽트방식비동기적임하드웨어입출력등과 같은것소프트웨어방식유효하지 않은 메모리접근과 같은 것.Section2. 프로세스와 쓰레드프로그램명령문의 집합체저장장치만 사용하는 수동적 존재프로세스실행중인 프로그램하드디스크에 저장된 파일이 메모리에 올라갔을때 프로세스라함메모리도 사용하고, cpu도 사용하고, 필요에 따라 입출력도 사용하기에 능동적인 존재임code: 실행코드data: 전역변수와 static(정적) 변수가 저장stack: 지역변수와 함수호출했을 때의 정보가 저장heap영역: 프로그래머가 동적으로 메모리를 할당하는데 쓰임PCB(Process Control Block)운영체제는 프로세스를 공평하게 해야함PCB: linked list라는 자료구조로 저장됨PCB포인터: 효율적인 접근을 위해사용프로세스상태: 생성, 준비, 실행, 대기, 완료를 나타냄프로세스 ID: 프로세스를 실행하기 위한 숫자프로그램 카운터: 다음에 실행될 명령어 주소를 포함레지스터 정보: 프로세스가 실행될때 사용된 레지스터 번호메모리 관련정보: 메모리 위치, 메모리 침범을 막기위한 정보CPU스케줄링 정보: 우선순위, 점유시간 등이 저장됨더 많은 정보가 저장됨컨텍스트 스위칭(context switching)프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태를 저장, 다른 프로세스 상태로 교체하는 것.PCB에 상태 저장PCB: 프로세스상태, 프로그램 카운터 ,각종 레지스터 정보가 변경됨CPU점유시간이 초과할경우: 인터럽트 실행레지스터값을 저장해둠발생이유cpu 점유시간 초과입출력요청다른 종류의 인터럽트의 발생쓰레드: 프로세스 내에 존재함1개의 프로세스안에 여러개에 존재함code, data, heap영역을 공유하고, stack은 하나씩 가지고 있음.ID도 부여하고 , TCB부여함으로써 운영체제가 구분할 수 있게됨.프로세스장/단점안전성: 다른 프로세스가 영향을 미치지 않음오버헤드가 큼쓰레드 장/단점안전성이 떨어짐 (일부공유하기 때문)오버헤드가 작음Section3. CPU 스케줄링cpu스케줄링이 고려할 점 (컴퓨터의 성능에 많은 영향을 줌)어떤 프로세스에 cpu 사용권을 주어야 하는가 cpu 할당받은 프로세스에 얼만큼의 시간을 주어야 하는가다중큐준비상태와 대기상태는 큐의 자료구조로 관리됨운영체제는 프로세스의 우선순위를 정해서 할당해줌 스케줄링 목표리소스 사용률: cpu사용율 or I/O 디바이스 사용률을 높임오버헤드 최소화: 계산이 너무 복잡하거나, 컨테스트 스위칭을 너무 자주하면 오버헤드 심해짐공평성: 모든 프로세스에게 공평하게 cpu할당을 위함.단 시스템에 따라 달라질 수 있음.예를들어, 자율주행 자동차에서는 안전관련이 제일 중요, 음악재생은 덜함.처리량: 같은 시간내 더 많은 처리를 하는 것을 목표로 삼음대기시간: 최소화를 목표로함응답시간: 짧은 것을 목표로함목표간의 상반되는 것이 있음.처리량과 응답시간의 목표를 동시에 이룰 수 없을 때는 사용자의 시스템에 따라 초점을 맞추어줌.특정한 경우아니고서는 발란스를 이루는 것이 중요. FIFO (First In First Out)장점: 단순, 직관적단점: 순차적이여서 늦게오면 대기시간이 길어짐, I/O시간동안 cpu가 쉬고있기 때문에 cpu사용률이 떨어짐. 스케쥴링 성능은 평균 대기시간으로 평가함!*burst time 계산시에는 대기시간을 총더한값에 프로세스 갯수 나누기이기 때문에, 프로세스 시간이 짧은 것을 먼저 할 경우 대기시간이 짧아짐.SJF(Shortest Job First)FIFO의 단점을 해결하기 위해 고안됨.실제 고안에서 발생 되었던 문제프로세스 종료시간이 어느정도인지 예측어려움burst time이 긴 프로세스는 언제 진행이 될지 모르게됨 = 불공평해짐.RR(Round Robin)FIFO -> SJF -> RRfifo의 단점 해결을 위해 한 프로세스에 일정시간(=할당시간)을 부여하고, 시간이 초과하면 다른 프로세스로 가게 만듬프로세스에게 할당하는 일정시간 = 타임퀀텀, 타임 슬라이스RR algorithm은 컨텍스트 스위칭이 포함됨.타임슬라이스를 너무 작게하면, 컨텍스트 스위칭이 너무 많이 일어나게됨 = 오버헤드가 너무크다.사용자가 버벅거리게 느끼지 않고, 오버헤드가 너무 크지 않고, 동시에 실행되는 것처럼 느끼게하기..MLFQ (Multi Level Feedback Queue)기본적으로 작은 타임슬라이스를 가지지만, cpu작업이 비교적 작은 (ex. I/O bound process) 프로세스가 작은 타임 슬라이스를 가지고, cpu작업이 비교적 큰 프로세스가 타임 슬라이스가 크게 됨.타임슬라이스 기준으로, 우선순위를 정하게됨.
