본문 바로가기

Computer Science116

[운영체제] 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.
[자료구조] 후기 코딩은 자고로 독학이라 생각한다 스스로 찾아보고 배우면서 시행착오를 겪어야지만 진정한 실력이 는다고 생각한다 이런 마인드를 가진 나였지만.. 자료구조 수업은 정말 힘들었다 비유를 하자면 알파벳을 알려주고서 바로 영작을 하라는 수준이었다c언어로 연결리스트를 처음 구현할 때의 그 막막함이란.. 진짜 심장이 턱! 하고 막히는 기분이었다 평소에 머리가 나쁘단 소리를 들어본 적이 없고, 수학 잘한다는 소리를 듣던 내가 그 순간만큼은 정말 심각한 바보가 된 것 같았다 손을 쓸 도리가 없었다 그러한 허탈감과 죄책감은 나의 오기를 발동하여 내 안에 있던 독기를 깨우는 듯했다 아마 연결리스트 문제를 세종대 OJ에 170번 넘게 submit 한 사람은 내가 유일하지 않을까..라는 생각이 든다 하지만 부끄러움은 단 1도 없.. 2024. 6. 25.
[자료구조] ep8) 분리집합(Disjoint Set) ㅇ분리집합 ADT: 교집합이 없는 집합들서로소집합이라고도 불리며 Union-Find라고도 한다 소속 관계가 분명해야 하는 데이터를 다룰 때 유용하다목적: 원소가 어느 집합에 귀속되어 있는지 (find 함수) 직접 응용: 동치관계(e.g. 그래프), 최소신장트리간접 응용: 알고리즘 구현, 저료구조 구현  - set find(e): 원소 e가 속한 집합을 반환- union(x, y): 집합 x, y를 통합- int size(S): 집합 S 원소의 수를 반환  [구현 방법 2가지]1. 리스트(or 배열)에 기초한 구현 find는 빠르고 union은 느리다2. 트리에 기초한 구현find는 느리고 union은 빠르다  1-1 리스트에 기초한 구현: 분리집합 집단을 레코드의 배열로 표현  1-2 배열에 기초한 구현.. 2024. 6. 11.
[자료구조] ep7++) 결정 트리(decision tree) - 양자택일식 문답시스템 ㅇ결정 트리(decision tree): 의사결정 과정과 연관된 이진트리- 내부노드: yes/no로 답 할 수 있는 질문- 외부노드(리프): 결정    활용) 프로그램 요구사항 다음과 같이 한 프로그램 내에서 양자택일식 문답시스템의 구축과 사용을 연속하여 지원하는 프로그램을 작성하라. 1) 문답시스템 구축 지원 기능 -  결정트리는 배열 또는 연결리스트 가운데 하나를 이용하여 구축되어야 한다. -  1회의 상담은 최소 3회 ~ 최대 5회의 문답을 통해 완료되도록 제한하라(즉, 상담설계자가 이 시스템을 이용하여 최소 8개 ~ 최대 32개의 결정을 포함하는 결정트리의 구축을 지원할 수 있어야 한다). -  설계된 결정트리를 프로그램을 통해 구축하라(즉, buildDecisionTree를 1회 호출). 2) .. 2024. 6. 11.
[자료구조] ep7+) 이진 트리 구현 및 탐색 이번 문제에서는 트리가 고정되지 않고 트리의 모양이 입력으로 주어진다. 1. 트리 만들기 (구현)◦ 트리는 연결이진트리로 구현하며 각 노드에 저장되는 정보는 아래와 같다.◦ 선위순회 순서로 각 노드에 대한 정보가 주어지면, 루트노드부터 확장해 가는 방식으로 트리를 구성할 수 있다.- 노드 번호는 유일한 양의 정수며, 노드 번호에 특별한 순서는 없다. - 각 노드에 대한 정보는 괄호에 싸인 세 개의 정수, 즉 (x y z)로 표현된다.- 여기서 x는 해당 노드의 번호, y는 x의 왼쪽 자식 노드의 번호, z는 x의 오른쪽 자식 노드의 번호를 나타낸다. 해당 자식이 없는 경우에는 번호 0이 주어진다.    2. 트리 탐색◦ 트리 탐색은 루트노드에서 시작하여 자식 링크를 따라 내려가면서 진행된다.- 탐색 도중.. 2024. 6. 11.
[자료구조] ep7-2) 트리 순회 트리 순회(tree traversal): 트리의 노드들을 체계적인 방식으로 방문하는 것을 의미트리의 주요 순회로는 크게 3가지가 있고 추가적인 순회로 또 2가지가 더 있다 1. 선위순회(predorder traversal): Root > Left > Right  응용: 구조적 문서를 인쇄, 계층적 파일 시스템의 모든 폴더들을 나열 void preorderTraversal(NODE* node) { // 재귀적 성질을 이용한다 if (node == NULL) { return; } printf(" %d", node->data); // Root preorderTraversal(node->left); // Left preorderTraversal(node->right); /.. 2024. 6. 10.

티스토리툴바