Linux 版 (精华区)

发信人: netiscpu (夜☆星光点点☆), 信区: Linux
标  题: NACHOS论坛(2)
发信站: 紫 丁 香 (Sun Nov  8 17:26:03 1998), 转信


寄信人: ship.bbs@bbs.xmu.edu.cn 
标  题: NACHOS论坛(2)(转寄)
发信站: 华南理工大学 BBS木棉站
日  期: Sun Mar  9 15:00:19 1997

作  家: solmon (所罗门王) on board 'Unix'
题  目: NACHOS论坛(2)
来  源:  鼓浪听涛站
日  期: Thu Mar  6 23:03:35 1997
出  处: mysu@JingXian.xmu.edu.cn

          第二章    进程管理


    在Nachos的教程里,第一个课程作业是进程管理,它将介绍进程的概念和并发性问
题.Nachos的设计者提供了一套基本的进程管理系统和一个信号量的实现.让学生们做
的课程作业是用信号量实现锁和状态变量.然后利用这些同步原语解决一些并发性问
题.例如实现一个简单的生产者-消费者问题,在实现中使用条件变量来表示缓冲区空
和缓冲区满两个状态.
   对于那些刚刚学习编程的学生来说,理解并发性需要一个概念上的飞跃.Nachos的设
计者认为,教授并发性的最好方法是让学生们能够直观地看到程序的并发行为,只有这
样,学生们才能学会实现并发性程序的正确方法.这一章的设计正体现了这个思想.

    Nachos中的进程管理有很多优点,学生们可以一条指令一条指令地跟踪进程切换的
过程,既可以从外界观察者的角度,也可以从相关进程的角度观察,在一个进程切换到另
一个进程的过程中发生了什么事情.Nachos的设计者相信,这个经历对帮助学生们解开
并发之谜是至关重要的.其次,Nachos是一个可以工作的进程系统,可以让学生们在它上
面编写并发性程序,并测试这些程序.在测试的过程中,学生们将发现许多过去没有注意
到的问题.事实证明,即使是有丰富经验的程序员也觉得考虑并发性问题是很困难的.在
一本广泛使用的操作系统教科书上,一个并发算法中就有一个错误,这个错误直到几年
后才被发现.在Nachos的早期版本中,进程管理系统忽略了许多实际的问题,设计者以为
学生们在课程的以后部分将学习到足够多的并发程序例子,他们会注意到这些实际的问
题的,但是许多学生到了课程的最后阶段还犯并发方面的错误,所以现在的版本增加了许
多实际问题的处理.

    Nachos是一个多进程的操作系统,每个进程占用的处理机是Nachos宿主机的CPU而不
是机器模拟部分模拟的CPU,也就是说Nachos实现的是真正的多进程系统,而不是只模拟
用户的多进程.Nachos的每一个进程都有自己的堆栈,运行状态,还有一块内存用于保存
进程放弃CPU时的寄存器内容.进程的状态有运行态,就绪态,阻塞态三种.进程的代码段
和数据段是共享的,都用Nachos的代码段和数据段.用户程序的多进程是用Nachos内部
的多个用户程序解释进程实现的.当用户程序要求生成一个新进程时,Nachos内核产生
一个新进程,这个进程给用户程序分配内存空间,并把用户程序的代码段和数据段装入
用户地址空间,然后解释执行用户程序.所以用户程序解释进程还有自己的用户地址空间
和用户寄存器.这些进程在正文切换的时候还要保存或恢复用户地址空间和用户寄存器.
   Nachos为进程提供的功能有:
          1.生成一个进程(Fork),
          2.使进程睡眠等待(Sleep),
          3.结束进程(Finish),
          4.设置进程状态(setStatus),
          5.放弃处理机(Yield).
    进程系统的结构如图:

              ┏━━━━━━━━━━━━━━━━━━━┓
              ┃         用    户    程     序        ┃
              ┣━━━━┳━━━━━┳━━━┓        ┃
              ┃ 信号量 ┃ 条件变量 ┃  锁  ┃        ┃
              ┣━━━━┻━━━━━┻━━━┻━━━━┫
              ┃            Thread   类               ┃
              ┣━━━━━━┳━━━━━━┳━━━━━┫
              ┃ 模拟中断   ┃   正文切换 ┃ 进程调度 ┃
              ┃   模块     ┃     模块   ┃   模块   ┃
              ┗━━━━━━┻━━━━━━┻━━━━━┛


    我们从下向上介绍进程系统的各个模块.模拟中断模块在机器模拟部分已作了介绍.
正文切换模块中有两个与机器相关的正文切换函数,学生不能改变这个模块.正文切换
过程依赖于具体的机器,这是因为正文切换过程中的寄存器保护,建立初始调用框架等
等操作对不同的处理机结构都是不一样的.Nachos分别为 DEC MIPS, SUN SPARC, HP
PA-RISC, Intel 386 实现了正文切换函数.一个正文切换函数是
ThreadRoot(int InitialPC, int InitialArg, int WhenDonePC, int StartupPC).
其中 InitialPC 指明这个进程要执行的函数的入口地址,InitialArg是InitialPC的参
数,StartupPC 是进程首次占用处理机时立即执行的函数地址,WhenDonePC 是进程最后
结束时执行的函数的地址,ThreadRoot函数是用汇编语言编写的,它的执行过程是:
          1.将栈顶寄存器压入堆栈.
          2.调用 StartupPC 函数.
          3.调用 InitialPC  函数.
          4.调用 WhenDonePC 函数.
          5.恢复栈顶寄存器.
    事实上执行 WhenDonePC函数过程中,此进程就放弃了处理机,由其他进程将它所占
的内存空间释放,此进程将不再运行.从ThreadRoot函数的执行过程可以看出它才是进
程运行的全过程.
    正文切换中用到的另一个函数是SWITCH(Thread* oldThread,Thread*newThread),
oldThread指向正在运行的进程对象,newThread指向将要运行的进程对象,在Thread对
象中有一块内存用来放本进程的CPU寄存器的内容,SWITCH函数先将宿主机的CPU寄存器
的内容保存到oldThread对象中,再从newThread对象中恢复除指令寄存器(PC)以外的所
有寄存器的内容,由于栈基址和栈顶寄存器的内容变为新进程的值,所以程序将在新进
程的堆栈上运行,当SWITCH函数结束返回时,会从新进程的堆栈中取出返回地址,这个地
址是新进程的断点而不是老进程的断点,所以CPU将执行新进程的代码,由此实现新老进
程的正文切换.因为SWITCH需要存取CPU寄存器,并且与具体机器有关,所以它用汇编语
言写成.
    Scheduler类用于实现进程的调度.它的类界面如图所示:

                  ┏━━━━━━━━━━━┓
                  ┃    Scheduler         ┃
                  ┣━━━━━━━━━━━┫
                  ┃   ReadyToRun         ┃
                  ┃   FindNextToRun      ┃
                  ┃   Run                ┃
                  ┗━━━━━━━━━━━┛

    Schedule类维护一个就绪进程队列,当一个进程可以占用处理机时,就可以调用
ReadyToRun成员函数把这个进程放入就绪进程队列,并把进程状态改成就绪态.
    FindNextToRun函数根据调度策略,取出下一个应运行的进程,并把这个进程从就绪
进程队列中删除.如果就绪进程队列为空,则此函数返回空(NULL).现有的调度策略是先
进先出策略(FIFO),在课程中将要求学生们实现其他的调度策略.
    Run函数用来调用另一个进程占用CPU.它的实现过程是:
          1.如果当前进程(由currentThread指明)是用户进程,
            则保存用户程序状态和用户空间的状态.
          2.将新进程的地址赋给currentThread变量,表明当前进程变为新进程了.
          3.将新进程的状态改为运行态.
          4.调用SWITCH函数切换进程正文.
          5.查看有没有已经结束但没有删除的进程,如果有,则将其删除.
          6.如果新进程是用户进程,则恢复用户程序状态和用户空间的状态.
    当老进程是因为结束而放弃CPU,我们要把它所占的内存释放,那么在什么时候删除
它呢?这里有个时机问题.我们只能在第五步上删除,在此之前是不行的.因为在此之前,
程序还运行在老进程的堆栈上,如果过早删除老进程,它的堆栈也被删掉了.造成内存出
错.
    Thread类的对象既用作进程的控制块,保存进程状态和CPU寄存器内容,又是用户调
用进程系统的界面.
    用户生成一个新进程的方法是:

    /* 生成一个进程类*/
    Thread* newThread = new Thread("New Thread");
    /*定义新进程的执行函数及其参数*/
    newThread->Fork(ThreadFunc,ThreadFuncArg);


    Fork函数分配一块固定大小的内存作为进程的堆栈,在栈顶放入ThreadRoot的地
址.当新进程被调上CPU时,要用SWITCH函数切换进程图像,SWITCH函数返回时,会从栈
顶取出返回地址,所以将ThreadRoot放在栈顶,SWITCH结束后就会执行ThreadRoot函数
了.
    ThreadRoot函数在前面已作了介绍,它是进程完整的执行过程.它的InitialPC及
InitialArg参数传的是Fork的两个参数;StartupPC参数传的是一个开中断函数,它将
在进程首次占用处理机时立即执行;WhenDonePC参数传的是Thread类的Finish成员函
数,它将在进程的工作函数执行完毕后运行,作一些收尾工作.它的执行过程是:
          1.关闭中断.
          2.将当前进程赋给全局变量threadToBeDestroyed,
            以便在它让出CPU后,在SWITCH函数中将它删除.
          3.调用Sleep函数睡眠等待.实际上进程在睡眠等待的时候就被删除了,
            所以它不会从Sleep函数中返回的.

    Yield函数用于本进程放弃处理机.它的执行过程是:

                      ┏━━━━━━━━┓
                      ┃ 关闭中断并记住 ┃
                      ┃ 原来的中断状态 ┃
                      ┗━━━┳━━━━┛
                              ┃
                              ↓
                       ━━━━━━━━━        Y
                         进程就绪队列         ━━━┓
                             为空?                  ┃
                       ━━━━━━━━━           ┃
                              ┃                    ┃
                              ┃N                   ┃
                              ↓                    ┃
                      ┏━━━━━━━━┓          ┃
                      ┃  取出就绪进程  ┃          ┃
                      ┗━━━┳━━━━┛          ┃
                              ↓                    ┃
                      ┏━━━━━━━━┓          ┃
                      ┃  将本进程放入  ┃          ┃
                      ┃    就绪队列    ┃          ┃
                      ┗━━━┳━━━━┛          ┃
                              ↓                    ┃
                      ┏━━━━━━━━┓          ┃
                      ┃  运行取出的    ┃          ┃
                      ┃   就绪进程     ┃          ┃
                      ┗━━━┳━━━━┛          ┃
                              ┃←━━━━━━━━━┛
                              ↓
                      ┏━━━━━━━━┓
                      ┃  恢复中断状态  ┃
                      ┗━━━┳━━━━┛
                              ↓

    Sleep函数可以使当前进程转入阻塞态,并放弃CPU,直到被另一个进程唤醒,把它放
回就绪进程队列.Sleep函数的执行过程是:

                      ┏━━━━━━━━┓
                      ┃  当前进程状态  ┃
                      ┃   设为阻塞态   ┃
                      ┗━━━┳━━━━┛
              ┏━━━━━━→┃
              ┃              ↓
              ┃       ━━━━━━━━━        N
              ┃          就绪进程队列        ━━━━┓
              ┃              为空                    ┃
              ┃       ━━━━━━━━━             ┃
              ┃              ┃ Y                    ┃
              ┃              ↓                      ┃
              ┃      ┏━━━━━━━━┓            ┃
              ┃      ┃  机器时钟前进  ┃            ┃
              ┃      ┃    直到一个    ┃            ┃
              ┃      ┃    中断发生    ┃            ┃
              ┃      ┗━━━┳━━━━┛            ┃
              ┃              ┃                      ┃
              ┗━━━━━━━┛                      ┃
                              ┏━━━━━━━━━━━┛
                              ↓
                      ┏━━━━━━━━┓
                      ┃  取出就绪进程  ┃
                      ┗━━━┳━━━━┛
                              ↓
                      ┏━━━━━━━━┓
                      ┃  运行取出的    ┃
                      ┃   就绪进程     ┃
                      ┗━━━┳━━━━┛
                              ↓

    在没有就绪进程时,就把时钟前进到一个中断发生的时刻,让中断发生,这是因为在
没有进程占用CPU时,只有中断处理程序可能唤醒一个进程,并把它放入就绪进程队列.

    进程要等到本进程被唤醒后,并且又被进程调度模块调上CPU时,才会从Sleep函数
返回.有趣的是,新取出的就绪进程有可能就是这个要睡眠的进程.例如,如果系统中只
有一个A进程,A进程在读磁盘的时候会进入睡眠,等待磁盘操作完成.因为这时只有一个
进程,所以A进程不会被调下CPU,只授循环语句中等待中断.当磁盘操作完成时,磁盘会
发出一个磁盘读操作中断,此中断将唤醒A进程,把它放入就绪队列.这样,当A进程跳出
循环时,取出的就绪进程就是自己.这就要求进程的正文切换程序可以将一个进程切换
到自己,经分析,Nachos的进程正文切换程序SWITCH可以做到这一点,于是A进程实际上
并没有被调下CPU,而是继续运行下去了.


--
m※ 来源:．鼓浪听涛站 bbs.xmu.edu.cn．[FROM: mysu@JingXian.xmu.ed] m
--
m;32m※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: mtlab.hit.edu.cn]
--

                              Enjoy Linux!
                          -----It's FREE!-----

※ 来源:．紫 丁 香 bbs.hit.edu.cn．[FROM: mtlab.hit.edu.cn]