CS (46) 썸네일형 리스트형 교착 상태 교착 상태 방지 -교착 상태 4가지 필요조건중 한개이상 불만족 -상호배타 -> 자원공유 가능 -보유 및 대기 -> 젓가락 놓기 -> 자원활용률 저하, 기아발생 가능 -비선점 -> 선점 가능 -환형대기 -> 패턴을 바꿈 교착 상태 검출 및 복구 -주기적으로 검사 -교착상태 발생시 복구 -검사에 따른 Overhead(계산, 메모리) 발생 -복구: 프로세스 일부 강제종료, 강제로 선점하여 할당 교착 상태 무시 -실제로 잘 일어나지 않음(무시) -발생시 PC 재시동 데이터 경로(1) 데이터 경로 -CPU가 명령어 실행을 위해 데이터를 경유시키는 경로 -단일 사이클 방식: 한 명령어당 한 사이클(하드웨어 1번씩만 사용가능) -다중 사이클 방식: 한 명령어에 여러개의 사이클(하드웨어 한번이상 사용가능) 단일 사이클 방식 -R형식(1): addi $rd, $rs, $rt // $rd 덱(Deque) 덱은 무엇인가? -양쪽 끝에서 삽입과 삭제가 가능한 자료구조 덱의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞뒤의 원소 확인이 O(1) 제일 앞뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 덱의 용도는? -배열을 써야하는데 앞/뒤가 모두 중요할때 STL deque deq; deq.push_front(1); // 1 deq.push_back(5); // 1 5 deq.push_front(2); // 2 1 5 for(auto x : deq) cout 전통적 동기화 예제 Producer and Consumer problem(생산자 소비자 문제) -생산자가 데이터를 생산하면 소비자는 그것을 소비 -유한 버퍼 문제(Bounded Buffer problem) -상호 배타 문제: 세마포 1개로 해결(mutual) -Busy wait(e.g. CPU가 while문을 계속돌림): 세마포 2개로 해결(empty, full) Readers - Writers problem -공유 데이터 베이스 접근 -Reader는 값을 변경하지 않으니 임계구역에 여러개를 허용(cf. Writer는 상호배타로 한개만 접근해야함) Dining Philosopher problem -교착상태(Deadlock) 발생하여 기아(Starvation) 교착상태 필요조건(4가지 만족하면 발생할 가능성이 있음) -Mut.. 큐(Queue) 큐는 무엇인가? -한쪽끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수 있는 자료구조 큐의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 큐의 용도는? - 선착순으로 해결해야 될때 쓰임 문제풀이에서 큐의 활용방식은? -BFS와 Flood Fill STL queue Q; Q.push(1); // 1 Q.push(2); // 2 Q.push(3); // 3 cout 세마포(Semaphores) 세마포(Semaphores) - 동기화 문제 해결을 위한 소프트웨어 도구 세마포의 구조 - value(number of permit), P 동작(acquire), V 동작(release) acquire(){ value = value - 1; if(value < 0){ acquire를 호출한 쓰레드를 큐안에 집어넣음(봉쇄) } } release(){ value = value + 1; if(value 데이터 표현과 연산 2의 보수를 쓰는 이유는? -다른 부호의 덧셈에서 뺄셈이 필요없음(덧셈으로 뺄셈까지 가능) -한개의 0으로 혼동(순환자리올림) 없음 cf. 1의 보수는 +0과 -0이 있음 -부호 확장 용이(MSB만 확장하면됨) 2의 보수에 대한 덧셈/뺄셈 연산 -두 수의 부호가 다를때: 자리 올림수 무시하고 10진수 연산하듯이 더한다. (무조건 범위안이기 때문) -두 수의 부호가 같을때 -오버플로우(V)가 발생하지 않았을때는 위 과정과 동일 -오버플로우(V)가 발생시 계산 불가(MSB 기준 Cin ⊕ Cout = 1이면 오버플로우(V) 발생) 덧셈/뺄셈기 구조 스택(Stack) 스택은 무엇은가? -한쪽 끝에서만 원소를 넣거나 뺄수있는 자료구조 스택의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 상단의 원소 확인이 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택의 용도는? 직전의 값을 저장(기억) 전체 값보다는 바로 직전값만 확인할때 거꾸로 출력하고 싶을때(함수 호출) 문제풀이에서 스택의 활용방식은? DFS 수식 괄호쌍 전위/중위/후위 표기법 STL stack s; s.push(1); // 1 s.push(2); // 1 2 s.push(3); // 1 2 3 s.push(4); // 1 2 3 4 cout 이전 1 2 3 4 5 6 다음
