분류 전체보기354

• 

  Operating Systems 6. Synchronization Tools Background - 공유 데이터에 대한 병행/병렬 접근은 데이터 일관성을 보장하지 못할 수 있다. -> data inconsistency - 이를 막기 위해 병행 프로세스가 공유 데이터에 접근할 때에는 프로세스 동기화가 필요하다. Producer-Consumer 생산자와 소비자는 counter 라는 공유변수에 접근한다. 경쟁조건(Race Condition) - 병행 프로세스가 공유 데이터를 접근하였을 때 공유 데이터의 일관성이 깨지는 상황을 의미한다. - 즉, 실행 결과가 자료의 접근 순서에 영향을 받는 상황이다. -> 불확실한 상태에 도달할 수 있다. -> 경쟁 조건의 예방을 위하여 한번에 오직 하나의 프로세스만이 특정 변수를 조작하는 것을 보장하기 위해 동기화가 필요하다. Critical Sect.. 운영체제(OS) 2021. 12. 4.

• 

  Operating Systems 4. Threads & Concurrency Multithreaded Architecture - 프로세스 생성은 heavy-weight, 쓰레드 생성은 light-weight 하다. - 단일 응용 프로그램이 여러 개의 작업을 동시에 실행할 필요가 있을 때 thread 를 사용한다. word processor: 화면 출력 + 키보드 입력 + 스펠링 검사 web browser: 화면출력 + 네트워크에서 데이터 수신 web server: 여러 개(수천 개도 가능)의 client의 요청 처리 OS kernel: 장치 관리, 인터럽트 처리 등의 여러 작업 하나의 웹 서버 프로세스가 외부로부터 요청을 받는 하나의 다수의 클라이언트를 담당하는 thread 들로 이루어진다. -> 클라이언트로부터 서비스 요청이 들어오면 대기하고 있던 쓰레드가 요청을 받는다. ->.. 운영체제(OS) 2021. 12. 4.

• 

  Operating Systems 10. Virtual Memory - (3) Allocation of Frames 각 프로세스에게 할당되는 메모리 프레임 수를 정해야 한다. - Equal allocation : 모든 프로세스에게 똑같이 할당 - Proportional allocation : 프로세스의 크기에 비례하여 할당 - Priority allocation : 프로세스 우선순위에 따라 비례할당 Global vs Local Allocation - Global replacement : 모든 frame 집합에서 교체할 frame 을 선택한다. 즉, 다른 프로세스로부터 frame 을 가져올 수 있다. -> 특정 프로세스가 많은 메모리를 차지할 수 있다. - Local replacement : 각 프로세스는 자신에게 할당된 frame 집합에서 교체할 frame 을 선택한다. -> 바쁜.. 운영체제(OS) 2021. 12. 4.

• 

  Operating Systems 10. Virtual Memory - (2) Demand Paging - pure demand paging : 어떤 page 가 필요해지기 전까지는 그 page 를 메모리에 load 하지 않는다. - 실제로는 page fault 가 지역성(시간 지역성, 공간 지역성) 으로 인해 잘 일어나지 않는다. - Hardware 는 demand paging 을 지원하기 위해 다음과 같은 지원을 한다. valid/ invalid bit 를 가진 Page table swap space Instruction restart Performance of Demand Paging - Demand Paging 발생시 단계 trap 이 발생한다. user register, process state 를 저장한다. 인터럽트가 page fault 인지 결정한다. page refe.. 운영체제(OS) 2021. 12. 4.

• 

  Constraint Propagation in CSPs, Local Consistency, Node consistency, Arc consistency Constraint Propagation in CSPs - CSP 를 푸는 두 가지 방법 Search Constraint propagation - 추론의 특정한 종류 변수가 취할 수 있는 값들이 줄어들게 된다. -> search space (탐색 공간) 이 줄어들게 된다. -> 효율성이 높아진다. - 전처리 단계에 constraint propagation 이 일어나거나, search 중간에 일어날 수도 있음 Local Consistency - Node consistency CSP 를 구성하는 한 변수가 가질 수 있는 모든 변수, 즉 domain 이 변수의 unary constraint 를 모두 만족시킨다면 node-consistent 하다. 예) unary constraint : SA 노드는 green .. 인공지능 2021. 11. 23.

• 

  Constraint satisfaction problems (CSPs) - 이전 챕터까지는 atomic representation 사용 -> 6장 부터는 Factored representation 사용 (state 를 표현하는 여러개의 variable 이 존재한다.) - Constraint satisfaction problems (CSPs) : variable value 가 제약조건을 만족해야한다. - CSP search 알고리즘은 general-purpose(범용) heuristic 이다. 반대로 이전까지 배운 search 알고리즘은 구체적인 문제의 heuristic 으로만 사용이 되었다. Defining CSPs - 세 가지 구성요소 X : 변수 {X1, ... , Xn} D : 도메인 {D1, ... , Dn} C : 제약조건 - i 번째 제약조건인 Ci : 의 쌍으로.. 인공지능 2021. 11. 23.

• 

  Evaluation Functions Imperfect Real-Time Decisions - 실시간으로 결정을 할 때에는 결함이 존재한다. - Alpha-beta search 는 terminal state 까지 계산을 하는데 시간이 오래 걸린다. (실제로 바둑, 체스를 alpha beta 로 구현을 할 수 없음) -> 실용적이지 않다. - Heuristic minimax - terminal state 까지 검사를 하지 않아도 된다. - terminal state 인지 테스트하는 대신 CUTOFF-TEST 를 사용한다. 원래는 utility(s) 로, s는 terminal state 였다. 그러나 EVAL(s) 에서는 depth-limit 와 유사하게, 제한을 둔 d까지만 탐색을 한다. cutoff 에 도달을 하였다면, EVAL(s) 로 m.. 인공지능 2021. 11. 23.

• 

  A Pruning, Alpha-Beta Pruning, Mover Ordering The Problem with Minimax Search - 재귀적으로 구현된 minimax search 는 depth search 와 비슷하고, 이는 O(b^m) 의 시간복잡도를 가지기 때문에 실용적이지 않다. - 그러나 어떤 경우에는 모든 노드에 대해 검사를 하지 않더라도 정확한 minimax value 를 알 수 있게 된다. A Pruning Example (a) 에서 [-무한, +무한] 은 A가 가질 수 있는 utility value 의 범위를 뜻한다. B를 방문하더라도 아직 알려진 것이 없기 때문에 B의 utility 범위도 [-무한, +무한] 이 된다. 이때 3을 방문하게 되면, B에서는 utility value 의 최댓값을 3으로 보장할 수 있게 되는 것이다. 다른 노드들을 방문해서 3보다 .. 인공지능 2021. 11. 23.

• 

  A Game Search Problem, A Two-Ply (One Move Deep) Game Tree, The Optimal Strategy in a Game Tree Games - Multiagent (competitive) environments : 상대방 agent 의 action 을 예측할 수 없기 때문에 Contingency 가 존재한다. (상대방의 action 이 ~라면 if , else 로 나눠서 결정) - 대부분의 게임은 deterministic, turn-taking (돌아가면서 진행), two-player , zero-sum game(한 명이 무조건 이기는 게임), perfect information(full observation, 게임에 필요한 모든 정보가 주어짐, 바둑, 체스) - 탐색 공간이 매우 크다 : chess 의 경우 branching factor 가 35에 가깝고, 각 플레이어는 50번 정도를 움직인다. search tree 는 35^1.. 인공지능 2021. 11. 22.

• 

  Transitions in a Pratially Observable World, Maintaining One's Belief State Many Sensorless Problems are Difficult to Solve - belief state 의 개수가 너무 많아지기 때문에 실제로 구현하기 어렵다. - 10 x 10 vacuum world 의 initial belieft state 는 100 x 2^100 = 10^32 의 physical states 를 가질 수 있다. - Solution : Incremental belieft-state search : {1,2,3,4,5,6,7,8} 의 physical state 가 존재할 때 1번 physical state 부터 시작해서 solution 을 탐색하고, 그 solution 을 2번 ,,, 8번 state 에 적용해본다. 그러나 8-puzzle 와 같은 경우에는 sensing 없이.. 인공지능 2021. 11. 22.

• 

  Sensorless Problems, The Belief-State Search Problem Searching with Partial Observations - agent 의 percept 는 현재 위치한 state 를 정확히 알지 못한다. 가능한 state 가 둘 이상 존재할 수 있다. - Belief states : 내가 어떤 state 에 있는지 정확히 알 순 없지만 가능한 state 에 있을 것이라고 생각 (후보군) Searching with No Observation - percept 가 없는 경우이다. - sensor 가 없고 그에 순응하는 문제들이다. (sensor 의 비용이 크기 때문에) - 예) 컨테이너 벨트에서 물품의 방향을 고치기 위해 카메라가 존재할 수 있다. 카메라로 방향을 파악하는데, 카메라가 비싸니깐 몇번의 action 으로 고정된 방향을 가리치도록 대체할 수 있다. .. 인공지능 2021. 11. 20.

• 

  Partially Observable and/or Nondeterministic Worlds, AND-OR Search Trees, The Slippery Vaccum World Partially Observable and/or Nondeterministic Worlds - fully observable, deterministic 한 문제들에서 percept 은 새로운 정보를 제공하지 않았다. - partially observable 하다면, 가능한 state 들 중 agent 가 어떤 state 에 있는지 percept 가 좁혀줄 수 있다. - nondeterministic 하다면, 가능한 결과가 실제로 일어난 것을 percept 가 알려준다. -> percept 들이 미리 정해져있지 않다. 따라서 어떤 percept 가 들어오냐에 따라 agent 가 action 을 다르게 해야 한다. solution 은 action sequence 가 아니라 contingency plan 이.. 인공지능 2021. 11. 19.