분류 전체보기 (174) 썸네일형 리스트형 [ 운영체제 ] 데드락(Deadlock)의 개념과 발생조건 저번 시간에는 세마포어에 대해 알아봤었다. 세마포어는 Block & Wakeup 구조를 통해 spinlock 문제를 해결했지만 이로 인해 또 다른 문제가 발생한다고 했었다. 그 중 하나가 Deadlock and Starvation 문제다. 데드락은 아래 그림과 같이 서로 다른 두 프로세스가 wait 상태에 있는 자원을 요청하는 경우 발생한다. 만약이 이 문장을 이해했다면 데드락의 개념은 이해한 것이다. 이번 글에서는 데드락이 정확하게 무엇인지, 어떤 상황에서 발생하는지 알아볼 것이다. 데드락(Deadlock)의 개념 - 식사하는 철학자 문제 '식사하는 철학자 문제'는 데드락의 개념을 설명할 때 정말 많이 사용되는 예시다. 아래의 상황을 가정하고 시작한다. 좀 말이 안 되기는 하지만 개념 설명을 위한 가정.. [ 백준 17086 ] 아기상어 2 (C++) https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net bfs로 금방 해결할 수 있는 문제다. 아이디어는 매우 간단하다. 아래를 구현할 수 있으면 된다. 모든 칸마다 안전 거리를 구하고, 최대값을 계속 갱신한다! 나는 문제를 풀기 위해 세 개의 배열을 사용했다. int init[50][50] → 초기 입력값 (변하지 않음) int use[50][50] → bfs 탐색할 때 사용하는 배열 (계속 바뀜) int visit[50.. [ 백준 14226 ] 이모티콘 (C++) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 숨바꼭질2 문제와 거의 똑같은 문제다. 경로가 겹칠 수 있으므로 방문 처리는 pop과 동시에 해준다. 큐에 들어가는 원소는 총 아래의 세가 정보를 담고 있어야 한다. 1. 모니터 속 이모티콘 개수 (monitor) 2. 클립보드 이모티콘 개수 (board) 3. 시간 (time) 나는 obj라는 구조체를 선언해 세 가지 정보를 담았다. typedef struct{ int monitor; int bo.. [ 운영체제 ] 동기화 방법3 - Semaphores 세마포어는 Mutex의 spin lock 문제를 해결해주는 동기화 방법이다. 참고로 세마포어는 유명하신 '다익스트라' 님께서 고안해내신 알고리즘이다. 다익스트라 알고리즘의 그 다익스트라 맞다. 정말 대단하신 분인 것 같다. Mutex에서 lock은 boolean 값으로 참 또는 거짓의 값만 가진다. 반면에 세마포어에서는 boolean 대신 integer 값의 변수를 이용한다. 엄밀히 말해서 세마포어는 구조체 형태인데, 구조는 아래와 같다. typedef struct{ int value; // 사용 가능한 자원의 수 struct process *list; // waiting queue }semaphore; 세마포어의 집입 구역과 퇴출 구역은 각각 wait() 함수와 signal() 함수가 담당한다. 세마포.. [ 백준 13913 ] 숨바꼭질 4 (C++) https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질2 문제와 거의 비슷한데 경로까지 출력해야되는 문제다. parent 배열을 만들어 경로를 역추적 하는 것이 핵심이다. 부모를 찾는 아이디어는 합집합 찾기와 비슷하다. parent[현재 위치] = 이전 위치 // 목적지에 도달한 경우 pre1 = parent[to] parent[pre1] = pre2 { pre2 - pre1 - 목적지 } 경로가 성립한다 위.. [ 백준 13549 ] 숨바꼭질 3 (C++) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 그냥 bfs로 풀면 된다. 움직일 수 있는 경우의 수는 세 가지이므로 세 가지 조건에 대해 방문처리를 해주고 큐에 push 해주면 된다. 다만 조건문의 순서가 중요하다. 순서가 정답 코드와 동일해야 정답처리된다. 현재 위치를 Now라고 했을 때 조건문의 순서는 아래와 같다. 1. Now * 2 1 → 2 로 이동하는 경우를 생각해보자. 아래 두 가지 방법이 있다... [ 운영체제 ] 동기화 방법2 - TestAndSet(), Mutex Locks 저번 시간에는 피터슨 방법에 대해 다뤘었다. 피터슨 방법의 단점 및 문제점을 다시 한번 살펴보자. 1. 소프트웨어적 방법 - 속도가 느리다 2. 프로세스가 두 개인 경우에만 적용 가능 3. 자원을 많이 소모한다(Busy Waiting) 4. 현대 컴퓨터에서 정상 작동 하지 않음 이번에 소개하는 방법은 피터슨 방법에서 Busy Waiting을 제외한 나머지 단점들을 보완한 방법이다. 소프트웨어적인 방법으로 경쟁 상태를 해결하는 것은 컴퓨터 구조적으로 문제가 발생할 수 있기 때문에 이번에는 하드웨어적인 방법으로 접근한다. 하드웨어적 방법은 원자적 실행 단위를 보장하므로 코드의 순서가 바뀌거나 하는 일은 없다. Synchronization Hardware: TestAndSet() TestAndSet()은 하드.. [ 운영체제 ] 동기화 방법1 - Peterson's Solution C.S Algorithm의 문제점 임계구역의 일반적인 형태는 아래와 같다. do{ wants[i] = true; // i 프로세스가 공유 자원을 사용하겠다고 선언 while(wants[j]) {;} // j 프로세스가 공유 자원을 사용중이면 진입 불가(진입구역) CRITICAL SECTION wants[i] = false; // i 프로세스가 공유 자원 사용 완료 후 반납(퇴출구역) REMAINDER SECTION } while(TRUE) 기본적인 구조는 잘 갖춰져 있다. 그렇다면 저번 시간에 살펴본 임계구역의 세 가지 요구사항을 만족하는지 살펴보자. 기본적으로 상호배타적 접근은 전제로 깔고 가기 때문에 진행과 한계 대기만 확인하면 된다. 상호 배타도 뒤에서 따져보기 때문에 천천히 보시기를... 이게 무.. 이전 1 ··· 10 11 12 13 14 15 16 ··· 22 다음
