Semaphore and Mutexes

so what are the methods to implement mutexes ?

various, it depends how the system is
for uniprocessor

• disabling the interrupts

for multiprocessor

• use atomic operations like ExchangeWord or testAndSet if supported by processor bus

other wise

• use the software solution

busy waiting is involved in case of option 2/3
option 2 requires hw assistance and can be employed if multiple processors share the memory as well
option 3 is generic and can be used if none of other solutions are working


So what is the option 3 ?

2 process mutex

int cur = -1;
int interested [2] ;
lock(int id)
{
cur = id;
interested[id] = true;
while(cur == id && interested[id ^1])
;
}

unlock(int id)
{
interested[id] = 0;
}

ok, what other problem may arise in multiprogramming?
in multiprogramming, while sharing of resources, process cooperate /compete
to deal with co-operation , mutex is employed, for competing processes in view of shared limited resources, we need to use the semaphores.
actually semaphores can be used to solve the problem of resource sharing as well as mutual exclusion.

So what is Semaphore ?
just an integer variable . Actually a data structure which mostly has integer and 2 operations P and V (wait and signal). Semaphore can be attached / detached to particular process to make them share the resources.

wait(int sem_id)
{
Semaphore *s = getSemaPhore(sem_id);
lock(s->lock);
if(s->busy == false)
{
s->busy = true;
}
else
{
s->q->enq(current_process);
block(current_process);
}
unlock(s->lock);
}

similarly
signal(int sem_id)
{ Semaphore *s = getSemaPhore(sem_id);
lock(s->lock);
if(!s->q->empty())
{
unBlock(s->q->deq() );
}
else
{
s->busy = false;

}
unlock(s->lock);

}

Readers writes problem?

• no reader shall wait unless share is open for reading
  
• as soon as writer starts , all reader should stop and exclusive access to writer should be provided. Writers should be preferred
• 
  

virtual memory

so What are swapper and overlays in old systems ?

in old days , with the revolution of PCs, we went into multiprogramming mode where programs could be larger than the memory and there can be several such processes executing at a time.
The solutions implemented were swapping and overlays.
in overlays , we keep only the portion of program which are needed at the time of execution. Thus for a compiler we will only have lexer, then parser and then builder ...one by one . This needs a great deal of programming headache as programmers need to decide the overlay structure of their program to make it successful.
swapping is when a process finishes its timeslice, it is moved to secondary storage and bring back when scheduler demands for it again.The process which does this is called as swapper and used to be part of dispatcher(CPU scheduler). These two ways together makes a system as time shared system.

so how does multiprogramming was evolved then ?

well, it seems like there were a number of issues faced by ppl. foremost were fragmentation problem.
since processes used to be of multiple sizes, swapping them creats fragmented array where even though space is available but no process can occupy it. to deal with this situation , they thought to minimize the space required by a process to something which create a minimal fragmentaion. So they implemented Segmentation scheme. here all processes used to have segments for stack, heap, data ....
class segment{
register *logical_code;
register *logical_data;
register * logicalToPhysical(reg *logical){
/**
* if logical address is current Program counter
*/
if(logical == pc){
return (logical + logical_code);
}
return (logical + logical_data);
}
}
but this does not solve the proble at all, just minimizes it to some extent.
so concept of Page evolved. A page is fixed length and further divides the process