COMP 3000 2012 Week 10 Notes

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.

Concerning the lab:

• 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 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

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 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

• | 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 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?
  • There is a great example of this on wikipedia