Semaphor Package
/* mykernel.c: your portion of the kernel
 *
 *    Below are procedures that are called by other parts of the kernel.
 *    Your ability to modify the kernel is via these procedures.  You may
 *    modify the bodies of these procedures any way you wish (however,
 *    you cannot change the interfaces).
 */
 
#include "aux.h"
#include "sys.h"
#include "mykernel3.h"
 
#define FALSE 0
#define TRUE 1
 
/*    A sample semaphore table.  You may change this any way you wish.
 */
 
static struct {
    int valid;    /* Is this a valid entry (was sem allocated)? */
    int value;    /* value of semaphore */
} semtab[MAXSEMS];
 
/*    InitSem () is called when kernel starts up.  Initialize data
 *    structures (such as the semaphore table) and call any initialization
 *    procedures here.
 */
 
void InitSem ()
{
    int s;
 
    /* modify or add code any way you wish */
 
    for (s = 0; s < MAXSEMS; s++) {        /* mark all sems free */
        semtab[s].valid = FALSE;
    }
}
 
/*    MySeminit (p, v) is called by the kernel whenever the system
 *    call Seminit (v) is called.  The kernel passes the initial
 *     value v, along with the process ID p of the process that called
 *    Seminit.  MySeminit should allocate a semaphore (find a free entry
 *    in semtab and allocate), initialize that semaphore's value to v,
 *    and then return the ID (i.e., index of the allocated entry).
 */
//static pre_id;
 
static int  block_queue[MAXPROCS];//circular queue
static int front = 0, rear = 0;
 
void add_q ( int item)
{
    rear++;
    rear = (rear % MAXPROCS);
    if (front == rear){
        Printf("Error! queue is full!\n");
        return;
    }
    else {
        block_queue[rear] = item;
    }
}
 
int delete_q ()
{    
    int pid;
    if (front == rear ){
//        Printf("Queue is empty!\n");
        return(0); 
    }
    else{
        front++;
        front = front % MAXPROCS;
        pid = block_queue[front];
        return (pid);
    }
} 
 
int MySeminit (p, v)                // allocate a semaphor with initialized value v for process p in semtab[]
    int p, v;
{
    int s;
 
    /* modify or add code any way you wish */
 
    for (s = 0; s < MAXSEMS; s++) {        // check if there is free semaphor (we can use 10 semaphors at the same time) 
        if (semtab[s].valid == FALSE) {
            break;
        }
    }
    if (s == MAXSEMS) {
        Printf ("No free semaphores\n");
        return (-1);
    }
 
    semtab[s].valid = TRUE;
    semtab[s].value = v;
 
    return (s);          // s is a index to semtab[], which refers to a corresponding semaphor
                     // in user program, it uses a semaphor with shared memory to store the index.
           // ex. shared int mutex = MySeminit(p, v);               
        //  after that, the user program can call MyWait(p, mutex) to access the corresponding semaphor
}
 
/*    MyWait (p, s) is called by the kernel whenever the system call
 *    Wait (s) is called.
 */
 
void MyWait (p, s)
    int p, s;
{
    /* modify or add code any way you wish */
    semtab[s].value--;
    if (semtab[s].value < 0){ 
        add_q(p);
        Block(p);
    }
}
 
/*    MySignal (p, s) is called by the kernel whenever the system call
 *    Signal (s) is called.
 */
 
void MySignal (p, s)
    int p, s;
{
    /* modify or add code any way you wish */
    int pre_pid = delete_q();
    semtab[s].value++;
    Unblock(pre_pid);
}

Note:
There is something wrong in this package. Signal() should only unblock the process which is blocked because of waiting for the same semaphor. However, in this code, all blocked processes are stored in the same array, and Signal() unblock a process in this array without carrying about which semaphor cause it blocked.
To solve it, we should add a linked list node pointer in every semaphor object, and the linked list stores all processes which is blocked by it.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License