mos.cpp

语法分析器 完成从c/c++向C++转变

//////////////////////////////////////////////////////////////////////////////*
//
// Module Name:   MOS.CPP
// 
// Description:   Multi-tasking
//                Operating
//                System
//                Simulation
//
//                Moss is a simulation of a multi-tasking operating system
//                which uses many of the C standard algorithms.
//
//
// Written by:  John Tal
//
//
//
// Modification History:
//
// Date          Programmer      Mod#     Modification
// ---------------------------------------------------------------------------
// 04-JUL-1991   J. Tal          V1.0-000 New
//
// -
//


//    VERSION 1 - July 4, 1991
//
//    MOS uses concepts which are familiar to various implementations of
//    multi-tasking operating systems.   It has a scheduler to select a
//    process (or job) to run from a list of waiting processes.   It has
//    inter-process-communication (IPC) and (currently) one semaphore.

//    What it does not do is context switching.  Normally, when the
//    scheduler takes one job which was running and allows another
//    to have some cpu, it saves the current context of the process
//    which was running by saving the values of the important machine
//    (cpu) registers as used by the interrupted process.   When the
//    interrupted process is placed back in a running state, it has
//    no clue that it ever stopped running.   This version of MOS
//    does not perform context switching.   It simply services ready
//    processes (by priority order) and makes each process start at
//    the beginning of its code.

//    Another major function of an operating system which is not 
//    implemented here is memory management.   This is management
//    not only of calloc, malloc, cfree, and free requests by
//    the applications, but it also deals with swapping inactive
//    applications out to disk until they run again.  This is
//    virtual memory management and is beyond the scope of the
//    humble goals of MOS.   

//    The concepts used in MOS are a subset of any multi-tasking
//    operating system.   A recommended book for a detailed explanation
//    of the function of operating system design is 'Operating System
//    Design: The XINU Approach'  by Douglas Comer.  There is also
//    source code available in the public domain which implements XINU
//    on top of PcDos.   The source code is not recommended because
//    of serious mistakes made in the specific implemention of sitting
//    on top of dos (a non-multi-tasking operating system).  But the 
//    book is good reference material.

//    Mos was written in a few hours on July 4, 1991 using the Brief
//    editor and Microsoft C 5.1 on an AT clone.
//

//    VERSION 2 - Fall 1991

//    The Moss name was changed to MOS for consistency with other members
//    of the Algorithms volumes.  The major changes/enhancements for this
//    version include:
//
//              o       Support for unlimited number of semaphores
//                      (1 was supported with v 1.0)
//
//              o       Enhanced messaging.   A process will now
//                      wait for a message if one is not ready yet.
//
//              o       Swap control is enhanced.   A process may
//                      specify exactly which function is to be
//                      called next when a process is swapped back
//                      into execution. 
//
//   Version 2 is highly source code compatible with Version 1 and
//   most applications calling MOS will require only recompilation
//   and linking with Version 2 libraries.
//
//   A number of weeks were spent researching a full-context swapping
//   implemention of MOS.  This involved using assembly language to
//   change the stack pointer as each process begins execution.
//   The current version of MOS has provided more than adequate 
//   execution and elementary multi-tasking in both DOS and UNIX
//   environments while maintaining the portability not possible
//   in assembly language.  If you are interested in extending MOS
//   into full context-swapping and/or interrept driven modes, there
//   is ample documentation in Dr. Dobbs Journal and C Users Group
//   magazines to do so.
//

//    VERSION 2 C++ - February 1992

//    The C++ port of MOS provided quite a number of suprises.
//    Once again, C++ has the ability to point out inefficiencies
//    in a seemingly effective design.  Specific tips which were
//    learned during the MOS port are provided in a document called
//    c_2_cpp.txt which is released with MOS on Volume 2 of the
//    Algorithms series.



#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#include <cmemlib.h>
#include <time.h>

#include "mos.h"





#ifdef TEST


SHORT MosTestProc(MOS_C *, PVOID);


//
//   Mos Main
//


int main()
{
   C_DEF_MODULE("MosMain")

   
   MOS_C   Mos;

   //
   //  Load up some processes, all use the MosGenericProc as their
   //  code.   This could be modified for experimentation to
   //  be other processes modeled after MosGenericProc but
   //  with specialized functions
   //

   C_STATUS = Mos.ProcCreate(MosTestProc,"Plankton",10,NULL);
   C_STATUS = Mos.ProcCreate(MosTestProc,"Trilobite",10,NULL);
   C_STATUS = Mos.ProcCreate(MosTestProc,"Volvox",5,NULL);
   C_STATUS = Mos.ProcCreate(MosTestProc,"Tree",5,NULL);
   C_STATUS = Mos.ProcCreate(MosTestProc,"Eagle",1,NULL);

   Mos.Scheduler();

   C_RETURN
}

#endif



//
//  Init Mos Environment
//

SHORT
MOS_C::Init(VOID)
{
   C_DEF_MODULE("MOS_C::Init")

   //
   //  Init semaphore
   //

   sProcId = 0;
   sSemHandle = 0;

#if 0
   strcpy(szProcStates[0],"Non Existant");
   strcpy(szProcStates[1],"Running");
   strcpy(szProcStates[2],"Ready");
   strcpy(szProcStates[3],"Sleeping");
   strcpy(szProcStates[4],"Waiting on Semaphore");
   strcpy(szProcStates[5],"Waiting on Message");
#endif

   //
   //  Must always have a process on the ready queue, the NULL process
   //  does nothing.   In operating systems, nothing else can EVER
   //  have access to the NULL process or the swapper process.
   //  Noone or nothing can kill them or the system dies.
   //

   C_STATUS = ProcCreate(MosNullProc,"NULL_PROC",0,(PVOID) NULL);

   C_RETURN
}


//
//  MosCompareTreProcId
//
//      Use for node to node comparision of binary tree, for InsertNode
//

SHORT
CompareTreProcId(PVOID pvData1,PVOID pvData2)
{
   PROC_P   pclProc1;
   PROC_P   pclProc2;

   pclProc1 = (PROC_P) pvData1;
   pclProc2 = (PROC_P) pvData2;

   if(pclProc1 -> GetId() == pclProc2 -> GetId())
      return(C_EQUAL);
   else if(pclProc1 -> GetId() < pclProc2 -> GetId())
      return(C_LOWER);
   else
      return(C_HIGHER);
}


//
//   MosCompareIdNode
//

SHORT
MosCompareIdNode(PVOID pvData1,PVOID pvData2)
{
   PROC_P   pclProc;
   PSHORT   psProcId;


   psProcId = (PSHORT) pvData1;
   pclProc = (PROC_P) pvData2;
                            
   if(*psProcId == pclProc -> GetId())
      return(C_EQUAL);
   else if(*psProcId < pclProc -> GetId())
      return(C_LOWER);
   else if(*psProcId > pclProc -> GetId())
      return(C_HIGHER);

}


//
//   MosCompareProcWakeTime
//

SHORT
MosCompareProcWakeTime(PVOID pvData1,PVOID pvData2)
{
   PROC_P   pclProc1;
   PROC_P   pclProc2;

   pclProc1 = (PROC_P) pvData1;
   pclProc2 = (PROC_P) pvData2;

   if(pclProc1 -> GetWakeTime() == pclProc2 -> GetWakeTime())
      return(C_EQUAL);
   else if(pclProc1 -> GetWakeTime() < pclProc2 -> GetWakeTime())
      return(C_LOWER);
   else
      return(C_HIGHER);
}




//
//    MOS APIs
//

//
//    Create a new process
//

SHORT
MOS_C::ProcCreate(SHORT (*pProc)(MOS_C *, PVOID), PCHAR szProcName, SHORT sPriority,PVOID pvWorkArea)
{
   C_DEF_MODULE("MOS_C::ProcCreate")

   PROC_P   pclProc;

   pclProc = (PROC_P) new PROC_C;

   pclProc -> SetPriority(sPriority);  // set priority
   pclProc -> SetName(szProcName);     // set name
   pclProc -> SetId(sProcId);          // set proc id
   sProcId++;                          // inc global

   pclProc -> SetState(PROC_STATE_READY);         // It is ready 
   pclProc -> SetPrevState(PROC_STATE_NO_EXIST);  // no prvious state
   pclProc -> pProc = pProc;          // Point to proc to run
   pclProc -> pBlockedFunc = NULL;
   pclProc -> SetWorkArea(pvWorkArea);

   lNumProcs++;

   //
   //   Store this process in the global process tree
   //

   C_STATUS = clProcTree.SetCompareFunc(MosCompareProcName);
   C_STATUS = clProcTree.Insert((PVOID) &pclProc);

   //
   //   Store this process in proc id list
   //

   C_STATUS = clPidList.SetCompareFunc(MosCompareProcId);
   C_STATUS = clPidList.Insert((PVOID) &pclProc);

   //
   //  Place this process on the ready queue
   //

   C_STATUS = ReschedReady(pclProc);

   C_RETURN
}


//
//    Terminate a process
//

SHORT
MOS_C::ProcTerm(VOID)
{
   C_DEF_MODULE("MOS_C::ProcTerm")

   PVOID    pvData;

   C_STATUS = clProcTree.SetCompareFunc(MosCompareProcName);
   C_STATUS = clProcTree.Delete((PVOID) pclRunProc);

   C_STATUS = clPidList.SetCompareFunc(MosCompareProcId);
   C_STATUS = clPidList.Find((PVOID) pclRunProc,&pvData);
   C_STATUS = clPidList.DeleteCur();

   pclRunProc -> SetState(PROC_STATE_NO_EXIST);

   lNumProcs--;

   delete pclRunProc;
 
   C_RETURN
}


//
//   MosScheduler
//       
//      This is the central workhorse function
//

SHORT
MOS_C::Scheduler(VOID)
{
   C_DEF_MODULE("MOS_C::Scheduler")
   
   PROC_P  pclProc;

   while(1)
   {

      /* if only NULL proc is running, terminate */

      if(lNumProcs == 1)
        break;


      /*
      **  Run check on all events
      */

      C_STATUS = EventCheckList();


      //
      //  You may want to put a delay here or get a character from the
      //  keyboard to see what Mos is doing on each iteration through
      //  the code
      //

      C_STATUS = CheckSleepQueue();

      C_STATUS = GetReadyProc(&pclProc);

      pclRunProc = pclProc;

      //
      //  Invoke the process
      //

      if(pclRunProc -> pBlockedFunc == NULL)
	 C_STATUS = (*pclRunProc -> pProc)(this,pclRunProc->GetWorkArea());
      else
	 C_STATUS = (*pclRunProc -> pBlockedFunc)(this,pclRunProc->GetWorkArea());
 

      //       The function   ^ ptr to MOS     ^ proc workarea
   
      //
      //  If we were running the NULL process, then MUST put it back on the
      //  ready queue.   An empty ready queue = system crash
      //
   
      if(C_STATUS != PROC_STATE_NO_EXIST)
      {
	 if(pclRunProc -> GetState() == PROC_STATE_RUNNING)
	    C_STATUS = ReschedReady(pclRunProc);
      }
           
   }

   //
   //  Some compilers will tell you that the next statement is unreachable,
   //  That is ok.
   //

   C_RETURN
}


//
//  Mos CheckSleepQueue
//    
//      Check the sleep queue.  If anything there and is ready to be 
//      waked-up, place on the ready queue
//

SHORT
MOS_C::CheckSleepQueue(VOID)
{
   C_DEF_MODULE("MOS_C::CheckSleepQueue")

   PROC_P    pclProc;

   while(1)
   {
      //
      //  Loop to free all jobs which we can
      //

      C_STATUS = clQueSleep.FindFirst((PVOID *) &pclProc);

      if(pclProc != NULL)
      {
	 if(pclProc -> GetWakeTime() <= GetTime())
         {
            printf("Process %d: %s : Being awakened\n", pclProc -> GetId(),
                                                        pclProc -> GetName());
            //  Delete from Sleep list/queue
   
            C_STATUS = clQueSleep.DeleteCur();
    
            C_STATUS = ReschedReady(pclProc);
         }
         else 
           break;
      }
      else
         break;
   }
      
   C_RETURN
}


//
//   MosReschedReady
//       
//       Places a process on the ready queue
//

SHORT
MOS_C::ReschedReady(PROC_P pclProc)
{
   C_DEF_MODULE("MOS_C::ReschedReady")

   pclProc -> SetPrevState(pclProc -> GetState()); // save state
   pclProc -> SetState(PROC_STATE_READY);          // set state
   C_STATUS = clQueReady.Enq(pclProc -> GetPriority(),(PVOID) pclProc);

#ifdef ANNOUNCE
   C_STATUS = ProcAnnounce(pclProc);
#endif

   C_RETURN
}


//
//  Mos GetReadyProc
//
//      It retrieves the process that should be run next from the ready queue
//

SHORT
MOS_C::GetReadyProc(PROC_P * ppclProc)
{
   C_DEF_MODULE("MOS_C::GetReadyProc")

   SHORT  sPriority;

   //
   //  Get a process
   //

   C_STATUS = clQueReady.Deq(&sPriority, (PVOID *) ppclProc);

   //
   //  Set proc state to running
   //

   (*ppclProc) -> SetState(PROC_STATE_RUNNING);

#ifdef ANNOUNCE
   printf("\n");

   C_STATUS = ProcAnnounce(*ppclProc);
#endif

   C_RETURN
}


//
//  MosProcAnnounce
//
//       It is used for processes to announce when they have started running
//

//SHORT
//MOS_C::ProcAnnounce(PROC_P pclProc)
//{
//   C_DEF_MODULE("MOS_C::ProcAnnounce")
//
//   printf("Process %d: %s : Is %s\n",
//           * pclProc -> GetProcId();
//           * pclProc -> GetName(),
//           szProcStates[pclProc -> sState]);
//
//   C_RETURN
//}


//
//  MosNullProc
//
//       The Null Process
//

SHORT
MosNullProc(MOS_P pclMos,PVOID pvWorkArea)
{
   C_DEF_MODULE("MOS_C::NullProc")

   pvWorkArea = pvWorkArea;  // to keep compiler quiet
   pclMos = pclMos;          // to keep compiler quiet

#ifdef ANNOUNCE
   C_STATUS = ProcAnnounce();
#endif

   //  If running under any multi-tasking/processing
   //  operating system, sleep here so dont eat up CPU

#ifdef C_UNIX
   sleep(1);
#endif

   C_RETURN
}


//
//  Semaphore
//

//
//  Mos  SemInit
//