COMP 3000 2012 Week 10 Notes - Revision history

Cdelahou at 23:11, 13 December 2012

2012-12-13T23:11:20Z

← Older revision		Revision as of 23:11, 13 December 2012
Line 114:		Line 114:
	** is that memory location valid? Pages are a sparse data structure, so there's alot of null pointer		** is that memory location valid? Pages are a sparse data structure, so there's alot of null pointer
	** is it accessible? Do we have permission to access it?		** is it accessible? Do we have permission to access it?
	** is it dirty? dirty means ~~not~~ stored on disk		** is it dirty? dirty means the page has been changed. These changes are no longer stored on disk, so the next time we write to the page file, we'll write this page.
	** is this accessed?		** is this accessed?
	** There is a great example of this on wikipedia		** There is a great example of this on wikipedia

Cdelahou: added page table bits

2012-12-13T22:40:51Z

added page table bits

← Older revision		Revision as of 22:40, 13 December 2012
Line 101:		Line 101:
	Page table		Page table
	* every process has its own page table (of virt --> phys. mapping)		* every process has its own page table (of virt --> phys. mapping)
			* a "page walk" only happens if the memory address mapping does not exist in the TLB.
			* once found in the table, an address is written to the TLB
	* it's a tree where every node is a page table pointing to another page table		* it's a tree where every node is a page table pointing to another page table
	* shallow and sparse tree		* shallow and sparse tree

Cdelahou: blarg

2012-11-14T19:33:01Z

blarg

← Older revision		Revision as of 19:33, 14 November 2012
Line 73:		Line 73:
	** Can only cache a subset of memory address mappings.		** Can only cache a subset of memory address mappings.

	Segmented Memory [[http://en.wikipedia.org/wiki/Virtual_memory#Segmented_virtual_memory]]		Segmented Memory [http://en.wikipedia.org/wiki/Virtual_memory#Segmented_virtual_memory wiki]
	* base, bound		* base, bound
	* break memory mappings into segments		* break memory mappings into segments
Line 81:		Line 81:
	** you need to break up the new allocations into other segments		** you need to break up the new allocations into other segments

	Paged virtual memory [[http://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory]]		Paged virtual memory [http://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory]
	* like segmented memory, but with fixed sizes.		* like segmented memory, but with fixed sizes.
	* fixed sizes are called page sizes		* fixed sizes are called page sizes

Cdelahou: fixed links

2012-11-14T19:31:37Z

fixed links

← Older revision		Revision as of 19:31, 14 November 2012
Line 73:		Line 73:
	** Can only cache a subset of memory address mappings.		** Can only cache a subset of memory address mappings.

	Segmented Memory [http://en.wikipedia.org/wiki/Virtual_memory#Segmented_virtual_memory]		Segmented Memory [[http://en.wikipedia.org/wiki/Virtual_memory#Segmented_virtual_memory]]
	* base, bound		* base, bound
	* break memory mappings into segments		* break memory mappings into segments
Line 81:		Line 81:
	** you need to break up the new allocations into other segments		** you need to break up the new allocations into other segments

	Paged virtual memory [http://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory]		Paged virtual memory [[http://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory]]
	* like segmented memory, but with fixed sizes.		* like segmented memory, but with fixed sizes.
	* fixed sizes are called page sizes		* fixed sizes are called page sizes
Line 88:		Line 88:
	* so you try to get smaller page sizes to avoid internal fragmentation		* so you try to get smaller page sizes to avoid internal fragmentation
	* if you get too small though, you run out of space for mappings in the TLB		* if you get too small though, you run out of space for mappings in the TLB
	* memory gets loaded into "frames"		* memory gets loaded into "frames".
			* What are frames vs pages?
			** frames are only loaded in memory when you need them.
	* frames are only loaded in memory when you need them.		** you can unload frames when you're not using them
	* you can unload frames when you're not using them

Cdelahou: added virt mem.

2012-11-09T17:56:13Z

added virt mem.

← Older revision		Revision as of 17:56, 9 November 2012
Line 59:		Line 59:
	* mutual exclusion		* mutual exclusion
	* flock is a file based mutext		* flock is a file based mutext

			=== VIRTUAL MEMORY (revisited) ===
			Purpose: Create an abstraction from physical memory
			** Simplicity: unified memory interface
			** protection: no memory overwritten between programs
			* [ http://en.wikipedia.org/wiki/Virtual_memoryhttp://en.wikipedia.org/wiki/Virtual_memory ]

			MMU - Memory management unit
			* chip that virtual addressing is deferred to
			* Translation Lookaside Buffer [ http://en.wikipedia.org/wiki/Translation_lookaside_bufferhttp://en.wikipedia.org/wiki/Translation_lookaside_buffer TLB]
			** Cache (table) of virtual to physical mappings of memory
			** Must be done in constant time, but this is hard
			** Can only cache a subset of memory address mappings.

			Segmented Memory [http://en.wikipedia.org/wiki/Virtual_memory#Segmented_virtual_memory]
			* base, bound
			* break memory mappings into segments
			* trying to map segments with variable sizes
			* fundamental weakness: fragmentation
			** based on passed allocation, you don't have a contiguous places to write new memory locations
			** you need to break up the new allocations into other segments

			Paged virtual memory [http://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory]
			* like segmented memory, but with fixed sizes.
			* fixed sizes are called page sizes
			* easier to stack fixed sizes
			* tradeoff is more internal fragmentation (within the page) (vs. segmented memory)
			* so you try to get smaller page sizes to avoid internal fragmentation
			* if you get too small though, you run out of space for mappings in the TLB
			* memory gets loaded into "frames"


			* frames are only loaded in memory when you need them.
			* you can unload frames when you're not using them



			* you can swap pages in physical memory with locations in a page file on the HD (when you run out of phys. memory)
			* security implications: deleting from disk or ram doesn't mean the data has disappeared. You typically have the option of encrypting to disk


			Page table
			* every process has its own page table (of virt --> phys. mapping)
			* it's a tree where every node is a page table pointing to another page table
			* shallow and sparse tree
			* every 10 bits in an virtual mem address (32bit) represent the path which we take when we descent from the root, the offset is
			* \|10\|10\|12\| -> first 20=10+10 bits is the path, the 12 bit represents the location within the frame that the leaf will point to


			Page table entries
			* \| frame number (20 bits) \| meta data (12 bits) \|
			* What does the meta data say?
			** is that memory location valid? Pages are a sparse data structure, so there's alot of null pointer
			** is it accessible? Do we have permission to access it?
			** is it dirty? dirty means not stored on disk
			** is this accessed?
			** There is a great example of this on wikipedia

Cdelahou: more formatting

2012-11-08T17:27:47Z

more formatting

← Older revision		Revision as of 17:27, 8 November 2012
Line 5:		Line 5:
	** multi processes		** multi processes
	** multi hosts		** multi hosts
	**Kernel tasks/ handlers		** Kernel tasks/ handlers

	Mutual exclusion		Mutual exclusion
	*"Take turns"		* "Take turns"

	HOw?		HOw?
Line 19:		Line 19:
	** Between the if statment and the assignment, the CPU may schedule anothe rprocedure that accesses variable m.		** Between the if statment and the assignment, the CPU may schedule anothe rprocedure that accesses variable m.

	Concerning ~~assignement~~:		Concerning the lab:
	* Each echo (line) is atomic.		* Each echo (line) is atomic.
	* Flock controls access to writing to race.txt		* Flock controls access to writing to race.txt
	* Flock tries to write to lock, but if it can't, it'll wait		* Flock tries to write to lock, but if it can't, it'll wait

	Starvation		Starvation
	* There's an issue with writing and reading locks		* There's an issue with writing and reading locks
	* If a process depends on a lock and that lock is never freed, that process will starve		* If a process depends on a lock and that lock is never freed, that process will starve

	Deadlock		Deadlock

Cdelahou: formatting

2012-11-08T17:25:55Z

formatting

← Older revision		Revision as of 17:25, 8 November 2012
Line 1:		Line 1:

	Concurrency		Concurrency
	Examples:		*Examples:
	- multi threaded		** multi threaded
	- multi processes		** multi processes
	- multi hosts		** multi hosts
	- Kernel tasks/ handlers		**Kernel tasks/ handlers

	Mutual exclusion		Mutual exclusion
	"Take turns"		*"Take turns"

	HOw?		HOw?
	* State "variable". Stores state saying who's turn is it? COudl be memory location,		* State "variable". Stores state saying who's turn is it? COudl be memory location, variable, file on disk
	variable, file on disk
	* These include locks, semaphores, mutexes, monitors		* These include locks, semaphores, mutexes, monitors

	* Variables: set a variable to true or false if a current facility is being used.		* Variables: set a variable to true or false if a current facility is being used. THis is a stupid method though, because two procedures may write to that variable at the same time
	THis is a stupid method though, because two procedures may write to that
	variable at the same time
	* "TOCTTOU" Time to check to time to use:		* "TOCTTOU" Time to check to time to use:
	** if ( m < 1) then m = 1;		** if ( m < 1) then m = 1;
	** Between the if statment and the assignment, the CPU may schedule anothe rprocedure that accesses		** Between the if statment and the assignment, the CPU may schedule anothe rprocedure that accesses variable m.
	variable m. ~~Your c~~

	Concerning assignement:		Concerning assignement:
Line 30:		Line 26:
	Starvation		Starvation
	* There's an issue with writing and reading locks		* There's an issue with writing and reading locks
	* If a process depends on a lock and that lock is never freed, that process will		* If a process depends on a lock and that lock is never freed, that process will starve
	starve

	Deadlock		Deadlock

Cdelahou: added initial notes

2012-11-07T17:57:31Z

added initial notes

New page

Concurrency
Examples:
- multi threaded
- multi processes
- multi hosts
- Kernel tasks/ handlers

Mutual exclusion
"Take turns"

HOw?
* State "variable". Stores state saying who's turn is it? COudl be memory location,
variable, file on disk
* These include locks, semaphores, mutexes, monitors

* Variables: set a variable to true or false if a current facility is being used.
THis is a stupid method though, because two procedures may write to that
variable at the same time
* "TOCTTOU" Time to check to time to use:
** if ( m < 1) then m = 1;
** Between the if statment and the assignment, the CPU may schedule anothe rprocedure that accesses
variable m. Your c

Concerning assignement:
* Each echo (line) is atomic.
* Flock controls access to writing to race.txt
* Flock tries to write to lock, but if it can't, it'll wait

Starvation
* There's an issue with writing and reading locks
* If a process depends on a lock and that lock is never freed, that process will
starve

Deadlock
* "Death Pact"
* Mutually dependent on resources
* see [http://en.wikipedia.org/wiki/Deadlock wikipage]
* happens when there are multiple locks

*requirements for deadlock:
** mutual exclusion
** hold + wait.
** no preemption. "Sit there, waiting for that lock forever"
** circular wait "I'm waiting on you you and you're waiting on me"

* How do deal with deadlock?
** 1. Ignore it! Ostrich algorithm
** 2. detection. Are we in deadlock?
*** Example: Timeout. If a process times out, then it's depending on resources that
aren't there.
*** Watchdog timer. "If you don't call me every 30 minutes, call the cops!!!"
**** check state every interval, react if something isn't right
** 3. Prevention. Make sure that one of the one of the requirements for deadlock is never satisfied
** 4. Avoidance. Requirements are satisfied... So watch the transactions to see if
anything fishy happens. If so, pull out. (banker's algorithm):w

Semaphores
* just a counting variable

Mutex
* semaphore with values of either 1 or 0
* mutual exclusion
* flock is a file based mutext