Operating Systems 2014F: Tutorial 5 - Revision history

Soma: /* Locks */

2014-10-06T19:03:58Z

Locks

← Older revision		Revision as of 19:03, 6 October 2014
Line 114:		Line 114:
	==Locks==		==Locks==

	Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsLocks.tgz (v2)] to answer the following questions from the [http://www.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf Locks] chapter.		Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsLocks.tgz x86.py (v2)] to answer the following questions from the [http://www.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf Locks] chapter.

	# First let’s get ready to run x86.py with the flag -p flag.s. This code “implements” locking with a single memory flag. Can you understand what the assembly code is trying to do?		# First let’s get ready to run x86.py with the flag -p flag.s. This code “implements” locking with a single memory flag. Can you understand what the assembly code is trying to do?

Soma at 16:53, 3 October 2014

2014-10-03T16:53:57Z

← Older revision		Revision as of 16:53, 3 October 2014
Line 2:		Line 2:

	Note there are a lot of material here. Do not expect to do all of it in detail in tutorial; instead, try to do some of everything so you can see where have significant conceptual gaps. On your own you should do these exercises in more detail to make sure you understand the associated concepts.		Note there are a lot of material here. Do not expect to do all of it in detail in tutorial; instead, try to do some of everything so you can see where have significant conceptual gaps. On your own you should do these exercises in more detail to make sure you understand the associated concepts.


	==Relocation==		==Relocation==
Line 17:		Line 18:
	* Run some of the same problems above, but with larger address spaces (-a) and physical memories (-p).		* Run some of the same problems above, but with larger address spaces (-a) and physical memories (-p).
	* What fraction of randomly-generated virtual addresses are valid, as a function of the value of the bounds register? Make a graph from running with different random seeds, with limit values ranging from 0 up to the maximum size of the address space.		* What fraction of randomly-generated virtual addresses are valid, as a function of the value of the bounds register? Make a graph from running with different random seeds, with limit values ranging from 0 up to the maximum size of the address space.


	==Segmentation==		==Segmentation==
Line 46:		Line 48:
	# What happens when you change the percent allocated fraction -P to higher than 50? What happens to allocations as it nears 100? What about as it nears 0?		# What happens when you change the percent allocated fraction -P to higher than 50? What happens to allocations as it nears 100? What about as it nears 0?
	# What kind of specific requests can you make to generate a highly-fragmented free space? Use the -A flag to create fragmented free lists, and see how different policies and options change the organization of the free list.		# What kind of specific requests can you make to generate a highly-fragmented free space? Use the -A flag to create fragmented free lists, and see how different policies and options change the organization of the free list.


	==Paging==		==Paging==
Line 73:		Line 76:
	:Which of these parameter combinations are unrealistic? Why?		:Which of these parameter combinations are unrealistic? Why?
	* Use the program to try out some other problems. Can you find the limits of where the program doesn’t work anymore? For example, what happens if the address-space size is bigger than physical memory?		* Use the program to try out some other problems. Can you find the limits of where the program doesn’t work anymore? For example, what happens if the address-space size is bigger than physical memory?


	==Threads (Intro)==		==Threads (Intro)==
Line 106:		Line 110:
	./x86.py -p wait-for-me.s -a ax=0,ax=1 -R ax -M 2000		./x86.py -p wait-for-me.s -a ax=0,ax=1 -R ax -M 2000
	:How do the threads behave? What is thread 0 doing? How would changing the interrupt interval (e.g., -i 1000, or perhaps to use random intervals) change the trace outcome? Is the program efficiently using the CPU?		:How do the threads behave? What is thread 0 doing? How would changing the interrupt interval (e.g., -i 1000, or perhaps to use random intervals) change the trace outcome? Is the program efficiently using the CPU?


	==Locks==		==Locks==

Soma: /* Locks */

2014-10-03T16:52:42Z

Locks

← Older revision		Revision as of 16:52, 3 October 2014
Line 113:		Line 113:
	# First let’s get ready to run x86.py with the flag -p flag.s. This code “implements” locking with a single memory flag. Can you understand what the assembly code is trying to do?		# First let’s get ready to run x86.py with the flag -p flag.s. This code “implements” locking with a single memory flag. Can you understand what the assembly code is trying to do?
	# When you run with the defaults, does flag.s work as expected? Does it produce the correct result? Use the -M and -R flags to trace variables and registers (and turn on -c to see their values). Can you predict what value will end up in flag as the code runs?		# When you run with the defaults, does flag.s work as expected? Does it produce the correct result? Use the -M and -R flags to trace variables and registers (and turn on -c to see their values). Can you predict what value will end up in flag as the code runs?
	# Change the value of the register %bx with the -a flag (e.g., -a bx=2, bx=2 if you are running just two threads). What does the code do? How does it change your answer for the question above?		# Change the value of the register %bx with the -a flag (e.g., -a bx=2,bx=2 if you are running just two threads). What does the code do? How does it change your answer for the question above?
	# Set bx to a high value for each thread, and then use the -i flag to generate different interrupt frequencies; what values lead to bad outcomes? Which lead to good outcomes?		# Set bx to a high value for each thread, and then use the -i flag to generate different interrupt frequencies; what values lead to bad outcomes? Which lead to good outcomes?
	# Now let’s look at the program test-and-set.s. First, try to understand the code, which uses the xchg instruction to build a simple locking primitive. How is the lock acquire written? How about lock release?		# Now let’s look at the program test-and-set.s. First, try to understand the code, which uses the xchg instruction to build a simple locking primitive. How is the lock acquire written? How about lock release?

Soma: /* Locks */

2014-10-03T16:52:04Z

Locks

Soma: /* Locks */

2014-10-03T16:49:13Z

Locks

← Older revision		Revision as of 16:49, 3 October 2014
Line 110:		Line 110:

	Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsLocks.tgz (v2)] to answer the following questions from the [http://www.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf Locks] chapter.		Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsLocks.tgz (v2)] to answer the following questions from the [http://www.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf Locks] chapter.

			# First let’s get ready to run x86.py with the flag -p flag.s. This code “implements” locking with a single memory flag. Can you understand what the assembly code is trying to do?
			# When you run with the defaults, does flag.s work as expected? Does it produce the correct result? Use the -M and -R flags to trace variables and registers (and turn on -c to see their values). Can you predict what value will end up in flag as the code runs?
			# Change the value of the register %bx with the -a flag (e.g., -a bx=2, bx=2 if you are running just two threads). What does the code do? How does it change your answer for the question above?
			# Set bx to a high value for each thread, and then use the -i flag to generate different interrupt frequencies; what values lea d to a bad outcomes? Which lead to good outcomes?
			# Now let’s look at the program test-and-set.s. First, try to understand the code, which uses the xchg instruction to build a simple locking primitive. How is the lock acquire written? How a bout lock release?
			# Now run the code, changing the value of the interrupt inter val ( -i ) again, and making sure to loop for a number of times. Does the code always work as expected? Does it sometimes lead to an ine fficient use of the CPU? How could you quantify that?
			# Use the -P flag to generate specific tests of the locking code. For example, run a schedule that grabs the lock in the first thread , but then tries to acquire it in the second. Does the right thing ha ppen? What else should you test?
			# Now let’s look at the code in peterson.s , which implements Peterson’s algorithm (mentioned in a sidebar in the text). Stu dy the code and see if you can make sense of it.
			# Now run the code with different values of -i. What kinds of different behavior do you see?
			# Can you control the scheduling (with the -P flag) to “prove” that the code works? What are the different cases you should show hold? Think about mutual exclusion and deadlock avoidance. Now study the code for the ticket lock in ticket.s. Does it match the code in the chapter?
			# Now run the code, with the following flags: -a bx=1000,bx=1000 (this flag sets each thread to loop through the critical 1000 t imes). Watch what happens over time; do the threads spend much time spinning waiting for the lock?
			# How does the code behave as you add more threads?
			# Now examine yield.s , in which we pretend that a yield instruction enables one thread to yield control of the CPU to another (realistically, this would be an OS primitive, but for the simpl icity of simulation, we assume there is an instruction that does the t ask). Find a scenario where test-and-set.s wastes cycles spinning, but yield.s does not. How many instructions are saved? In what scenarios do these savings arise?
			# Finally, examine test-and-test-and-set.s. What does this lock do? What kind of savings does it introduce as compared to test-and-set.s?

Soma: /* Threads (Intro) */

2014-10-03T16:43:45Z

Threads (Intro)

← Older revision		Revision as of 16:43, 3 October 2014
Line 95:		Line 95:
	* Now run with random interrupt intervals:		* Now run with random interrupt intervals:
	./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 0		./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 0
	Then change the random seed, setting -s 1, then -s 2, etc. Can you tell, just by looking at the thread interleaving, what the final value of x will be? Does the exact location of the interrupt matter? Where can it safely occur? Where does an interrupt cause trouble? In other words, where is the critical section exactly?		:Then change the random seed, setting -s 1, then -s 2, etc. Can you tell, just by looking at the thread interleaving, what the final value of x will be? Does the exact location of the interrupt matter? Where can it safely occur? Where does an interrupt cause trouble? In other words, where is the critical section exactly?
	* Now use a fixed interrupt interval to explore the program further. Run:		* Now use a fixed interrupt interval to explore the program further. Run:
	./x86.py -p looping-race-nolock.s -a bx=1 -t 2 -M 2000 -i 1		./x86.py -p looping-race-nolock.s -a bx=1 -t 2 -M 2000 -i 1

Soma: /* Threads (Intro) */

2014-10-03T16:43:30Z

Threads (Intro)

Soma: /* Threads (Intro) */

2014-10-03T16:43:02Z

Threads (Intro)

← Older revision		Revision as of 16:43, 3 October 2014
Line 78:		Line 78:
	Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsIntro.tgz x86.py (v1)] to answer the following questions from the [http://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf Concurrency: An Introduction] chapter.		Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsIntro.tgz x86.py (v1)] to answer the following questions from the [http://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf Concurrency: An Introduction] chapter.

	# To start, let’s examine a simple program, “loop.s”. First, just look at the program, and see if you can understand it: <tt>cat loop.s</tt>. Then, run it with these arguments:		* To start, let’s examine a simple program, “loop.s”. First, just look at the program, and see if you can understand it: <tt>cat loop.s</tt>. Then, run it with these arguments:
	./x86.py -p loop.s -t 1 -i 100 -R dx		./x86.py -p loop.s -t 1 -i 100 -R dx
	:This specifies a single thread, an interrupt every 100 instructions, and tracing of register %dx. Can you figure out what the value of %dx will be during the run? Once you have, run the same above and use the -c flag to check your answers; note the answers, on the left, show the value of the register (or memory value) after the instruction on the right has run.		:This specifies a single thread, an interrupt every 100 instructions, and tracing of register %dx. Can you figure out what the value of %dx will be during the run? Once you have, run the same above and use the -c flag to check your answers; note the answers, on the left, show the value of the register (or memory value) after the instruction on the right has run.
	# Now run the same code but with these flags:		* Now run the same code but with these flags:
	./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx		./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx
	:This specifies two threads, and initializes each %dx register to 3. What values will %dx see? Run with the -c flag to see the answers. Does the presence of multiple threads affect anything about your calculations? Is there a race condition in this code?		:This specifies two threads, and initializes each %dx register to 3. What values will %dx see? Run with the -c flag to see the answers. Does the presence of multiple threads affect anything about your calculations? Is there a race condition in this code?

Soma: /* Threads (Intro) */

2014-10-03T16:42:30Z

Threads (Intro)

@@ Line 78: / Line 78: @@
 Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsIntro.tgz x86.py (v1)] to answer the following questions from the [http://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf Concurrency: An Introduction] chapter.
 ==Locks==
 Use the program [http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-ThreadsLocks.tgz (v2)] to answer the following questions from the [http://www.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf Locks] chapter.

Soma: /* Paging */

2014-10-03T16:36:10Z

Paging

← Older revision		Revision as of 16:43, 3 October 2014
Line 84:		Line 84:
	./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx		./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx
	:This specifies two threads, and initializes each %dx register to 3. What values will %dx see? Run with the -c flag to see the answers. Does the presence of multiple threads affect anything about your calculations? Is there a race condition in this code?		:This specifies two threads, and initializes each %dx register to 3. What values will %dx see? Run with the -c flag to see the answers. Does the presence of multiple threads affect anything about your calculations? Is there a race condition in this code?
	# Now run the following:		* Now run the following:
	./x86.py -p loop.s -t 2 -i 3 -r -a dx=3,dx=3 -R dx		./x86.py -p loop.s -t 2 -i 3 -r -a dx=3,dx=3 -R dx
	:This makes the interrupt interval quite small and random; use different seeds with -s to see different interleavings. Does the frequency of interruption change anything about this program?		:This makes the interrupt interval quite small and random; use different seeds with -s to see different interleavings. Does the frequency of interruption change anything about this program?
	# Next we’ll examine a different program (looping-race-nolock.s). This program accesses a shared variable located at memory address 2000; we’ll call this variable x for simplicity. Run it with a single thread and make sure you understand what it does, like this:		* Next we’ll examine a different program (looping-race-nolock.s). This program accesses a shared variable located at memory address 2000; we’ll call this variable x for simplicity. Run it with a single thread and make sure you understand what it does, like this:
	./x86.py -p looping-race-nolock.s -t 1 -M 2000		./x86.py -p looping-race-nolock.s -t 1 -M 2000
	:What value is found in x (i.e., at memory address 2000) throughout the run? Use -c to check your answer.		:What value is found in x (i.e., at memory address 2000) throughout the run? Use -c to check your answer.
	# Now run with multiple iterations and threads:		* Now run with multiple iterations and threads:
	./x86.py -p looping-race-nolock.s -t 2 -a bx=3 -M 2000		./x86.py -p looping-race-nolock.s -t 2 -a bx=3 -M 2000
	:Do you understand why the code in each thread loops three times? What will the final value of x be?		:Do you understand why the code in each thread loops three times? What will the final value of x be?
	# Now run with random interrupt intervals:		* Now run with random interrupt intervals:
	./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 0		./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 0
	Then change the random seed, setting -s 1, then -s 2, etc. Can you tell, just by looking at the thread interleaving, what the final value of x will be? Does the exact location of the interrupt matter? Where can it safely occur? Where does an interrupt cause trouble? In other words, where is the critical section exactly?		Then change the random seed, setting -s 1, then -s 2, etc. Can you tell, just by looking at the thread interleaving, what the final value of x will be? Does the exact location of the interrupt matter? Where can it safely occur? Where does an interrupt cause trouble? In other words, where is the critical section exactly?
	# Now use a fixed interrupt interval to explore the program further. Run:		* Now use a fixed interrupt interval to explore the program further. Run:
	./x86.py -p looping-race-nolock.s -a bx=1 -t 2 -M 2000 -i 1		./x86.py -p looping-race-nolock.s -a bx=1 -t 2 -M 2000 -i 1
	:See if you can guess what the final value of the shared variable x will be. What about when you change -i 2, -i 3, etc.? For which interrupt intervals does the program give the “correct” final answer?		:See if you can guess what the final value of the shared variable x will be. What about when you change -i 2, -i 3, etc.? For which interrupt intervals does the program give the “correct” final answer?
	# Now run the same code for more loops (e.g., set -a bx=100). What interrupt intervals, set with the -i flag, lead to a “correct” outcome? Which intervals lead to surprising results?		* Now run the same code for more loops (e.g., set -a bx=100). What interrupt intervals, set with the -i flag, lead to a “correct” outcome? Which intervals lead to surprising results?
	# We’ll examine one last programin this homework (wait-for-me.s). Run the code like this:		* We’ll examine one last programin this homework (wait-for-me.s). Run the code like this:
	./x86.py -p wait-for-me.s -a ax=1,ax=0 -R ax -M 2000		./x86.py -p wait-for-me.s -a ax=1,ax=0 -R ax -M 2000
	:This sets the %ax register to 1 for thread 0, and 0 for thread 1, and watches the value of %ax and memory location 2000 throughout the run. How should the code behave? How is the value at location 2000 being used by the threads? What will its final value be?		:This sets the %ax register to 1 for thread 0, and 0 for thread 1, and watches the value of %ax and memory location 2000 throughout the run. How should the code behave? How is the value at location 2000 being used by the threads? What will its final value be?
	# Now switch the inputs:		* Now switch the inputs:
	./x86.py -p wait-for-me.s -a ax=0,ax=1 -R ax -M 2000		./x86.py -p wait-for-me.s -a ax=0,ax=1 -R ax -M 2000
	:How do the threads behave? What is thread 0 doing? How would changing the interrupt interval (e.g., -i 1000, or perhaps to use random intervals) change the trace outcome? Is the program efficiently using the CPU?		:How do the threads behave? What is thread 0 doing? How would changing the interrupt interval (e.g., -i 1000, or perhaps to use random intervals) change the trace outcome? Is the program efficiently using the CPU?

← Older revision		Revision as of 16:36, 3 October 2014
Line 59:		Line 59:
	paging-linear-translate.py -P 2k -a 1m -p 512m -v -n 0		paging-linear-translate.py -P 2k -a 1m -p 512m -v -n 0
	paging-linear-translate.py -P 4k -a 1m -p 512m -v -n 0		paging-linear-translate.py -P 4k -a 1m -p 512m -v -n 0
	Before running any of these, try to think about the expected trends. How should page-table size change as the address space grows? As the page size grows? Why shouldn’t we just use really big pages in general?		:Before running any of these, try to think about the expected trends. How should page-table size change as the address space grows? As the page size grows? Why shouldn’t we just use really big pages in general?
	* Now let’s do some translations. Start with some small examples, and change the number of pages that are allocated to the address space with the -u flag. For example:		* Now let’s do some translations. Start with some small examples, and change the number of pages that are allocated to the address space with the -u flag. For example:
	paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 0		paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 0
Line 66:		Line 66:
	paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 75		paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 75
	paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 100		paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 100
	What happens as you increase the percentage of pages that are allocated in each address space?		:What happens as you increase the percentage of pages that are allocated in each address space?
	* Now let’s try some different random seeds, and some different (and sometimes quite crazy) address-space parameters, for variety:		* Now let’s try some different random seeds, and some different (and sometimes quite crazy) address-space parameters, for variety:
	paging-linear-translate.py -P 8 -a 32 -p 1024 -v -s 1		paging-linear-translate.py -P 8 -a 32 -p 1024 -v -s 1
	paging-linear-translate.py -P 8k -a 32k -p 1m -v -s 2		paging-linear-translate.py -P 8k -a 32k -p 1m -v -s 2
	paging-linear-translate.py -P 1m -a 256m -p 512m -v -s 3		paging-linear-translate.py -P 1m -a 256m -p 512m -v -s 3
	Which of these parameter combinations are unrealistic? Why?		:Which of these parameter combinations are unrealistic? Why?
	* Use the program to try out some other problems. Can you find the limits of where the program doesn’t work anymore? For example, what happens if the address-space size is bigger than physical memory?		* Use the program to try out some other problems. Can you find the limits of where the program doesn’t work anymore? For example, what happens if the address-space size is bigger than physical memory?