操作系统实验一——模拟进程调度时间片轮转算法

时间：2021-01-27 19:50:54

本程序用于模拟进程。
总体思路为：用一个调度线程来模拟操作系统的调度进程，用一个线程来模拟一个进程。于是，对应于每一个被模拟的进程，都有相应的线程来模拟，并在调度线程的调度下，实现时间片轮转的调度算法。
具体实现：
PCB块的数据结构：
typedef struct PCB {
 int id;
 char name[20];
 int status;
 int ax, bx, cx, dx;
 int pc;
 int psw;
 struct PCB* next;
 HANDLE hThis;
 DWORD threadID;
 int count;
}PCB, *pPCB;

ReadyList 和 FreeList的数据结构：
typedef struct {
 pPCB head;
 pPCB tail;
 int pcbNum;
}readyList, freeList, *pList;

状态列表：
enum STATUS { RUN, READY, WAIT };

PCB块总数：
const int PCB_LIMIT = 10;

在本程序中，调度线程为DWORD WINAPI scheduleThread(LPVOID lpParameter)。模拟进程的线程为：DWORD WINAPI processThread(LPVOID lpParameter)。

程序中每个时间片设置为1秒，其中每个进程在每个时间片内可以运行两条指令，将导致其pc加2。每个进程的各个寄存器，在进程生成时自动生成。

程序可以动态的创建进程，动态的撤销进程，并将最终的运行结果写在process_log.txt文件中。程序的运行界面如下：（可直接运行文件夹可执行程序中的Pro_test。）
create pro_name pro_len（如create p0 10）用于创建一个新进程。
remove pro_name （如remove p0）用于撤销一个进程。
current 用于显示当前运行进程以及当前就绪队列信息。

源代码如下：

pcb.h
#ifndef PCB_H
#define PCB_H

typedef struct PCB {
 int id;
 char name[20];
 int status;
 int ax, bx, cx, dx;
 int pc;
 int psw;
 struct PCB* next;
 HANDLE hThis;
 DWORD threadID;
 int count;
}PCB, *pPCB;

typedef struct {
 pPCB head;
 pPCB tail;
 int pcbNum;
}readyList, freeList, *pList;

typedef struct apply{
 char name[20];
 int time;
 struct apply* next;
}applyProcess, *applyList;

typedef struct {
 applyList head;
 applyList tail;
 int applyNum;
}applyQueue;

enum STATUS { RUN, READY, WAIT };
const int PCB_LIMIT = 10;

void init();
void createProcess(char* name, int ax);
void addApplyProcess(char* name, int time);
void createIfAnyApply();
void scheduleProcess();
void removeProcess(char* name);
void fprintReadyList();
void printCurrent();

#endif

pcb.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include "pcb.h"
#include "funCode.h"

pList   pReadyList = new readyList;
pList   pFreeList = new freeList;
pPCB   runPCB;
bool   firstTime = true;
applyQueue*  queue = new applyQueue;
HANDLE   hSchedule = NULL;
bool   schIsActive = false;
CRITICAL_SECTION cs_ReadyList;
CRITICAL_SECTION cs_SaveSection;
//CRITICAL_SECTION cs_RunPCB;

extern FILE* log;
extern PC;
extern FUN functions[FUN_NUM];

void initialPCB(pPCB p) {
 p->id = 0;
 strcpy(p->name, "");
 p->status = WAIT;
 p->ax = 0;
 p->bx = 0;
 p->cx = 0;
 p->dx = 0;
 p->pc = 0;
 p->psw = 0;
 p->next = NULL;
 p->hThis = NULL;
 p->threadID = 0;
 p->count = 0;
}

pPCB getPcbFromFreeList() {
 pPCB freePCB = NULL;
 if (pFreeList->head != NULL && pFreeList->pcbNum > 0) {
  freePCB = pFreeList->head;
  pFreeList->head = pFreeList->head->next;
  pFreeList->pcbNum--;
 }
 return freePCB;
}

void returnPcbToFreeList(pPCB p) {
 initialPCB(p);

 if (pFreeList->head == NULL) {
  pFreeList->head = p;
  pFreeList->tail = p;
  pFreeList->pcbNum++;
 } else {
  pFreeList->tail->next = p;
  pFreeList->tail = p;
  pFreeList->pcbNum++;
 }
}

DWORD WINAPI processThread(LPVOID lpParameter) {
 pPCB currentPcb = (pPCB)lpParameter;
 MSG msg;

 while (true) {
  Sleep(500);
  fprintf(log, "process %d:%s is running.../n", currentPcb->id, currentPcb->name);
  currentPcb->pc++;
  fflush(log);

  EnterCriticalSection(&cs_SaveSection);
  if (PeekMessage(&msg, NULL, 0, 0,PM_REMOVE)) {
   if (msg.message == WM_USER) {
    //printf("Process %d:%s recieve a message. It's to be suspended./n",
    // currentPcb->id, currentPcb->name);
   }
  }
  LeaveCriticalSection(&cs_SaveSection);
 }
 /*
 while (true) {
  PC = currentPcb->pc;
  
  for (int i = 0; i < TIME_SLOT; i++) {
   (*functions[PC%FUN_NUM].pc)();
   PC++;
  }
  
  currentPcb->pc = PC;
  SuspendThread(currentPcb->hThis);
 }*/

 return 0;
}

DWORD WINAPI scheduleThread(LPVOID lpParameter) {
 pList readyList = (pList)lpParameter;
 while (true) {
  scheduleProcess();

  if (readyList->pcbNum <= 0 && schIsActive) {
   schIsActive = false;
   SuspendThread(hSchedule);
  } else if (readyList->pcbNum >0 && !schIsActive) {
   schIsActive = true;
   ResumeThread(hSchedule);
  }
 }

 return 0;
}

void init() {
 ////////////////////////////////////////////////////////////////
 if (firstTime) {
  pReadyList->head = NULL;
  pReadyList->tail = NULL;
  pReadyList->pcbNum = 0;

  pFreeList->head = NULL;
  pFreeList->tail = NULL;
  pFreeList->pcbNum = 0;

  for (int i = 0; i < PCB_LIMIT; i++) {
   pPCB pTempPCB = new PCB;
   initialPCB(pTempPCB);
   pTempPCB->id = i;
   if (pFreeList->head == NULL) {
    pFreeList->head = pTempPCB;
    pFreeList->tail = pTempPCB;
    pFreeList->pcbNum++;
   } else {
    pFreeList->tail->next = pTempPCB;
    pFreeList->tail = pTempPCB;
    pFreeList->pcbNum++;
   }
  }

  hSchedule = CreateThread(NULL, NULL, scheduleThread, pReadyList, CREATE_SUSPENDED, 0);

  InitializeCriticalSection(&cs_ReadyList);
  InitializeCriticalSection(&cs_SaveSection);
  //InitializeCriticalSection(&cs_RunPCB);

  firstTime = false;
 }
 //////////////////////////////////////////////////////////////////////
}

void createProcess(char* name, int count/*, int pc*/) { 
 //
 EnterCriticalSection(&cs_ReadyList);
 //
 if (pFreeList->pcbNum > 0) {
  pPCB newPcb = getPcbFromFreeList();
  newPcb->status = READY;
  strcpy(newPcb->name, name);
  newPcb->count = count;
  //newPcb->pc = 0;
  newPcb->next = NULL;

  srand( (unsigned)time( NULL ) );
  newPcb->ax = rand() % 20;
  newPcb->bx = rand() % 20;
  newPcb->cx = rand() % 20;
  newPcb->dx = rand() % 20;
  newPcb->pc = rand() % 20;
  newPcb->psw = rand() % 20;
  
  if (pReadyList->pcbNum == 0) {
   pReadyList->head = newPcb;
   pReadyList->tail = newPcb;
   pReadyList->pcbNum++;
  } else {
   pReadyList->tail->next = newPcb;
   pReadyList->tail = newPcb;
   pReadyList->pcbNum++;
  }
  
  fprintf(log, "New Process Created.  /nProcess ID: %d  Process Name: %s  Process Length: %d/n",
   newPcb->id, newPcb->name, newPcb->count);
  fprintf(log, "AX: %d/tBX: %d/tCX: %d/tDX: %d/tPC: %d/tPSW: %d/n/n",
   newPcb->ax, newPcb->bx, newPcb->cx, newPcb->dx, newPcb->pc, newPcb->psw);
  fprintf(log, "Current ReadyList is:/n");
  fprintReadyList();

  newPcb->hThis = CreateThread(NULL, NULL, processThread, newPcb, CREATE_SUSPENDED, &(newPcb->threadID));
 } else {
  printf("PCB used out/n");
  fprintf(log, "New process intend to append. But PCB has been used out!/n/n");
 }
 //
 LeaveCriticalSection(&cs_ReadyList);
 //
}

void scheduleProcess() {
 ////
 //EnterCriticalSection(&cs_RunPCB);
 ////
 
 //
 EnterCriticalSection(&cs_ReadyList);
 //
 if (pReadyList->pcbNum > 0) {
  runPCB = pReadyList->head;
  
  pReadyList->head = pReadyList->head->next;
  if (pReadyList->head == NULL) {
   pReadyList->tail = NULL;
  }
  pReadyList->pcbNum--;

  runPCB->count--;
  fprintf(log, "Process %d:%s is to be scheduled./n"
   "Process %d:%s Information:/tAX: %d/tBX: %d/tCX: %d/tDX: %d/tPC: %d/tPSW: %d/n/n",
   runPCB->id, runPCB->name, runPCB->id, runPCB->name,
   runPCB->ax, runPCB->bx, runPCB->cx, runPCB->dx, runPCB->pc, runPCB->psw);
  ResumeThread(runPCB->hThis);
  runPCB->status = RUN;
  Sleep(1000);
  fprintf(log, "/nOne time slot used out!/n/n");
  runPCB->status = READY;
  PostThreadMessage(runPCB->threadID, WM_USER, 0, 0);
  //
  EnterCriticalSection(&cs_SaveSection);
  //
  SuspendThread(runPCB->hThis);
  //
  LeaveCriticalSection(&cs_SaveSection);
  //

  if (runPCB->count <= 0 && runPCB != NULL) {
   printf("/nProcess %d:%s has finished./n", runPCB->id, runPCB->name);
   printf("COMMAND>");
   fprintf(log, "Process %d:%s has finished./n/n", runPCB->id, runPCB->name);
   fprintf(log, "Current ReadyList is:/n");
   fprintReadyList();
   fflush(log);

   TerminateThread(runPCB->hThis, 0);
   returnPcbToFreeList(runPCB);
   runPCB = NULL;
  }
  
  if (runPCB != NULL) {
   if (pReadyList->pcbNum == 0) {
    pReadyList->head = runPCB;
    pReadyList->tail = runPCB;
   } else {
    pReadyList->tail->next = runPCB;
    pReadyList->tail = runPCB;
   }
   runPCB->next = NULL;
   runPCB = NULL;
   pReadyList->pcbNum++;
  }
 } else if (pReadyList != NULL) {
  pReadyList->head = NULL;
  pReadyList->tail = NULL;
  pReadyList->pcbNum = 0;
 }
 //
 LeaveCriticalSection(&cs_ReadyList);
 //
 ////
 //LeaveCriticalSection(&cs_RunPCB);
 ////
}

void addApplyProcess(char* name, int time) {
 applyProcess* newApply = new applyProcess;
 strcpy(newApply->name, name);
 newApply->time = time;
 newApply->next = NULL;
 
 if (queue->applyNum <= 0) {
  queue->head = newApply;
  queue->tail = newApply;
  queue->applyNum = 1;
 } else {
  queue->tail->next = newApply;
  queue->tail = newApply;
  queue->applyNum++;
 }

 createIfAnyApply();
}

void createIfAnyApply() {
 if (queue != NULL && queue->applyNum >= 1) {
  applyProcess* temp = queue->head;
  createProcess(temp->name, temp->time);
  
  if (queue->applyNum <= 1) {
   queue->head = NULL;
   queue->tail = NULL;
  } else {
   queue->head = queue->head->next;
  }
  
  queue->applyNum--;
  delete temp;
 }

 if (!schIsActive) {
  schIsActive = true;
  ResumeThread(hSchedule);
 }
}

void removeProcess(char* name) {
 pPCB removeTarget = NULL;
 pPCB preTemp = NULL;

 //
 EnterCriticalSection(&cs_ReadyList);
 //
 if (runPCB != NULL && strcmp(name, runPCB->name) == 0) {
  removeTarget = runPCB;
  
  printf("Process %d:%s has been removed./n", removeTarget->id, removeTarget->name);
  fprintf(log, "/nProcess %d:%s has been removed./n", removeTarget->id, removeTarget->name);
  
  TerminateThread(removeTarget->hThis, 0);
  returnPcbToFreeList(removeTarget);
  runPCB = NULL;

  fprintf(log, "Current ReadyList is:/n");
  fprintReadyList();
  fflush(log);

  //
  LeaveCriticalSection(&cs_ReadyList);
  //
  return;
 } else if (pReadyList->head != NULL) {
  for (removeTarget = pReadyList->head, preTemp = pReadyList->head;
   removeTarget != NULL; removeTarget = removeTarget->next) {

   if (removeTarget == pReadyList->head && strcmp(name, removeTarget->name) == 0) {
    pReadyList->head = pReadyList->head->next;
    if (pReadyList->head == NULL) {     
     pReadyList->tail = NULL;
    }
    
    printf("Process %d:%s has been removed./n", removeTarget->id, removeTarget->name);
    fprintf(log, "/nProcess %d:%s has been removed./n", removeTarget->id, removeTarget->name);
    
    TerminateThread(removeTarget->hThis, 0);
    returnPcbToFreeList(removeTarget);
    pReadyList->pcbNum--;

    fprintf(log, "Current ReadyList is:/n");
    fprintReadyList();
    fflush(log);

    //
    LeaveCriticalSection(&cs_ReadyList);
    //
    return;
   } else if (removeTarget != pReadyList->head && strcmp(name, removeTarget->name) == 0) {
    preTemp->next = removeTarget->next;
    if (removeTarget == pReadyList->tail) {
     pReadyList->tail = preTemp;
    }
    
    printf("Process %d:%s has been removed./n", removeTarget->id, removeTarget->name);
    fprintf(log, "/nProcess %d:%s has been removed./n", removeTarget->id, removeTarget->name);
    
    TerminateThread(removeTarget->hThis, 0);
    returnPcbToFreeList(removeTarget);
    pReadyList->pcbNum--;

    fprintf(log, "Current ReadyList is:/n");
    fprintReadyList();
    fflush(log);

    //
    LeaveCriticalSection(&cs_ReadyList);
    //
    return;
   } else if (removeTarget != pReadyList->head) {
    preTemp = preTemp->next;
   }
  }
 }
 
 printf("Sorry, there's no process named %s/n", name);
 //
 LeaveCriticalSection(&cs_ReadyList);
 //
 return;
}

void fprintReadyList() {
 pPCB tmp = NULL;
 tmp = pReadyList->head;
 if (tmp != NULL) {
  for (int i = 0; i < pReadyList->pcbNum; i++) {
   fprintf(log, "--%d:%s--", tmp->id, tmp->name);
   tmp = tmp->next;
  }
 } else {
  fprintf(log, "NULL");
 }
 fprintf(log, "/n/n");
}

void printReadyList() {
 pPCB tmp = NULL;
 tmp = pReadyList->head;
 if (tmp != NULL) {
  for (int i = 0; i < pReadyList->pcbNum; i++) {
   printf("--%d:%s--", tmp->id, tmp->name);
   tmp = tmp->next;
  }
 } else {
  printf("NULL");
 }
 printf("/n/n");
}

void printCurrent() {
 if (runPCB != NULL) {
  printf("Process %s is running.../n", runPCB->name);
 } else {
  printf("No process is running./n");
 }
 printf("Current readyList is:/n");
 printReadyList();
}

main.cpp

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

#include <windows.h>

#include "pcb.h"
#include "funCode.h"

FILE *log;
int PC = 0;

extern applyQueue* queue;

void helpInfo() {
 printf("/n************************************************/n");
 printf("COMMAND LIST:/n");
 printf("create process_name process_length (create p0 8)/n"
  "/t append a process to the process list/n");
 printf("remove process_name (remove p0)/n"
  "/t remove a process from the process list/n");
 printf("current/t show current runProcess readyList/n");
 printf("exit/t exit this simulation/n");
 printf("help/t get command imformation/n");
 printf("************************************************/n/n");
}

main() {
 queue->head = NULL;
 queue->tail = NULL;
 queue->applyNum = 0;

 log = fopen("Process_log.txt", "w");
 funsInitial();

 helpInfo();
 init();

 char command[20] = {0};
 while (strcmp(command, "exit") != 0) {
  printf("COMMAND>");
  scanf("%s", command);
  
  if (strcmp(command, "exit") == 0) {
   break;
  }else if (strcmp(command, "create") == 0) {
   char name[20] = {'/0'};
   int time = 0;
   scanf("%s %d", name, &time);

   addApplyProcess(name, time);
  } else if (strcmp(command, "remove") == 0) {
   char name[20] = {'/0'};
   scanf("%s", name);
   
   removeProcess(name);
  } else if (strcmp(command, "current") == 0) {
   printCurrent();
  } else if (strcmp(command, "help") == 0) {
   helpInfo();
  } else {
   printf("Enter help to get command information!/n");
  }
 }

 fclose(log);

 return 0;
}

 

 

 

标签：

相关文章