본문 바로가기

Computer Science112

[알고리즘] ep1-3) 힙(heap) *완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종 + 영단어 heap: 무엇인가를 차곡차곡 쌓아 올린 더미+ 자료구조의 힙(Heap)과 컴퓨터 메모리의 힙 영역(Heap Area)은 완전히 다른 개념이다  [힙의 활용]우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 각 요소가 우선순위를 가지는 큐힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, O(nlog(n))의 시간 복잡도를 가진다그래프 알고리즘: 크루스칼 알고리즘, 다익스트라 알고리즘 등에서 우선순위 큐를 활용해 최소 신장 트리,.. 2024. 7. 3.
[알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등  [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬  ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬   2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용   일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙)       출처 및 참고: 알고리즘-원리와.. 2024. 7. 3.
[알고리즘] ep1-2) 버블정렬, 선택정렬, 삽입정렬 컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유가 바로 이진 탐색이 가능한 데이터를 만들기 위해서이다이진탐색의 시간복잡도: O(log(n))   ㅇ제자리(in-place): 추가적인 메모리 공간을 거의 사용하지 않고, 주어진 데이터 구조 내에서만 작업을 수행하는 것일반적으로 어떤 정렬 알고리즘이 정렬 대상 개체를 위해 필요한 메모리에 추가하여 오직 상수 메모리만을 사용한다면, 해당 정렬 알고리즘이 제자리(in-place)에서 수행한다고 얘기한다 장점메모리 효율성: 추가적인 메모리 공간을 거의 사용하지 않으므로 메모리 효율성이 높다캐시 효율성: 메모리 내에서 직접 데이터 이동이 이루어지기 때문에 캐시 효율성이 높다단점복잡한 구현: 일부 복잡한 알고리즘의 경우 제자리 알고리즘으로 구현하기 어려울 수 있다비.. 2024. 7. 2.
[운영체제] ep7) Virtual Memory ㅁVirtual Memory(가상 메모리): m.m.에 프로그램의 일부만 남기고 나머지는 HDD에 적재- 현대 시스템의 99%가 가상 메모리 시스템 ※ 멀티 프로그래밍 레벨이 높을수록 좋은 시스템이다멀티 프로그래밍 레벨: 메모리에서 동시에 실행되는 프로세스의 숫자 1. OS가 프로그램 조각(resident set)을 m.m.로 가져온다- resident set: 프로그램 조각(Page들의 집합)2. 필요한 프로그램이 m.m.에 없으면 interrupt 발생!3. 필요한 프로그램을 가져오기 위해서 OS가 process를 blocked시킨다4. OS가 HDD에 I/O 읽기 요청을 한다5. HDD가 I/O 작업을 처리하는 동안 다른 프로세스가 디스패치된다6. 아까 blocked된 프로세스를 다시 ready 상.. 2024. 7. 2.
[운영체제] ep6) Memory Management 7단원은 8단원 VM(Virtual Memory)를 위한 빌드업이라 생각하면 된다메모리 관리에 있어서 중요한 요점 3가지- Relocation: 기준이 1000번지면 모든 주소에 1000을 더해 Relocation이 필요하다[Relative Address + Base Resister -> Physical Address]- Protection: 무슨 일이 있어도 프로그램을 실행할 때는 이 프로그램이 자기에게 할당된 메모리 영역 외에는 Access 하면 안 된다- Sharing    메모리를 관리하는(나누는) 방법 2가지1. Fixed Partitioning- Equal-size partitions- Unequal-size partitions  2. Dynamic PartitioningExternal fra.. 2024. 7. 2.
[운영체제] ep5) Concurrency: Deadlock and Starvation ㅁDeadlock의 발생 조건 4가지① Mutual Exclusion(상호배제)② Hold-and-Wait③ No preemption(비선점)④ Circular Wait: 여러 프로세스가 자원을 할당받은 후, 다른 프로세스가 점유하고 있는 자원을 추가로 요청하면서 서로 대기하는 상황이 순환 형태로 이루어지는 것  ㅇ자원 할당 그래프(Resource Allocation Graphs)       ㅁ데드락 해결방법 3가지1. Deadlock Prevention: 자원할당 규칙을 만든다(사전에 차단)④ Circular Wait를 깨기 위해 자원에 번호를 매긴다 - 자원을 요청할 때 번호 순서대로 요청 - 낭비 多, 실제로 사용은 x데드락이 발생하면 큰일이 나는 시스템이 아닌 이상 데드락 prevention보다는.. 2024. 6. 30.
[운영체제] ep4-3) Concurrency: Mutual Exclusion and Synchronization Concurrency 방안 3가지1. Software Approaches - 알고리즘을 잘 설계2. HW instruction을 이용3. OS가 제공하는 동기화 툴 이용 (e.g. 세마포, 모니터)1번과 2번에 이어 3번에 대해 알아보자 3. OS가 제공하는 동기화 툴 이용2가지에 대해서 다룰 거다ㅇ세마포(Semaphore): 정수 변수 + (blocked)큐가 결합된 구조체 변수오로지 3개의 동작만 수행한다 ① Initialize: 세마포를 0이나 양수값으로 초기화(음수값으로 초기화 하는 건 의미가 없다) ② semWait: 세마포값 -1, "blocked 큐에서 wait!"if (세마포값 >=0) 통과else if(세마포값  ③ semSignal: 세마포값 +1, "blocked 큐에서 ready 큐.. 2024. 6. 29.
[운영체제] ep4-2) Concurrency: Mutual Exclusion and Synchronization Concurrency 방안 3가지1. Software Approaches - 알고리즘을 잘 설계2. HW instruction을 이용3. OS가 제공하는 동기화 툴 이용 (e.g. 세마포, 모니터)저번 1번에 이어 2번에 대해서 알아보자 2. HW instruction을 이용 - 수정이 불가능하며 중간에 인터럽트로 중단되지도 않는다 HW적으로 움직인다2가지 HW instruction이 있다① Compare & Swap Instruction: 비교하고 같으면 swap// word: 어떠한 저장공간의 주소// 같다면 word를 newval로 swap한다// compare_and_swap 실행 전 word에 저장되어 있던 값을 returnint compare_and_swap(int* word, int test.. 2024. 6. 29.
[운영체제] ep4-1) Concurrency: Mutual Exclusion and Synchronization ㅁ동시성(Concurrency): 여러 작업이 짧은 시간 간격으로 번갈아 가며 수행됨으로써 동시에 처리되는 것처럼 보이게 만드는 것현대 OS는 멀티 프로그래밍, 멀티 프로세싱 등의 기법으로 동시성을 사용하는 데에 있어 발생하는 문제들을 해결해야만 한다 상황) 은행 계좌 파일에 있는 데이터 x를 저장, 처음 잔고는 0원이다 ㅇRace Condition: 결국에는 둘 중에서 마지막으로 작업한 결과만이 남는다Race Condition의 발생을 막기 위해 critical section의 mutually exclusive한 실행이 필요하다 ㅇcritical section(임계구역): Race Condition이 발생할 수 있는 코드 (전혀 예측할 수 없음)critical section은 동시에 실행시키면 안된다.. 2024. 6. 29.

티스토리툴바