분류 전체보기(78)
-
[OS] Multi-Processing vs Multi-Thread (+ IPC, Multi-Core)
1. Multi-Programming - Multi-programming의 목적: CPU 이용 최대화하기 위해 항상 어떤 process 실행되도록 하는 것 → 시분할: 각 프로그램 실행되는 동안 사용자와 상호작용 할 수 있도록 process 사이에서 CPU 빈번하게 교체하는 것 2. Multi-Processing (다중 처리기) - Multi-core 라고도 함 - CPU scheduling (= process scheduling) - CPU 여러 개 사용 (매우 밀접한 통신을 하는 둘 이상의 processor, 즉 CPU 가짐) - n개의 CPU를 가지는 multi-processor 하나가 1개의 CPU를 가지는 single-processor n개보다 비용 적게 듦 - 기능 적절히 분산된 경우 한 CP..
2023.10.11 -
[OS] Memory Management
- 레지스터는 일반적으로 CPU 클록 1 사이클 내에 접근 가능 - 메인 메모리의 경우 많은 CPU 클록 사이클 소요, CPU가 필요한 데이터가 없어 명령어 수행 못하는 stall 현상 발생 가능 - 이를 해결하기 위해 CPU와 메인 메모리 사이에 빠른 속도의 메모리(캐시)를 추가 Base Register, Limit Register - Base Register: 가장 작은 합법적인 물리 메모리 주소의 값 저장 - Limit Register: 주어진 영역의 크기 저장 → Base register, Limit register는 논리 주소 공간을 정의함 Hardware Address Protection 메모리 공간 보호 - 운영체제의 메모리 공간이나, 다른 사용자 프로그램의 메모리 공간의 접근이 일어나면 운..
2023.10.11 -
[OS] Synchronization & Deadlock
Synchronization 필요한 이유 - Process는 병행하게, 또는 병렬로 실행될 수 있음 - 공유 데이터에 동시 접근하게 되면 data inconsistency 발생할 수 있음 - Cooperating process들의 질서있는 실행을 위한 메커니즘이 필요함 Synchronization 관련 용어 - 동기화: 한정적인 자원에 여러 thread가 동시 접근하면 문제 발생하므로 thread에게 처리 권한을 주거나 순서 조정 - Race Condition 경쟁상황: process 간 자원을 사용하려고 경쟁하는 것 - Critical Section 임계구역: 공유 자원에 접근하는 process 내부의 코드 영역 한 process가 이 영역을 수행 중일 때 다른 process가 자신의 영역 수행하면 문..
2023.10.11 -
[Algorithm] 4. Divide and Conquer
✔️ Divide and Conquer? 1) 전략 - 주어진 문제의 입력을 분할하여 문제를 해결하는 방식 - 분할한 입력에 대해 동일 알고리즘을 적용하여 해 계산, 이들의 해를 취합하여 원래 문제의 해 얻음 - 부분문제(subproblem): 분할된 입력에 대한 문제, 부분해: 부분문제의 해 - 부분문제는 더이상 분할할 수 없을 때까지 계속 분할 2) 과정 - 분할(divide): 해결되기 쉽도록 문제를 여러 개의 작은 부분으로 나눔 - 정복(conquer): 나눈 작은 문제를 반복하여 각각 해결 (Top-Down) - 통합(combine): 해결된 작은 답들을 모아 원래 문제의 해답 구함 (Bottom-Up) 3) 종류 - Sorting: merge sort, quick sort - Binary tr..
2023.10.11 -
[Algorithm] 3. Brute Force Algorithm
✔️ Brute Force Algorithm - 가장 간단하고 직접적인 방식으로 문제를 해결 - 효율적이고 정교한 알고리즘보다 많은 작업을 할 가능성이 높음 - 그렇지만 구현하기가 쉬우며 이로 인해 더 효율적일 수도 있음 - Exhaustively enumerate all the possibilities. 1) Selection Sort - 현재 idx 값 ↔ 배열에서의 최솟값 for i ← 0 ~ n-2 min ← i for j ← i+1 ~ n-1 if A[j] < A[min] min ← j swap A[i] and A[min] - Time efficiency: O(n^2) 2) Bubble Sort - 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환 for j = 1 to n for i = 0 ..
2023.10.11 -
[Algorithm] 2. 탐색과 정렬 알고리즘
✔️ Searching Algorithm 1) 자료 탐색? - 수많은 자료 중 원하는 자료 찾는 작업 - 컴퓨터에서 처리되는 핵심 알고리즘 중 하나 - Search Key (탐색 키): 탐색할 때 기준이 되는 값 (항목과 항목을 구별하는 값) - 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등 - ex) 컴퓨터에서 저장된 파일 찾기: 파일 탐색기, 위치 모르면 완전 탐색 (exhaustive search) 2) 자료 탐색 과정 1) 탐색 기준 정하기: 탐색 키 선정 2) 자료 비교하기: 탐색 키와 자료 리스트에 포함된 자료들의 비교 ⭐️ 3) 자료 찾기: 탐색의 성공, 실패에 대한 판가름 3) 자료 탐색 결과 - 존재하는 경우: 탐색 키에 해당하는 인덱스 번호 반환 - 존재하지 않는 경우: 일..
2023.10.11