인프런 워밍업 클럽 스터디 2기 CS | 1주차 발자국

"인프런 워밍업 클럽 스터디 2기 CS" 과정을 듣게 되었다.

프로그래밍 언어 공부하기만 바빴지 CS에 대해서는 아는 것이 없었기에, 강의 수집가라 수집만 하고 완강을 한 적이 별로 없었기에, 항상 장바구니에 넣어두고 언젠가 사야지 고민하던 "감자"님 강의기에

2일 정도 고민 후 바로 강의 구매 및 스터디 신청을 하게 되었다.

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

섹션1) 운영체제 들어가기

운영체제 개요

• 컴퓨터는 운영체제가 없어도 동작할 수 있다. 하지만 다른 기능을 추가할 수 없다.

  • 운영체제 없는 컴퓨터 === 통화만 가능했던 옛날 유선 전화기

  • 요즘 컴퓨터 === 요즘 스마트폰

   

운영체제가 하는 일

1. 프로세스 관리

• 노래, 게임, 인터넷 서핑 전부 동시 실행 가능

  • 현재 실행 중인 것 외에는 백그라운드에서 실행됨

  • 만약 운영체제가 관리하지 않으면 CPU가 독차지 되어 동시에 실행 불가

2. 메모리 관리

• 모든 프로그램은 메모리에 올라와서 동작

   

  
  3. 하드웨어 관리

• 운영체제는 사용자의 하드웨어에 대한 직접적인 접근을 막음

  • 사용자가 데이터를 저장하려고 할 때 하드디스크의 특정 영역에 바로 저장 못 함

  • 운영체제가 판단해서 적절한 위치에 저장

     

    • 하드디스크 특정 영역에 중요한 데이터가 존재할 수 있기 때문

    • 사용자의 악의적인 공격 방어

       

  4. 파일 시스템 관리

   

   

   

   

  운영체제의 역사

• 비싼 CPU의 사용률을 늘릴려고 고민

• 오퍼레이터와 프로그래머 사이에서 낭비되는 시간을 줄이려고 함

   

  => 오늘날의 운영체제 탄생

운영체제의 구조

이미지 참조 ) https://ko.wikipedia.org/wiki/%EC%BB%A4%EB%84%90_%28%EC%BB%B4%ED%93%A8%ED%8C%85%29

• 운영체제의 핵심은 커널(kernel)

  • 컴퓨터 운영체제의 핵심이 되는 컴퓨터 프로그램, 시스템의 모든 것을 완전히 제어. 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당

• 사용자는 운영체제의 커널에 직접 접근X, 인터페이스를 통해서 접근할 수 있음.

  • 인터페이스

    • GUI(Graphic User Interface)

      • e.g. windows, Mac OS

    • CLI(Command-Line Interface)

      • e.g. 유닉스, 리눅스

  • 시스템 콜

    (system call)

    • 시스템 호출 또는 시스템 콜, 간단히 시스콜은 운영체제의 커널이 제공하는 서비스에 대해 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스

      • 어플리케이션은 시스템 콜을 통해서 커널에 접근 가능

  • 드라이버

    • 하드웨어와 커널의 인터페이스

    • e.g. 키보드, 마우스 등

컴퓨터 하드웨어와 구조

• 오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조

  • CPU와 메모리(RAM)를 두고 이들 사이는 버스로 연결

    • 버스: 데이터를 전달하는 통로

  • 프로그램은 메모리에 올려서 실행시키는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장방식이라고 함

  • 메모리에 올라간 프로그램은 명령에 따라 처리

• 컴퓨터 하드웨어

  • 가장 기본이 되는 것은 메인보드

    • 메인보드: 다른 하드웨어를 연결하는 장치

    • 장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당

• CPU(Central Processing Unit) 구조

  • 중앙처리장치, 컴퓨터 시스템을 통제하고 프로그램의 연산을 실행, 처리하는 가장 핵심적인 컴퓨터의 제어 장치, 혹은 그 기능을 내장한 칩. 컴퓨터에서 기억, 해석, 연산, 제어라는 4대 주요 기능을 관할하는 장치

    • 산술논리 연산장치

      • CPU에서 실제로 데이터 연산을 담당하는 것

    • 제어장치

      • 모든 장치들의 동작을 지시하고 제어하는 장치

    • 레지스터

      • CPU 내에서 계산을 위해 임시로 보관하는 장치. 변수라고 생각해라

• 메모리 종류

  • RAM(Random Access Memory)

    • 램덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음

    • 전력이 끊기면 데이터를 잃어버림

    • 메인 메모리로 사용

  • ROM(Read Only Memory)

    • 전력이 끊겨도 데이터를 계속 보관할 수 있음

    • 데이터를 한 번 쓰면 수정 불가능

    • 컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임

컴퓨터의 부팅과정

• 컴퓨터 부팅 -> ROM에 저장된 바이오스 실행 -> 바이오스는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상유무 확인 -> 이상 없으면 부트로더 실행, 있으면 부팅 불가 -> 부팅 후 실행되는 모든 응용 프로그램은 메모리에 올라와서 운영체제가 관리

인터럽트(Interrupt)

• 프로세스 실행 중 예기치 않은 상황이 발행할 때 발생한 상황을 처리한 후 실행 중인 작업으로 복귀하는 것. CPU가 특정 기능을 수행하는 도중에 급하게 다른 일을 처리하고자 할 때 사용할 수 있는 기능

    

• CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황

  • CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내림

  • CPU 관점에선 입출력 명령이 언제 완료될 지 알 수 없음

  • CPU는 주기적으로 계속 확인함 => 폴링(Polling)방식

    • 폴링 방식은 주기적으로 CPU가 확인해야 해서 성능이 안좋음

    • 폴링 방식의 단점을 해결한게 인터럽트 방식

  • CPU가 입출력 관리자에게 입출력 명령을 내리고

  • CPU는 다른 작업을 함

  • 입출력 관리자는 입출력이 완료되었을 때 CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료

    • 인터럽트 서비스 루틴(ISR): 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수

    • 인터럽트는 비동기적으로 동작 => 성능에 이점

  • 인터럽트 2가지 방식

    • 하드웨어 인터럽트

      • 위의 입출력 등과 같은 인터럽트

    • 소프트웨어 인터럽트

      • 사용자 프로그램에서 발생한 인터럽트

      • e.g. 유효하지 않은 메모리에 접근, 0으로 나누는 명령어 등

섹션2) 프로세스와 쓰레드

프로그램과 프로세스

• 프로그램(애플리케이션, 앱)

  • 하드디스크 등과 같은 저장장치(HDD, SSD)에 저장된 명령문의 집합체

  • Windows 운영체제에서는 .exe 파일의 모습

  • 컴퓨터 관점에서 프로그램은 저장 장치만 사용하는 수동적인 존재

• 프로세스

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

  • 컴퓨터 관점에서 프로세스는 메모리도 사용하고 운영체제의 CPU스케줄링 알고리즘에 따라서 CPU도 사용,

    필요에 따라 입력과 출력을 하기 때문에 능동적인 존재

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

• 유니프로그래밍

  • 메모리에 오직 하나의 프로세스가 올라온 것을 말함

• 멀티프로그래밍

  • 메모리에 여러 개의 프로세스가 올라온 것을 말함

• 멀티프로세싱

  • CPU가 여러 개의 프로세스를 처리하는 것을 말함

PCB(Process Control Block) 

• 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장

• PCB들은 연결리스트 자료구조로 저장

   

컨텍스트 스위칭

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

   

• 컨텍스트 스위칭이 발생할 때 PCB에서 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경

• 컨텍스트 스위칭이 발생하는 이유는 CPU점유 시간을 초과했거나, I/O요청이 있거나 다른 종류의 인터럽트가 있을 때 발생

프로세스 생성과 종료

• 일반적인 프로세스 생성

  • .exe파일 실행 -> 운영체제 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드 -> 빈 스택과 빈 힙을 만들어 공간 확보 -> 이 프로세스를 관리하기 위한 PCB를 만들어 값을 초기화

  • 운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 한번만 실행 됨

  • 다음의 모든 프로세스는 새로 생성되지않고 0번 프로세스를 fork() 함수로 복사해 생성됨

    • 새로 생성하는 것보다 복사가 더 빠르기 때문

    • 복사된 프로세스는 자식 프로세스

    • 자식 프로세스 입장에서 0번 프로세스는 부모 프로세스

  • fork()함수로 프로세스 복사 후 exec()함수를 실행하면 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게 됨

  • exit()함수는 자식 프로세스가 부모 프로세스에게 정상 종료됨을 알리는 함수

  • 부모 프로세스는 자식 프로세스의 exit status를 읽고 자식 프로세스를 정리

• 부모 프로세스가 자식 프로세스보다 먼저 종료되거나, 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해 exit status를 읽지 못해 메모리에 계속 살아 있는 상태는 "좀비 프로세스"라고 부름

쓰레드

• 운영체제가 작업을 처리하는 단위는 프로세스

• 기존 프로세스를 복사해서 사용하니 메모리를 많이 먹어 쓰레드가 등장

• 쓰레드는 프로세스 내에 존재하는 것으로 1개의 프로세스에 여러개의 쓰레드가 존재 가능

• 한 프로세스 내 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유 => 메모리 절약

• 스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음

• 쓰레드와 프로세스의 장단점

  • 안정성

    • 프로세스 > 쓰레드

    • 프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제가 있어도 다른 프로세스 영향을 받지 않음. 안정성

    • 쓰레는 하나의 프로세스 내에 있기 때문에 프로세스가 문제가 생기면 안의 모든 쓰레드에 문제가 생김

  • 속도, 자원

    • 프로세스 < 쓰레드

      • 프로세스는 서로 고유한 자원을 가지고 있음. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림

      • 쓰레드는 스택을 제외한 영역을 모두 공유하고 있기 때문에 오버헤드가 작음

CPU스케줄링

• 운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU스케줄링이라고 함

• CPU스케줄링에서 스케줄러(운영체제)가 고려해야할 사항

  • 어떤 프로세스에게 CPU리소스를 줘야하는가?

  • CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?

• CPU Burst

  • CPU를 할당받아 실행하는 작업

• I/O Burst

다중큐

• 프로세스 정보를 가지고 있는 PCB는 준비 상태의 다중큐에 들어가서 실행되기를 기다리고 있고 CPU스케줄러에 의해 실행상태로 전환

• 이때 CPU스케줄러는 준비 상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정

• I/O 작업 또한 실행 중인 프로세스에서 I/O 작업이 발생하면 해당 I/O 작업의 종류별로 나뉜 큐에 들어가고 CPU스케줄러는 이를 참조해서 스케줄링

스케줄링 목표

• 리소스 사용률

  • CPU 사용률을 높이는 것을 목표로 함

  • I/O 디바이스의 사용률을 높이는 것을 목표호 함

• 오버헤드 최소화

  • 스케줄링을 하기 위한 계산이 너무 복잡하거나 컨텍스트 스위칭을 너무 자주 X

• 공평성

  • 모든 프로세스에게 공평하게 CPU할당

• 처리량

  • 같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 함

• 대기 시간

  • 대기 시간이 짧은 것을 목표로 함

• 응답 시간

  • 응답 시간이 짧은 것을 목표로 함

• 사용자가 사용하는 시스템에 따라 목표를 다르게 설정해야 함

  • 터치스크린: 응답 시간이 짧게

  • 과학 계산: 처리량이 높게

  • 일반 사용자: 밸런스 유지

FIFO(First In First Out)

• 단순하고 직관적이나 한 프로세스가 완전히 끝나야 다음 프로세스가 시작된다는 단점이 있음

• I/O작업이 있다면 CPU는 끝날 때까지 쉬고 있기 때문에 CPU 사용률이 떨어짐

• 스케줄링의 성능은 "평균 대기시간"으로 평가

• FIFO알고리즘은 프로세스의 Burst Time에 따라 성능 차이가 심하게 나기 때문에 현대 운영체제에서는 잘 쓰이지 않고 일괄처리 시스템에 쓰임

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

 섹션1) 개요

자료구조와 알고리즘이란?

• 자료구조

  • 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄

    • 변수, 배열

• 알고리즘

  • 어떤 문제를 해결하기 위한 확실한 방법

• 데이터가 어떤 자료구조를 하고 있는 지에 따라서 값을 구하는 방식이 달라짐 => 자료구조에 따라 알고리즘이 달라짐

시간복잡도

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

• 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측 => 반복문

• 최악의 경우를 평가하는 Big-O를 많이 사용

  • 성능을 정확하게 표현하진 못함 => 단순히 해당 알고리즘의 입력이 늘어날 때 계산량이 얼마나 늘어나는지 표현하는 방법일 뿐

     

  • O(n): 선형시간 알고리즘, 데이터가 많아지면 그와 비례해서 계산량이 많아짐

  • O(1): 상수시간 알고리즘, 입력의 크기에 상관없이 상수의 시간이 소요

  • O(logn), O(nlogn), O(n^2), O(2^n), O(n!) 등

배열

• 자바스크립트에서 배열은 불연속적으로 할당, 내부적으로 연결해서 사용자에게 배열인 것처럼 보이게 함

연결리스트(Linked List)

• 빈 메모리 공간 아무곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열 초기 크기를 몰라도 됨

• 삽입, 삭제가 쉽다는 장점

• 데이터들이 전부 떨어져있기 때문에 바로 접근할 수 없다는 단점

  • 데이터참조 O(n)의 성능

스택(Stack)

• Fist In Last Out(FILO)

• 먼저 들어간 데이터가 나중에 나오는 규칙

• head에만 삽입, 제거하는 자료구조

큐(Queue)

• First In First Out(FIFO)

• 먼저 들어간 데이터가 먼저 나오는 규칙

• 운영체제에서 쓰는 FIFO 스케줄링: 먼저 들어온 프로세스 순으로 CPU가 처리

• head에서 삽입하고 tail에서 제거하는 자료구조

덱(Deque)

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

• 스택, 큐 전부 구현 가능

해시테이블(Hash Table)

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

• 프로그래밍 언어에 따라서 조금씩 다른 이름을 가지고 있음

  • 해시, 맵, 해시맵, 딕셔너리

• 장점

  • Key만 알면 Value에 O(1)의 성능으로 읽기 가능

  • 삽입, 수정, 삭제 다 O(1)

• 단점

  • 메모리를 많이 차지함

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

• 해시충돌

  • 충돌을 해결하기 위해서 해당 인덱스를 연결리스트로 구성해 데이터들을 연결 => O(n)

셋(Set)

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

• 해시 테이블을 사용한다고 해서 해시 셋(Hash Set)이라고도 불림

회고

운영체제를 처음 공부해서 그런지 낯선 단어들이 굉장히 많았다. 그래서인지 생각했던 시간보다 많이 소요되었다.

알고리즘 개념은 어느정도 알고 있었지만 구현을 하려니 어려웠고 이것 또한 생각했던 것보다 시간이 많이 소요되었다...

반복하다보면 익숙해지겠지 🙂 그리고 강의 들으면서 길게 작성하는 방법보단 강의의 핵심만 작성하도록 해야겠다.