[워밍업클럽3기] CS전공지식 1주차

그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

Section01. 개요

1. 자료구조

   1. var (variable, 변수)

   2. arr (Array, 배열)

      1. index를 이용하여 해당 data에 접근함

      2. 자료 구조에 따라 배열을 사용하는 것이 편할 수 있음.

          

2. Algorithm.

   1. 확실한 방법을 의미함

   2. 시키는대로 했을 때 답이 나와야함.

   3. 모호한 방법은 안됨

   4. 자료구조에 따라 알고리즘이 달라짐

   5. 특정 자료구조 =/= 하나의 알고리즘

3. 시간복잡도

   1. 더 좋은 알고리즘이란?

      1. 사용자의 니즈에 따라 다름

         1. depend on the memory size, speed or both

      2. 일반적으로 알고리즘 속도 = 성능속도 = 시간 복잡도

   2. 시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간

      1. 사용자마다 컴퓨터 사양이 다르기 때문에 실행시간이 무조건 같지는 않음.

   3. 알고리즘의 평가는 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 것임.

      1. 코드에서 성능에 많은 영향을 주는 부분 = 반복문

   4. 빅오 표기법

       

      1. 빅오 표기법이 성능을 정확하게 표현하지 못하는 이유: 단순히 해당알고리즘의 입력이 늘어날 때, 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문

      2. O(n) : 선형시간 알고리즘

      3. O(1): 상수시간 알고리즘

      4. O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)

      5. 계산에 가장 많이 영향을 미치는 차수만 표시함

Section02. 자료구조

1. 배열 [array]

   1. 기본적으로 제공하는 자료구조

   2. 일반적인 배열: 선언시 배열의 크기를 알려줌

      1. 읽기/쓰기/참조에서 좋은 성능을 보임

      2. 삽입/ 삭제에서 좋지 않은 성능을 보임

         1. 이유: 이미 연속된 메모리공간을 선언하였기 때문에 배열의 끝에 새로운 메모리로의 추가가 어렵기 때문에 새로운 사이즈의 배열을 추가할 수 있는 메모리를 찾아야함. (삭제도 같은 이유)

         2. 배열을 너무 크게할경우, 일시적으로 해결 되는 것처럼 보이지만, 결국 제한적이고 배열의 크기와 메모리의 크기가 비례하기 때문에, 너무 큰 배열은 너무 많은 메모리를 차지하게됨.

2. 연결리스트 [linked list]

   1. 배열의 단점을 해결해줌

   2. 연결은 노드를 이용함

   3. node는 data의 위치 + next node number

      1. 위와 같은 이유로 node = linked list

   4. 장점

      1. 열의 초기 크기를 알아야하는 단점이 없음.

      2. 삽입과 삭제가 용의함

   5. 단점

      1. 데이터들이 떨어져 있어서(노드번호에 따라 위치가 다름) 특정 순서의 데이터로 바로 갈 수 없음.

      2. 각 노드의 다음노드를 무조건 알아야 하기때문에 O(n)의 성능을 가짐.

         1. array의 성능은 O(1)

데이터의 참조가 많이 일어나는 경우에는 배열이,

데이터의 삽입과 삭제가 많이 일어나는 경우에는 연결리스트가 도움이 됨.

3. 스택(Stack)

   1. Stack의 사전적의미: 더미, 무더기 인것처럼 무작정 쌓는 개념

   2. FILO(First in Last Out)

      1. 그냥 물건 쌓아두는 개념

      2. 선입선출과 반대됨

          

4. 큐(Queue)

   1. FIFO (First In First Out)

      1. 선입선출의 개념임

      2. 질서를 위해 서는 줄

      3. head에 삽입, 제거

   2. 연결리스트로 구현함.

   3. O(n)의 성능이 나옴

      1. 그렇기 때문에 head는 가장 앞의 노드, tail은 가장 뒤의 노드로 tail 변수추가로 O(1)의 성능이 나오게함

      2. 일반 연결리스트 아닌 이중 연결리스트 사용. (양방향 연결리스트임)

      3. tail의 이전노드를 할당함.

         1. enqueue : insert data

         2. dequeue : delete data

         3. front : 데이터 참조

         4. isEmpty : 비어있는가 확인

스택은 위로 쌓아 올려서 위에서 꺼내는 느낌이면

큐의 경우 왼쪽에서 데이터 넣고 오른쪽에서 데이터 빼내는 느낌?

5. 덱(Deque)

   1. 삽입과 제거를 head와 tail모두에서 가능하기 때문에 스텍과 큐의 형태 모두 구현가능

   2. 추상자료형

      1. printAll: 모든 데이터 출력

      2. addFirst: head에 데이터 삽입

      3. removeFirst: head에서 데이터 제거

      4. addLast: tail에 데이터 삽입

      5. removeLast: tail에서 데이터 제거

      6. isEmpty: 리스트가 비어있는지 확인

6. 해시테이블(hash Table)

   1. 해시테이블 (hash table)

      • hash, map, hashmap, dictionary라고도 불림

      • 표를 저장하는 가장쉬운방법 = array에 저장

        • index로 접근하다보니 빈공간이 많아지고, 낭비되는 공간이있음

        • 메모리 절약을 위해 어떠한 계산을 거쳐 인덱스로 치환함: 어떠한 계산이 해시함수임

        • 삽입, 수정, 삭제까지 O(1)의 성능을 가짐

        • 문제: 충돌이 발생하기도함

          • 해당인덱스를 연결리스트로 구현해 저장함: O(n)의 성능을 가짐

            • 이렇기 때문에 해시테이블은 해시함수의 선정이 매우 중요함.

      • 장점: 빠른 데이터 읽기, 삽입, 삭제

      • 단점: 메모리를 많이 차지함.

7. 셋(Set)

   1. 데이터의 중복을 허용하지 않는 자료구조

   2. 해시테이블을 이용함

   3. hash set이라고도 부름

   4. hash table의 key만 사용

   5. 추상자료형

      1. add(data) 데이터 삽입

      2. isContain(data) 데이터 체크(boolean)

      3. remove(data) 데이터 제거

      4. clear() 셋비우기

      5. isEmpty() 셋이 비었는지 체크

      6. printAll() 모든 데이터 출력 

그림으로 쉽게 배우는 운영체제

Section1. 운영체제 들어가기

운영체제가 하는일

• 프로세스관리

  • 멀테가가능하게해줌

  • 예시) 게임하는중, 백그라운드로 노래나 인터넷 브라우저를 틀어놓을 수 있음

• 메모리 관리

  • 모든 프로그램은 메모리를 사용

• 하드웨어관리

  • 운영체제가 판단하여 적절한데 저장

  • 하드디스크에 중요한 것이 저장 될 수 있기 때문

• 파일 시스템 관리

  • 하드디스크의 효율적인 저장과 관리를 위함

운영체제의 구조

• 커널: 프로레스와 메모리, 저장장치를 관리하는 핵심적인 기능

• 사용자는 인터페이스를 통해서만 접근가능함

  • GU

    I (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스케줄링이 고려할 점 (컴퓨터의 성능에 많은 영향을 줌)

1. 어떤 프로세스에 cpu 사용권을 주어야 하는가

    

2. cpu 할당받은 프로세스에 얼만큼의 시간을 주어야 하는가

다중큐

• 준비상태와 대기상태는 큐의 자료구조로 관리됨

• 운영체제는 프로세스의 우선순위를 정해서 할당해줌

 스케줄링 목표

1. 리소스 사용률: cpu사용율 or I/O 디바이스 사용률을 높임

2. 오버헤드 최소화: 계산이 너무 복잡하거나, 컨테스트 스위칭을 너무 자주하면 오버헤드 심해짐

3. 공평성: 모든 프로세스에게 공평하게 cpu할당을 위함.

   1. 단 시스템에 따라 달라질 수 있음.

      1. 예를들어, 자율주행 자동차에서는 안전관련이 제일 중요, 음악재생은 덜함.

4. 처리량: 같은 시간내 더 많은 처리를 하는 것을 목표로 삼음

5. 대기시간: 최소화를 목표로함

6. 응답시간: 짧은 것을 목표로함

목표간의 상반되는 것이 있음.

• 처리량과 응답시간의 목표를 동시에 이룰 수 없을 때는 사용자의 시스템에 따라 초점을 맞추어줌.

• 특정한 경우아니고서는 발란스를 이루는 것이 중요.

 FIFO (First In First Out)

장점: 단순, 직관적

단점: 순차적이여서 늦게오면 대기시간이 길어짐, I/O시간동안 cpu가 쉬고있기 때문에 cpu사용률이 떨어짐.

스케쥴링 성능은 평균 대기시간으로 평가함!

*burst time 계산시에는 대기시간을 총더한값에 프로세스 갯수 나누기이기 때문에, 프로세스 시간이 짧은 것을 먼저 할 경우 대기시간이 짧아짐.

SJF(Shortest Job First)

• FIFO의 단점을 해결하기 위해 고안됨.

• 실제 고안에서 발생 되었던 문제

  • 프로세스 종료시간이 어느정도인지 예측어려움

  • burst time이 긴 프로세스는 언제 진행이 될지 모르게됨 = 불공평해짐.

RR(Round Robin)

• FIFO -> SJF -> RR

• fifo의 단점 해결을 위해 한 프로세스에 일정시간(=할당시간)을 부여하고, 시간이 초과하면 다른 프로세스로 가게 만듬

프로세스에게 할당하는 일정시간 = 타임퀀텀, 타임 슬라이스

RR algorithm은 컨텍스트 스위칭이 포함됨.

타임슬라이스를 너무 작게하면, 컨텍스트 스위칭이 너무 많이 일어나게됨 = 오버헤드가 너무크다.

사용자가 버벅거리게 느끼지 않고, 오버헤드가 너무 크지 않고, 동시에 실행되는 것처럼 느끼게하기..

MLFQ (Multi Level Feedback Queue)

• 기본적으로 작은 타임슬라이스를 가지지만, cpu작업이 비교적 작은 (ex. I/O bound process) 프로세스가 작은 타임 슬라이스를 가지고, cpu작업이 비교적 큰 프로세스가 타임 슬라이스가 크게 됨.

  • 타임슬라이스 기준으로, 우선순위를 정하게됨.