saving the state and restoring it

• program counter, process status word, registsers 

Creating it from scratch:

• Allocate memory
• Load code into memory
• Create (empty) call stack
• Create and initialize process control block
• Make process known to dispatcher

Forking (copying existing process)

• Make sure process to be copied isn't running and has all stave saved
• Make a copy of cade, data, stack
• Copy PCB into new PCB
• Mark process as ready
• Make process known to dispatcher 

• neither affect nor affected by the rest of the universe
• deterministic
• reproducible
• scheduling does not affect the result

• share state
• nondeterministic
• irreproducible

Why allows processes to cooperate?

• want to share resources
• want to do things faster

• References and assignments are atomic in almost all systems
• In uniprocess systems, anything between interrupts is atomic
• If you don't have an atomic operation, you can't make one
• If you have any atomic operation, you can use it to generate higher-level constructs and make parallel programs work correctly

using atomic operations to ensure correct cooperation between processes

•  important to figure out what you want to achieve

1. Must lock before using
2. Must unlock when done
3. Must wait if locked

• Fair
• Efficient
• Simple

• Always lock before manipulating shared date
• Always unlock after manipulating shared data
• Do not lock again if already locked
• Do not unlock if not locked by you
• Do not spend large amounts of time in critical section

An integer variable that can be accessed only through two atom operations

•  P(semaphore): waits for semaphore to become positive, then decrements it by 1
• V(semaphore):increments semaphore by 1

High-level data abstraction tool combining interesting features

• Wait(condition)
• Signal(condition)
• Broadcast(condition)

No existing hardware implementes P&V directly

• Uniprocessor solution: disable interrupts
• Multiprocessos use test and set
• Test-and-set: set value to one, but return old value

• Message: a piece of information that is passed from one process to another
• Mailbox(port): a place where messages are stored until they are received

• Send: copy a message into mailbox
• Receive: copy message out of mailbox, delete from mailbox

• 1-way: messages flow in a single direction
• 2-way: messages flow back-and-forth

Why use messages?

• Many applications fit into the model of processing a sequential flow of information
• less error-prone, because no invisibile side effects
• they might not trust each other
• they might have been written at different times by different programmers
• they might be running on different processors on a network

Differing styles:

• Relationship between mailboxes and processes
• Extent of buffering
• Waiting (blocking vs. non-blocking ops)
• Additional forms of waiting 

• Process coordination
• Resource management

• preemptible (sharable)
• non-preemptible (non-sharable)

• Allocation: who gets what
• Scheduling: how long can they keep it

• Running
• Ready
• Blocked 

• Efficiency of resource utilization
• Minimize overhead
• Minimize response time
• Distribute cycles equitably

Problem: slow, inefficient

Solution: limit maximum amount of time that a process can run without a context switch 

Run process for one time slice, then move to back of queue

• Each process can run without a context switch
• Too long, it becomes like FIFO
• Too short, there's too much overhead from context switching
• Implement priorities with priority queues

Exponential Queue

(Multi-Level Feedback Queue) 

Give newly runnable process a high priority and a very short time slice. If process uses up the time slice without blocking then decrease priority by 1 and double time slice for next time

Example of an adaptive techinque, common to interactive systems 

• Keep history of recent CPU usage for each process
• Give highest priority to process that has used the least CPU time recently
• Can adjust priorities by changing "billing factors" for processes

• Analytic methods
  • deterministic modeling
  • queueing model
• simulation
• implementation

a situation where each of a collection of processes is waiting for something from other processes in the collection 

• Mutual exclusion
• No preemption
• Hold and wait
• Circular waiting 

Detection and resolution: determine when the system is deadlocked and then take drastic action

• Requires termination of one or more processes in order to release their resources
• Not very practical

Prevention: organize the system so that it is impossible for deadlock ever to occur

• May lead to less efficient resource utilization in order to guarantee no deadlocks

must find a way to eliminate one of the four necessary conditions for deadlock

• Don't allow exclusive access (not reasonable for many applications)
• Create enough resources so that there's always plenty for all
• Don't allow waiting (puts the problem back to the user)
• Allow preemption (ex. preempt student's thesis disk space)

Make process ask for everything at once. Either get them all or wait for them all

• must be able to wait on many things without locking anything 

Define an ordering among resources and enforce it. Make ordered or hiearchical requests. All processes must follow the same ordering scheme 

• Static allocation: finding a slot in memory big enough to load a.out
• Dynamic allocation: while executing the program, finding space for additional memory requests

• Recursive procedures
• Complex structures

• Allocate
• Free

• Stack allocation (hierarchical; LIFO): restricted but simple and efficient
• Heap allocation: more general, but less efficient, more difficult to implement

memory allocation and freeing are partially predictable (we do better when we can predict the future)

• Allocation is hierchical: memory is freed in opposite order from allocation
• Stacks are also useful for lots of other things: tree traversel, expression evaluation, top-down recursive descent parsers
• A stack-based organization keeps all the free space together in one place 

Allocation and release are unpredictable. Heaps are used for arbitrary list structures, complex data organizations

• Memory consists of allocated areas and free areas (or holes). Inevitably end up with lots of holes. Goals: reuse the space in holes to keep the number of holes small, their size large
• Fragmentation: inefficient use of memory due to holes that are too small to be useful. In stack allocation, all the holes are together in one big chunk
• Typically, heap allocation schemes use a free list to keep track of the storage that is not in use. Algorithm differ in how they managethe free list
• Best fit: keep linked list of free blocks, search the whole list on each allocation, choose block that comes closest to matching the needs of the allocation,save the excess for later. during release operations, merge adjacent free blocks.
• First fit: just scan list for the first hole that is large enough. Merge on releases
• First fit tends to leave "average" size holes, while best fit tends to leave some very large ones, some very small ones. The very small ones can't be used very easily

How do we know when dynamically-allocated memory can be freed?

• Easy when a chunk is only used in one place
• Hard when information is shared: it can't be recycle until all of the sharers are finished. Sharing is indicated by the presence of pointers to the data

• Reference counts: keep track of the number of outstanding pointers to each chunk of memory. when this goes to zero, free the memory.
• Garbage collection: no explicit free operation. when the system needs storage, it searches through all of the pointers (must be able to find them all) and collects things that aren't used. If structues are circular then this is the only way to reclaim space. Makes life easier on the applicatio programmer, but garbage collectors are incredibly difficult to program and debug, especially if compaction is also done.
  • Must be able to find all pointers to objects
  • Must be able to find all objects

• Garbage collection is often expensive: 10% or more of CPU time used in systems that use it.

Issues:

• Transparency: no process should need to be aware of the fact that memory is shared. Each must run regardless of the number and/or locations of processes
• Protection: processes must not be able to corrupt each other
• Efficiency shouldn't be degraded badly by sharing 

• Highest memory holds OS
• Process is allocated memory starting at 0, up to the OS area
• When loading a process, just bring it in at 0

Relocation adjusts a program to run in a different area of memory 

Static relocation

• Highest memory holds OS
• Processes allocated memory starting at 0, up to the OS area
• When a process is loaded, relocate it so that it can run in its allocated memory area
• Problem: not much protection; hard to relocate later, once it starts running

Dynamic relocation: instead of changing the addresses of a program before it's loaded, change the address dynamically during every reference

• Each program-generated address (called logical address) is translated in hardware to a physical address. This happens as part of each memory reference.
•  Good example of indirection

Base and limit relocation:

• Two hardware registers: base address for process, limit register that indicates the last valid address the process may generate.
• Each process must be allocated contiguously in real memory
• On each memory reference, the virtual address is compared to the limit regist, then added to the base register. A limit violation results in an error trap.
• Each process appears to have a completely private memory of size equal to the limit register plus 1. Processes are protected from each other. No address relocation is necessary when a process is loaded.
• OS runs with relocation turned off
• OS must prevent users from turning off relocation or modifying the base and limit registers
• Base and limit is cheap (only 2 registers) and fast (add and compare can be done in parallel)
• Problem: only one segment

Multiple segments

• Permit process to be split between several areas of memory
• Use a separate base and limit for each segment, and also add two protection bits (read and write)
• Each memory reference indicates a segment and offset. Top bit of address select segment, low bits the offset
• Segment table holds the bases and limit for all the segments of a process
• Memory mapping procedure consists of table lookup + add + compare 

Managing segments 

• Keep copy of segment table in PCB
• When creating process, allocate space for segment, fill in PCB bases and limits
• When switching contexts, save segment table inold process's PCB, reload it from new process's PCB
• When process dies, returns segments to free pool
• When then no space to allocate a new segment
  • Compact memory to get all free space together
  • Or swap one or more segments to disks to make space
• To enlarge segment
  • See if space above segment is free. If so, update limit and use that space.
  • Or, move the segment above this one to disk, in order to make the memory free.
  • Or, move this segment to disk and bring it back into a larger hole
• Problem: external fragmentation: segments of many different sizes, have to be allocated contiguously