Basic Synchronization Principles - Revision history

Ndickson: added note about cli and sti only being accessible from kernel

2007-10-21T16:45:43Z

added note about cli and sti only being accessible from kernel

← Older revision		Revision as of 16:45, 21 October 2007
Line 59:		Line 59:
	void use_list() {		void use_list() {
	asm { // disable interrupts		asm { // disable interrupts
	cli		cli // note: this instruction can only be executed from kernel code
	}		}
	while (using_list) {		while (using_list) {
	asm { // enable interrupts, because access wasn't acquired this time		asm { // enable interrupts, because access wasn't acquired this time
	sti		sti // note: this instruction can only be executed from kernel code
	}		}
	sleep(0);// go to sleep so that other threads will run		sleep(0);// go to sleep so that other threads will run

Ndickson: fixed Starvation to be general type of starvation

2007-10-12T04:01:14Z

fixed Starvation to be general type of starvation

← Older revision		Revision as of 04:01, 12 October 2007
Line 289:		Line 289:

	===Starvation===		===Starvation===
	Starvation in ~~the case~~ of ~~concurrency~~ is when a thread gets access to a resource and then because of scheduling or other decisions (beyond its reasonable control), it can never release access to the resource (or at least it holds it for a long time).		Starvation is a more general situation than deadlock, in that deadlock is a type of starvation. Starvation refers to any situation in which one or more threads end up waiting either indefinitely long or just unreasonably long in order to perform a particular operation.

			An example of starvation that is not what is normally referred to as deadlock, is when a thread gets access to a resource and then because of scheduling or other decisions (beyond its reasonable control), it can never release access to the resource (or at least it holds it for a long time).

	Consider three threads (on a single-processor system): thread1 is an idle priority thread (only run when nothing else is running), and both thread2 and thread3 are medium-to-high priority threads. Then the following could occur:		Consider three threads (on a single-processor system): thread1 is an idle priority thread (only run when nothing else is running), and both thread2 and thread3 are medium-to-high priority threads. Then the following could occur:
Line 297:		Line 299:
	# thread1 and thread3 don't run again until thread2 has stopped, which could be a while		# thread1 and thread3 don't run again until thread2 has stopped, which could be a while

	~~Unlike deadlocks, this~~ can (almost) always be avoided if the operating system manages the thread concurrency. Using the same extension of a binary semaphore as mentioned in the deadlocks section, the operating system can know that thread3 is waiting for thread1, and as such, thread1 should be given the higher priority of thread3 until it releases the access, at which point it returns to its original priority. This is still fair, because thread3 depends upon thread1 releasing access before it can continue, and the starvation issue is solved.		This example type of starvation can (almost) always be avoided if the operating system manages the thread concurrency. Using the same extension of a binary semaphore as mentioned in the deadlocks section, the operating system can know that thread3 is waiting for thread1, and as such, thread1 should be given the higher priority of thread3 until it releases the access, at which point it returns to its original priority. This is still fair, because thread3 depends upon thread1 releasing access before it can continue, and the starvation issue is solved.

			However, there is no general solution to starvation problems, since they can be arbitrarily complex. (Also, the lack of a general solution for deadlocks implies that there is a lack of a general solution for starvation, since deadlocks are a type of starvation.)

Ndickson: added Advanced Issues section

2007-10-05T01:46:55Z

added Advanced Issues section

← Older revision		Revision as of 01:46, 5 October 2007
Line 252:		Line 252:
	This is robust (scalable to size of the internet), but slow, whereas shared memory isn’t scalable, but fast.		This is robust (scalable to size of the internet), but slow, whereas shared memory isn’t scalable, but fast.
	Still a lot of error cases to be handled: code you don’t want to mess with unless you really know what you’re doing.		Still a lot of error cases to be handled: code you don’t want to mess with unless you really know what you’re doing.

			==Advanced Issues==

			===Deadlocks===
			A deadlock is when a set of threads get into a state where they all need access that other threads in the set have. The simplest case is shown below.

			<code><pre>
			int semaphoreA = 1;
			int semaphoreB = 1;

			void thread1() {
			down(semaphoreA); // Gain access to resource A
			down(semaphoreB); // Gain access to resource B

			// use A and B

			up(semaphoreB); // Release access to resource B
			up(semaphoreA); // Release access to resource A
			}
			void thread2() {
			down(semaphoreB); // Gain access to resource B
			down(semaphoreA); // Gain access to resource A

			// use A and B

			up(semaphoreA); // Release access to resource A
			up(semaphoreB); // Release access to resource B
			}
			</pre></code>

			A deadlock scenario with this example is when thread1 gets access to A, then thread2 gets access to B before thread1 gets access to B. This means that thread1 is waiting for thread2 to release access to B, and thread2 is waiting for thread1 to release access to A, and neither will ever happen, thus the threads are said to be deadlocked.

			In the case where there is a fixed set of controlled resources to be acquired by any given function, as long as all threads acquire them in the same order, a deadlock will be avoided (e.g. switch the first two lines of thread2). However, this is not always possible in more complex situations.

			It is always possible to identify deadlocks when using binary semaphores if one extends them to keep track of which thread has access and which threads are waiting for access. Conceptually, the state of the thread interaction can be represented by a directed graph, in which the nodes are threads and there is an edge from thread1 to thread2 if thread1 wants access that thread2 has. Then any directed cycles represent deadlocks, and the nodes in the cycle are the deadlocked threads. Unfortunately, there is no single way to avoid deadlocks in all cases. Also note that identifying deadlocks is not the same as predicting them, which can be as difficult as avoiding them.

			===Starvation===
			Starvation in the case of concurrency is when a thread gets access to a resource and then because of scheduling or other decisions (beyond its reasonable control), it can never release access to the resource (or at least it holds it for a long time).

			Consider three threads (on a single-processor system): thread1 is an idle priority thread (only run when nothing else is running), and both thread2 and thread3 are medium-to-high priority threads. Then the following could occur:
			# thread1 acquires mutually exclusive access to a resource
			# thread2 starts running an intense computation that could take days, so thread1 is no longer running
			# thread3 tries to acquire access to the resource that thread1 has
			# thread1 and thread3 don't run again until thread2 has stopped, which could be a while

			Unlike deadlocks, this can (almost) always be avoided if the operating system manages the thread concurrency. Using the same extension of a binary semaphore as mentioned in the deadlocks section, the operating system can know that thread3 is waiting for thread1, and as such, thread1 should be given the higher priority of thread3 until it releases the access, at which point it returns to its original priority. This is still fair, because thread3 depends upon thread1 releasing access before it can continue, and the starvation issue is solved.

Ndickson: edited Readers-Writers

2007-10-04T19:53:54Z

edited Readers-Writers

← Older revision		Revision as of 19:53, 4 October 2007
Line 192:		Line 192:

	An example of this is airline reservation. There is a database of seats sold, and one wants to allow as many people as possible to look at what seats are available, but only one person can buy a seat at the same time. Then, as soon as someone buys a seat, the info needs to be updated as soon as possible to everyone.		An example of this is airline reservation. There is a database of seats sold, and one wants to allow as many people as possible to look at what seats are available, but only one person can buy a seat at the same time. Then, as soon as someone buys a seat, the info needs to be updated as soon as possible to everyone.


	'''A solution to problem:'''		'''A solution to problem:'''

	When a writer wants to write:		When a writer wants to write:
	* no new readers and no other writers		* no new readers and no other writers
Line 199:		Line 201:
	* writer writes		* writer writes
	* gives back access to readers and writers		* gives back access to readers and writers


	'''A faster solution:''' (for cases where the data structure allows reading while writing)		'''A faster solution:''' (for cases where the data structure allows reading while writing)

	When a writer wants to write:		When a writer wants to write:
	* no other writers		* no other writers

Ndickson: edited Abstractions

2007-10-04T19:52:23Z

edited Abstractions

← Older revision		Revision as of 19:52, 4 October 2007
Line 140:		Line 140:
	Making a massively parallel system with separate memories isn’t hard, but making it work with shared memory is very difficult.		Making a massively parallel system with separate memories isn’t hard, but making it work with shared memory is very difficult.

	==Abstractions==		==Abstractions and High-Level Problems==
	Test-and-set and swap are quite low-level and painful to use in complex cases, so we want to wrap them in an abstraction.		Test-and-set and swap are quite low-level and painful to use in complex cases, so we want to wrap them in an abstraction.

Line 210:		Line 210:

	'''Network three-way handshake to open TCP connection:'''		'''Network three-way handshake to open TCP connection:'''
	{\|		{\| border="1"
			\|-
	! Computer A		! Computer A
	! Messages		! Messages
Line 242:		Line 243:
	\|		\|
	\| open		\| open
			\|-
	\|}		\|}

	This is robust (scalable to size of the internet), but slow, whereas shared memory isn’t scalable, but fast.		This is robust (scalable to size of the internet), but slow, whereas shared memory isn’t scalable, but fast.
	Still a lot of error cases to be handled: code you don’t want to mess with unless you really know what you’re doing.		Still a lot of error cases to be handled: code you don’t want to mess with unless you really know what you’re doing.

Ndickson: added Message Passing

2007-10-04T19:49:26Z

added Message Passing

@@ Line 193: / Line 193: @@
 An example of this is airline reservation.  There is a database of seats sold, and one wants to allow as many people as possible to look at what seats are available, but only one person can buy a seat at the same time.  Then, as soon as someone buys a seat, the info needs to be updated as soon as possible to everyone.
-'''A solution to problem'''
+'''A solution to problem:'''
 When a writer wants to write:
 * no new readers and no other writers
@@ Line 200: / Line 200: @@
 * gives back access to readers and writers
-'''A faster solution''' (for cases where the data structure allows reading while writing)
+'''A faster solution:''' (for cases where the data structure allows reading while writing)
 When a writer wants to write:
 * no other writers
@@ Line 206: / Line 206: @@
 * gives back access to writers
-'''NOTE: I'll add the rest of the notes later today.'''
+This is robust (scalable to size of the internet), but slow, whereas shared memory isn’t scalable, but fast.

Ndickson: finished Producer-Consumer and Readers-Writers

2007-10-04T19:37:29Z

finished Producer-Consumer and Readers-Writers

@@ Line 165: / Line 165: @@
 ===Producer-Consumer===
-The (Bounded-Buffer) Producer-Consumer problem itself is more of an abstraction of problems rather than an abstraction of solutions, but its common solutions are abstractions as well.  Suppose that there is a thread (or multiple threads) producing items in a buffer, and a thread (or multiple threads) consuming items in a buffer.  An example of this is an assembly line (referring to manufacturing, not assembly language).
+The (Bounded-Buffer) Producer-Consumer Problem itself is more of an abstraction of problems rather than an abstraction of solutions, but its common solutions are abstractions as well.  Suppose that there is a thread (or multiple threads) producing items in a buffer, and a thread (or multiple threads) consuming items in a buffer.  An example of this is an assembly line (referring to manufacturing, not assembly language).
 What needs to occur?
@@ Line 173: / Line 173: @@
 A classic bug is for either the producer or the consumer to never wake up after some point.
-Modern OSs provide a simple solution to this problem, namely ''pipes''.
+Modern OSs provide a simple solution to this problem, namely ''pipes''.  All of the sleeping and waking up is handled by the OS when reading/writing from/to a pipe.  All that the producer must do is write to the pipe, and all that the consumer must do is read from the pipe.
 '''NOTE: I'll add the rest of the notes later today.'''

Ndickson: more Producer-Consumer

2007-10-04T19:14:20Z

more Producer-Consumer

← Older revision		Revision as of 19:14, 4 October 2007
Line 164:		Line 164:
	</pre></code>		</pre></code>

	==Producer-Consumer==		===Producer-Consumer===
	The (Bounded-Buffer) Producer-Consumer problem itself is more of an abstraction of problems rather than an abstraction of solutions, but its common solutions are abstractions as well. Suppose that there is a thread (or multiple threads) producing items in a buffer, and a thread (or multiple threads) consuming items in a buffer. An example of this is an assembly line (referring to manufacturing, not assembly language).		The (Bounded-Buffer) Producer-Consumer problem itself is more of an abstraction of problems rather than an abstraction of solutions, but its common solutions are abstractions as well. Suppose that there is a thread (or multiple threads) producing items in a buffer, and a thread (or multiple threads) consuming items in a buffer. An example of this is an assembly line (referring to manufacturing, not assembly language).

			What needs to occur?
			* The consumer needs to sleep when there is no work to be done (empty buffer), and wake up when there is once again work to be done (non-empty buffer).
			* The producer needs to sleep when the buffer is full (it can't put any more in), and wake up when the buffer is no longer full (it can put more in again).

			A classic bug is for either the producer or the consumer to never wake up after some point.

			Modern OSs provide a simple solution to this problem, namely ''pipes''.


	'''NOTE: I'll add the rest of the notes later today.'''		'''NOTE: I'll add the rest of the notes later today.'''

Ndickson: added Semaphore and started on Producer-Consumer

2007-10-04T19:08:10Z

added Semaphore and started on Producer-Consumer

@@ Line 137: / Line 137: @@
+}
 </pre></code>
 '''NOTE: I'll add the rest of the notes later today.'''

Ndickson: added second example to Multi-Processor System

2007-10-04T16:00:49Z

added second example to Multi-Processor System

@@ Line 89: / Line 89: @@
 ''swap'': one can swap a variable with the value 1, get back its previous value, and check whether it was 0 or 1 before
+'''Using test-and-set:'''
 <code><pre>
 linked_list list;
@@ Line 100: / Line 100: @@
          jnc         GotAccess       ;got access if the bit was 0 at the beginning of the test-and-set
                                      ;previous value of bit is in carry flag, so no carry (nc) means bit was 0 before
+     }
      sleep(0);                       // go to sleep so that other threads will run