랄뚜기의 코딩일기

Search vs Planning milk, bananas 그리고 cordless drill을 가져오는 임무가 있다고 하자. Standard search algorithms은 아마 fail 할 것이다. Planning systems do the following: open up action and goal representation to allow selection divide-and-conquer by subgoaling relax requirement for sequential construction of solutions Planning as state space search Planning as a search problem : search from the initial state through ..

Internet에서의 Unicast routing은 hierarchical routing을 사용해야만 한다. General Idea In unicast routing, a packet is routed, hop by hop, from its source to its destination by the help of forwarding tables. The source host needs no forwarding table because it delivers its packet to the default router in its local network. The destination host needs no forwarding table either because it receives the packet f..

위는 각각의 layer마다 적용되는 protocol의 종류이다.(모두 외우기) Network-Layer Protocols Network layer는 하나의 main protocol 그리고 3개의 부수적인 protocol로 생각되어질 수 있다. Main protocol은 IPv4로 packetizing, forwarding 그리고 packet의 delivery에 책임이 있다. ICMPv4는 IPv4가 delivery과정에서 발생하는 error를 다룰 수 있게 해준다. IGMP는 IPv4가 multicasting하는 것을 돕는다. ARP는 address mapping을 하는데 쓰인다. 여기서 강의자료에서는 ARP가 Network layer에서 이뤄진다고 했지만, 교수님께서는 Data-link에서 이뤄진다고 ..

FOL to PL FOL(First order logic)을 inference하기 위해서는 PL(Propositional logic)으로 바꿔줘야 한다. Propositional inference를 할 때 Ground sentence를 이용한다. 위 처럼 variable이 없는 sentence를 Ground setence라고 하고, ground atomic setence를 propositional symbol로 보면 된다. Universal Instantiation (UI) Rule 만약 ∀v ɑ 라는 FOL을 PL로 바꾼다고하자. 그렇다면 식은 아래와 같다. 위의 식이 의미하는 것은 ɑ에다가 v(variable) 대신에 g(ground term)을 넣으라는 뜻이다. SUBST(𝝷,ɑ) = ɑ𝝷 : th..

Packetizing Network layer의 첫번째 임무는 packetizing이다. payload를 encapsulate해주고 목적지에서는 payload를 decapsulate해준다. Network layer는 payload를 변형되지 않게 옮기는 것이 목적이다. Routing and Forwarding network layer의 또 다른 목적은 routing과 forwarding이다. Packet Switching From the discussion of routing and forwarding, we infer that a kind of switching occurs at the network layer A router is a switch that creates a connection betw..

Sequential systems ( finite state machine ) systems with memory Output depends on present input and past history Synchoronous systems Clock signal regulates input, internal, and output signal Clock Alternating sequence of 0 and 1 at a regular rate Two kinds : 0 and 1 in same length, 0 longer than 1 Clock period T = 1/clock_rate Moore machine Moore machine은 현재의 Input이 아니라 과거의 input에만 영향을 받는다. 첫번째..

thread : Used to interact with this thread. attr : Used to specify any attributes this thread might have. Stack size, Scheduling priority,... start_routine : the function this thread start running in arg : the argument to be passed to the function (start routine) a void pointer allows us to pass in any type of argument 만약 start_routine 대신에 다른 type argument가 필요하다면 declaration은 위와 같을 것이다. thread :..

Thread란 single running process를 위한 새로운 abstraction이다. Multi-threaded program Multi-threaded program은 한 개 이상의 execution을 가진다. Multiple PCs (Program Counter) Thread들끼리 같은 address space를 공유한다. 각각의 thread들은 고유의 PC(Program Counter)와 register들을 가지고 있다. 여러개의 TCB(thread control block)이 각각의 thread의 상태를 저장하기 위해 필요하다. 만약 T1에서 T2로 switching된다면 T1의 register state는 저장이되고 T2의 register state가 restore될 것이다. addr..

Implementing LRU Algorithm Counter implementation 모든 page table에는 counter가 있다 page는 entry를 통해서 참조 되고, counter에 clock을 복사한다. clock은 memory에 참조가 일어날 때마다 증가한다. page가 replace 되야할 때, counter를 확인하여 어떤 page가 replace 될 지 결정한다. Stack implementation doubly linked list 형식으로 page number를 stack으로 만든다. page가 참조 될 때마다 해당 page number를 stack의 top에 올려놓는다. 즉, top이 most recently used가 되고 bottom이 LRU가 된다. update하는데 ..

Cache Management의 목표는 cache miss의 수를 최소화 하는 것이다. 그렇다면 어떤 기준으로 cache를 설정하면 될까? 이것이 Tracing the Optimal Policy이지만 현실적으로 미래를 알 수 없으므로 불가능하다. FIFO 방식으로하면 Hit rate이 36.4%로 급격히 낮아진다. 0이 계속 들어올 것이지만 제거해버렸기 때문이다. 당연히 cache가 커지면 hit rate가 오를 것이라고 생각하겠지만 FIFO에서는 오히려 줄어들 수 도 있다. ex) 3->4 차라리 Random하게 cache에 저장하는 것이 오히려 효율적 일 수 있다.(약 45%) 때때로는 Random이 optimal처럼 좋을 수도 있다. 위 두 개의 history( recency, frequency )..