본문 바로가기
반응형

CS

 (23)
Blocking vs Non-blocking / Sync vs Async Blocking vs Non-blocking 처리되어야하는 하나의 작업이 전체 작업 흐름을 막느냐 (Blocking), 막지 않느냐(Non-blocking) 에 대한 관점이다 즉, 제어권이 누구한테 있느냐가 포인트이다 Blocking Blocking 의 경우, 제어권이 호출하는 쪽에 있다 Non-blocking 반대로 Non-blocking 의 경우, 제어권이 작업을 시킨 주체에게 있다 Synchronous vs Asynchronous 처리해야할 작업들을 어떠한 흐름으로 처리할 것인가의 관점이다 호출되는 함수의 작업 완료 여부에 따라 이어지는 작업을 누가 처리하느냐의 차이이다 Synchronous 호출하는 함수 A가 호출되는 함수 B의 작업 완료 후 리턴을 기다리거나, 바로 리턴받더라도 미완료 상태이면 ..
DB 트랜잭션 & 트랜잭션 격리수준 트랜잭션이란? 여러 쿼리를 논리적으로 하나의 작업으로 묶어 주는 것 트랜잭션의 4가지 특징 : ACID Atomicity : 원자성 한 트랜잭션의 연산이 모두 성공하거나(commit), 모두 실패해야한다 (rollback) Consistency : 일관성 한 트랜잭션 이전과 이후의 데이터베이스 상태가 유효해야한다 즉, 데이터베이스의 제약이나 규칙을 만족해야한다 Isolation : 독립성 모든 트랜잭션은 다른 트랜잭션으로부터 독립되어야한다 둘 이상의 트랜잭션이 동시 실행되고 있을 때 어떤 트랜잭션도 다른 트랜잭션 연산에 끼어들 수 없다 durability : 지속성 한 트랜잭션이 성공적으로 수행되었다면 결과는 영구히 반영되어야 한다 트랜잭션이 동시 접근 시 발생되는 현상 Dirty Write : 커밋되지..
[운영체제] Context Switching Context 란? CPU가 어떤 프로세스를 실행하기 위해 필요한 프로세스의 정보들로, 이 정보들은 PCB(Process Control Block)에 저장된다 PCB(Process Control Block) 포인터 : 프로세스의 현재 위치 저장 프로세스 상태 : 생성(new), 준비(ready), 실행(running), 대기(waiting), 종료(terminated) 저장 프로세스 번호 (PID) : 프로세스에 할당되는 고유한 ID 프로그램 카운터 (제어 레지스터) : 다음 실행될 명령어의 주소를 가르킴 스택 포인터 (데이터 레지스터) : 현재 스택 영역의 top을 가르킴 Process State Context Switching Interrupt reference https://math-coding.t..
[운영체제] Program vs Process vs Thread Program 어떤 작업을 위해 실행할 수 있는 정적인 파일 ex) file system 의 .exe file Process 메모리에 올라와 CPU를 할당받아 실행중인 동적인 프로그램 Process의 특징 프로세스는 각각 code, data, stack, heap의 구조로 되어있는 독립된 메모리 영역을 할당 받는다. 각 프로세스는 별도의 주소 공간에서 실행되어 메모리 공간을 공유할 수 없다. 따라서 다른 프로세스의 자원에 접근하려면 프로세스간 통신(IPC)을 사용해야한다. 또한 프로세스는 최소 하나 이상의 Thread를 포함한다. 각 영역은 다음과 같은 역할을 한다. code(text) : 실행할 프로그램의 코드가 저장. CPU는 이 영역에서 명령어를 하나씩 가져와 처리한다. data : 전역 변수와 정..
[알고리즘] Heap Sort Heap Sort 최대 힙, 최소 힙 구조를 통해 정렬하는 알고리즘 Heap 이란? 최솟값이나 최댓값을 빠르게 찾아내기 위해 사용되는 구조로 완전 이진 트리를 기반으로 하는 트리이다 각 노드의 값이 자신의 자식노드가 가진 값보다 크거나 같다면 최대 힙 (Max Heap) 각 노드의 값이 자신의 자식노드가 가진 값보다 작거나 같다면 최소 힙 (Min Heap) Process 1. 완전 이진트리 형태의 최대 힙을 만든다 2. 힙에서 하나씩 데이터를 꺼내어 배열의 맨 뒤에 저장한다 이 때 최댓값부터 꺼내지므로 내림차순으로 정렬된다 3. 남겨진 데이터는 최대 힙을 유지한다 heapify 힙 성질을 만족하도록 하는 연산을 heapify 라고 한다 예를 들어 최대 힙의 경우 루트 노드부터 리프 노드까지 부모 노드가..
[알고리즘] Counting Sort Counting Sort 데이터의 크기 범위가 양의 정수이며, 값의 범위가 메모리 사이즈를 넘지 않는 경우 값을 카운팅해 정렬하는 알고리즘 Process 1. 최댓값을 찾는다 2. 최댓값 + 1 크기의 카운팅 배열을 만든다 3. 데이터를 카운팅 배열의 인덱스와 매핑해 갯수를 센다 4. 카운팅 배열을 조회하며 카운트만큼 출력한다 Code numbers = [1, 0, 3, 2, 4, 3, 2, 2, 1, 1, 1, 1, 5, 3, 3, 4, 5] k = 5 counts = [] result = [] length = len(numbers) counts = [0] * length for num in numbers: counts[num] += 1 for num, cnt in enumerate(counts): f..
[알고리즘] Merge Sort Merge Sort Divide and Conquer(분할정복) 방법을 통해 구현 Pivot 없이 정확히 반씩 나누어 나중에 정렬하는 알고리즘 Process 1. 리스트 길이가 2 이상일 때 절반으로 분할한다 (divide) 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다 (conquer) 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병하며, 정렬 결과를 임시배열에 저장한다 (combine) 4. 임시 배열에 저장된 결과를 원래 배열에 복사한다 (copy) Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) def merge(start, middle, end): temp = [] i, j =..
[알고리즘] Quick Sort Quick Sort Divide and Conquer(분할정복) 방법을 사용 기준 데이터인 Pivot을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘 Process 1. 기준 데이터(Pivot)를 고른다 2. 피벗 앞에는 피벗보다 값이 작은 데이터, 피벗 뒤에는 피벗보다 값이 큰 데이터들이 오도록 배열을 둘로 나눈다 이 때 피벗값은 위치가 정해진다. 3. 분할된 두개의 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) def quickSort(start, end): global numbers if start >= end: re..
반응형

티스토리툴바