[Note #4][Algorithm] Backtracking

Backtracking: http://acm.nudt.edu.cn/~twcourse/Backtracking.html

Example:

• Problem: 
• A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
• Note: the number of first circle should always be 1.
• You are to write a program that completes above process.
• AC: https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_524.cc

[Note] TCP/IP State Transition

TCP/IP State Transition Diagram:

• http://www.cs.northwestern.edu/~agupta/cs340/project2/TCPIP_State_Transition_Diagram.pdf

UNIX Network Programming (Volume1) 3rd:

• https://github.com/shihyu/Linux_Programming/blob/master/books/UNIX%20Network%20Programming(Volume1%2C3rd).pdf 

There are 11 different states defined for a connection and the rules of TCP dictate the transitions from one state to another, based on the current state and the segment received in that state. For example, if an application performs an active open in the CLOSED state, TCP sends a SYN and the new state is SYN_SENT. If TCP next receives a SYN with an ACK, it sends an ACK and the new state is ESTABLISHED. This final state is where most data transfer occurs.

The two arrows leading from the ESTABLISHED state deal with the termination of a connection. If an application calls close before receiving a FIN (an active close), the transition is to the FIN_WAIT_1 state. But if an application receives a FIN while in the ESTABLISHED state (a passive close), the transition is to the CLOSE_WAIT state.

We denote the normal client transitions with a darker solid line and the normal server transitions with a darker dashed line. We also note that there are two transitions that we have not talked about: a simultaneous open (when both ends send SYNs at about the same time and the SYNs cross in the network) and a simultaneous close (when both ends send FINs at the same time).



Three-Way Handshake

The following scenario occurs when a TCP connection is established:

1. The server must be prepared to accept an incoming connection. This is normally done by calling socket, bind, and listen and is called a passive open. 
2. The client issues an active open by calling connect. This causes the client TCP to send a "synchronize" (SYN) segment, which tells the server the client's initial sequence number for the data that the client will send on the connection. Normally, there is no data sent with the SYN; it just contains an IP header, a TCP header, and possible TCP options (which we will talk about shortly).
3. The server must acknowledge (ACK) the client's SYN and the server must also send its own SYN containing the initial sequence number for the data that the server will send on the connection. The server sends its SYN and the ACK of the client's SYN in a single segment.
4. The client must acknowledge the server's SYN.

The minimum number of packets required for this exchange is three; hence, this is called TCP's three-way handshake.



TCP Connection Termination

While it takes three segments to establish a connection, it takes four to terminate a connection.

1. One application calls close first, and we say that this end performs the active close. This end's TCP sends a FIN segment, which means it is finished sending data. 
2. The other end that receives the FIN performs the passive close. The received FIN is acknowledged by TCP. The receipt of the FIN is also passed to the application as an end-of-file (after any data that may have already been queued for the application to receive), since the receipt of the FIN means the application will not receive any additional data on the connection.
3. Sometime later, the application that received the end-of-file will close its socket. This causes its TCP to send a FIN.
4. The TCP on the system that receives this final FIN (the end that did the active close) acknowledges the FIN.

References:

• http://www.serverframework.com/asynchronousevents/2011/01/time-wait-and-its-design-implications-for-protocols-and-scalable-servers.html

我回來了。

（中午休息阿比指我，殊不知另外四指指著自己 XD）

我回來了。

感謝大家願意等我回來。


這陣子花很多時間偷懶，花很多時間調適，因為安安來我們家當我們的寶貝，有時候小哭包一直哭一直哭，忍不住洩氣抱怨你到底要怎樣，也有時候半夜四點起來鬧，抱著走來走去泡牛奶躺在地墊玩，直到早上九點沿莉把我從深淵拯救出來，更有時候婆婆幫忙照顧安安，讓沿莉和我出來透風發呆。


可是想到自己可能比安安先走，又忍不住眼淚想哭。勞動法老師講課時告訴我們，他希望有生之年可以看到最低工資法過關，老師不是批評政府，而是期望自己長命百歲。這邊得到一個結論，盡量把身體弄健康點，就可以看久一點的沿莉和安安。


感謝賓賓體恤民心，願意開散步路線讓大家散散步。很努力跟上大家腳步（鑽芒草很像螞蟻在草地上那邊鑽來鑽去），很努力跟著大家聊天話題回憶什麼東西，很久沒出來走早已沒貨可以講（掩面），比較糟的行為是亂指路，大量預設散步等級的路在腦海，接著剔除路底太差的小路，然後發現沒路可走（被龍頭揪錯）。磺嘴山火山口是漂亮，可惜螞蟻看不到上帝視角，在冰島的時候很想繞大的火山口走一圈，結果到台灣磺嘴山的火山口，又嫌太累沒去走一圈，整個就是偷懶的人。


至少載三個人可以拿來說嘴。


下山送人回家，原本車上打算聽陳聰富講民總，結果只是聽著廣播累著發呆，我想感冒在家顧安安的沿莉應該更累。


感謝沿莉愛護安安，安安長大也會愛麻麻。

[Note] Some questions about threads & processes

1. Singleton pattern: https://en.wikipedia.org/wiki/Singleton_pattern

• Initialization-on-demand holder idiom: https://en.wikipedia.org/wiki/Initialization-on-demand_holder_idiom
• [Java] Relies on the initialization phase of execution within the Java Virtual Machine (JVM) as specified by the Java Language Specification
• Double-checked locking: https://en.wikipedia.org/wiki/Double-checked_locking
• [Java] The volatile keyword now ensures that multiple threads handle the singleton instance correctly.
• [Java] synchronized

2. The difference between a process and a thread

Processes

• Concept
• A process is an instance of a program in execution.
• Modern systems allow a single process to have multiple threads of execution, which execute concurrently.
• Process Scheduling
• The two main objectives of the process scheduling system are to keep the CPU busy at all times and to deliver "acceptable" response times for all programs, particularly for interactive ones.
• The process scheduler must meet these objectives by implementing suitable policies for swapping processes in and out of the CPU.

(Quote from here)

Threads

• Overview
• A thread is a basic unit of CPU utilization, consisting of a program counter, a stack, and a set of registers, (and a thread ID.)
• Traditional (heavyweight) processes have a single thread of control - There is one program counter, and one sequence of instructions that can be carried out at any given time.
• Motivation
• Threads are very useful in modern programming whenever a process has multiple tasks to perform independently of the others.
• This is particularly true when one of the tasks may block, and it is desired to allow the other tasks to proceed without blocking. For example in a word processor, a background thread may check spelling and grammar while a foreground thread processes user input (keystrokes), while yet a third thread loads images from the hard drive, and a fourth does periodic automatic backups of the file being edited. 
• Another example is a web server - Multiple threads allow for multiple requests to be satisfied simultaneously, without having to service requests sequentially or to fork off separate processes for every incoming request.
• Benefits
• Responsiveness - One thread may provide rapid response while other threads are blocked or slowed down doing intensive calculations.
• Resource sharing - By default threads share common code, data, and other resources, which allows multiple tasks to be performed simultaneously in a single address space. 
• Economy - Creating and managing threads is much faster than performing the same tasks for processes. 
• Scalability, i.e. Utilization of multiprocessor architectures - A single threaded process can only run on one CPU, no matter how many may be available, whereas the execution of a multi-threaded application may be split amongst available processors.

Example: Chrome

• Problem 
• It's nearly impossible to build a rendering engine that never crashes or hangs. It's also nearly impossible to build a rendering engine that is perfectly secure. 
• In some ways, the state of web browsers around 2006 was like that of the single-user, co-operatively multi-tasked operating systems of the past. As a misbehaving application in such an operating system could take down the entire system, so could a misbehaving web page in a web browser. All it took is one browser or plug-in bug to bring down the entire browser and all of the currently running tabs. 
• Modern operating systems are more robust because they put applications into separate processes that are walled off from one another. A crash in one application generally does not impair other applications or the integrity of the operating system, and each user's access to other users' data is restricted.

3. The producer-consumer problem: race condition

• In this condition a piece of code may or may not work correctly, depending on which of two simultaneous processes executes first, and more importantly if one of the processes gets interrupted such that the other process runs between important steps of the first process.
• A specific example of a more general situation known as the critical section problem. 
• A solution to the critical section problem must satisfy the following three conditions:
  • Mutual Exclusion - Only one process at a time can be executing in their critical section.
  • Progress - If no process is currently executing in their critical section, and one or more processes want to execute their critical section, then only the processes not in their remainder sections can participate in the decision, and the decision cannot be postponed indefinitely.
  • Bounded Waiting - There exists a limit as to how many other processes can get into their critical sections after a process requests entry into their critical section and before that request is granted.
• Peterson's Solution
• Peterson's Solution is a classic software-based solution to the critical section problem. It is unfortunately not guaranteed to work on modern hardware, due to vagaries of load and store operations.
• Synchronization Hardware
• To generalize the solution expressed above, each process when entering their critical section must set some sort of lock, to prevent other processes from entering their critical sections simultaneously, and must release the lock when exiting their critical section, to allow other processes to proceed. Obviously it must be possible to attain the lock only when no other process has already set a lock. 
• Mutex Locks
• The hardware solutions presented above are often difficult for ordinary programmers to access, particularly on multi-processor machines, and particularly because they are often platform-dependent.
• Therefore most systems offer a software API equivalent called mutex locks or simply mutexes.
• The terminology when using mutexes is to acquire a lock prior to entering a critical section, and to release it when exiting.
• One problem with the implementation shown here is the busy loop used to block processes in the acquire phase. These types of locks are referred to as spinlocks, because the CPU just sits and spins while blocking the process. 
• Spinlocks are wasteful of cpu cycles, and are a really bad idea on single-cpu single-threaded machines, because the spinlock blocks the entire computer, and doesn't allow any other process to release the lock.
• On the other hand, spinlocks do not incur the overhead of a context switch, so they are effectively used on multi-threaded machines when it is expected that the lock will be released after a short time.
• Semaphores
• A more robust alternative to simple mutexes is to use semaphores, which are integer variables for which only two atomic operations are defined, the wait and signal operations.
• Note that not only must the variable-changing steps (S-- and S++) be indivisible, it is also necessary that for the wait operation when the test proves false that there be no interruptions before S gets decremented.

4. Deadlocks

• A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set.
• Necessary Conditions
• Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process requests this resource, then that process must wait for the resource to be released. 
• Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at least one resource that is currently being held by some other process. 
• No preemption - Once a process is holding a resource, then that resource cannot be taken away from that process until the process voluntarily releases it. 
• Circular Wait - A set of processes { P[0], P[1], P[2], ..., P[N] } must exist such that every P[i] is waiting for P[(i+1) % (N+1)]. 
• Methods for Handling Deadlocks
• Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
• Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.
• Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection.

5. Classical Synchronization Problems

• The Producer/Consumer (Bounded Buffer) Problem
• The Dining Philosophers Problem 
• The Readers/Writers Problem

References:

• The Chromium Projects: Design documents: https://www.chromium.org/developers/design-documents
• https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/3_Processes.html
• https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/4_Threads.html
• https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html
• https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html
• https://cseweb.ucsd.edu/classes/wi06/cse120/Lec06x4.pdf 

[Note] Competitive Programming Overview

Category:

• Ad Hoc
• Straightforward
• Simulation
• Complete Search
• Iterative
• Backtracking
• Divide & Conquer
• Greedy
• Classic
• Original
• Dynamic Programming
• Classic
• Kadane's algorithm
• Original
• Graph
• Mathematics
• Factorial
• Fibonacci Q-Matrix
• String Processing
• Computational Geometry
• Otherwise