For my midterm project for Operating System at my college I was given a special chance to write a piece of code that will show how synchronization can be achieved. To start with I was asked to use the baker's algorithm.
The baker's algorithm is a combination of three different algorithms for synchronization. For the pseudocode the term n is for max amount of threads, and the term i is supposed to be the thread ID. The pseudo code for this algorithm requires the common data structure of
boolean choosing[n];
int number[n];
The pseudocode is as follows
choosing [i]=true;
number[i]=max(number[0],number[1],...,number[n-1])+1;
choosing[i]=false;
for (j=0;j<n;j++){
while(choosing[j]);
while((number[j]!=0)&&((number[j],j)<(number[i],i)));
}
critical section
number[i]=0;
remainder section of code
This allows the critical section to work on a shared resource so that one does not either modify data that is being read by another source, or call anything that is in the process of being used by another program.
The important thing to realize is that this is meant to be a multi process piece but because it is done by control functions I decided to make a C++ program to simulate it. In the C++ program the main is the original function, while the thread is the second process, if this code is entered, there is a slight I/O error as the thread interrupts the output of the main program. This is one of the main reasons for synchronization, but seeing as this is an example of code and not a finished product it should be overlooked.
The shared resource is the double variable called shared.
//This program is to show a basic understanding of shared resources, the bakers algorithm, and
//show an example of what it's use might be, we are to believe what shared can't be duplicated.
//Let us believe the shared resources are large and we don't have enough memory to reproduce them.
#include <windows.h>
#include <process.h>
#include <stdio.h>
#include <iostream.h>
#include <math.h>
bool whichisfirst(int pid, int pid2);
int maxnumber();
bool choosing[ 2 ]; //This is choosing since it is a DUAL stream there
//is no need for a larger system
int number [2]; //This is the number system for the algorithm
int Threadworking; //This line makes is a counter of working threads.
double shared; //This is our shared resource. nothing special but could be anything of any size.
void Thread( void* pParams )
{
int pid=1;//This is the process id for this thread.
cout<<"\nHello I am the Thread. I am NOT the main program.. don't get us confused!\n";
//now the baker's algorithm
choosing[pid]=true;
number[pid]=maxnumber()+1;
choosing[pid]=false;
for(int j=0;j<2;++j) //j<2 because there is only 2 processes here!
{while(choosing[j]);
while(number[j]!=0 && whichisfirst(pid,j));
}
cout<<"\nThis is the thread, my number was "<<number[pid]<<". And my ID was "<<pid;
cout<<".\nThe shared resource is currently"<<shared<<"\nNow I must do my critical section.\n";
shared=195;
shared=(shared*shared)-1;
shared=shared+4025;
shared=sqrt(shared);
cout<<"The key is "<<shared;
number[pid]=0; //telling everything that this thread is done in critical section
cout<<".\nNow the thread is done I am gone. poof";
Threadworking--; //This line says that there is one less thread running
}
int main( void )
{
int pid=0;//This is the process id for this thread.
//The program must first initalize all it's numbers to zero.
for(int x=0;x<2;x++)
{number[x]=0;
choosing[x]=false;
}
Threadworking=0; //This line initalizes the counter.
_beginthread( Thread, 0, NULL ); //This line calls the thread. creating a multithreaded program.
//note we can make it many threads as this is a reusable line.
//now the baker's algorithm
choosing[pid]=true;
number[pid]=maxnumber()+1;
choosing[pid]=false;
for(int j=0;j<2;++j) //j<2 because there is only 2 processes her!
{while(choosing[j]);
while(number[j]!=0 && whichisfirst(pid,j));
}
cout<<"This is the main program, my number was "<<number[pid]<<". And my ID was "<<pid;
cout<<".\nThe shared resource is currently"<<shared<<"\nNow I must do my critical section.\n";
shared=256;
shared=sqrt(shared);
cout<<"The key is "<<shared<<". And now I am done. Good bye.";
number[pid]=0; //telling everything that this thread is done in critical section
Threadworking++; //This line says there is one more thread running
cout<<"I am the main program.\n"; //This line is the MAIN PROGRAM talking. not the thread.
while(Threadworking!=0); //This line makes it so the program doesn't quit before all the pieces are finished.
return 0;
}
bool whichisfirst(int pid, int pid2)
{
if(pid==pid2) return false; //This line is NOT in the code, beware.
if(number[pid]<number[pid2]) return false;
if(number[pid]>number[pid2]) return true; //if one of the numbers is more or less then return which.
if(pid<pid2) return false;
return true;
}
int maxnumber()//this function is to tell what the highest number in the array;
{
int max=0;
for(int x=0;x<5;x++)
{if(max<number[x])
max=number[x];
}
return max;
}