进程管理模拟实验.doc

 进程管理

一、目的与要求
1．目的
    进程是操作系统最重要的概念之一，是了解操作系统实质的关键。本课题实习的目的是，加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构、通讯机构的实施。

2．要求
   要求设计一个允许n个进程并发运行的进程管理模拟系统。该系统包括以下内容：（1）简单的进程控制 （2）同步及通讯机构 （3）中断机构 （4）进程调度。其进程调度算法可任意选择。每个进程用一个PCB表示，其内容可根据具体情况设置。各进程之间有一定的同步关系。系统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及系统的管理过程。

二、范例
1．题目        支持多个进程并发运行的简单进程管理模拟系统

    本系统的同步机构采用信号量上的P、V操作的机制；控制机构包括阻塞和唤醒操作；时间片中断处理程序模拟时间片中断；进程调度程序负责为各进程分配处理机。系统中涉及了3个并发进程。它们之间的关系是：3个进程需要互斥使用临界资源S2，进程1和进程2又需互斥使用临界资源S1．本系统在运行过程中随机打印出各进程的状态变换过程，系统的调度过程及公共变量的变化情况。

2．算法与N～S图
    系统为进程设置了5种运行状态：e—执行态；r—高就绪态；t—低就绪态（执行进程因时间片到限而转入）；w—等待态；c—完成态。各进程的初始状态均设置为r.
    系统分时执行各进程，并规定3个进程的执行概率均为33％。通过产生随机数x来模拟时间片。当进程process1访问随机数x时，若x>=0.33；当进程process2访问x时，若x<0.33或x>=0.66;当进程process3访问x时，若x<0.66，则分别认为各进程的执行时间片到限，产生“时间片中断”而转入低就绪态t。
    进程调度算法采用剥夺式最高优先数法。各进程的优先数通过键盘输入予以静态设置。调度程序每次总是选择优先数最小（优先权最高）的就绪进程投入执行。先从r状态进程中选择，再从t状态进程中选择。当现行进程唤醒某个等待进程，且被唤醒进程的优先数小于现行进程时，则剥夺现行进程的执行权。
    各进程在使用临界资源S1和S2时，通过调用信号量sem1和sem2上的P、V操作来实现同步。阻塞和唤醒操作负责完成从进程的执行态到等待态以及从等待态到就绪态的转换。
    系统启动后，在完成必要的系统初始化后便执行进程调度程序。当执行进程因“时间片中断”，或被排斥使用临界资源，或唤醒某个进程时，立即进行进程调度。当3个进程都处于完成状态后，系统退出运行。

N-S图在此显示不出。

  3．数据结构
 （1）每个进程有一个进程控制块PCB，内容包括：
       id    进程标识数，id＝0，1，2；
       status     进程状可为e，r，t，w，c；
       priority  进程优先数；
       nextwr  等待链指针，指示在同一信号量上等待的下一个进程的标识数。
  （2）信号量semaphore，对应于临界资源S1和S2分别有sem1和sem2，均为互斥信号量，内容包括：
        value     信号量，初值为1；
        firstwr     等待链首指针，指示在同一信号量上等待的下一个进程的标识数。
   （3）现场保留区，在PCB中模拟，用inum，addr分别模拟通用寄存器和PC的内容。
( 4) 进程通信机构，在PCB中模拟，用mess变量模拟用于接收其它进程所发送消息的信箱。
此外，系统中还用到下列主要全程变量：
      exe   执行进程指针，其值为进程标识数；
       i      用来模拟一个通用寄存器；
     addr    用来模拟程序计数器；
     s1,s2   两个公共变量，用作共享临界资源。
4．程序及运行结果
 program processc(input,output);
const MAXPRI=100;
      NIL=-1;

TYPE
      message=^messagetp;
      procb=record
           id:integer;
           status:char;
           nextwr:integer;
           priority:integer;
           mess:message;
            inum:integer;
            addr:char;
           end;
      messagetp=record
           num:integer;
           next:message;
           pro:integer;
      end;
      semaphorel=record
           value:integer;
           firstwr:integer;
               end;
var
      pcb:array[1..3] of procb;
      sem:array[1..2] of semaphorel;
      addr:char;
      i,seed,exe:integer;
      style:integer;

procedure send (sender, receiver, snum:integer);
Var q,p:message;
begin
      new(p);
      p^.num:=snum;
      p^.next:=NIL;
      p^.pro:=sender;
      writeln('send message to process  ',receiver);
      writeln('process ',sender,' already run   ',snum,'   times');
      q:=pcb[receiver].mess;
      if(q=NIL) then pcb[receiver].mess:=p
        else begin
              while(q^.next<>NIL) do
                    q:=q^.next;
             q^.next:=p;
             end
end;

procedure   receive(receiver:integer);
      var p:message;
begin
      p:=pcb[receiver].mess;
      if (p<>NIL) then
                     while(p<>NIL) do
                         begin
                            writeln;
                            writeln('receive massage form process ',p^.pro);
                            writeln('process  ',p^.pro,' is already run ',p^.num,'  time');
                            writeln;
                            p:=p^.next;
                         end;
      pcb[receiver].mess:=NIL;
end;

PROCEDURE init;
          VAR
             j:integer;
          begin
               for j:=1 to 3 do
                   begin
                        pcb[j].id:=j;
                        pcb[j].status:='r';
                        pcb[j].nextwr:=NLL;
                        write('process',j,' priority?');
                        readln(i);
                        pcb[j].priority:=i;
                        pcb[j].mess:=NIL;
                        pcb[j].inum:=0;
                        pcb[j].addr:='0';
                    end;
                    sem[1].value:=1;
                    sem[1].firstwr:=NLL;
                    sem[2].value:=1;
                    sem[2].firstwr:=NLL;
                    exe:=NLL
           end;

FUNCTION random:real;
         VAR
            m:integer;
         begin
              if seed<0 then m:=-seed
              else m:=seed;
              seed:=(25173*seed+13849) mod 65536;
              random:=m/32767.0
         end;

FUNCTION find:integer;
         VAR
            j,pd,w:integer;
         begin
              pd:=NLL;  w:=MAXPRI;
              for j:=1 to 3 do
                  if pcb[j].status='r' then
                     if pcb[j].priority<w then
                        begin w:=pcb[j].priority; pd:=j end;
              if pd=NLL then
              for j:=1 to 3 do
                  if pcb[j].status='t' then
                     if pcb[j].priority<w then
                        begin w:=pcb[j].priority; pd:=j end;
              find:=pd
         end;

FUNCTION scheduler:integer;
         VAR
            pd:integer;
         begin
              pd:=find;
              if( (pd=NLL) and (exe=NLL)) then scheduler:=NLL
              else begin
                        if pd<>NLL then
                           begin
                                if exe=NLL then
                                   begin
                                        pcb[pd].status:='e';
                                        exe:=pd;
                                        writeln('process',exe,' is executing.');
                                   end
                                else if pcb[pd].priority<pcb[exe].priority then
                                        begin
                                             pcb[exe].status:='r';
                                             writeln('process',exe,' enter into ready.');
                                             pcb[pd].status:='e';
                                             exe:=pd;
                                             writeln('process',exe,'is executing.');
                                        end
                           end;
                        i:=pcb[exe].inum;
                        addr:=pcb[exe].addr;
                        scheduler:=exe
                  end
         end;

PROCEDURE block(se:integer);
          VAR
             w:integer;
          begin
               writeln('process',exe,' is blocked');
               pcb[exe].status:='w';
               pcb[exe].nextwr:=NLL;
               w:=sem[se].firstwr;
               if (w=NLL) then
                  sem[se].firstwr:=exe
               else begin
                         while (pcb[w].nextwr<>NLL) do
                               w:=pcb[w].nextwr;
                               pcb[w].nextwr:=exe
                    end
          end;

FUNCTION p(se:integer;ad:char):boolean;
         begin
              sem[se].value:=sem[se].value-1;
              if sem[se].value>=0 then p:=false
              else begin
                        block(se);
                        pcb[exe].inum:=i;
                        pcb[exe].addr:=ad;
                        exe:=NLL;
                        p:=true
                    end
         end;

PROCEDURE wakeup(se:integer);
          VAR
             w:integer;
          begin
               w:=sem[se].firstwr;
               if w<>NLL then
                  begin
                       sem[se].firstwr:=pcb[w].nextwr;
                       pcb[w].status:='r';
                       writeln('process',w,' is waken up')
                  end
          end;

FUNCTION v(se:integer;ad:char):boolean;
         begin
              sem[se].value:=sem[se].value+1;
              if sem[se].value>0 then v:=false
              else begin
                        wakeup(se);
                        pcb[exe].inum:=i;
                        pcb[exe].addr:=ad;
                        v:=true
                    end
         end;

FUNCTION timeint(ad:char):boolean;
        var x:real;
        begin
             x:=random;
             if((x<0.33) and (exe=1)) then timeint:=false
             else if((x<0.66) and (exe=2)) then timeint:=false
             else if((x<1.00) and (exe=3)) then timeint:=false
             else begin
                      pcb[exe].inum:=i;
                      pcb[exe].addr:=ad;
                      pcb[exe].status:='t';
                      writeln('Times silce interrupt.');
                      writeln('process',exe,' enter into ready.');
                      exe:=NLL;
                      timeint:=true
                  end
         end;

procedure eexit(n:integer);
begin
    pcb[n].status:='c';
    writeln('process',n,' is completed !');
    exe:=NLL;
end;

procedure process1(var s1,s2:integer);
label a1,b1,c1,d1,e1,f1,stop1,end1;
begin
   if(addr='a') then goto a1;
   if(addr='b') then goto b1;
   if(addr='c') then goto c1;
   if(addr='d') then goto d1;
   if(addr='e') then goto e1;
   if(addr='f') then goto f1;
   while(i<5) do
      begin
           receive(1);
           writeln('process1 calls P on semaphore1.');
           if(p(1,'a')) then goto stop1;
      a1:  writeln('process1 is executing on its cretical section1.');
           if(timeint('b')) then goto stop1;
      b1:
           s1:=s1+1;
           writeln('s1=',s1);
           writeln('process1 calls V on semaphore1 and quit cretical setion1.');
           if(v(1,'c')) then goto stop1;
      c1:  writeln('process1 calls P on semaphore2.');
           if(p(2,'d')) then goto stop1;
      d1:  writeln('process1 is execting cretical section2.');
           if(timeint('e')) then goto stop1;
      e1:
           s2:=s2+1;
           writeln('s2=',s2);
           writeln('process1 calls V on semaphore2 and quit cretical section2.');
           if(v(2,'f')) then goto stop1;
      f1:  writeln('process 1 cyclen count=',i+1);
           i:=i+1; send(1,2,i);send(1,3,i);readln;
      end;
stop1:  if(i<5) then goto end1;
       eexit(1);
end1:
end;

procedure process2(var s1,s2:integer);
label a2,b2,c2,d2,e2,f2,stop2,end2;
begin
   if(addr='a') then goto a2;
   if(addr='b') then goto b2;
   if(addr='c') then goto c2;
   if(addr='d') then goto d2;
   if(addr='e') then goto e2;
   if(addr='f') then goto f2;
    while(i<5) do
      begin
           receive(2);
           writeln('process2 calls P on semaphore2.');
           if(p(2,'a')) then goto stop2;
      a2:  writeln('process2 is executing on its cretical section2.');
           if(timeint('b')) then goto stop2;
      b2:
           s2:=s2+1;
           writeln('s2=',s2);
           writeln('process2 calls V on semaphore2 and quit cretical setion2.');
           if(v(2,'c')) then goto stop2;
      c2:  writeln('process2 calls P on semaphore1.');
           if(p(1,'d')) then goto stop2;
      d2:  writeln('process2 is execting cretical section1.');
           if(timeint('e')) then goto stop2;
      e2:
           s1:=s1+1;
           writeln('s1=',s1);
           writeln('process2 calls V on semaphore1 and quit cretical section1.');
           if(v(1,'f')) then goto stop2;
      f2:  writeln('process 2 cyclen count=',i+1);
           i:=i+1;send(2,1,i);send(2,3,i);readln;
      end;
stop2:  if(i<5) then goto end2;
       eexit(2);
end2:
end;

procedure process3(var s1,s2:integer);
label a3,b3,c3,stop3,end3;
begin
   if(addr='a') then goto a3;
   if(addr='b') then goto b3;
   if(addr='c') then goto c3;
   while(i<5) do
      begin
           receive(3);
           writeln('process3 calls P on semaphore2.');
           if(p(2,'a')) then goto stop3;
      a3:  writeln('process3 is executing on its cretical section2.');
           if(timeint('b')) then goto stop3;
      b3:
           s2:=s2+1;
           writeln('s2=',s2);
           writeln('process3 calls V on semaphore2 and quit cretical setion2.');
           if(v(2,'c')) then goto stop3;
      c3:  writeln('process 3 cyclen count=',i+1);
           i:=i+1;send(3,1,i);send(3,2,i);readln;
      end;
stop3:  if(i<5) then goto end3;
       eexit(3);
end3:
end;

procedure main;
var k:integer;
    s1,s2:integer;
label 100;
begin
    writeln('                     C . O . S   Example  one');
    writeln;
    init;
    s1:=0;s2:=0;
    writeln('s1=',s1,',s2=',s2);
    writeln('process1,process2,process3 are all in ready!');
100:k:=scheduler;
    if(k<>NLL)  then
      case k of
           1: begin process1(s1,s2);
                    goto 100;
              end;
           2: begin process2(s1,s2);
                    goto 100;
              end;
           3: begin process3(s1,s2);
                    goto 100;
              end;
          else writeln('process identifer error.');
      end;
   writeln;writeln;
   writeln('s1=',s1,',s2=',s2);
   writeln;
   writeln('               COMPLETED!');
   readln;
end;

begin
    main
end.

程序运行结果如下：
                     C . O . S   Example  one

process1 priority? 1
process2 priority? 2
process3 priority? 3
s1=0,s2=0
process1,process2,process3 are all in ready!
process1 is executing.
process1 calls P on semaphore1.
process1 is executing on its cretical section1.
s1=1
process1 calls V on semaphore1 and quit cretical setion1.
process1 calls P on semaphore2.
process1 is execting cretical section2.
s2=1
process1 calls V on semaphore2 and quit cretical section2.
process 1 cyclen count=1
send message to process  2
process 1 already run   1   times
send message to process  3
process 1 already run   1   times
process1 calls P on semaphore1.
process1 is executing on its cretical section1.
s1=2
process1 calls V on semaphore1 and quit cretical setion1.
process1 calls P on semaphore2.
process1 is execting cretical section2.
s2=2
process1 calls V on semaphore2 and quit cretical section2.
process 1 cyclen count=2
send message to process  2
process 1 already run   2   times
send message to process  3
process 1 already run   2   times
process1 calls P on semaphore1.
process1 is executing on its cretical section1.
s1=3
process1 calls V on semaphore1 and quit cretical setion1.
process1 calls P on semaphore2.
process1 is execting cretical section2.
Times silce interrupt.
process1 enter into ready.
process2 is executing.

receive massage form process 1
process  1 is already run 1  time

          ·       
          ·
          ·
process1 enter into ready.
process2 is executing.
process2 is executing on its cretical section2.
s2=4
process2 calls V on semaphore2 and quit cretical setion2.
process3 is waken up
process2 calls P on semaphore1.
process2 is blocked
process3 is executing.
process3 is executing on its cretical section2.
s2=5
process