#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <string.h>
#include "ipccalls.h"
/*****************************************************/
/*
*
* Tasks.
*
*/
int FMIN=20;
int FMAX=25;
unsigned int fibo(unsigned int n)
{
if(n<2)
return n;
else
return fibo(n-1)+fibo(n-2);
}
/*
*
* This is a printer server
*
*/
#define PRINTER_PRINT 1
#define PRINTER_QUIT 2
int printer_task(int argl, void* args)
{
int ok;
Message m;
ok = CreateMailBox("printer");
assert(ok==0);
SendPort(GetPPid(), 0L);
while(1) {
GetMail("printer", &m);
if(m.type == PRINTER_PRINT)
printf("Process %d: %s",m.sender,(char*)(m.data));
else if(m.type == PRINTER_QUIT) {
/* only if parent says so! */
if(m.sender==GetPPid()) break;
}
/* else ignore */
}
return 0;
}
/*
* This modified fibo_task get work from boot and sends messages to another
* process.
*/
void output_string(char* s)
{
Message m;
int ok;
m.type = PRINTER_PRINT;
m.data = s;
m.len = strlen(s);
ok = SendMail("printer", &m);
assert(ok==0);
}
int fibo_task(int argl, void* args)
{
unsigned int k,f;
long msg;
char *prbuf = malloc(1024);
Pid_t pid;
sprintf(prbuf,"Hello from fibo_task process %d.\n",GetPid());
output_string(prbuf);
while(1) {
// Wait for a request to compute a Fibonacci number.
pid = ReceivePort(&msg, 1);
assert(pid = GetPPid());
if(msg<0) {
sprintf(prbuf, "fibo_task exiting (pid = %d). Bye!\n", GetPid());
output_string(prbuf);
free(prbuf);
Exit(0);
}
k = msg;
sprintf(prbuf,"I will compute the %d-th Fibonacci number\n",k);
output_string(prbuf);
f = fibo(k);
sprintf(prbuf,"The %d-th Fibonacci number is %d.\n",k,f);
output_string(prbuf);
}
return 0;
}
int fibodriver_task(int argl, void* args)
{
int work;
Pid_t child;
assert(argl == sizeof(int));
work = *((int*)args) ;
child = Exec(fibo_task, 0, NULL);
while(work>0) {
SendPort(child, lrand48() % (FMAX-FMIN+1) + FMIN);
work --;
}
SendPort(child, -1);
WaitChild(child,NULL);
return 0;
}
/*
* This is the initial task, which starts all the other tasks (except for the idle task).
*/
#define SUBTASKS 5
int boot_task(int argl, void* args)
{
int i,num_fibo;
int status;
long msg;
Message m;
Pid_t pid;
Pid_t printer;
Pid_t* pids;
int param;
num_fibo = *((int*)args);
param = num_fibo/SUBTASKS;
pids = malloc(sizeof(Pid_t)*SUBTASKS);
/* Launch child processes */
printer = Exec(printer_task,0,NULL);
/* Wait until it is ready to print */
ReceivePort(&msg,1);
for(i=0; i<SUBTASKS; i++) {
pids[i] = pid = Exec(fibodriver_task,sizeof(param),¶m);
printf("boot_task: executed process fibo%d pid=%d\n",i+1,pid);
}
/* Wait for child processes */
for(i=0;i<SUBTASKS;i++) {
Pid_t pid = WaitChild(NOPROC, &status);
printf("boot_task: Process %d exited with exit value %d.\n",pid,status);
}
/* Tell printer to exit */
m.type = PRINTER_QUIT;
m.data = NULL;
m.len = 0;
SendMail("printer",&m);
/* Loop until all children have exited */
while(WaitChild(NOPROC,NULL) != NOPROC)
printf("boot_task: child exited.\n");
printf("boot_task: exiting!\n");
return 0;
}
/****************************************************/
void usage(const char* pname)
{
printf("usage:\n %s <number of calls>\n\n where <number of calls> is from %d to 500\n",
pname, SUBTASKS);
exit(1);
}
int main(int argc, const char** argv)
{
int ntasks;
if(argc!=2) usage(argv[0]);
ntasks = atoi(argv[1]);
if( (ntasks < SUBTASKS) || (ntasks > 500) ) usage(argv[0]);
// adjust for many processes
if(1) {
FMIN = 35 - (int)( log((double)ntasks)/log(.5+.5*sqrt(5.)));
FMAX = FMIN+10;
}
/* boot */
boot(boot_task, sizeof(ntasks), &ntasks);
printf("This is main again! Bye!\n");
return 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>
#include <ucontext.h>
#include <signal.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>
#include "syscalls.h"
#include "ipccalls.h"
/* Set the quantum time and stack size */
#define QUANTUM (20000L) // microseconds
#define PROCESS_STACK_SIZE 16384 // stack size
/************* PROJECT_2 ***************/
#define MNAME_SIZE 31 //maximum characters for th name of a new mailbox
#define MMAIL_SIZE 8 //maximum mails in a mailbox
#define MBOX_SIZE 64 //aximum number of mailboxes
/*
* Function Prototypes
*/
void InsertList(int pid);
void RemoveList(void);
void SetTail(void);
void doSignal(CondVar* cv);
void atomic_release_mutex_and_sleep(Mutex *mutex);
void wakeup_process(int pid);
void init_context(ucontext_t* uc, void* stack, size_t stack_size,Task task, int argl, void* args);
void mytask(Task task,int argl,void* args);
void Idle(void);
void yield();
void schedule(int sig);
void pause_scheduling();
void resume_scheduling();
void reset_timer();
void run_scheduler();
void Initialize(void);
// For asynchronous //
/*typedef struct mailmessage_s {
Pid_t sender; //sender's ID
int type; //type
void* data; //data
size_t len; //length
} Message;*/
typedef struct mail_info {
Pid_t owner_pid; //mailbox owner's ID
char name[MNAME_SIZE+1]; //mailbox name
Message mail[MMAIL_SIZE+1]; //mailbox mail with info
int first;
int last;
} Minfo;
typedef struct mailboxes {
Minfo* data; //point at a mailbox
//Mutex mtxLock;
CondVar Prod; //condition variable for producer
CondVar Cust; //condition variable for customer
} Mailbox;
Mailbox MailBox[MBOX_SIZE]; //our mailbox
int MailBoxes=0; //the number of the mailboxes we use
/*************************************************************/
/*
* Kernel variables
*/
enum ProcState {READY , RUNNING , SLEEPING , FINISHED , DEAD }; //States of processes
// Processes struct
typedef struct PCB_struct{
Pid_t pid;
Pid_t parent_pid;
int exit_value;
ucontext_t context;
enum ProcState state;
Pid_t waiting;
long data;
int receiver;
int recreq;
}PCB;
PCB ProcTable[MAX_PROC]; //Processes table
PCB *curproc; //pointer to current process
int numproc; // processes counter
Mutex kernel_lock; // kernel mutex
ucontext_t _saved_context;
sigset_t __sigprof_mask;
struct itimerval quantum_itimer;
/*
* Circular Single Linked List Structs
*/
typedef struct ProcessListNode{
Pid_t Pid;
struct ProcessListNode *next;
}ProcListNode;
typedef struct ProcessList{
ProcListNode *head,*tail;
}ProcList;
ProcList *list;
/*
* Circular Single Linked List Functions
*/
void InsertList(int pid) {
ProcListNode *NewNode;
NewNode=(ProcListNode*)malloc(sizeof(ProcListNode));
NewNode->Pid=pid;
if(list->head==NULL) {
list->head=list->tail=NewNode;
list->tail->next = list->head; //link to head
}
else {
list->tail->next=list->tail=NewNode;
list->tail->next=list->head; //link to head
}
}
void RemoveList(void) {
ProcListNode *victim;
victim=list->head;
list->head=victim->next;
list->tail->next=list->head; //link to head
free(victim);
}
void SetTail(void) {
ProcListNode *back,*count=list->head;
for(;;){
back=count;
count=count->next;
if(count==list->head) {
list->tail=back; //set tail right before head
break;
}
}
}
/*
* Concurrency control
*/
int Mutex_TryLock(Mutex *lock) {
char oldval;
__asm__ __volatile__("xchgb %b0,%1"
:"=q" (oldval), "=m" (*lock)
:"0" (0) : "memory");
return oldval > 0;
}
void Mutex_Unlock(Mutex* lock) {
*lock = MUTEX_INIT;
}
void Mutex_Lock(Mutex* lock) {
while(!Mutex_TryLock(lock))
yield();
}
void Cond_Init(CondVar* cv) {
cv->waitset_lock = MUTEX_INIT;
cv->waitset = NULL;
}
void Cond_Wait(Mutex* mutex, CondVar* cv) {
__cv_waiter * newnode;
newnode = (__cv_waiter*) malloc(sizeof(__cv_waiter));
newnode->pid = GetPid();
Mutex_Lock(&(cv->waitset_lock));
if(cv->waitset==NULL)
newnode->next = newnode->prev = cv->waitset = newnode;
else {
newnode->prev = cv->waitset->prev;
newnode->next = cv->waitset;
cv->waitset->prev->next = newnode;
cv->waitset->prev = newnode;
}
/* Now atomically release mutex and sleep */
Mutex_Unlock(mutex);
atomic_release_mutex_and_sleep(&(cv->waitset_lock));
Mutex_Lock(mutex);
}
void doSignal(CondVar* cv) {
/* Wakeup first process in the waitset list */
if(cv->waitset != NULL) {
__cv_waiter *node = cv->waitset;
wakeup_process(node->pid);
if(node->next==node->prev)
cv->waitset = NULL;
else {
cv->waitset = node->next;
node->next->prev = node->prev;
node->prev->next = node->next;
}
free(node);
}
}
void atomic_release_mutex_and_sleep(Mutex *mutex) {
pause_scheduling();
Mutex_Unlock(mutex);
RemoveList();
ProcTable[GetPid()].state=SLEEPING;
resume_scheduling();
yield();
}
void wakeup_process(int pid) {
pause_scheduling();
InsertList(pid);
ProcTable[pid].state=READY;
resume_scheduling();
}
void Cond_Signal(CondVar* cv) {
Mutex_Lock(&(cv->waitset_lock));
doSignal(cv);
Mutex_Unlock(&(cv->waitset_lock));
}
void Cond_Broadcast(CondVar* cv) {
Mutex_Lock(&(cv->waitset_lock));
while(cv->waitset!=NULL)
doSignal(cv);
Mutex_Unlock(&(cv->waitset_lock));
}
/*
* System calls
*/
void Exit(int exitval) {
Mutex_Lock(&kernel_lock);
RemoveList();
ProcTable[GetPid()].exit_value=exitval;
ProcTable[GetPid()].state=DEAD;
int i;
for(i=0;i<=numproc;i++){
if( ProcTable[i].state!=FINISHED && ProcTable[i].parent_pid==GetPid() )
ProcTable[i].parent_pid=1;
}
if(curproc->waiting!=0) //check if waits parent
{
InsertList(curproc->waiting);
list->head=list->tail;SetTail();
}
Mutex_Unlock(&kernel_lock);
yield();
}
Pid_t Exec(Task call, int argl, void* args) {
void *args2=malloc(sizeof(args)),*stack=malloc(PROCESS_STACK_SIZE);
//change args for each new process
memmove(args2,args,argl);
Mutex_Lock(&kernel_lock);
ProcTable[numproc].pid=numproc;
if(numproc==0 || numproc==1)
ProcTable[numproc].parent_pid=-1;
else
ProcTable[numproc].parent_pid=GetPid();
ProcTable[numproc].exit_value=-1;
ProcTable[numproc].state=READY;
ProcTable[numproc].waiting=0;
ProcTable[numproc].data=-1;
ProcTable[numproc].receiver=-1;
ProcTable[numproc].recreq=0;
init_context(&(ProcTable[numproc].context),stack,PROCESS_STACK_SIZE,call,argl,args2);
pause_scheduling();
InsertList(numproc);
resume_scheduling();
numproc++;
Mutex_Unlock(&kernel_lock);
return ProcTable[numproc-1].pid;
}
Pid_t GetPid() {
if(curproc==NULL)
return NOPROC;
else
return curproc->pid;
}
Pid_t WaitChild(Pid_t cpid, int* status){
int i;
Mutex_Lock(&kernel_lock);
printf("bika waitchild me %d*********************************************************\n",cpid);
if(cpid==NOPROC){
for(i=0;i<=numproc;i++){
if( ProcTable[i].state!=FINISHED){//puts("OK1");
if( ProcTable[i].parent_pid==GetPid() ){//puts("OK2");
for(;;){
if(ProcTable[i].state==DEAD){
// printf("\n Teleiose h ************ %d ***********\n",i);
ProcTable[i].state=FINISHED;
printf("\nTELEIOSE %d &&&&&&&&&&############################################################\n",i);
free(ProcTable[i].context.uc_stack.ss_sp);
ProcTable[i].context.uc_stack.ss_sp=0;
Mutex_Unlock(&kernel_lock);
return ProcTable[i].pid;
}
for(i=0;i<=numproc;i++){
if( ProcTable[i].parent_pid==GetPid() )
ProcTable[i].waiting=GetPid();
}
//ProcTable[i].wait=GetPid();
RemoveList();
ProcTable[GetPid()].state=SLEEPING;
Mutex_Unlock(&kernel_lock);
yield();
//printf("---->>>>> %d\n",i);
Mutex_Lock(&kernel_lock);
for(i=1;i<=numproc;i++){
if(ProcTable[i].state==DEAD){
ProcTable[i].state=FINISHED;
//printf("\nTELEIOSE %d &&&&&&&&&&\n",i);
free(ProcTable[i].context.uc_stack.ss_sp);
ProcTable[i].context.uc_stack.ss_sp=0;
Mutex_Unlock(&kernel_lock);
return ProcTable[i].pid;
}
}
//puts("xipnisa o geros\n");
}
}
}
}
Mutex_Unlock(&kernel_lock);
return NOPROC;
}
if(cpid!=NOPROC){
if(cpid>numproc){
Mutex_Unlock(&kernel_lock);
return NOPROC;
}
if( ProcTable[cpid].parent_pid!=GetPid() ){
Mutex_Unlock(&kernel_lock);
return NOPROC; //s den einai paidi tis trexousas diergasias
}
for(;;){
if(ProcTable[cpid].state==DEAD){
ProcTable[cpid].state=FINISHED;
//printf("\nTELEIOSE %d--------------\n",cpid);
//*status=ProcTable[cpid].exit_value;
free(ProcTable[cpid].context.uc_stack.ss_sp);
ProcTable[cpid].context.uc_stack.ss_sp=0;
Mutex_Unlock(&kernel_lock);
return ProcTable[cpid].pid;
}
ProcTable[cpid].waiting=GetPid();
RemoveList();
ProcTable[GetPid()].state=SLEEPING;
Mutex_Unlock(&kernel_lock);
yield();
Mutex_Lock(&kernel_lock);
}
}
return NOPROC;
}
void boot(Task boot_task, int argl, void* args){
Initialize();
Exec((Task)Idle,0,NULL);
Exec(boot_task,argl,args);
run_scheduler();
}
/*
*
* Initialization
*
*/
void Idle(void){
for(;;);
}
void Initialize(void){
list=(ProcList*)malloc(sizeof(ProcList));
list->head=NULL;
kernel_lock=1;
// initialization: scheduler pause/resume
sigemptyset(&__sigprof_mask);
sigaddset(&__sigprof_mask, SIGPROF);
quantum_itimer.it_interval.tv_sec=0L;
quantum_itimer.it_interval.tv_usec=QUANTUM;
quantum_itimer.it_value.tv_sec=0L;
quantum_itimer.it_value.tv_usec=QUANTUM;
numproc=0;
curproc=NULL;
curproc=&ProcTable[0];
}
void init_context(ucontext_t* uc, void* stack, size_t stack_size,Task task, int argl, void* args){
// initialize a context
getcontext(uc); // necessary to initialize context
uc->uc_link = NULL; // context to load when this exits
uc->uc_stack.ss_sp = stack; // the new stack
uc->uc_stack.ss_size = stack_size; // size of above stack
uc->uc_stack.ss_flags = 0; // flags (we dont care about them)
makecontext(uc,(void *)mytask,3,task,argl,args); // force context to start by a call to task(argl,args)
}
// use for disabling scheduler signal
void pause_scheduling(){
sigprocmask(SIG_BLOCK,&__sigprof_mask,NULL);
}
void resume_scheduling(){
sigprocmask(SIG_UNBLOCK,&__sigprof_mask,NULL);
}
void mytask(Task task,int argl,void* args){
Exit(task(argl,args));
}
//set the timer to interrupt us, raising SIGPROF
void reset_timer() {
setitimer(ITIMER_PROF,&quantum_itimer,NULL);
}
/*
* starting the scheduler: we have already initialized everything,
* ans esp. the context of process 'idle' and process 'init' (boot_task)
*/
void run_scheduler() {
struct sigaction sa;
int err;
// set up SIGPROF to schedule
sa.sa_handler = schedule;
sa.sa_flags = SA_RESTART;
sigemptyset(&(sa.sa_mask));
while((err=sigaction(SIGPROF, &sa, NULL)) && (errno==EINTR));
assert(err==0);
reset_timer();
// Switch to the context of the idle task
curproc = &ProcTable[0];
swapcontext(&_saved_context, &(curproc->context) );
free(ProcTable[1].context.uc_stack.ss_sp); //sbisimo init(boot_task)
free(ProcTable[0].context.uc_stack.ss_sp); //sbisimo idle
}
void yield(){
schedule(0);
}
void schedule(int sig){
if(curproc->state==DEAD && curproc->waiting!=0) {
pause_scheduling();
curproc=&ProcTable[list->head->Pid];
//reset_timer();
resume_scheduling();
setcontext(&ProcTable[list->head->Pid].context);
}
else {
pause_scheduling();
if(curproc->state!=DEAD)//
ProcTable[curproc->pid].state=READY;
list->head=list->head->next;SetTail();
if(curproc->pid == list->head->Pid) {
ProcTable[1].state=FINISHED;
reset_timer();//
resume_scheduling();//
swapcontext(&(ProcTable[curproc->pid].context),&_saved_context);
}
ProcTable[list->head->Pid].state=RUNNING;
Pid_t tmp=curproc->pid;
curproc=&ProcTable[list->head->Pid];
reset_timer();
resume_scheduling();
swapcontext(&(ProcTable[tmp].context),&(ProcTable[list->head->Pid].context));
}
}
/**************************************************************************************************************************
* IPC
**************************************************************************************************************************/
Pid_t GetPPid(){
if (curproc==NULL)
return NOPROC;
else
return curproc->parent_pid;
}
int SendPort(Pid_t receiver, long data){
int i;
/*
RemoveList();
ProcTable[GetPid()].state=SLEEPING;
puts("bgike o sender(pobos) apo ti list\n");
Mutex_Unlock(&kernel_lock);
yield();
Mutex_Lock(&kernel_lock);
*/
ProcTable[GetPid()].receiver=receiver;
ProcTable[GetPid()].data=data;
for(;;){
for(i=0;i<=numproc;i++){
//puts("elenxos gia to an exei ginei to receive request(an iparxei dektis)\n");
//if(ProcTable[i].recreq==1 && receiver==ProcTable[i].pid )
if(ProcTable[i].recreq==1){
InsertList(ProcTable[i].pid);
ProcTable[i].state=READY;
//puts("brethike pobos,xipna dekti \n");
ProcTable[i].recreq=0;
Mutex_Unlock(&kernel_lock);
return 0;
}
}
//ProcTable[GetPid()].receiver=receiver;
//ProcTable[GetPid()].data=data;
RemoveList();
ProcTable[GetPid()].state=SLEEPING;
Mutex_Unlock(&kernel_lock);
yield();
Mutex_Lock(&kernel_lock);
if( ProcTable[GetPid()].receiver == -2 ){
Mutex_Unlock(&kernel_lock);
return 0;
}
i=0;
}
return -1;
}
Pid_t ReceivePort(long* data, int waitflag){
int i;
Mutex_Lock(&kernel_lock);
// puts("bika ReceivePort");
for(;;){
//puts("bika wile(1)\n");
for(i=0;i<=numproc;i++){
//if(ProcTable[i].receiver==GetPid() && ProcTable[i].state==SLEEPING)
if(ProcTable[i].receiver==GetPid() )
{
*data=ProcTable[i].data;
// printf("i proc %d elabe apo tin %d\n",GetPid(),ProcTable[i].pid);
//ProcTable[i].receiver=-1;
//printf("%d\n",*data);
InsertList(ProcTable[i].pid);
ProcTable[i].state=READY;
//ProcTable[GetPid()].recreq=1;
ProcTable[i].receiver=-2;
Mutex_Unlock(&kernel_lock);
return GetPid();
//return ProcTable[i].pid;
}
}
if(waitflag==0){
Mutex_Unlock(&kernel_lock);
return -1;
}
RemoveList();
//puts("koimisou kai perimene na iparxei pobos \n");
ProcTable[GetPid()].state=SLEEPING;
ProcTable[GetPid()].recreq=1;
// printf("perimenei os dektis i %d\n",GetPid() );
Mutex_Unlock(&kernel_lock);
yield();
Mutex_Lock(&kernel_lock);
i=0;
}
Mutex_Unlock(&kernel_lock);
return GetPid();
return NOPROC;
}
int CreateMailBox(const char* mbox){
int i=0;
/* 1st case for error */
if (*mbox==0) //wrong call of fuction
return NOPROC;
Mutex_Lock(&kernel_lock); //from now on we don't want to change the MailBoxes number
//with new entries or delete so we lock the mutex
/* 2nd case for error */
if (MailBoxes==MBOX_SIZE){ //check if we can create another one mailbox
Mutex_Unlock(&kernel_lock); //if we can't,unlock the mutex
return -1; //and return -1
}
/* 3rd case for error */
for (i=0; i<MBOX_SIZE; i++) //check all the array with the mailboxes
{
if (MailBox[i].data != NULL) //if you find an array with data,continue
{
if (strncmp(MailBox[i].data->name, mbox, MNAME_SIZE) == 0) //if this array haw the same name with
{ //the one we want to create
Mutex_Unlock(&kernel_lock); //unlock the mutex
return -1; //and return
}
}
}
/* now we can create the new mailbox */
for (i=0; i<MBOX_SIZE; i++) //check all the array with the mailboxes
if (MailBox[i].data == NULL) //find the first empty
break; //and break
MailBox[i].data=(Minfo*)malloc(sizeof(Minfo)); //allocate memory for the new mailbox
assert(MailBox[i].data); //check if we get the memory
MailBox[i].data->owner_pid=curproc->pid; //save owner's pid
strncpy(MailBox[i].data->name, mbox, MNAME_SIZE); //save the name
MailBox[i].data->name[MNAME_SIZE]=0; //the last character of the name should be null
MailBox[i].data->first=0;
MailBox[i].data->last=0;
//assert(MailBox[i].mtxLock.lock==1); /* make sure no one is using */
assert(MailBox[i].Cust.waitset_lock==0); /* the mutexes and condition */
assert(MailBox[i].Prod.waitset_lock==0); /* variables (as should be) */
//MailBox[i].mtxLock.lock=1;
MailBox[i].Prod.waitset_lock=MUTEX_INIT;
MailBox[i].Prod.waitset=0;
MailBox[i].Cust.waitset_lock=MUTEX_INIT;
MailBox[i].Cust.waitset=0;
MailBoxes++; //increase the number of the mailboxes which we use
Mutex_Unlock(&kernel_lock); //and finally unlock the mutex;
return 0;
}
int DestroyMailBox(const char* mbox)
{
int i=0;
/* 1st case for error */
if (*mbox==0) //wrong call of fuction
return NOPROC;
Mutex_Lock(&kernel_lock); //from now on we don't want to change the MailBoxes number
/* 2nd case for error */
for (i=0; i<MBOX_SIZE; i++) //check all the array with the mailboxes
if (MailBox[i].data != NULL) //if you find an array with data,continue
if (strncmp(MailBox[i].data->name, mbox, MNAME_SIZE) == 0) //if this array exist we find it
break; //and break;
if (i == MBOX_SIZE) //we scan all the array but we didn't find this mailbox
{ //so something goes wrong
Mutex_Unlock(&kernel_lock); //unlock mutex
return -1; //and return
}
/* 3rd case for error */
if (MailBox[i].data->owner_pid!=curproc->pid) //curproc isn't the owner of this mailbox
{
Mutex_Unlock(&kernel_lock); //unlock mutex
return -1; //and return
}
/* lockup mutex (we erase data) */
// Mutex_Acquire(&MailBox[i].mtxLock);
Cond_Broadcast(&MailBox[i].Prod); //we should wake up all the produser's who waiting to send
//message to this mailbox
/* wake up all consumers (list should be empty - assert it) */
assert(!MailBox[i].Cust.waitset);
Cond_Broadcast(&MailBox[i].Cust);
free(MailBox[i].data); //free the space we had allocated for this mailbox
MailBox[i].data=0; //and a last clean up...
MailBoxes--; //decrease the number of the mailboxes we use
Mutex_Unlock(&kernel_lock); //and unlock mutex before return
return 0;
}
int SendMail(const char* mbox, Message* msg){
int i=0;
Mutex_Lock(&kernel_lock); //we lock the mutex to avoid troubles...
/* 1st case for error */
for (i=0; i<MBOX_SIZE; i++) //we will check if this name exist
{
if (MailBox[i].data!=0)
{
if (strncmp(MailBox[i].data->name, mbox, MNAME_SIZE) == 0)
break;
}
}
if (i == MBOX_SIZE) //we check all the array but we didn't find this mailbox
{
Mutex_Unlock(&kernel_lock); //so unlock the mutex
return -1; //and return
}
/* 2nd case for error */
if (MailBox[i].data->owner_pid==curproc->pid) //we are trying to send a mail to ourselves
{
Mutex_Unlock(&kernel_lock); //so unlock the mutex
return -1; //and return
}
/* now we can send the message */
//Mutex_Acquire(&MailBox[i].mtxLock);
//Mutex_Release(&mtxMailbox); /* we don't allow anyone to destroy the
// mailbox */
while ( (MailBox[i].data->last+1)%(MMAIL_SIZE+1) == MailBox[i].data->first ) //if there is no space for new mail
Cond_Wait(&kernel_lock,&MailBox[i].Prod); //we should waiting...
if (MailBox[i].data == NULL) //if the mailbox has been destroyd
{
Mutex_Unlock(&kernel_lock); //unlock the mutex
return -1; //and return
}
if ( MailBox[i].data->first == MailBox[i].data->last ) //if the mailbox is empty
Cond_Broadcast(&MailBox[i].Cust);
/* NOTE: even if consumers wake up here, they still got to lockup the mutex
* so we are safe... */
// MailBox[i].data->count++;
/* InsertList element */
{
MailBox[i].data->mail[MailBox[i].data->last].sender=curproc->pid;
MailBox[i].data->mail[MailBox[i].data->last].type=msg->type;
if ( (MailBox[i].data->mail[MailBox[i].data->last].len = msg->len) ) {
/* we keep a copy of the message, so sender may free() or even
* quit and not affect the message-passing functions */
// if(msg->len > 0)
// {
assert( MailBox[i].data->mail[MailBox[i].data->last].data = malloc(msg->len) );
memcpy(MailBox[i].data->mail[MailBox[i].data->last].data, msg->data, msg->len);
}
else
{
MailBox[i].data->mail[MailBox[i].data->last].data = NULL ;
}
MailBox[i].data->last = (MailBox[i].data->last+1)%(MMAIL_SIZE+1);
}
//if(MailBox[i].data->count==1)
// Cond_Broadcast(&MailBox[i].Cust); //wake up all the customers for this mailbox
Mutex_Unlock(&kernel_lock);
return 0;
}
int GetMail(const char* mbox, Message* msg){// puts("BIKE STIN GETMAIL");
int i=0;
// int rem=0;
Mutex_Lock(&kernel_lock); //we lock the mutex to avoid troubles...
/* 1st case for error */
for (i=0; i<MBOX_SIZE; i++) //we will check if this name exist
{
if (MailBox[i].data!=0)
{
if (strncmp(MailBox[i].data->name, mbox, MNAME_SIZE) == 0)
break;
}
}
if (i == MBOX_SIZE) //we check all the array but we didn't find this mailbox
{
Mutex_Unlock(&kernel_lock); //so unlock the mutex
return -1; //and return
}
/* 2nd case fo error */
if (MailBox[i].data->owner_pid != curproc->pid) //we can't get mail from a mailbox
{ //which doesn't own us!!!
Mutex_Unlock(&kernel_lock); //so unlock the mutex
return -1; //and return
}
/* now we can get the mail */
//Mutex_Acquire(&MailBox[i].mtxLock);
//Mutex_Release(&mtxMailbox);
while ( MailBox[i].data->first == MailBox[i].data->last ) //if the mailbox is empty
Cond_Wait(&kernel_lock,&MailBox[i].Cust); //waiting...
if ( (MailBox[i].data->last+1)%(MMAIL_SIZE+1) == MailBox[i].data->first ) //if the mailbox is full
Cond_Broadcast(&MailBox[i].Prod); //wake up all the producers
// rem= (MMAIL_SIZE - count) - 1;
// MailBox[i].data->rem=1;
//MailBox[i].data->count--;
/* remove element */
{
msg->sender=MailBox[i].data->mail[MailBox[i].data->first].sender;
msg->type=MailBox[i].data->mail[MailBox[i].data->first].type;
if ( (msg->len = MailBox[i].data->mail[MailBox[i].data->first].len) ) {
/* return copy of the data */
assert( msg->data=malloc(MailBox[i].data->mail[MailBox[i].data->first].len) );
memcpy (msg->data, MailBox[i].data->mail[MailBox[i].data->first].data, MailBox[i].data->mail[MailBox[i].data->first].len);
free (MailBox[i].data->mail[MailBox[i].data->first].data);
} else
{
msg->data=0;
}
MailBox[i].data->first = (MailBox[i].data->first+1)%(MMAIL_SIZE+1);
}
//if(MailBox[i].data->count==MMAIL_SIZE)
Mutex_Unlock(&kernel_lock);
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef __IPCCALLS_H__
#define __IPCCALLS_H__
#include "syscalls.h"
/*
This function returns the parent pid of the current process.
*/
Pid_t GetPPid(void);
/*********************************************
Synchronous process communication: ports
**********************************************/
/*
This function transfers the long value of the second argument to the
process whose pid is given in the first argument. The calling
process will sleep until the receiving process has received the
data by calling ReceivePort.
The return value is 0 on sucess and -1 on error. Possible errors
are:
- the receiver is not a valid process (returns immediately)
- the receiver is the calling process (returns immediately)
- the receiver exited without calling ReceivePort
*/
int SendPort(Pid_t receiver, long data);
/*
This function receives a value sent to the current process' port and
stores it in the variable pointed to by the first argument. The
return value of the function is the PID of the sender of the data.
If there is no value sent to this process' port at the time the
function is called, the behavior depends on the value of the second
argument, waitflag.
-- If waitflag is false, the call returns immediately the value
NOPROC without modifying the location pointed to by the first
argument.
-- If waitflag is true, the process is suspended until a value is
sent to the process port by another process calling SendPort.
*/
Pid_t ReceivePort(long* data, int waitflag);
/*************************************************
Asynchronous process communication: mailboxes
**************************************************/
/*
The structure below defines the messages sent to mailboxes.
The sender must fill in the attributes: type, data, and len.
If len is greater than 0, data must point to a memory area of length
len. If len is zero, the value of data is ignored.
The receiver receives a structure with the folllowing attributes:
- attribute sender contains the PID of the sending process.
- attribute type contains a copy of the value sent by the sender.
- attribute len contains a copy of the value sent by the sender.
- if len>0, attribute data points to a memory area of length len,
containing ***** A COPY OF THE DATA SENT BY THE SENDER ******
if len==0, attribute data is NULL.
*/
typedef struct mailmessage_s {
Pid_t sender;
int type;
void* data;
size_t len;
} Message;
/*
This function creates a mailbox with the name given by the first
parameter, which must be a non-NULL string. The owner of
the new mailbox is the calling process. Only the owner can read mail
from this mailbox, and destroy it.
The function returns 0 on success, and -1 on failure. Reasons of
failure are:
- The given value of mbox is the name used by another mailbox.
- The total number of mailboxes in the system is exceeded.
*/
int CreateMailBox(const char* mbox);
/*
This function destroys a mailbox with the name given by the first
parameter, which must be a non-NULL string. The owner of
the mailbox must be the calling process. Any messages contained in
the mailbox are discarded.
The function returns 0 on success and -1 on failure. Reasons of
failure are:
- The given value of mbox is not the name of a mailbox.
- The caller is not the owner of the mailbox.
When a process exits, all its mailboxes are destroyed aytomatically.
*/
int DestroyMailBox(const char* mbox);
/*
This function sends the message described by the second argument to
the mailbox specified by the first argument. If the mailbox is full,
the function blocks until space is available in the mailbox, or the
mailbox is destroyed.
The function returns 0 on success and -1 on failure. Reasons of
failure are:
- The given value of mbox is not the name of a mailbox.
- The calling process is the owner of the mailbox (i.e. mail to yourself
is not allowed).
*/
int SendMail(const char* mbox, Message* msg);
/*
This function receives a message in the structure given in second
argument, from the mailbox specified by the first argument. If the
mailbox is empty, the function blocks until a message arrives.
The function returns 0 on success and -1 on failure. Reasons of
failure are:
- The given value of mbox is not the name of a mailbox.
- The calling process is not the owner of the mailbox (i.e. cannot
read others' mail).
*/
int GetMail(const char* mbox, Message* msg);
#endif
//////////////////////////////////////////////////////////////////////
#ifndef __SYSCALLS_H__
#define __SYSCALLS_H__
/*
*
* Public kernel declarations
*
*/
/*******************************************
* Processes types and constants.
*******************************************/
typedef int Pid_t; /* The PID type */
/* The invalid PID */
#define NOPROC (-1)
/* The maximum number of processes */
#define MAX_PROC 65536
/*******************************************
* Concurrency control
*******************************************/
/* Mutexes */
typedef volatile unsigned int Mutex;
/*
This macro is used to initialize mutexes. Always create a mutex as
follows:
Mutex mu_mytex = MUTEX_INIT;
*/
#define MUTEX_INIT 1
/* Try to lock a mutex, return 1 on success, 0 on failure (when the
mutex is taken). This function does not block. */
int Mutex_TryLock(Mutex*);
/* Lock a mutex by waiting if necessary as long as it takes. */
void Mutex_Lock(Mutex*);
/* Unlock a mutex that you locked. */
void Mutex_Unlock(Mutex*);
/* Helper structure for condition variables. */
typedef struct __cv_waiter_s {
Pid_t pid;
struct __cv_waiter_s *prev, *next;
} __cv_waiter;
/* Condition variables */
typedef struct {
Mutex waitset_lock;
__cv_waiter *waitset;
} CondVar;
/* This macro is used to initialize a condition variable. It is used
as follows:
CondVar my_cv = CONDVAR_INIT;
*/
#define CONDVAR_INIT { MUTEX_INIT, NULL }
/* Initialize a CondVar when CONDVAR_INIT cannot
be used (e.g. an array of CondVars) */
void Cond_Init(CondVar*);
/* Wait on a condition variable. This must be called only while we
have locked the mutex that is associated with this call. It will
put our process to sleep, unlocking the mutex. These operations
happen atomically. When our process is woken up later (by another
process that called Cond_Signal or Cond_Broadcast), this function
first re-locks the mutex and then returns. */
void Cond_Wait(Mutex*, CondVar*);
/* Signal wakes up exactly one process sleeping on this condition
variable (if any). */
void Cond_Signal(CondVar*);
/* Broadcast wakes up all processes sleeping on this condition variable
(if any). */
void Cond_Broadcast(CondVar*);
/*******************************************
*
* Process creation
*
*******************************************/
/* New processes are created by calling a starting function, whose
signature is Task. */
typedef int (*Task)(int, void*);
/* Create a new process by calling the function with signature Task
and pass it parameters argl and args, where argl is the length of
byte array args (args can be NULL). */
Pid_t Exec(Task, int argl, void* args);
/* When this function is called by a process, the process terminates
and sets its exit code to val. */
void Exit(int val);
/* This function will return the exit status of a child process,
waiting if necessary for a child process to end. When parameter
pid holds the value of a specific child process of this process,
WaitChild will wait for this specific process to finish. If
parameter pid is equal to NOPROC, then WaitChild will wait for
*any* child process to exit.
If parameter exitval is a not null, the exit code of the child
process will be stored in the variable pointed to by status.
On success, WaitChild returns the pid of an exited child.
On error, WaitChild returns NOPROC. Possible errors are:
- the specified pid is not a valid pid.
- the specified process is not a child of this process.
- the process has no child processes to wait on (when pid=NOPROC).
*/
Pid_t WaitChild(Pid_t pid, int* exitval);
/* This function returns the pid of the current process */
Pid_t GetPid(void);
/* This function is called with the same parameters as exec, to boot
the system. The system must initialize the scheduler and then call
the function boot_task with parameters argl and args. The boot task
can then create more processes.
When the boot task finishes, and no other processes are running,
this call halts the scheduler, cleans up TinyOS structures and then
returns. */
void boot(Task boot_task, int argl, void* args);
#endif
#ifndef __SYSCALLS_H__
#define __SYSCALLS_H__
/*
*
* Public kernel declarations
*
*/
/*******************************************
* Processes types and constants.
*******************************************/
typedef int Pid_t; /* The PID type */
/* The invalid PID */
#define NOPROC (-1)
/* The maximum number of processes */
#define MAX_PROC 65536
/*******************************************
* Concurrency control
*******************************************/
/* Mutexes */
typedef volatile unsigned int Mutex;
/*
This macro is used to initialize mutexes. Always create a mutex as
follows:
Mutex mu_mytex = MUTEX_INIT;
*/
#define MUTEX_INIT 1
/* Try to lock a mutex, return 1 on success, 0 on failure (when the
mutex is taken). This function does not block. */
int Mutex_TryLock(Mutex*);
/* Lock a mutex by waiting if necessary as long as it takes. */
void Mutex_Lock(Mutex*);
/* Unlock a mutex that you locked. */
void Mutex_Unlock(Mutex*);
/* Helper structure for condition variables. */
typedef struct __cv_waiter_s {
Pid_t pid;
struct __cv_waiter_s *prev, *next;
} __cv_waiter;
/* Condition variables */
typedef struct {
Mutex waitset_lock;
__cv_waiter *waitset;
} CondVar;
/* This macro is used to initialize a condition variable. It is used
as follows:
CondVar my_cv = CONDVAR_INIT;
*/
#define CONDVAR_INIT { MUTEX_INIT, NULL }
/* Initialize a CondVar when CONDVAR_INIT cannot
be used (e.g. an array of CondVars) */
void Cond_Init(CondVar*);
/* Wait on a condition variable. This must be called only while we
have locked the mutex that is associated with this call. It will
put our process to sleep, unlocking the mutex. These operations
happen atomically. When our process is woken up later (by another
process that called Cond_Signal or Cond_Broadcast), this function
first re-locks the mutex and then returns. */
void Cond_Wait(Mutex*, CondVar*);
/* Signal wakes up exactly one process sleeping on this condition
variable (if any). */
void Cond_Signal(CondVar*);
/* Broadcast wakes up all processes sleeping on this condition variable
(if any). */
void Cond_Broadcast(CondVar*);
/*******************************************
*
* Process creation
*
*******************************************/
/* New processes are created by calling a starting function, whose
signature is Task. */
typedef int (*Task)(int, void*);
/* Create a new process by calling the function with signature Task
and pass it parameters argl and args, where argl is the length of
byte array args (args can be NULL). */
Pid_t Exec(Task, int argl, void* args);
/* When this function is called by a process, the process terminates
and sets its exit code to val. */
void Exit(int val);
/* This function will return the exit status of a child process,
waiting if necessary for a child process to end. When parameter
pid holds the value of a specific child process of this process,
WaitChild will wait for this specific process to finish. If
parameter pid is equal to NOPROC, then WaitChild will wait for
*any* child process to exit.
If parameter exitval is a not null, the exit code of the child
process will be stored in the variable pointed to by status.
On success, WaitChild returns the pid of an exited child.
On error, WaitChild returns NOPROC. Possible errors are:
- the specified pid is not a valid pid.
- the specified process is not a child of this process.
- the process has no child processes to wait on (when pid=NOPROC).
*/
Pid_t WaitChild(Pid_t pid, int* exitval);
/* This function returns the pid of the current process */
Pid_t GetPid(void);
/* This function is called with the same parameters as exec, to boot
the system. The system must initialize the scheduler and then call
the function boot_task with parameters argl and args. The boot task
can then create more processes.
When the boot task finishes, and no other processes are running,
this call halts the scheduler, cleans up TinyOS structures and then
returns. */
void boot(Task boot_task, int argl, void* args);
#endif
/////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <string.h>
#include "syscalls.h"
/* We use the routines below to "burn" CPU cycle, by
computing Fibonacci numbers by the ultra-slow recursive definition.
*/
#define FBASE 30
#define FGAP 10
int FMIN= FBASE;
int FMAX= FBASE+FGAP;
unsigned int fiborand() { return lrand48() % (FMAX-FMIN+1) + FMIN; }
unsigned int fibo(unsigned int n) /* Very slow routine */
{
if(n<2) return n;
else return fibo(n-1)+fibo(n-2);
}
/* Dining Philosophers */
int N=0; /* Number of philosophers */
/* utilities */
int LEFT(int i) { return (i+1) % N; }
int RIGHT(int i) { return (i+N-1) % N; }
typedef enum { NOTHERE=0, THINKING, HUNGRY, EATING } PHIL;
PHIL* state; /* state[N]: Philosopher state */
Mutex mx = MUTEX_INIT; /* Mutual exclusion among philosophers (on
array 'state') */
CondVar *hungry; /* hungry[N}: put hungry philosophers to sleep */
/* Prints the current state given a change (described by fmt) for
philosopher ph */
void print_state(const char* fmt, int ph)
{
int i;
for(i=0;i<N;i++) {
char c= (".THE")[state[i]];
if(i==ph) printf("[%c]", c);
else printf(" %c ", c);
}
printf(fmt, ph);
}
/* Functions think and eat (just burn CPU cycles). */
void think(int i) { fibo(fiborand()); }
void eat(int i) { fibo(fiborand()); }
/* Attempt to make a (hungry) philosopher i to start eating */
void trytoeat(int i)
{
if(state[i]==HUNGRY && state[LEFT(i)]!=EATING && state[RIGHT(i)]!=EATING) {
state[i] = EATING;
print_state(" %d is eating\n",i);
Cond_Signal(&(hungry[i]));
}
}
/* Main philosopher routine */
int Philosopher(int argl, void* args)
{
int i,j;
int bites;
assert(argl == sizeof(int[2]));
i = ((int*)args)[0];
bites = ((int*)args)[1];
Mutex_Lock(&mx); /* Philosopher arrives in thinking state */
state[i] = THINKING;
print_state(" %d has arrived\n",i);
Mutex_Unlock(&mx);
for(j=0; j<bites; j++) { /* Number of bites (mpoykies) */
think(i);
Mutex_Lock(&mx);
state[i] = HUNGRY;
trytoeat(i); /* This may not succeed */
if(state[i]==HUNGRY) {
print_state(" %d waits hungry\n",i);
Cond_Wait(&mx, &(hungry[i])); /* If hungry we sleep. trytoeat(i) will wake us. */
}
assert(state[i]==EATING);
Mutex_Unlock(&mx);
eat(i);
Mutex_Lock(&mx);
state[i] = THINKING; /* We are done eating, think again */
print_state(" %d is thinking\n",i);
trytoeat(LEFT(i)); /* Check if our left and right can eat NOW. */
trytoeat(RIGHT(i));
Mutex_Unlock(&mx);
}
Mutex_Lock(&mx);
state[i] = NOTHERE; /* We are done (eaten all the bites) */
print_state(" %d is leaving\n",i);
Mutex_Unlock(&mx);
return i;
}
/*
This process executes a "symposium" for a number of philosophers.
*/
int Symposium(int argl, void* args)
{
int bites; /* Bites (mpoykies) per philosopher */
Pid_t pid;
int i;
assert(argl == sizeof(int[2]));
N = ((int*)args)[0]; /* get the arguments */
bites = ((int*)args)[1];
/* Initialize structures */
state = (PHIL*) malloc(sizeof(PHIL)*N);
hungry = (CondVar*) malloc(sizeof(CondVar)*N);
for(i=0;i<N;i++) {
state[i] = NOTHERE;
Cond_Init(&(hungry[i]));
}
/* Execute philosophers */
for(i=0;i<N;i++) {
int Arg[2];
Arg[0] = i;
Arg[1] = bites;
pid = Exec(Philosopher, sizeof(Arg), Arg);
}
/* Wait for philosophers to exit */
for(i=0;i<N;i++) {
pid = WaitChild(NOPROC, NULL);
}
free(state);
free(hungry);
return 0;
}
/*
* This is the initial task, which starts all the other tasks (except for the idle task).
*/
int boot_task(int argl, void* args)
{
/* Just start task Symposium */
Exec(Symposium, argl, args);
while( WaitChild(NOPROC, NULL)!=NOPROC ); /* Wait for all children */
return 0;
}
/****************************************************/
void usage(const char* pname)
{
printf("usage:\n %s <philosophers> <bites>\n\n where <philosiphers> is from 1 to %d\n",
pname, MAX_PROC);
exit(1);
}
int main(int argc, const char** argv)
{
int nphil, bites;
if(argc!=3) usage(argv[0]);
nphil = atoi(argv[1]);
bites = atoi(argv[2]);
/* check arguments */
if( (nphil <= 0) || (nphil > MAX_PROC) ) usage(argv[0]);
if( (bites <= 0) ) usage(argv[0]);
/* ajdust work per fibo call (to adapt to many philosophers/bites) */
if(1) {
FMIN = FBASE - (int)( log((double)(2*nphil*bites))/log(.5+.5*sqrt(5.)));
FMAX = FMIN + FGAP;
}
/* boot TinyOS */
{
int args[2];
args[0] = nphil; args[1] = bites;
printf("*** Booting TinyOS\n");
boot(boot_task, sizeof(args), args);
}
printf("*** TinyOS halted. Bye!\n");
return 0;
}