Virtual Memory

It is desirable to be able to execute a process whose logical address space is larger than the available physical address space. Virtual memory is a technique that enables us to map a large logical address space onto a smaller physical memory. Virtual memory allowrs us to run extremely large processes and to raise the degree of multiprogramming, increasing CPU utilization. Further, it frees application programmers from worrying about memory availability. In addition, with virtual memory, several processes can share system libraries and memory. Virtual memory also enables us to use an efficient type of process creation known as copy-on-write, wherein parent and child processes share actual pages of memory.

Virtual memory is commonly implemented by demand paging. Pure demand paging never brings in a page until that page is referenced. The first reference causes a page fault to the operating system. The operating-system kernel consults an internal table to determine where the page is located on the backing store. Tt then finds a free frame and reads the page in from the backing store. The page table is updated to reflect this change, and the instruction that caused the page fault is restarted. This approach allows a process to run even though its entire memory image is not in main memory at once. As long as the page-fault rate is reasonably low, performance is acceptable.

We can use demand paging to reduce the number of frames allocated to a process. This arrangement can increase the degree of multiprogramming (allowing more processes to be available for execution at one time) and—in theory, at least—the CPU utilization of the system. It also allows processes to be run even though their memory requirements exceed the total available physical memory Such processes run in virtual memory.

If total memory requirements exceed the physical memory, then it may be necessary to replace pages from memory to free frames for new pages. Various page-replacement algorithms are used. FIFO page replacement is easy to pro- gram but suffers from Belady's anomaly. Optimal page replacement requires future knowledge. LRU replacement is an approximation of optimal page replacement, but even it may be difficult to implement. Most page-replacement algorithms, such as the second-chance algorithm, are approximations of LRU replacement.

In addition to a page-replacement algorithm, a frame-allocation policy is needed. Allocation can be fixed, suggesting local page replacement, or dynamic, suggesting global replacement. The working-set model assumes that processes execute in localities. The working set is the set of pages in the current locality. Accordingly, each process should be allocated enough frames for its current working set. If a process does not have enough memory for its working set, it will thrash. Providing enough frames to each process to avoid thrashing may require process swapping and scheduling.

Most operating systems provide features for memory mapping files, thus allowing file I/O to be treated as routine memory access. The Win32 API implements shared memory through memory mapping files.
Kernel processes typically require memory to be allocated using pages that are physically contiguous. The buddy system allocates memory to kernel processes in units sized according to a power of 2, which often results in fragmentation. Slab allocators assign kernel data structures to caches associated with slabs, which are made up of one or more physically contiguous pages. With slab allocation, no memory is wasted due to fragmentation, and memory requests can be satisfied quickly.

In addition to requiring that we solve the major problems of page replacement and frame allocation, the proper design of a paging system requires that we consider page size, I/O, locking, prepaging, process creation, program structure, and other issues.

Deadlock

====== Deadlock  =====

Conditions for Deadlock

1. deadlock prevention

2. deadlock avoidance

Prevention

- made some one of the conditions necessary for deadlock don't hold

Avoidance

- OS gets info about what resources a process may require during its lifetime anbased on 

this makes decisions about whether immediately grant request or to make a process wait.

Prevention

----------

1. Mutual Exclution

- some resources sharable e.g. reading files.

- some resources intringsically not sharable.

* CAN NOT prevent deadlock by preventing the mutual exclusive condition.

2. Hold and wait

- make process request all the resources it needs at the start.

- cons:

- resource utilization.

- let a process request a resources only if it holds none.

- cons: starvation

3. No Preemption (of already allocated resoruces)

- protocal 1

P holds R1.....Rn, requests Rm;

Rm not available

resources held (R1...Rn) are implicitely released.

P now waiting for R1...Rn,Rm, resumes when they are available

- protocal 2

P requests R1,...Rn

if available, 

P gets them

else if they are allocated to another process P2 that is waiting for other resources,

then they are taken from P2 and gien to P

else not availabe & not allocated to processes waiting on something

P waits.

while P waits some of its resources may be preempted.

4. Circular Wait

- Define a total order > on the resource types

F:R -> N

- Protocal 1

Process request resources in increasing order

- request instances of Ri (all needed instances at once)

- later request Rj only if F(Rj) > F(Ri)

- Protocal 2

Before Rj requested process must release all instances of Ri s.t. F(Ri) >= F(Rj)

NEVER holding resources numbered higher than the ones  ???? requesting

then no circular wait.

Deadlock Avoidance

-------------------

- use information about a process's possible future resource use.

- OS gets info about max # of (instances of each) resource-type that a process needs.

Algorithm looks at resource allocation stat to avoid circular conditions.

- resource allocation state = f(# of availabe resources, 

# of allocated resources, 

max possible demands of the processes)

Safe State

-----------

- if the system can allocate resources to each process (up to its maximum) in some order and  still avoid a deadlock,

i.e. if there exists a safe sequence (of processes)

sequence <P1,P2,Pi,..Pn> is a safe sequence for the currenct allocation state, 

if for each Pi the resources that Pi can still request 

can be satisfied by 

- currently available resources and 

- resources held by all Pj, j<i

(P1 can request all availabe resources because no resources is held.

P2 can request all avilable resources + resources held by P1.

etc......)

Example.(P.257)

12 units of resources

Processes P0, P1, P2

Process Max Needs Cuurent Allocated

====== ========= =================

P0 10 5

P1 4 2

P2 9 2

--------

3 available

System IS in a safe state

safe sequence: <P1, P0,P2>

P1, : needs 2 more resources (that can be get from available resources)

P0: needs 5, = 3 free + 2 held by P1

P2: needs 7, = 3 free + 2 from P1 + 5 from P0

Go from safe to unsafe:

P2 request and is allocated 1 more unit

Process Max Needs Cuurent Allocated

====== ========= =================

P0 10 5

P1 4 2

P2 9 3

--------

2 available

any sequence must start with : P1 needs 2 more resources

<P1, P0  

P1: needs 2 = 2 free 

P0: needs 5 > 2 free + 2 from P1

 OR <P1, P2

P1: needs 2 = 2 free 

P2: needs 6 > 2 free + 2 from P1

So system won't immediately grant P2's request

Resource Allocation from Graph algorithm  (See notes on paper)

- for 1 instance per resource

- resource use (max) known in advance

- reqeust edge 

Banker's Algorithm

------------------

extension of safe state idea

- n processes in resources

- data structure used

available   

  0 m-1

-------------------------------------

| | | | | | | | | |  # of units of each resource still unallocated.

-------------------------------------

max

  ------------------------------------

i |___________________________________|

  |___________________________________|

n |___________________________________|

max(i,j) max # of units of resource j needed by process i

alloc 

m

  ------------------------------------

  |___________________________________|

  |___________________________________|

n |___________________________________|

alloc(i,j) process i currently holding this many units of resource j

Need : "could still need"

m

  ------------------------------------

  |___________________________________|

  |___________________________________|

n |___________________________________|

need(i,j): # of units of resources j that may still be needed by process i

need = max - alloc

ResourceTotal

  0 m-1

-------------------------------------

| | | | | | | | | |  # of units of each resource still unallocated.

-------------------------------------

avail[j] = resourceTotal[j] - Sum(alloc[ij])

Safety Algorithm

----------------

See if there is an order of processes(safe sequence) Pi0, Pi1.... where we can do the following:

1. satifsy the outstanding need of process Pi0 with unused resources which is available only.

2. consider Pi0 finished and rturn its resources.

3. repeat for Pi1, Pi2, ... etc.

Notes: if there is more than one candidate for Pi0, it does NOT matter which one you choose.

Example:

4 resources R0,R1,R2,R3

5 processes: P0,P1,P2,P3,P4

resourceTotal  

R0 R1 R2 R3

---------------------------------

| 8 | 5 | 9 | 1 |

---------------------------------

Max:

-------------------------------------

| R0 | R1 | R2 | R3 |

-------------------------------------

P0 | 3 | 2 | 1 | 4 |

-------------------------------------

P1 | 0 | 2 | 5 | 2 |

-------------------------------------

P2 | 5 | 1 | 0 | 5 |

-------------------------------------

P3 | 1 | 5 | 3 | 0 |

-------------------------------------

P4 | 3 | 0 | 3 | 3 |

-------------------------------------

Alloc

-------------------------------------

| R0 | R1 | R2 | R3 |

-------------------------------------

P0 | 2 | 0 | 1 | 1 |

-------------------------------------

P1 | 0 | 1 | 2 | 1 |

-------------------------------------

P2 | 4 | 0 | 0 | 3 |

-------------------------------------

P3 | 0 | 2 | 1 | 0 |

-------------------------------------

P4 | 1 | 0 | 3 | 0 |

-------------------------------------

Total| 7 | 3 | 7 | 5 |

-------------------------------------

NEED:

-------------------------------------

| R0 | R1 | R2 | R3 |

-------------------------------------

P0 | 1 | 2 | 0 | 3 |

-------------------------------------

P1 | 0 | 1 | 3 | 1 |

-------------------------------------

P2 | 1 | 1 | 0 | 2 |

-------------------------------------

P3 | 1 | 3 | 2 | 0 |

-------------------------------------

P4 | 2 | 0 | 0 | 3 |

-------------------------------------

NEED = MAX - ALLOC

---------------------------------

| R0 | R1 | R2 | R3 |

---------------------------------

ResourceTotal | 8 | 5 | 9 | 7 |

---------------------------------

TotalAlloc | 7 | 3 | 7 | 5 |

---------------------------------

Avail | 1 | 2 | 2 | 2 |

---------------------------------

1. Find need[i] such that avail >= need[i]

- only P2

2. consider P2 done return its resources

change Avail: = Avial + alloc

(alloc, NOT need)

---------------------------------

Avail | 5 | 2 | 2 | 5 |

---------------------------------

P2 DONE.

3. back to 1. Find another satisfiable Process

- P0 or P4

4. consider P0 (arbitrarily) done + its resources returnd.

- change avail

---------------------------------

Avail | 7 | 2 | 3 | 6 |

---------------------------------

P0 done

5. find next satisfiable process.

- P1 or P4

6. Consider P1 done, return its resources

---------------------------------

Avail | 7 | 3 | 5 | 7 |

---------------------------------

7. remaining processes P3, P4 satisfiable.

State IS SAFE.

State safe. Now comes a request from P3 for 1 unit of R0.

i.e.  P3 requests <1,0,0,0>

Consider request by temprorily changing the allocation to reflect granting request.

Alloc

-------------------------------------

| R0 | R1 | R2 | R3 |

-------------------------------------

P0 | 2 | 0 | 1 | 1 |

-------------------------------------

P1 | 0 | 1 | 2 | 1 |

-------------------------------------

P2 | 4 | 0 | 0 | 3 |

-------------------------------------

P3 | 1 | 2 | 1 | 0 |

-------------------------------------

P4 | 1 | 0 | 3 | 0 |

-------------------------------------

Total| 8 | 3 | 7 | 5 |

-------------------------------------

NEED:

-------------------------------------

| R0 | R1 | R2 | R3 |

-------------------------------------

P0 | 1 | 2 | 0 | 3 |

-------------------------------------

P1 | 0 | 1 | 3 | 1 |

-------------------------------------

P2 | 1 | 1 | 0 | 2 |

-------------------------------------

P3 | 0 | 3 | 2 | 0 |

-------------------------------------

P4 | 2 | 0 | 0 | 3 |

-------------------------------------

---------------------------------

| R0 | R1 | R2 | R3 |

---------------------------------

ResourceTotal | 8 | 5 | 9 | 7 |

---------------------------------

TotalAlloc | 8 | 3 | 7 | 5 |

---------------------------------

Avail | 0 | 2 | 2 | 2 |

---------------------------------

So avail is 0, 2 ,2 ,2

What can be first process in safe sequence??

- NO process 

- So NO Safe Sequence

------------------------------

This means granting P3's request would put the system into an unsafe state,

Must wait to satisfy request.

------------------------------

Aside. A request by P3 for 2 units of R0 would exceeds system resources.

sem_overview

Name
sem_overview - Overview of POSIX semaphores

Description

POSIX semaphores allow processes and threads to synchronise their actions.

A semaphore is an integer whose value is never allowed to fall below zero. Two operations can be performed on semaphores: increment the semaphore value by one (sem_post(3)); and decrement the semaphore value by one (sem_wait(3)). If the value of a semaphore is currently zero, then a sem_wait(3) operation will block until the value becomes greater than zero.

POSIX semaphores come in two forms: named semaphores and unnamed semaphores.

lseek() - (C System Call)

lseek is a system call that is used to change the location of the read/write pointer of a file descriptor. The location can be set either in absolute or relative terms.

Required Include Files

gcc: Compilation Warning: incompatible implicit declaration of built-in function `exit’

reference: ttp://joysofprogramming.com/gcc-incompatible-implicit-declaration-exit/

Posted by Joys of Programming on in C/C++

The purpose of exit() as described by the man page

exit - cause normal process termination

Let’s make use of exit in a simple program

int main(int argc, char*argv[]){     int status; exit(status);     return 0; }

Now compile the program exit.c…

$ gcc exit.c