Shared Flashcard Set

Details

CS414
Operating Systems
48
Computer Science
Undergraduate 3
05/07/2008

Additional Computer Science Flashcards

 


 

Cards

Term
Context switching
Definition

saving the state and restoring it

 

  • program counter, process status word, registsers 
Term
Birth of a process
Definition

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 
Term
Independent process
Definition
  • neither affect nor affected by the rest of the universe
  • deterministic
  • reproducible
  • scheduling does not affect the result
Term
Cooperating processes
Definition
  • share state
  • nondeterministic
  • irreproducible


Why allows processes to cooperate?

  • want to share resources
  • want to do things faster
Basic assumption for cooperating process systems is that the order of some operations is irrelevant; certain operations are independent of certaion other operations
Term
Atomic operations
Definition
  • 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
Term
Synchronization
Definition

using atomic operations to ensure correct cooperation between processes

  •  important to figure out what you want to achieve
Term
Mutual exclusion
Definition
mechanisms that ensure that only one process is doing certain things at one time
Term
Critical section
Definition
a section of code, or collection of operations, in which only one process may be executing at a given time
Term
Three elements of locking
Definition
  1. Must lock before using
  2. Must unlock when done
  3. Must wait if locked
Term
Desirable properties from mutual exclusion
Definition
  • Fair
  • Efficient
  • Simple
Term
Desirable properties of processes using mutual exclusion
Definition
  • 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
Term
Semaphore
Definition

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
Semaphores used for mutual exclusion and scheduling
Term
Reader process
Definition
P(Mutex);
if ((AW+WW) == 0) {
V(OKToRead);
AR = AR+1;
} else {
WR = WR+1;
}
V(Mutex);
P(OKToRead);
-- read the necessary data;
P(Mutex);
AR = AR-1;
if (AR==0 && WW>0) {
V(OKToWrite);
AW = AW+1;
WW = WW-1;
}
V(Mutex);
Term
Writer process
Definition
P(Mutex);
if ((AW+AR+WW) == 0) {
V(OKToWrite);
AW = AW+1;
} else {
WW = WW+1;
}
V(Mutex);
P(OKToWrite);
-- write the necessary data;
P(Mutex);
AW = AW-1;
if (WW>0) {
V(OKToWrite);
AW = AW+1;
WW = WW-1;
} else while (WR>0) {
V(OKToRead);
AR = AR+1;
WR = WR-1;
}
V(Mutex);
Term
Monitors
Definition

High-level data abstraction tool combining interesting features

  • Wait(condition)
  • Signal(condition)
  • Broadcast(condition)
monitor QueueHandler;
struct {int first, last, buffer[200]} queue;
condition q;
AddToQueue(val)
int val;
{ -- add val to end of queue -- }
signal(q);
int RemoveFromQueue()
if (QueueEmpty)
wait(q);
remove first element;
return it;
endmonitor;
Term
Semaphore implementation
Definition

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
typedef struct {
    int count;
    queue q;
    int t;
} SEMAPHORE;
P(s)
SEMAPHORE *s;
{
    Disable interrupts;
    while (TAS(s->t) != 0) /* do nothing */;
    if (s->count > 0) {
        s->count = s->count-1;
        s->t = 0;
        Enable interrupts;
        return;
    }
    Add process to s->q;
    s->t = 0;
    Redispatch;
}
V(s)
SEMAPHORE *s;
{
    Disable interrupts;
    while (TAS(s->t) != 0) /* do nothing */;
    if (s->q empty) {
        s->count += 1;
    } else {
        Remove first process from s->q;
        Wake it up;
    }
    s->t = 0;
    Enable interrupts;
}
Term
Message Communication
Definition
  • 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 
Term
Operating systems typically consists of two parts:
Definition
  • Process coordination
  • Resource management
Term
Resources fall into two classes:
Definition
  • preemptible (sharable)
  • non-preemptible (non-sharable)
Term
OS makes two related kinds of decisions about resources
Definition
  • Allocation: who gets what
  • Scheduling: how long can they keep it
Term
Process scheduling states
Definition
  • Running
  • Ready
  • Blocked 
Term
Goals for scheduling disciplines
Definition
  • Efficiency of resource utilization
  • Minimize overhead
  • Minimize response time
  • Distribute cycles equitably
Term
FIFO
Definition

Problem: slow, inefficient

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

Term
Round Robin
Definition

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
Term
Shortest Time to Completion First
Definition
Can't use because we need to be able to predict the future
Term
General rule: Give the most to those who need the least
Definition
Term

Exponential Queue

(Multi-Level Feedback Queue) 

Definition

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 

Term
Fair-share scheduling
Definition
  • 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
Term
Performance evaluation of scheduling algorithms:
Definition
  • Analytic methods
    • deterministic modeling
    • queueing model
  • simulation
  • implementation
Term
Deadlock
Definition

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

Term
Conditions for deadlock
Definition
  • Mutual exclusion
  • No preemption
  • Hold and wait
  • Circular waiting 
Term
Solutions to deadlock
Definition

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
Avoidance: divide into safe and unsafe state (Banker's algorithm). Each process declares max resource requirement for each resource type, and the system maintains necessary information to avoid unsafe state 
Term
Deadlock prevention
Definition

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)
Term
Attack hold and wait
Definition

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 
Term
Attack circular wait
Definition

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

Term
Aspects of memory allocation
Definition
  • 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
OS cannot predict when a process will come and ask for storage space: Need dynamic memory allocation both for main memory and for file space on disk
Term
Static allocation isn't sufficient for everything
Definition
  • Recursive procedures
  • Complex structures
Term
Basic operations in dynamic storage management
Definition
  • Allocate
  • Free
Term
Dynamic allocation can be handled in one of two ways:
Definition
  • Stack allocation (hierarchical; LIFO): restricted but simple and efficient
  • Heap allocation: more general, but less efficient, more difficult to implement
Term
Stack organization
Definition

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 
Term
Heap organization
Definition

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
Term
bit map
Definition
used for allocation for storage that comes in fixed-sized chunks. Keep a large array of bits, one for each chunk. If bit is 0, it means chunks is in use; if 1, it means chunk is free. When freeing, no need to merge.
Term
Problems with BF, FF, bitmap?
Definition
Pools: keep a separate allocation ppol for each popular size. Allocation is fast, no fragmentation. It may get some inefficiency if some pools run out while other pools have lots of free blocks: get shuffle between pools.
Term
Reclamation
Definition

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.
Term
Goal: let several processes co-exist in memory
Definition

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 
Term
Uniprogramming with a single segment per process
Definition
  • 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
Term
Relocation
Definition

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 
Term

Managing segments 

Definition
  • 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
Supporting users have an ad free experience!