COMP 3000 2012 Week 10 Notes

Concurrency

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

Mutual exclusion

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.

Concerning the lab:

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

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

Mutex

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 wiki

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 [1]

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".
What are frames vs pages?
- 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)
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
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