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

I came across opengl questions a lot since I developed a 2d lib on graphics acc card of Fujitsu. Some points to always know are:

1. What the hell is Opengl?

open graphics library or open spec for graphics lib. This library provides the spec how the graphics pipeline should work and how it should be invoked. Standard opengl is client server based architecture but one We used for KGE is direct lib call because of hard RTOS system nature.

2. What is the OpengL Pipeline ?

opengl functions in pipeline fashion, a user can modify the pipeline state by the api it defines.
pipline takes the input from 2 sources :
a raw pixel data or vertex data
a 3rd source can be display list but that is nothing but the container of pixel/vertex data

vertex data ----> evaluators------------> per vertex operations and primitive assembly ------->RASTERIZATION

evaluators are used to derive the vertices actual coord from control points sometimes used in describing the surface
per vertex operations : converts vertices into primitives, if Texture are used, their coord are created and transform here.
primitive assembly: clipping is applied followed by viewport and depth calculations. then culling is applied.
[ After primitive assembly state, one has the complete geometric primitive which are the transformed & clipped vertices with related color , depth and texture coord values]

2nd source of pipeline are direct pixel values
pixel data---->pixel operations---------|
|------------texture assembly
|------------RASTERIZATION

Pixel data /Pixel operations: pixels are read from system memory and unpacked into proper format , next the data is scaled, processed by a pixel map and clamped, and then either sent to texture assembly or to Rasterization step

Texture Assembly: apply texture images onto geometric objects, this step depends on implementation to implementation as it can be costly.

Rasterization----->per fragment operations----->framebuffer

Rasterization : converts geometric primitive/pixel data into fragments. where each fragment is onetoone map of framebuffer square pixel. color , depth , stippling, line width ... are calculated and associated with each of fragment. ontop of fragment , a series of operations are performed before actually putting fragment into framebuffer. e.g. texturing, scissor test, alpha test, depth buffer test, blending, dithering, logical operations, ...etc and all these operations can be enabled /disabled separately. finally the fragments are drawn over frambuffer as pixels.