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

[1 주차 시작하기 전 다짐]

• 아침에 일어나서 주어진 강의 분량을 다 듣기

• 틈날 때 강의 듣기

• 저녁에 집에 와서 다시 듣기 또는 실습 진행

  ---

  [1 주차 회고]

  • 칭찬할 점

    • 한 번 듣고 이해를 할 수 없다고 판단이 되어서 반복해서 들으려고 노력했다.

      
      => 5 일간 진행하는 동안 '시작하기 전 다짐'을 꼭 지켰다.

    • 현재 내가 공부하는 언어 java이다. 그런데 javascript로 진행되는 실습이라서 나는 코드를 java로 바꿔서 실습 해야 했다.
      => java로 바꾸는 과정이 어렵지 않았다. 스스로에게 놀랐다. java를 공부한 보람을 느낄 수 있었다.

  • 아쉬운 점

    • 듣기만 하고 정리를 하지 못했다.

    • 다음 주차부터는 듣고, 더 오래 기억에 남을 수 있게 정리를 하면서 들어야겠다.
      => 영상을 보면서 강의 노트를 작성하는 부분을 활용해 봐야겠다.

       

  ---

[강의 내용 정리]

[운영체제]

• 운영체제

  • 프로세스 간의 실행을 스케줄링 해주는 스케줄러

   

• 운영체제 구조

  • 커널

    • 프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능 담당

    • 사용자는 커널에 직접 접근 할 수 없다.

   

• 프로그램과 프로세스

  • 프로그램은 하드디스크에 저장된 실행 파일이다.

  • 프로세스는 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행중인 프로그램이다.

   

• 멀티프로그래밍과 멀티프로세싱

  • 멀티프로그래밍은 메모리에 여러 개의 프로세스를 올려서 처리하는 것이다.

  • 멀티 프로세싱은 멀티 프로세서로 작업을 처리하는 것이다.

    • 멀티 프로세서는 CPU를 한 개가 아닌 여러 개를 이용하는 것을 말한다.

   

• 컨텍스트 스위칭

  • 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고
    다른 프로세스의 상태 값으로 교체하는 작업이다.

   

• 쓰레드

  • 프로세스 내에 1개 이상 존재하는 작업을 뜻한다.

  • 한 프로세스 내에 쓰레드들은 PCB, 코드, 데이터, 힙 영역을 공유한다.
    스택은 쓰레드마다 하나씩 가지고 있다.

  • 장점

    • 한 프로세스 내에서 스택 영역을 제외한 모두 공유하기 때문에 오버헤드가 작다.

  • 단점

    • 쓰레드간 통신은 데이터를 공유를 쉽게 할 수 있다.
      그러나 공유되는 공간에 문제가 생길 수 있다. => 프로세스 동기화

       

  

• cpu 스케줄링

  • 운영체제가 모든 프로세스에게 CPU 를 할당/해제 하는 것을 말한다.

  • 목표

    • 리소스 사용률 - CPU 사용률 또는 I/O 사용률을 높이는 것이다.

    • 오버헤드 최소화 - 스케줄링 계산이 복잡하거나 컨텍스트 스위칭이 자주 발생하면 안된다.

    • 공평성 - 특수한 경우를 제외하고 모든 프로세스에게 CPU 가 골고루 할당 되어야 한다.

    • 처리량 - 같은 시간 내에 더 많은 처리를 할 수 있어야 한다.

    • 대기 시간 - 작업을 요청하고 실제 작업이 이루어지기 전까지 대기하는 시간이 짧아야 한다.

    • 응답 시간 - 대화형 시스템에서 사용자의 요청에 얼마나 빨리 반응하는 지가 중요하다.

   

• cpu 스케줄링 알고리즘

  • FIFO(First In First Out)

    • 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식

    • 일괄처리 시스템에 쓰인다.

    • 장점

      • 단순하고 직관적이다.

    • 단점

      • 먼저 들어온 프로세스가 완전히 끝나야지만 다음 프로세스가 실행될 수 있다.

      • 실행 시간(Burst Time)이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 한다.

         

  

  • SJF(Shortest Job First)

    • Burst Time이 짧은 프로세스를 먼저 처리한다.

    • 문제 2가지

      • 프로세스가 얼마나 실행될 지 예측하기 어렵다.

      • Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.

    • 이러한 문제로 SJF 알고리즘은 사용되지 않는다.

  

  • RR (Round Robin)

    • FIFO 알고리즘의 단점을 해결한다.

    • 타임 슬라이스(프로세스에게 할당하는 일정 시간)만큼 CPU를 할당하고 할당된 시간이 지니면
      강제로 다른 프로세스에게 CPU를 할당한다.

    • 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려난다.

    • 타임 슬라이스의 값에 따라 성능이 크게 달라진다.

  

  • MLFQ(Multi Level Feedback Queue)

    • RR 의 업그레이드된 알고리즘이다.

    • 기본적으로는 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택한다.

    • 작동 원리

      • 우선순위를 가진 큐를 여러 개 준비를 한다.

      • 우선수위가 높으면 타임 슬라이스가 작고 우선순위가 낮을수록 타임 슬라이스 크기가 커진다.

      • 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU 를 빼앗긴다면 프로세스는 원래 있던 큐보다
        우선순위가 더 낮은 큐로 이동하게 된다.

      • 최종적으로 타임 슬라이스가 무한초에 가깝게 할당되기 때문에 FIFO 처럼 연속적으로 작업을 마칠 수 있게 된다.

[자료구조와 알고리즘]

[java로 실습한 것은 깃허브에 올려두었다.]

• 자료구조와

  알고리즘

  • 자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는 지를 나타내는 것이다.

    • 예시

      • 변수 - 하나의 값을 저장

      • 배열 - 여러 개의 값을 연속적으로 저장

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

  • 데이터가 어떤 자료구조를 하고 있는 지에 따라서 알고리즘이 달라진다.

• 시간 복잡도

  • 알고리즘이 어떤 문제를 해결하는데 걸리는 시간이다.

  • 알고리즘을 평가할 때 시간을 측정하는 방식이 아닌 코드에서 성능에 영향을 주는 부분을 찾아 실행을 예측하는 것이다.

  • 반복문이 성능에 많은 영향을 준다.

     

  • 최악의 경우를 평가하는 빅오

    • 입력이 늘어날 때 계산량이 늘어나는 척도를 나타낸다.

    • 계산에 가장 많은 영향을 미치는 항만 표기 한다. 상수는 제거해준다.

      • 예시

        • n제곱 + 2n + 100 -> O(n제곱)

        • 3n제곱 + 100 -> O(n제곱)

• 자료구조

  • 배열(Array)

    • 모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조

    • 요청한 크기만큼 메모리에 연속된 공간을 할당한다.

    • 운영체제는 배열의 시작 주소만 기억한다.

      • 길이가 10인 배열의 세 번째 값에 접근하고 싶다면 arr[2] 인덱스로 한 번에 접근 가능하다.

    • 장점

      • 배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다. O(1) 성능

    • 단점

      • 데이터 삽입, 삭제 성능이 좋지 않다.

      • 크기를 예측할 수 없어서 메모리가 낭비될 수 있다.

         

  • 연결리스트(LinkedList)

    • 저장하려는 데이터들을 메모리 공간에 분산해 할당하고 데이터들을 서로 연결해준다.

    • 노드를 만들어서 수행

      • 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있다.

      • 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.

    • 장점

      • 데이터 추가 시 빈 메모리 공간에 데이터를 생성하고 연결만 해주면 된다. (초기 크기를 알 필요 없다.)

      • 중간에 데이터를 삽입, 삭제할 때 다음 가리키는 노드만 변경하면 되기 때문에 아주 간단한 작업이 된다.

    • 단점

      • 데이터들이 전부 떨어져 있어서 원하는 데이터에 바로 접근할 수 없다.

      • 데이터를 찾으려면 첫 노드부터 차례대로 탐색 해야 한다. 데이터 참조가 O(n) 의 성능을 가진다.

  • 스택(Stack)

    • FILO(FIrst In Lost Out) - 먼저 들어간 데이터가 나중에 나오는 규칙이다.

    • 실생활 예시

      • 엘리베이터에 모든 사람이 같은 층에 내린다면 먼저 들어간 사람이 나중에 내린다.

    • 연결리스트로 스택 구현

      • head 를 이용한다.

      • 데이터 삽입을 무조건 첫 번째 인덱스에 한다.

      • 데이터 제거도 무조건 첫 번째 인덱스에 한다.

  • 큐(Queue)

    • FIFO(FIrst In First Out) - 먼저 들어간 데이터가 먼저 나오는 규칙이다.

    • 실생활 예시

      • 마트 계산대에 들어온 순서대로 계산한다.

      • 운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내서 처리 (FIFO 스케줄링)

    • 이중연결리스트로 큐 구현

      • 이중연결리스트(양방향 연결리스트)

      • 큐의 데이터 삽입

        • head 로 가장 앞부분에 삽입한다.

      • 큐의 데이터 제거

        • 가장 뒤에서부터 데이터를 제거한다.

        • 뒷부분에서 데이터를 제거하고 가리키는 tail 은 이전 노드를 가리킨다.

  • 덱(Deque)

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

    • 덱을 이용하면 스택과 큐를 전부 구현할 수 있다.

  • 해시 테이블(HashTable)

    • 해시와 테이블이 합쳐진 자료구조이다.

    • 해시 함수로 테이블의 인덱스를 새로 만든다.

      • Key 와 Value 로 이루어져 있다.

         

    • Value 부분에서 원하는 데이터의 키를 찾는 건 O(n) 의 성능을 가진다.

    • 장점

      • 빠른 데이터 읽기, 삽입, 삭제가 가능하다. O(1) 의 성능

    • 단점

      • 메모리를 많이 차지한다.

        • 미리 많은 공간을 마련해줘야 한다.

      • 좋은 해시 함수의 구현이 필수

        • 데이터를 골고루 분배 시켜주는 함수가 좋은 해시 함수이다.

  • 셋(Set)

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

    • 해시 테이블을 이용해서 쉽게 구현할 수 있다.

    • 해시 테이블의 Value 부분에서 HashData 로 저장을 한다.

      • HashData 에 key만 사용하고 value 부분은 사용하지 않는다.

      • key가 key임과 동시에 데이터로 쓰인다.

 ※ '강의 내용 정리' 출처

[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 1~3]

[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 1~2]