[워밍업 클럽 CS 3기] 1주차 발자국

운영체제

• 운영체제에 대해서

   

  • 운영체제는 프로세스 관리, 메모리 관리, 하드웨어 관리, 파일 시스템 관리 등의 역할을 함

  • 커널은 프로세스와 메모리를 관리 역할 (사용자 - 인터페이스, 애플리케이션 - 시스템콜, 하드웨어 - 드라이브)

  • 폰 노이만 구조 - CPU와 메모리 사이를 버스(데이터 전달 통로)로 연결하는 구조

  • CPU는 ALU(산술논리연산장치), 제어장치, 레지스터로 구성

  • 폴링 방식은 CPU가 주기적으로 확인이 필요, 인터럽트는 입출력 관리자가 작업이 완료되면 ISR을 실행시켜 작업

• 프로세스와 스레드

  • 프로그램은 하드 디스크에 저장된 명령문의 집합체, 프로세스는 실행중인(메모리에 올라간 상태) 프로그램

  • 프로그램은 수동적이지만, 프로세스는 능동적으로 필요에 따라 CPU를 사용하고 입력 출력을 함.

  • 프로세스의 구조(Code, Data, Heap, Stack)

     

  • 멀티프로그래밍과 멀티프로세싱(유니프로그래밍의 단점 보완)

    • 멀티 프로그래밍: 메모리에 여러개의 프로세스 올려서 처리

    • 멀티태스킹: 서로 다른 프로세스를 짧게씩 실행하며 동시에 처리하는것처럼 보이게 함

      • CPU가 여러개라면 멀티프로세서, 이렇게 작업하는 건 멀티프로세싱

  • PCB(Process Control Block) - 프로세스의 정보 저장(연결리스트 구조)

  • 프로세스의 상태 (생성, 준비, 실행, 대기, 완료)

  • 컨텍스트 스위칭

    • 다른 프로세스 실행을 위해 프로세스 상태를 저장하고 다른 프로세스 상태값으로 교체

  • 프로세스 생성 시에 기존의 프로세스를 fork로 복사해서 사용(자식 프로세스)

  • 쓰레드 - 한 프로세스 내에 여러개 있을 수 있으며, PCB, 데이터, 코드, 힙영역을 공유(스택은 고유)

    • TCB(Thread Control Block), TID(쓰레드 아이디)

    • 프로세스는 독립적이어서 안정적, 쓰레드는 프로세스에 문제가 생기면 전체 문제 생겨서 불안정적

    • 프로세스는 고유한 영역, IPC로 통신해 오버헤드 큼, 쓰레드는 데이터 공유가 가능해 오버헤드가 작음

• CPU 스케쥴링

  • 준비, 대기 상태는 큐로 관리

  • PCB는 다중 큐에 들어가서 준비 상태, CPU 스케쥴러가 결정해서 실행 상태로 전화시킴

  • 목표: 리소스 사용률, 오버헤드 최소화, 공평성, 처리량, 대기시간, 응답시간

  • 스케쥴링 알고리즘

    • FIFO: 먼저 들어온 순서대로 작업(실행시간에 따라 유동적으로는 작업X, I/O작업으로 인한 비효율)

    • SJF(Shortest Job First): 짧은 작업 먼저(시간 예측 힘듦, 긴 프로세스는 너무 오래 대기)

    • RR(Round Robin): 모두 공평한 Time Slice를 쓰고 다음 프로세스에게 뺏김(컨텍스트스위칭 시간 고려 필요)

    • MLFQ(Multi Level Feedback Queue): Time slice를 작게 쓰고, 프로세스의 구분에 따라 다르게 줌

자료구조와 알고리즘

• 자료구조와 시간 복잡도

  • 자료구조는 데이터가 어떤 구조로, 저장, 사용되는지 나타냄

  • 알고리즘은 문제를 해결하기 위한 방법(자료구조에 영향을 받음)

  • 시간 복잡도란 특정 알고리즘이 문제를 해결하는데 걸리는 시간 (반복문을 최소화 하는 것이 목표)

  • big-O 표기법은 계산량이 얼마나 늘었는지 표현법이므로 정확하지 않음(상수는 무시, 가장 큰 영향의 숫자만 표기)

• 배열

  • 운영체제는 배열의 주소를 기억하고 데이터를 가져옴

  • 인덱스 참조는 길이에 상관X, 한번에 가져오기 때문에 높은 효율 -> O(1) 그러나 삽입, 삭제 성능은 좋지않음

• 연결리스트

  • 데이터를 분산 저장 후 서로 연결 (노드를 사용)

  • 추가, 삭제는 데이터 연결 부분을 수정만 하면 되서 간단, 참조는 다 따라가서 봐야해서 효율 나쁨

• 스택

  • FILO구조, 먼저 들어간 데이터가 나중에 나옴

  • 배열, 연결리스트로 구현 가능(head사용)

• 큐

  • FIFO구조, 먼저 들어간 데이터가 먼저 나옴

  • 먼저 들어간 데이터 삭제시, head부터 다 따라가야 나오므로, tail추가 해서 구현

  • tail에 있는걸 삭제해도 tail도 업데이트가 필요하므로 양방향 변경 필요

• 덱

  • 데이터 삽입, 삭제를 head와 tail에서 자유롭게 가능

• 해시테이블

  • 인덱스로 배열에 접근(빈공간 발생 가능), 특정 숫자를 배열에 넣기 위해 하는 연산인 해시 함수 필요

  • 하나의 인덱스에 여러개의 데이터 들어가는 문제 발생시, 연결리스트로 해결 가능

  • 데이터 삽입, 탐색, 삭제가 효율적이나 공간 효율이 나쁘고 해시 함수 구현이 필수적

• 셋

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

  • value는 사용X, Key만 사용

칭찬할 점: 강의를 여러번 들은 게 잘한 것 같습니다. 2~3번 정도 들으니 머리에 더 잘 들어오는 것 같아요.

보완할 점: 목~금에 강의가 좀 밀렸습니다. 앞으론 밀리는 일 없게 오며가며 계속 들어야 할 것 같습니다.

다음 주 목표: 다음주에는 자바스크립트 공부를 좀 더 해서 자료구조 부분은 제가 복습하면서 더 활용해보고 싶습니다.