Semaforen opdracht

Als je de opdracht daadwerkelijk uit gaat voeren is het van belang de aanwijzigingen in IMPLEMENT.SEM te volgen. Let op: je gaat dan dus een nieuwe minix maken. Deze minix kernel staat na de nodige compilaties op flop en daarvan is het geheel te booten. Tip: wijzig in eerste instantie niets aan de kernel, mm en fs sources en probeer eerst een floppy-bootable minix te maken.

Maak duidelijk onderscheid tussen de wijzigingen in minix sourceboom en de uiteindelijke applicaties waarmee je de semaforen gaat testen. De test spullen staan in semlib.h, semlib.c, semtest.c, dp.c, sb.c, rw.c en prodcon.c. De file dp.c kun je ook onder een gewone minix compileren en runnen maar de filosofen eten er maar een eind op los. Pas als je een goed werkend minix-met-semaforen hebt gaat dit programma lopen zoals het hoort.

Om te weten wat je zoal moet doen kun je de file MOD.SEM lezen.

De semaforen zijn als volgt geimplementeerd. Elk process krijgt via de mproc struct de beschikking over maximaal 20 (de define NR_SDS) semaforen. De semaforen zelf zitten in een array van totaal 64 stuks (NR_SEMS). Deze 64 gelden dus voor alle processen samen. Dit is te vergelijken met de filp-array (van fsdata). De file sem.c gaat er als volgt uitzien.

 /*
*** The implementation of semaphores.
 *
 *  The entry points into this file are:
 *	do_semget:   perform the SEM_GET system call
 *	do_semput:   perform the SEM_PUT system call
 *	do_semop:    perform the SEM_OP system call
 *
 *	sys_semput:  do the work for the SEM_PUT call
 */

#include "mm.h"
#include < sys/stat.h> 
#include < signal.h> 
#include "param.h"
#include "mproc.h"
#include "sem.h"

FORWARD _PROTOTYPE (int sem_valid, (struct mproc *mp, int sd) );
FORWARD _PROTOTYPE (int sem_down,  (struct mproc *mp, int sd) );
FORWARD _PROTOTYPE (int sem_up,    (struct mproc *mp, int sd) );
FORWARD _PROTOTYPE (void add_queue, (struct mproc **tail, struct mproc * mp) );
FORWARD _PROTOTYPE (void del_queue, (struct mproc **tail, struct mproc * mp) );

/*============================================================================*
 * FUNCTION:	do_semget
 *		Searches for a free slot in the semaphore descriptor table
 *		of a process and for a free slot in the semaphore table.
 * PRE:		mp points to process slot of the caller
 *		semval contains the semaphore value
 * POST:	Returns EMSEM if the discriptor table is full or
 *		        ENSEM if the semaphore table is full.
 *		Otherwise the descriptor of an initialised semaphore is
 *		returned and the process slot is updated.
 *============================================================================*/
PUBLIC int do_semget (void)
{
   register struct sem *rsp;
   register int sd;

   /* Look for a free semaphore descriptor and a free semaphore slot. */
   for (sd = 0; sd < NR_SDS; sd++)
      if (mp->mp_sds[sd] == NIL_SEM)
      {  /* A free descriptor has been found. Look for a free semaphore slot. */
	 for (rsp = &sem[0]; rsp < &sem[NR_SEMS]; rsp++)
            if (rsp->sem_count == 0)
            {  
               mp->mp_sds[sd] = rsp; /* descriptor points to free sem */
rsp->sem_count = 1; /* process is using semaphore */
rsp->sem_val = semval /* initialise */
return sd; /* return free descriptor */
} /* No free semaphore was found. */ return ENSEM; } /* If control passes here, the descriptor table must be full. Report that. */ return EMSEM; } /*============================================================================* * FUNCTION: do_semput * Performs the semput (semdes) system call. * PRE: mp points to the process slot of the caller * semdes contains the descriptor for a semaphore. * POST: Returns EBSEM if the descriptor is invalid otherwise returns * the value of sys_semput (mp, semdes). *============================================================================*/ PUBLIC int do_semput (void) { if (!sem_valid (mp, semdes)) return EBSEM; else { sys_semput (mp, semdes); return OK; } } /*============================================================================* * FUNCTION: do_semop * Performs the semop (semdes, semop) system call. * PRE: mp points to the process slot of the caller * semdes contains the descriptor for a semaphore * semop contains the operation code * POST: Returns EBSEM if the descriptor is invalid or * ENOSYS if the operation code is invalid. * If the opcode is SEM_UP the value of sem_up (mp, semdes) is * returned otherwise the value of sem_down (mp, semdes). *============================================================================*/ PUBLIC int do_semop (void) { if (!sem_valid (mp, semdes)) return EBSEM; else switch (semop) { case SEM_UP: return sem_up (mp, semdes); case SEM_DOWN: return sem_down (mp, semdes); default: return ENOSYS; } } /*---------------------------------------------------------------------------- * PROCEDURE: sys_semput * Do the work for the semput system call. * This procedure is called if a process does a SEM_PUT call or * if a process is killed and still uses a semaphore. * PRE: mp point to the process slot of the caller * sd is a valid semaphore desriptor * POST: If the process is blocked for this semaphore it is released * from the queue. Otherwise if every other process using this * semaphore is blocked for it, then another process is released. * The semaphore identified by sd is updated and the descriptor * and the semaphore are released. *----------------------------------------------------------------------------*/ PUBLIC void sys_semput (struct mproc *mp, int sd) { struct sem *sp = mp->mp_sds[sd]; struct mproc *this_proc; if (mp->mp_sem == sp) /* process is blocked for this semaphore */ { sp->sem_val++; /* semaphore is unused so increment value; */ del_queue(&sp->semtail, mp); /* remove process from queue */ mp->mp_sem = NIL_SEM; /* process isn't blocked waiting, reset pointer */ mp->mp_next = NIL_MPROC; /* process is removed from queue */ } else if (sp->sem_count > 1 && -sp->sem_val == sp->sem_count -1) { /* Does there exist a blocked process and is every */ /* other process using this semaphore blocked for it? */ /* wake up another process */ this_proc = (sp->sem_tail)->mp_next; /* first proc in queue */ del_queue(&sp->sem_tail, this_proc); /* remove from queue */ sp->sem_val++; /* increment value */ this_proc->mp_sem = NIL_SEM; /* cleanup */ this_proc->mp_next = NIL_MPROC; reply(this_proc - mproc, 0, 0, NULL); /* Tell OS: I'm awake */ } sp->sem_count--; /* process is death */ mp->mp_sds[sd] = NIL_SEM; /* cleanup descriptor */ } /*============================================================================= * FUNCTION: sem_valid * Checks the validity of a semaphore descriptor for a process. * POST: Returns 0 if the descriptor is out of range or no semaphore * is available for the descriptor otherwise 1. *============================================================================*/ PRIVATE int sem_valid (struct mproc *mp, int sd) { return (sd >= 0 && sd < NR_SDS && mp->mp_sds[sd] != NIL_SEM); } /*============================================================================* * FUNCTION: sem_up * Does the work for the semup system call. * PRE: mp points to the process slot of the caller * sd is a valid semaphore desriptor * POST: If, after incrementing the semaphore value, it is non positive * another process is released from the queue and waked up. * sem_up always returns OK. *============================================================================*/ PRIVATE int sem_up (struct mproc *mp, int sd) { struct sem *sp = mp->mp_sds[sd]; struct mproc *this_proc; if (++sp->sem_val <= 0) { /*wake up a blocked process */ this_proc = (sp->sem_tail)->mp_next; del_queue(&sp->sem_tail, this_proc); this_proc->mp_sem = NIL_SEM; this_proc->mp_next = NIL_MPROC; reply (this_proc - mproc, 0, 0, NULL); } return OK; } /*============================================================================* * FUNCTION: sem_down * Does the work for the semdown system call. * PRE: mp points to the process slot of the caller * sd is a valid semaphore desriptor * POST: If the semaphore value is positive it is decremented and OK * is returned. Otherwise if all other process using this * semaphore are blocked for it EPERM is returned. Otherwise the * process is added to the queue of the semaphore and goes asleep. * The semaphore identified by sd is updated and OK is returned. *============================================================================*/ PRIVATE int sem_down (struct mproc *mp, int sd) { struct sem *sp = mp->mp_sds[sd]; if (sp->sem_val > 0) { sp->sem_val--; return OK; } else if (-sp->sem_val == sp->sem_count -1) /* All other processes using this semaphore are blocked waiting. */ return EPERM; else { sp->sem_val--; add_queue(&sp->sem_tail, mp); mp->mp_sem = sp; dont_reply = TRUE; /* the process is blocked now */ return OK; } } /*---------------------------------------------------------------------------- * PROCEDURE: add_queue * Adds a process to a circular semaphore queue. * PRE: *tail points to the tail of the semaphore queue * mp points to the process to be added * POST: If mp is invalid an error is reported and the queue is left * unchanged otherwise mp is added to the tail of the queue. *----------------------------------------------------------------------------*/ PRIVATE void add_queue (struct mproc **tail, struct mproc *mp) { if (mp == NIL_MPROC) printf ("\nERROR: Can't add NIL_MPROC to the queue.\n"); else { if (*tail == NIL_MPROC) mp->mp_next = mp; else { mp->mp_next = (*tail)->mp_next; (*tail)->mp_next = mp; } *tail = mp; } } /*---------------------------------------------------------------------------- * PROCEDURE: del_queue * Deletes a process from a circular semaphore queue. * PRE: *tail points to the tail of the semaphore queue * mp points to the process to be deleted * POST: If mp is invalid or the queue is empty or the process is not in * the queue an error is reported and the queue is left unchanged. * Otherwise mp is deleted from the queue. *----------------------------------------------------------------------------*/ PRIVATE void del_queue (struct mproc **tail, struct mproc *mp) { if (mp == NIL_MPROC) printf ("\nERROR: Can't remove NIL_MPROC.\n"); else if (*tail == NIL_MPROC) printf ("n\ERROR: Queue is empty.\n"); else { struct mproc *cur = *tail, *next = cur->mp_next; while (next != mp && next != *tail) /* search for the process */ { cur = next; next = next->mp_next; } if (next != mp) printf ("\nERROR: Process to be deleted not in queue.\n"); else { if (cur == next) /* is it the only one ? */ *tail = NIL_MPROC; else { cur->mp_next = next->mp_next; /* remove the process */ if (next == *tail) *tail = cur; } mp->mp_next = NIL_MPROC; /* update process slot */ } } }

Bestudeer de code goed (let op ik heb wellicht een tikfoutje gemaakt). Belangrijk is dat je snapt hoe een en ander werkt. Op het tentamen kunnen hier vragen over gesteld worden.
In de file mod.sem staan nog andere gegevens die in diverse minix files verwerkt moeten worden. Zo zijn in table.c de entries van de system calls (do_semget etc.) aangebracht. In forkexit.c moet ook rekening gehouden worden met het bestaan van semaforen. Bij een fork krijgt het kind-process de semaforen van de ouder mee. De semaforen zelf moeten dan ook aangepast worden (er komt een extra process bij). Bij exit moet men ook rekening houden met het bestaan van semaforen, het betreffende process moet ze weer vrijgeven (sys_semput).
Schrijf een verslag over semaforen waarin antwoorden gegeven worden op de volgende vragen:

  1. Waartoe dienen semaforen?
  2. Hoe worden ze in deze opdracht geimplementeerd?
  3. Hoe kunnen processen semaforen gemeenschappelijk hebben? (kijk in een van de testprogramma's zoals dp.c). Semaforen hebben namelijk pas zin als meer processen over dezelfde semafoor kunnen beschikken.
  4. Wat gebeurt er als twee of meer processen een 'critical section' willen binnengaan?
  5. Een process, dat meer semaforen gebruikt, kan maar in een enkele wachtrij zitten, waarom?
  6. Beschrijf in woorden hoe do_semget, do_semput, sem_up en sem_down werken.

Leo van Moergestel
<leovm@cable.A2000.nl>
Aangemaakt 10 december 1997
Laatst bijgewerkt 16 december 1997