인프런 워밍업 클럽 - CS Week 1
그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)자료구조 & 알고리즘자료구조 : 데이터가 어떤 구조로 저장되고, 어떻게 사용되는지를 나타낸다.자료구조에 따라서 결과를 얻기 위한 처리 방법이 달라진다.알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법시간 복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간Bit-Ω : 최선의 시간 복잡도Big-O : 최악의 시간 복잡도가장 많이 사용된다.Big-θ : 평균의 시간 복잡도ADT(Abstract Data Type)데이터의 논리적인 동작을 정의한다.구현 방법을 명시하지 않고, 자료구조의 특성과 연산만을 설명한다.내부 구현 세부사항은 숨기고 인터페이스만을 제공한다.Array배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다.삽입, 삭제의 성능이 좋지 않다.Linked List배열의 단점인 삽입, 삭제의 성능을 보완하기 위한 자료구조특정 데이터를 찾고 싶다면 노드를 순차적으로 순회해야 한다.저장하려는 데이터들을 메모리에 분산하여 할당하고, 해당 데이터를 서로 연결한다.노드를 사용하여 데이터들을 저장하고, 각 노드가 다음 노드를 가리키도록 한다.첫 노드의 주소만 알고 있으면 그 이후의 모든 노드에 접근할 수 있다.StackLIFO(Last-in First-out)단방향 Linked List를 사용하여 구현할 수 있다.head를 사용하여 스택을 간단하게 구현할 수 있다.데이터 삽입을 무조건 첫 번째 인덱스에 수행한다.QueueFIFO(First-in First-out)양방향 Linked List를 사용하여 구현할 수 있다.Deque데이터의 삽입과 제거를 head와 tail에서 자유롭게 할 수 있는 자료구조Hash TableHash Function해시 함수는 키(key)를 입력받아 해당 키의 저장 위치(버킷 또는 인덱스)를 결정하는 계산을 하는 함수좋은 해시 함수 ⇒ 데이터를 골고루 분배시켜주는 함수 Hash Collision해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력 값에 대해 동일한 해시 값을 출력하는 상황을 의미Hash 충돌이 발생한 곳의 Value들을 연결리스트로 구성하여 데이터들을 연결한다.기존값과 새로운 값을 동시에 저장할 수 있다.찾고자 하는 Value가 나올 때까지 연결리스트를 탐색한다.→ O(n)의 성능을 갖는다.Set데이터의 중복을 허용하지 않는 자료구조HashTable을 사용하여 구현할 수 있다.→ HashTable을 사용하기 때문에 HashSet이라고도 한다.→ HashTable의 value 값은 사용하지 않고 key만 사용하여 구현한다.(key가 key와 value의 역할을 수행한다.)그림으로 쉽게 배우는 운영체제OS가 하는 일프로세스 관리 : 여러 개의 프로그램들을 동시에 수행할 수 있게 한다.메모리 관리 : 모든 프로그램은 메모리에 올라가서 동작한다.H/W 관리 : 사용자가 직접 H/W에 접근하는 것을 막는다.File System 관리Program저장장치에 저장된 명령문의 집합체저장 장치만 사용하는 수동적인 존재Process실행중인 프로그램저장장치에 저장된 프로그램이 메모리에 올라갔을 대 프로세스라고 한다.메모리, CPU, I/O 작업을 수행하는 능동적인 존재Multi-Programming메모리 관점메모리에 여러개의 프로세스가 올라온 상태Multi-ProcessingCPU 관점CPU가 여러 개의 프로세스를 처리하는 것을 의미PCB(Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장한다.PCB들은 연결 리스트로 저장된다.운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.Context Switching프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 전환하는 작업작업 과정에서 PCB의 내용(프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등)이 변경된다.Process의 생성OS가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 수행된다.→ 그 이후에 생성되는 프로세스는 fork()를 사용하여 복사해서 사용된다.→ 새로 생성하는 것보다 복사를 하는 것이 더 빠르기 때문좀비 프로세스부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아있는 상태Thread프로세스 내에 존재하고, 1개 이상이 존재할 수 있다.하나의 프로세스 내에 있는 쓰레드들은 프로세스의 PCB, Code, Data, Heap 영역을 공유한다.Stack은 공유하지 않고, 쓰레드 마다 하나씩 갖고 있다.OS에서 작업을 처리하는 단위이다.Process vs Thread안정성Process는 독립적이기 때문에 서로 영향을 받지 않는다.Thread는 하나의 Process를 공유하기 때문에 하나의 Thread에 이상이 생기면 다른 Thread에도 이상이 전파될 수 있다.⇒ Process가 유리속도와 자원각각의 Process는 서로 고유한 자원을 갖는다.코드, 데이터, 힙, 스택 영역을 전부 따로 두고 있다.Process간에 통신을 하려면 IPC를 사용해야 해서 오버헤드가 크고 속도가 느리다.쓰레드는 하나의 Process의 자원을 스택 영역을 제외한 영역을 모두 공유하기 때문에 오버헤드가 느리다.CPU Scheduling목표목표들을 전부 만족할 수는 없다.→ 목표들에 따라 Trade-Off가 있기 때문ex) 처리량 ↑ ⇒ CPU 오래 할당, 응답시간 ↓ ⇒ 여러 프로세스에 CPU를 골고루 할당⇒ 처리량과 응답시간 사이에 Trade-Off가 발생한다.리소스 사용률CPU 사용률 높이기I/O 디바이스의 사용률 높이기오버헤드의 최소화Context Switching시에 발생하는 오버헤드를 최소화하는 것공평성모든 프로세스에게 우선순위에 따라 공평하게 CPU가 할당되어야 한다.처리량같은 시간내에 더 많은 처리를 할 수 있게 하는 것대기시간작업을 요청하고 실제 작업이 실행되기 전까지 대기하는 시간이 짧은 것응답시간사용자의 요청이 얼마나 빨리 요청하는지Retrospect아쉬운 점커리큘럼을 잘못 봐서 운영체제 쪽은 쉬는 날에 몰아서 들었다.커리큘럼을 명확하게 파악하고 당일에 들을 강의들을 정확히 정리해야겠다.잘한 점매일매일 빠지지 않고 강의를 들은 점매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것
