第一章   机器模拟

    Nachos是建立在一个软件模拟的虚拟机上的.这个虚拟机包括计算机的基本部分,
如CPU,主存,中断系统,还有一些外部设备,如键盘,显示器,网络,以及磁盘系统.现代
许多操作系统都是先在用软件模拟的硬件上建立并调试,最后才在真正的硬件上运行.
这样做便于调试程序.因为软件模拟的硬件可靠性比真实的硬件高的多,不会因为硬件
故障而导致系统出错.模拟的硬件还可以监视程序对硬件的操作,严格限制程序对硬件
的操作,并在程序误操作时报告详尽的出错信息.这些都是真实硬件难以做到的.
    Nachos用软件来模拟硬件还可以充分利用现有的软件资源,避免了编写复杂的硬件
控制程序.更重要的是可以提高程序的可移植性,只要在不同硬件上实现这个虚拟机器
就完成了大部分移植工作.我们移植Nachos的工作就受益于这种设计.
    下面就介绍Nachos的机器模拟的细节.
    Machine类用来模拟计算机主机.它提供的功能有:读写寄存器,读写主存,运行一条
用户程序的汇编指令,运行用户程序,单步调试用户程序,显示主存和寄存器状态,将虚拟
内存地址转换为物理内存地址,陷入Nachos内核等等.

    Machine类实现方法是分配两块内存分别作为虚拟机的寄存器和物理内存.运行用户
程序时,先将用户程序从Nachos文件系统中读出,然后调用指令模拟模块对每一条用户指
令解释执行.对用户程序的读写内存要求,将调用虚拟内存模块提供的功能把它转变为对
物理内存地址的读写.当用户要求调试程序时,执行一条指令后会自动停下来,让用户查
看系统状态.如果用户程序想使用操作系统提供的功能或者发出异常信号时,Machine调
用系统陷入功能,进入Nachos的核心部分.
    从Machine类的功能可以看出,它是用户和操作系统的界面,用户的各种操作都通过
它去调用相应的Nachos模块,也可以说Machine类是Nachos的总控部分.

    Interrupt类用来模拟硬件中断系统.在这个中断系统中,中断状态有开,关两种,中
断类型有时钟中断,磁盘中断,控制台写中断,控制台读中断,网络发送中断,网络接收中
断.机器状态有用户态,核心态和空闲态.中断系统提供的功能有开/关中断,读/写机器状
态,将一个即将发生中断放入中断队列,以及使机器时钟前进一步.
    在Interrupt类中有一个记录即将发生中断的队列,这个队列的元素中包括的信息有:
中断类型, 中断处理程序的地址及参数,中断应当发生的时间.一般是由硬件设备模拟程
序把将要发生的中断放入中断队列.中断系统提供了一个模拟的机器时钟,机器时钟在下
列情况前进一步:
        1.用户程序打开中断
        2.执行一条用户指令
        3.没有进程占用处理机
机器时钟前进时,处理的过程如下图:

                                  ┃
                                  ↓
                      ┏━━━━━━━━━━━┓
                      ┃       关闭中断       ?
                      ┗━━━━━━━━━━━┛
                                  ┃
        ┏━━━━━━━━━━━→↓
        ┃                 ━━━━━━━━━
        ┃                    中断队列中有       ━━━━━━━┓
        ┃                    应当发生的中断                   ┃
        ┃                 ━━━━━━━━━                  ┃
        ┃                        ┃                           ┃
        ┃                        ┃Y                          ┃
        ┃                        ↓                           ┃
        ┃          ┏━━━━━━━━━━━━━━━┓         ┃
        ┃          ┃取出队列中一个应当发生的中断, ┃         ┃
        ┃          ┃调用这个中断的处理程序去处理  ┃         ┃
        ┃          ┃          中断                ┃         ┃
        ┃          ┗━━━━━━━━━━━━━━━┛         ┃
        ┃                        ┃                           ┃
        ┃                        ┃                           ┃
        ┗━━━━━━━━━━━━┛                           ┃
                                                               ┃
                                   ┏━━━━━━━━━━━━━┛
                                   ┃
                                   ↓
                       ┏━━━━━━━━━━━┓
                       ┃      打开中断        ┃
                       ┗━━━━━━━━━━━┛
                                   ┃
                                   ┃
                                   ↓
                         ━━━━━━━━━━━━       N
                              中断的处理程序          ━━━┓
                             要求进行正文切换               ┃
                         ━━━━━━━━━━━━           ┃
                                   ┃                       ┃
                                   ┃Y                      ┃
                                   ↓                       ┃
                        ┏━━━━━━━━━━━┓          ┃
                        ┃    进行正文切换      ┃          ┃
                        ┗━━━━━━━━━━━┛          ┃
                                   ┃                       ┃
                                   ┃                       ┃
                                   ┃ ←━━━━━━━━━━┛
                                   ↓

    由此可见,在Nachos中,即使打开了中断,中断也不能在任意时刻发生.只有在模拟时
钟前进的时候才能处理等待着的中断,也就是说,在执行非用户代码的大部分时间里,系
统不会被中断.这意味着不正确的同步代码可能在这个硬件模拟环境下工作正常,而在真
正的硬件上无法运行.
    中断处理程序可以调用Interrupt类的一个成员函数来要求时钟前进的时候进行正
文切换.中断系统还提供关机的功能,关机后Nachos就结束了.
    在这个中断系统基础上,Nachos模拟了各种硬件设备,这些设备都是异步设备,依靠
中断来与主机通信.

    Timer类模拟的是定时器.定时器每隔X个时钟周期就向CPU发一个时钟中断.它是时
间片管理必不可少的硬件基础.它的实现方法是将一个即将发生的时钟中断放入中断队
列,到了时钟中断应发生的时候,中断系统将处理这个中断,在中断处理的过程中又将一
个即将发生的时钟中断放入中断队列,这样每隔X个时钟周期,就有一个时钟中断发生.在
计算下一个时钟中断应发生的时间时,Nachos还加入了一些随机值,使得中断发生的时间
间隔不确定,这样就与现实的定时器更相似了.

    Nachos还模拟了控制台设备.当用户向控制台写一个字符时,写程序立即返回,过了
给定的时钟周期后I/O操作完成,控制台向CPU发一个写中断.此外,控制台每隔给定的时
钟周期向CPU发一个读中断,周期性地发中断的方法与定时器的类似,即先计算下一个中
断将发生的时间,然后将中断放入中断队列,等待中断的发生.中断发生后,读中断处理过
程将控制台输入的字符放入字符缓冲区.当用户从控制台读字符时,把字符缓冲区的内容
传给用户.控制台的读/写分别用两个文件来模拟.

    Nachos模拟了物理磁盘,它一次只能接受一个读写请求,当读写操作完成后向CPU发
一个磁盘中断.这个磁盘只有一个面,分为几个磁道,每道又分为几个扇区.每道的扇区
数,每个扇区的存储容量都是固定的.磁盘的使用者可以读写指定的扇区,读写单位是一
个扇区.模拟磁盘用一个文件来实现,当用户发出读写请求时,Nachos的处理过程如下:
          1.从模拟文件中读出数据或向模拟文件写入数据.
          2.计算磁盘操作需要的时间.磁盘操作时间 = 移动磁头寻道的时间 +
                旋转到读写扇区的时间 + 数据传送的时间.
          3.将一个磁盘读写中断放入中断队列,因为中断是在操作完成后发生的,所
                以.中断发生时间 = 当前时间 + 磁盘操作时间

    Network类模拟了一个网络节点.这个网络节点可以把报文发送到网络的其他节点
上.报文的长度固定,还可以模拟在现实网络中时常发生的报文丢失.不过一旦报文收到
了,里面的内容是正确的,不会在网络传送中被修改破坏.每个网络节点都有一个全网络
唯一的标志号,报文传送的起始节点,目的节点都是由这个标志号表示.每个网络节点在
接收到报文后除了做所有节点一样的操作外,还可以做一些本节点特有的操作.定义这
些特有的操作的函数及其参数是在这个节点生成时用参数传入的.在节点发送报文完成
时,也可以做一些自定义的操作.这样就可以在这个网络硬件层次上再构造一层更抽象,
功能更完善的虚拟网络了.例如虚拟网络可以通过请求重发机制来实现一个不会丢失报
文的虚拟网络.
    报文在网络中的传递是用UNIX中的套接口(Socket)实现的.每个节点还有一个可靠
性系数,用来模拟报文从这个节点发出后丢失的概率.Network的实现与控制台类似,每
隔一定的时钟周期,就产生一个读取网络的中断,中断处理过程是:
          1.将下一个中断放入中断队列以实现中断的周期性发生.
          2.如果报文缓冲区中已有报文,则返回.
          3.读取套接口,如果没有报文,则返回.
          4.读取报文,把它放入报文缓冲区.
          5.调用本节点自定义的接收处理函数.
    在现有实现中,报文缓冲区只能存放一个报文,有可能因为报文缓冲区满而造成报文
丢失,可以多设几个报文缓冲区来减少丢失的可能性.
    Network提供了让网络用户读取已经收到的报文的成员函数,当报文缓冲区为空时,
它返回空,否则从报文缓冲区读出报文,并将报文缓冲区清空,返回刚读出的报文.
    报文发送的过程是:
          1.将网络发送中断放入中断队列.
          2.产生一个随机数.
          3.如果这个随机数大于网络的可靠性系数,则不发送报文(用来模拟报文丢
失),否则通过套接口将报文发送出去.

:]

--

                                              Howard
                                              From HOWARD Studio
                                              CopyLEFT All Rights SHARED!!!

※ 来源:．West Garden bbs.ncut.edu.cn．[FROM: unknown]

发信人: Howard (root), 信区: COMPUTER
标  题: NACHOS论坛(2)
发信站: West Garden (Sat Dec 11 15:37:21 1999), 转信

          第二章    进程管理

    在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,而是继续运行下去了

:]

--

                                              Howard
                                              From HOWARD Studio
                                              CopyLEFT All Rights SHARED!!!

※ 来源:．West Garden bbs.ncut.edu.cn．[FROM: unknown]
发信人: Howard (root), 信区: COMPUTER
标  题: NACHOS论坛(3)
发信站: West Garden (Sat Dec 11 15:38:30 1999), 转信

          第三章    文件系统

    Nachos文件系统的界面类似于UNIX,有与UNIX的creat,open,close,read,write,
lseek和unlink相似(不是完全一样)的系统调用.一个重要的不同点在于Nachos文件系
统是用C++实现的.Creat(相当于UNIX中的creat),Open(open),和Remove(unlink)都是
定义在FileSystem类中的,因为它们都是与正在操作的文件名和目录相联系的.
FileSystem::Open返回一个指针,它指向一个OpenFile对象,OpenFile对象与UNIX中的
打开文件描述符类似,可以用这个对象直接对文件进行操作,如Seek(lseek), Read
(read), Write(write)只要把这个OpenFile对象删除(delete)就可以关闭(close)这个
已打开文件了.
    Nachos文件系统的结构如图:

      ┏━━━━━━━━━━━━━━━━━━━┓
      ┃           文  件  用  户             ┃
      ┣━━━━━━━━━━━━━━━━━━━┫
      ┃ FileSystem   OpenFile     Directory  ┃
      ┣━━━━━━━━━━━━━━━━━━━┫
      ┃             FileHeader               ┃
      ┣━━━━━━━━━━━━━━━━━━━┫
      ┃              SynchDisk               ┃
      ┣━━━━━━━━━━━━━━━━━━━┫
      ┃               Disk                   ┃
      ┗━━━━━━━━━━━━━━━━━━━┛

    在Nachos文件系统中,许多数据结构既可存放在内存里,又可存放在磁盘里.为了一
致起见,文件系统中Synchdisk以上的类都有一个FetchFrom成员函数,它把数据结构从
磁盘读到内存;还有一个WriteBack成员函数,它与FetchFrom相反,把数据结构从内存写
回磁盘.在内存中的数据结构与磁盘上的完全一致,没有增减数据项,给管理带来了不少
方便.在以后的介绍中这两个函数不再重复了.
    让我们从下往上分析文件系统.Disk模拟了一个物理磁盘,它的具体实现在机器模
拟部分已经介绍了.

    SynchDisk类在物理磁盘的基础上定义了一个同步磁盘的抽象界面.象别的I/O设备
一样,物理磁盘是异步设备.用户提出读写请求后立即返回,这以后会有一个中断发生,
报告磁盘操作完成.同步磁盘有些不同,进程提出读写请求后将睡眠等待,以后在磁盘中^?
断的处理函数中唤醒它,所以进程将等待磁盘操作完成后才能返回.
    SynchDisk类的界面为:
              ┏━━━━━━━━━━━┓^?
              ┃      SynchDisk       ┃
              ┣━━━━━━━━━━━┫
              ┃     ReadSector       ┃
              ┃     WriteSector      ┃
              ┗━━━━━━━━━━━┛
    SynchDisk类的生成函数生成了一个锁,一个信号量,一个物理磁盘对象,由于物理
磁盘一次只能接受一个读写请求,锁就是用来实现读写互斥的.信号量用来实现中断程
序和发出磁盘请求的程序之间同步。
    ReadSector成员函数的执行过程如下:
          1.关闭锁.(如果别的进程正在操作磁盘,则睡眠等待别的进程的磁盘操作完^?
            成)
          2.向物理磁盘发读数据请求.
          3.对信号量作P操作(睡眠等待磁盘操作的完成,将由读磁盘的中断处理程序
            唤醒本进程).
          4.解锁.
    WriteSector成员函数的执行过程与ReadSector类似.

    FileHeader类是用来管理一个文件块在磁盘上分布情况的数据结构.这个数据结构
称为文件控制块.文件控制块中还可以包括一些有关文件的信息,如长度,拥有者等等,
文件控制块与UNIX中的i-node类似.文件控制块可以放在内存中或磁盘里.当它在磁盘
里时,只占用一个扇区,Nachos没有实现文件控制块的间接定位,所以文件控制块的大小
是固定的,也导致Nachos文件最大长度为4Kbytes.
    FileHeader的界面为:
              ┏━━━━━━━━┓
              ┃  FileHeader    ┃
              ┣━━━━━━━━┫
              ┃  Allocate      ┃
              ┃  Deallocate    ┃
              ┃  ByteToSector  ┃
              ┃  FileLength    ┃
              ┣━━━━━━━━┫
              ┃  numBytes      ┃
              ┃  numSectors    ┃
              ┃  dataSectors[] ┃
              ┗━━━━━━━━┛
    其中numBytes 为文件长度,numSectors为文件占用的扇区数,dataSectors[]数组
指明文件的每个数据块存放在第几个扇区里.例如,有一个文件长度为200 byte,Nachos
定义一个扇区的长度为128 byte,则numBytes=200, numSectors= ceil(200/128)=2,文
件占用了两个扇区,如果文件的第一块放在第5扇区,第二块放在第20扇区,则
dataSectors[0]=5,dataSectors[1]=20,dataSectors数组其他元素值不定,也没有用.
    Allocate成员函数用来初始化文件控制块,为本文件分配磁盘空间.它的执行过程如
下:
          1.根据文件长度对numBytes,numSectors赋初值.
          2.如果文件需要的扇区数大于磁盘上的空闲扇区数,则返回失败.
          3.给文件分配空闲扇区,把扇区号放入dataSectors数组,并把这些扇区的使
                  用标志从空闲改为已占用.
    Deallocate成员函数释放文件占用的扇区.
    ByteToSector返回存放着文件第x字节数据的扇区号.
    FileLength返回文件长度.
    OpenFile类用来实现文件的读写操作.Nachos将文件的操作转化为对扇区的操作.
在现有实现中并没有考虑文件系统的并发问题,这些留给学生作为课程作业.OpenFile
的界面为:

              ┏━━━━━━━━┓
              ┃    OpenFile    ┃
              ┣━━━━━━━━┫
              ┃    Seek        ┃
              ┃    ReadAt      ┃
              ┃    WriteAt     ┃
              ┃    Read        ┃
              ┃    Write       ┃
              ┃    Length      ┃
              ┣━━━━━━━━┫
              ┃  seekPosition  ┃
              ┃ FileHeader* hdr┃
              ┗━━━━━━━━┛
    seekPosition是文件当前读写指针,hdr是文件控制块的地址.OpenFile的生成函数
带有一个int型的参数,指明存放文件控制块的扇区号.生成函数先给hdr分配空间,然后
从磁盘中读出这个文件的文件控制块,放入hdr指向的内存.seekPositon 赋为0,使得文
件当前读写指针指向文件开头.
    Seek成员函数将文件当前读写指针移到新的位置.

    ReadAt/WriteAt用于读写数据.读写的开始位置和读写数据长度由参数指定.由于
Nachos文件长度不可改变,所以超过文件长度的读写都被忽略.又因为磁盘读写单位是
整个扇区,所以ReadAt读出包括要读数据的所有扇区,然后只把要求读出的数据拷贝给
调用者.WriteAt先读出写入数据所在的全部扇区,然后把新数据写入要修改的位置,最
后将这些扇区写回磁盘,这样就保证了不会覆盖不应被修改的部分.这两个函数返回实
际读/写的长度.
    Read/Write成员函数分别调用ReadAt/WriteAt成员函数,从文件当前读写指针处开
始读/写数据.它的执行过程如下:
          1.分别调用ReadAt/WriteAt函数从文件当前读写指针处开始读/写数据.
          2.文件当前读写指针向后移动实际读/写的长度.
          3.返回实际读/写的长度.
    Length返回文件长度.

    Nachos的目录是由一组目录项组成,每个目录项代表一个文件.目录项的内容有:已
使用标志inUse,文件控制块所在扇区号sector,文件名字name,文件名有最大长度,这样
每个目录项都有固定长度.当我们知道文件所在目录和文件名后,就可以从它所在目录
中找到名字与之相同的目录项,于是就可以知道此文件的文件控制块所在扇区,而文件
控制块中记录了文件内容所在的扇区号,这样就可以读写这个文件了.与文件系统的其
他数据结构一样,目录结构既可以放在内存中,又可以放在磁盘上.当它存放在磁盘上时,
是作为一个常规的Nachos文件存储的,由于Nachos文件长度固定,所以目录的目录项个
数在生成目录时就固定了,以后不能改变.现有实现中,对目录操作的互斥是由调用者保
证的.
    目录的界面为:
              ┏━━━━━━━━┓
              ┃   Directory    ┃
              ┣━━━━━━━━┫
              ┃   Find         ┃
              ┃   Add          ┃
              ┃   Remove       ┃
              ┃   List         ┃
              ┃   FindIndex    ┃
              ┣━━━━━━━━┫
              ┃   tableSize    ┃
              ┃   table        ┃
              ┗━━━━━━━━┛
    tableSize放的是目录项的个数,table是目录项数组的地址.
    Directory类的生成函数的执行过程如下:
          1.此目录的目录项个数由参数传入,用这个参数给
            tableSize赋值.
          2.给目录项数组table分配空间,它的元素个数为tableSize.
          3.将所有目录项的使用标志清零.
    一个目录类对象才生成时,目录项内容总是空的,如果这个目录已经存在,就需要用
FetchFrom成员函数把目录项内容从磁盘上读出来.
    FindIndex(char* name)成员函数在目录中寻找文件名为name的文件,如果找到就
返回此文件在目录项数组中的索引,否则返回-1.
    Fine(char* name)成员函数在目录中寻找文件名为name的文件,如果找到就返回此
文件的文件控制块所在扇区号,否则返回-1.
    bool Add( char* name,int newSector) 函数增加一个文件到目录中,这个文件的
名字为name,文件控制块所在扇区号为newSector.如果添加成功,返回TRUE.在下列情况
返回FALSE:
          1.目录中已经存在这个文件名.
          2.目录已满.
    bool Remove( char* name ) 把名字为name的文件从目录中删除.如果成功返回
TRUE.若在目录中没有这个文件,则失败,返回FALSE.
    List() 显示目录中所有的文件.
    FileSystem是Nachos的文件系统的顶层界面.它提供了一些用文件名来操作文件的
功能.
    FileSystem的界面为:

              ┏━━━━━━━━┓
              ┃  FileSystem    ┃
              ┣━━━━━━━━┫
              ┃    Creat       ┃
              ┃    Open        ┃
              ┃    Remove      ┃
              ┃    List        ┃
              ┣━━━━━━━━┫
              ┃  freeMapfile   ┃
              ┃ directoryFile  ┃
              ┗━━━━━━━━┛

    其中freeMapfile和directoryFile是两个OpenFile类的指针.
    freeMapfile指向用来管理磁盘空间的BitMap文件.磁盘的每个扇区对应BitMap中
的一位,如果在BitMap中这位为0,则说明此扇区为空,否则说明此扇区已被某个文件占
用.directoryFile指向根目录文件.Nachos没有实现多级目录结构,它只有一个根目录,
文件系统的所有文件都放在根目录下.
    FileSystem的生成函数有一个format参数,如果它为非零,将格式化(Format)整个
文件系统,否则从模拟磁盘上读出文件系统的信息.
    Format文件系统的过程为:
          1.生成一个空的BitMap和根目录.
          2.把磁盘0扇区分配给freeMapfile文件的文件控制块;
                  1扇区分配给根目录的文件控制块.
          3.为这两个文件分配磁盘空间.
          4.打开这两个文件,即在内存中生成两个OpenFile对象.
          5.把freeMapfile,directoryFile两个文件写回磁盘.
          6.释放函数中分配的辅助内存空间,但freeMapfile和directoryFile这两个
                  OpenFile对象仍然保留在内存中.
    如果生成文件系统时不需要格式化,就只要从磁盘上读出freeMapfile,
directoryFile两个文件即可.
    文件系统生成后,freeMapfile,directoryFile这两个OpenFile对象总是保留在内
存中的.

    Creat(char* name, int initialSize)成员函数用来创建一个新文件,新文件的名
字是name,长度为initialSize,它的执行过程如下:
              ┏━━━━━━━━┓
              ┃  从磁盘读入根  ┃
              ┃    目录文件    ┃
              ┗━━━┳━━━━┛
                      ┃
                      ↓
               ━━━━━━━━━
                   目录中已经           Y
                  存在同名文件       ━━━━━━┓
               ━━━━━━━━━                ┃
                      ┃                         ┃
                      ┃ N                       ┃
                      ↓                         ┃
              ┏━━━━━━━━┓               ┃
              ┃从磁盘读入BitMap┃               ┃
              ┃文件,给文件控制 ┃               ┃
              ┃块分配一个扇区  ┃               ┃
              ┗━━━┳━━━━┛               ┃
                      ┃                         ┃
                      ┃                         ┃
                      ↓                         ┃
                 ━━━━━━━        N         ┃
                   分配成功      ━━━━━━━→┃
                 ━━━━━━━                  ┃
                      ┃                         ┃
                      ┃ Y                       ┃
                      ↓                         ┃
              ┏━━━━━━━━┓               ┃
              ┃ 将文件加入根   ┃               ┃
              ┃     目录       ┃               ┃
              ┗━━━┳━━━━┛               ┃
                      ┃                         ┃
                      ↓                         ┃
                 ━━━━━━          N         ┃
                   成功加入      ━━━━━━━→┃
                 ━━━━━━                    ┃
                      ┃                         ┃
                      ┃ Y                       ┃
                      ↓                         ┃
              ┏━━━━━━━━┓               ┃
              ┃   为文件分配   ┃               ┃
              ┃   磁盘空间     ┃               ┃
              ┗━━━┳━━━━┛               ┃
                      ┃                         ┃
                      ↓                         ┃
                 ━━━━━━         N          ┃
                   分配成功      ━━━━━━━→┃
                 ━━━━━━                    ┃
                      ┃                         ┃
                      ┃  Y                      ┃
                      ↓                         ┃
              ┏━━━━━━━━┓               ┃
              ┃ 将BitMap文件和 ┃               ┃
              ┃ 根目录文件写入 ┃               ┃
              ┃    磁盘        ┃               ┃
              ┗━━━┳━━━━┛               ┃
                      ┃                         ┃
                      ┃                         ┃
                      ↓                         ↓
              ┏━━━━━━━━┓       ┏━━━━━━━━┓
              ┃   返回TRUE     ┃       ┃   返回FALSE    ┃
              ┗━━━━━━━━┛       ┗━━━━━━━━┛

    在Creat函数的处理过程中只修改内存中的BitMap和根目录,磁盘上的数据不会被
修改,这样如果文件生成失败,只要返回FALSE即可.如果执行成功,才把这两个文件写
回磁盘.
    Remove(char* name)删除文件名为name的文件.它的执行过程如下:
          1.从磁盘读入根目录文件.
          2.如果根目录中没有这个文件,则返回FALSE.
          3.读入此文件的文件控制块.
          4.释放此文件占用的磁盘扇区,并删除其目录项.
          5.释放此文件的文件控制块占用的磁盘扇区.
          6.把修改后的BitMap和目录文件写回磁盘.
          7.返回TRUE.
    OpenFile* Open(char* name)成员函数打开名为name的文件,可以用返回的
OpenFile指针读写此文件.Open的执行过程如下:
          1.将目录文件读入内存.
          2.用Directory::Find(char* name)函数求出name文件的文件控制块所在扇
                 区.
          3.读入文件控制块,并生成此文件的OpenFile对象.
          4.返回OpenFile对象的指针.
    List成员函数显示根目录的内容.
    关闭文件只须删除(delete)OpenFile对象即可.

:]

--

                                              Howard
                                              From HOWARD Studio
                                              CopyLEFT All Rights SHARED!!!

※ 来源:．West Garden bbs.ncut.edu.cn．[FROM: unknown]
发信人: Howard (root), 信区: COMPUTER
标  题: NACHOS论坛(4)
发信站: West Garden (Sat Dec 11 15:39:13 1999), 转信

           第四章    网络及虚拟内存

    Nachos的网络的实现分为两层:Network和PostOffice.首先,请您不要误解Network
的含义,它并不是一个网络操作系统,而是Nachos操作系统在接收或发送网络信息时的
管理模块.换句话说,Nachos的Network只管本地机对网络信息的处理,它并不关心网络
是如何实现信息传递的.Network的结构是,每个主机上有一个邮局(PostOffice)来负责
处理用户的Network请求.每个邮局中有几个信箱(MailBox),它存放着从网络上接收到
的信息.

    如果一个Nachos进程要通过网络将信息从本地发往另一个Nachos工作站,它首先要
象现实生活中那样先填写收信人,发信人的地址.地址由两部分组成:1.节点地址;2.信
箱号.然后将信的内容放在地址信息之后,送到邮局去发送(即调用PostOffice的Send成
员函数).当一个进程要接收一个信息,它就到邮局去取某个信箱中的信息(即调用
PostOffice的Receive成员函数),如果信箱中有信件,邮局会把信件给它,同时把发信人
的节点地址和信箱号也告诉它.与现实生活不同的是:如果信箱里没有信,取信进程并不
返回,而是睡眠等待,直到有信件来到时才唤醒它.Nachos还模拟了信件的丢失,但是由
于现代网络通讯中使用了检验纠错码,可以检查信件内容是否被改动过了.如果信件内
容不对,则认为信件丢失,所以Nachos只对信件丢失进行模拟,而没有模拟信件内容出
错.Nachos假定只要收到信件,就认为它的内容是正确的.Nachos的现有实现中,发信进
程并不知道信是否成功地发到了指定信箱.

    现在让我们看看网络实现的细节.Network模拟了一个物理网络节点.它的具体实现
在机器模拟部分已作了介绍,这里就不再重复了.PostOffice是与网络用户打交道的界
面.PostOffice中有一组信箱类的对象(MailBox),信箱类提供了将信件放入信箱和从信
箱中取出信件的功能.不过这些功能只供PostOffice类使用,网络用户不能直接调用.每
个信箱中有一个信件队列,当进程要从一个信箱中取出信件时,如果信件队列非空,则从
队列头部取出一封信交给取信进程,否则取信进程将睡眠等待信的到来.当一封信放入
信箱时,它被加入此信箱的信件队列.如果有进程在等待这个信箱的信,就唤醒这个进程.
    PostOffice的生成函数的参数有:
        1.本PostOffice所在网络的地址;
        2.网络的可靠性参数;
        3.PostOffice中MailBox的个数.
    PostOffice的生成函数的执行过程如下:
        1.生成两个信号量:报文发送和报文收到信号量.它们的初值都为零.
        2.再生成报文发送锁,几个MailBox对象,一个Network对象.
        3.利用Nachos的进程管理系统生成一个“Postal Worker"进程.
    "Postal Worker"进程做一个无穷循环工作,每次循环的过程如下:
        1.对报文收到信号量作P操作,作用是等待报文的来到.当从网络中收到了一个
                报文时,中断处理程序将对报文收到信号量作V操作,以唤醒本进程.
        2.它重新占用CPU后,从网络上读出这则报文.调用报文中指定的信箱的Put函
                数,将这则报文放入信箱.
    PostOffice发送信件的过程是:
        1.关闭报文发送锁.以保证只有一个报文在发送.
        2.把报文放到网络上发送.
        3.对报文发送信号量作P操作,等待报文发送完毕.报文发送完毕后,中断系统
                将发送中断,在中断处理程序中将对报文发送信号量作V操作.就可以
                唤醒本进程.
        4.打开报文发送锁,让下一个报文可以发送.
    网络用户进程调用PostOffice去取信箱中的信件时,PostOffice调用相应的MailBox
的Get 成员函数取出信箱中的信件.如果信箱中没有信件,在Get函数中,取信进程将睡
眠等待.

    Nachos的虚拟内存管理比较简单,主要是页式管理.用户程序中的虚拟地址向物理
内存地址变换的过程受页表或快表控制.页表和快表的数据项的结构是一样的,都由一
个虚页号,一个实页和一些其它的标志组成.页表和快表的不同点在于大小不同,快表比
页表小得多,里面放的是最常用的页表项,可以看作是页表的高速缓冲区.当快表不存在
时就用页表进行地址转换,否则使用快表.虚实地址转换是由
int translate(int virtAddr,int * physAddr, int size, bool writing)完成的.
其中:
        virAddr --要转换的虚地址;
        physAddr--用来存放转换成功后的实地址;
        size--内存读写的长度;
        writing--是否是写内存操作.
    如果转换成功,则返回无错的标志,否则返回出错类型.
    当用户程序读写内存时,Nachos先调用translate函数进行虚实地址转换,如果
translate返回值是无错,则用实地址读写内存,否则发出一个异常信号,信号类型就是
translate的返回值.让我们来看看地址转换具体过程:

                      ↓
               ━━━━━━━━
                 虚地址是否             N
                  字对齐了          ━━━━━━┓
               ━━━━━━━━                 ┃
                      ┃                        ┃
                      ┃Y                       ↓
                      ↓             ┏━━━━━━━━┓
              ┏━━━━━━━━┓   ┃  返回地址错误  ┃
              ┃ 计算出虚地址   ┃   ┗━━━━━━━━┛
              ┃ 对应的虚页号vpn┃
              ┃ 和页内偏移量   ┃
              ┗━━━┳━━━━┛
                      ┃
                      ↓
               ━━━━━━━━━       Y
                   快表存在          ━━━━┓
               ━━━━━━━━━            ┃
                      ┃                     ┃
                      ┃ N                   ┃
                      ↓                     ↓
                ━━━━━━━         ━━━━━━━━
          Y       虚页号vpn         N   有一个快表项的
       ┏━━    大于页表个数     ┏━  虚页号等于vpn
       ┃       ━━━━━━━    ┃   ━━━━━━━━
       ↓             ┃          ┃             ┃
┏━━━━━━━━┓  ┃ N        ↓             ┃
┃  返回地址错误  ┃  ┃     ┏━━━━━━━━┓┃ Y
┗━━━━━━━━┛  ┃     ┃ 返回页失效错误 ┃┃
                      ┃     ┗━━━━━━━━┛┃
                      ↓
          N      ━━━━━━                    ↓
       ┏━━     此页已装入          ┏━━━━━━━━┓
       ┃            内存             ┃ entry=此虚页   ┃
       ↓        ━━━━━━         ┃ 对应的快表项   ┃
┏━━━━━━━━┓  ┃              ┃    入口        ┃
┃ 返回页失效错误 ┃  ┃              ┗━━━━┳━━━┛
┗━━━━━━━━┛  ┃ Y                      ┃
                      ↓                        ┃
              ┏━━━━━━━━┓              ┃
              ┃ entry=此虚页   ┃              ┃
              ┃ 对应的页表项   ┃              ┃
              ┃    入口        ┃              ┃
              ┗━━━┳━━━━┛              ┃
                      ┃                        ┃
                      ┃                        ┃
                      ┗━━━━━┳━━━━━━┛
                                  ┃
                                  ↓
                          ━━━━━━━━━━
                 Y         writing参数为TRUE
             ┏━━━      而entry指向的页为
             ┃                 只读页
             ┃           ━━━━━━━━━━
             ┃                   ┃
             ↓                   ┃
     ┏━━━━━━━━┓         ┃   N
     ┃  返回只读错误  ┃         ┃
     ┗━━━━━━━━┛         ↓
                    ┏━━━━━━━━━━━━━━━┓
                    ┃  PageFrame = entry 项中的    ┃
                    ┃         物理页号             ┃
                    ┗━━━━━━┳━━━━━━━━┛
                                  ┃
                                  ↓
               Y     ━━━━━━━━━━━━━━
             ┏━━    PageFrame >= 物理页总数
             ┃      ━━━━━━━━━━━━━━
             ┃                   ┃
             ↓                   ┃
      ┏━━━━━━━━┓        ┃ N
      ┃  返回总线错误  ┃        ┃
      ┗━━━━━━━━┛        ↓
                        ┏━━━━━━━━━━━┓
                        ┃  置entry的使用标志   ┃
                        ┗━━━━┳━━━━━━┛
                                  ┃
                                  ↓
                            ━━━━━━━       N
                              是写请求       ━━━━┓
                            ━━━━━━━           ┃
                                  ┃                 ┃
                                  ┃ Y               ┃
                                  ↓                 ┃
                        ┏━━━━━━━━━━━┓   ┃
                        ┃  置entry的写标志     ┃   ┃
                        ┗━━━━┳━━━━━━┛   ┃
                                  ┃                 ┃
                                  ┃ ←━━━━━━━┛
                                  ↓
                        ┏━━━━━━━━━━━┓
                        ┃ 计算实地址,并放入    ┃
                        ┃     physAddr中       ┃
                        ┗━━━━┳━━━━━━┛
                                  ┃
                                  ↓
                          ┏━━━━━━━━┓
                          ┃  返回无错误    ┃
                          ┗━━━━━━━━┛

:]

--

                                              Howard
                                              From HOWARD Studio
                                              CopyLEFT All Rights SHARED!!!

※ 来源:．West Garden bbs.ncut.edu.cn．[FROM: unknown]
发信人: Howard (root), 信区: COMPUTER
标  题: NACHOS论坛(5)
发信站: West Garden (Sat Dec 11 15:41:07 1999), 转信

           第五章     Nachos在8086上的实现

    Nachos是一个优秀的操作系统课程设计系统,它对学生理解和学习操作系统的基本
概念,基本原理和方法很有帮助.但是Nachos的运行环境必须是UNIX的工作站,硬件平台
为DEC MIPS,SUN SPARC ,HP PA-RISC或Intel386.如果使用其网络部分,还必须将工作
站联网.要让大量同学在在这样的软硬件环境上完成Nachos课程设计,对国内大部分高
校来说,是很困难的.我们根据国内大部分高校的实际情况,将Nachos系统移植到广泛使
用的DOS操作系统上,移植后的Nachos只要Intel386微机和DOS操作系统即可使用,如果
要使用Nachos的网络部分,只需再加一个DOS的多任务管理器,如DOSSHELL或Windows.这
些软硬件要求在国内大多数高校中都可以得到满足.甚至学生自己购买的微机上大部分
也有上述环境.这样移植后的Nachos就可以被广泛地使用了.
    在Nachos的移植过程中,我们做了以下几个工作:
        1.在8086上实现Nachos的两个进程切换函数.
        2.用自定义的数据类型改写Nachos中数据的数据类型,使其能够用DOS的16位
                编译器编译.
        3.将一些UNIX库函数移植到DOS.
        4.Nachos的应用程序解释器原来运行的应用程序是用MIPS机器指令写的,现改
                为运行8086机器指令的应用程序.

一.进程切换函数的移植.

    Nachos是一个真正的多进程系统,它的多进程不是依靠宿主机操作系统上的多进程
机制实现的.从宿主机操作系统的角度来看,Nachos只是一个应用程序,只有一个进程在
运行,但是Nachos内部实际上可以运行多个Nachos自己实现的进程.这些进程可以动?
地生成和消亡,并且轮流占用处理机运行.由于Nachos的这种设计方法不依赖于UNIX的
多进程机制,所以在将它移植到DOS环境时,不用在DOS上模拟UNIX的多进程功能,大大简
化了移植工作.
    Nachos进程管理系统的移植中,改动很大的有两个函数:SWITCH和ThreadRoot.这两
个函数都是用来实现进程正文切换的.此类工作与具体的处理机结构及函数调用格式密
切相关.Nachos虽然也为Intel386实现了这两个函数,但是它实现这两个函数所用的汇
编语言与DOS下的汇编语言大相径庭,并且是供32位编译器生成的程序调用的,调用格式
与DOS的16位编译器不一致,所以原有实现无法在DOS下使用,我们重新编写了这两个函数.
    SWITCH函数是用来在进程切换时保护老进程图象和恢复新进程图象的.进程图象包
括处理机寄存器状态和堆栈.它有两个参数:Thread* oldThread;Thread* newThread,
分别指向老进程和新进程的对象.改写过的SWITCH函数与原来的有很大不同.首先,新的
SWITCH函数是用C++语言中嵌入汇编语言(即行内汇编)编写的,而老的SWITCH全部由汇
编语言编写.之所以用行内汇编,是由于在进程切换时,需要把CPU各寄存器的值保存到
老进程对象的machineState数据成员中,而DOS下的编译器如Borland C++,MicroSoft
C++等,对对象中数据成员的内存地址没有明确的规定,如果使反汇编或其它方法强行找
出数据成员的位置,会带来许多问题.例如不同的编译器放置数据成员的位置并不一样,
当系统的移植到其它编译器时,要重新找出这个位置,很不方便.即使只使用一种编译
器,可以确定数据成员的位置,但是在稍稍改动进程对象的结构后,这个位置会不会改变
呢?没有人能作出肯定的回答.要保证这个位置不发生变化,就必须在每次改动后重新查
看这个数据成员的内存位置,可以想象,这将给Nachos的用户--学生带来多大的麻烦.我
们使用行内汇编,直接用C++语言存取对象的数据成员,这个问题就迎刃而解了.
    使用行内汇编也有其缺点,那就是程序员不能完全控制寄存器,一些C++语句,特别
是有关存取数组的语句会使用和改变寄存器的内容.我们解决这个问题的方法是,在寄
存器的值未被修改时将其压入堆栈,要用时再从堆栈中弹出,这样就万无一失了.
    SWITCH函数的执行过程为:
        1.将SP,SS,AX,BX,CX,DX,SI,DI,BP寄存器的值顺序压入堆栈.因为在压栈的过
                程中,栈顶寄存器SP会改变,所以首先将SP压入堆栈.
        2.C语言调用函数的压栈规则是:先将参数从右向左压入堆栈,再把函数的返回
                地址压入堆栈.根据这个规则,可以从栈上找到SWITCH函数的返回地
                址,取出这个地址放入一个临时变量中保存.
        3.从栈中分别弹出先前保存的各寄存器值,放入老进程的machineState中,以
                达到保护现场的目的.
        4.将SWITCH函数的返回地址也保存到老进程中.
        5.将newThread的machineState中保存的栈顶寄存器SP和栈段寄存器SS读入DX,
                CX寄存器,供下面切换堆栈时使用.
        6.将newThread的值读入AX,BX寄存器(高16位放入AX,低16位放入BX).这是因
                为newThread是SWITCH函数的参数,它是放在堆栈上的,切换堆栈后就
                找不到它了,所以先把它读入寄存器中.
        7.将CX的值赋给栈段寄存器SS,DX的值赋给栈顶寄存器SP,达到切换堆栈的目
                的.现在进程在新的堆栈上运行了.
        8.用AX,BX寄存器的值重新装配newThread指针.
        9.将新进程保存的SWITCH函数的返回地址放入新堆栈.这样SWITCH函数结束返
                回后,会从新进程的断点继续运行下去.
        10.从newThread的machineState中取出以前保存的BP,DI,SI,DX,CX,BX,AX寄
                存器的值,并把它们压入堆栈.
        11.从堆栈中分别弹出第10步压入的值,并放入相应的寄存器.不直接在第10步
                中将newThread中保存的值放入寄存器的原因与做第1步和第3部的原
                因一样,都是因为存取进程对象中保存的寄存器内容时,要使用一些
                通用寄存器,所以先得把寄存器的内容压入堆栈保存.
    我们在移植进程切换的另一个函数ThreadRoot时,对它做了一些简化.ThreadRoot
代表进程运行的全过程,既包括用户定义的进程函数,又包括进程的初始化函数和进程
的结束函数.ThreadRoot有四个参数,它们是:
        InitialPC,InitialArg,用户定义的工作函数及其参数;
        StartupPC,进程的初始化函数;
        WhenDonePC进程的结束函数.
    经过分析,我们发现在Nachos中只需有一个初始化函数和一个结束函数,所以没有
必要通过参数传入这两个函数,我们直接在ThreadRoot函数中调用这两个函数.
    ThreadRoot的另两个参数并不是由堆栈传入的,而是放在AX,BX,CX,DX四个寄存器
中传入的(这两个参数都是32位数,AX等通用寄存器只有16位,所以用4个寄存器传2个参
数).ThreadRoot的执行过程如下:
        1.将AX,BX,CX,DX寄存器的值压入堆栈.
        2.运行进程初始化函数.
        3.从堆栈中弹出寄存器的值,装配成两个参数.
        4.运行第3步装配的进程工作函数.
        5.运行进程结束函数.

    ThreadRoot函数的特殊的参数传入方法,将要求其它程序在调用它时要做一些额外
的工作,这不是太多余了吗?事实上,系统中没有一个地方显式地调用ThreadRoot函数,
而且ThreadRoot函数根本就不能结束返回(这一点在进程管理一章中已作了详细介绍).
那么ThreadRoot函数有什么用处呢?从前面的介绍中我们知道在进程切换时SWITCH函数
会返回到新进程以前的断点处,但是新进程首次被调度上CPU运行时,并没有以前的断
点,那么它将返回到哪里呢?为了解决这个问题,我们在生成一个新进程的时候,将
ThreadRoot函数的地址放入新进程堆栈中放返回地址的位置,并且在存放AX,BX,CX,DX
寄存器值的machineState数组中放入ThreadRoot需要的两个参数.这样,当新进程首次
占用处理机时,就可以运行ThreatRoot函数了.

  二.在16位编译器上编译Nachos.
    Nachos原来使用GNU C++编译器编译的,它是一个32位的编译器,而DOS下常用的编
译器,如MicroSoft C++,Borland C++都是16位编译器.32位编译器与16位编译器的主要
不同在于整型(int)的长度不一样,32位编译器中整型长度为32位,占4个字节.而16位编
译器中整型长度为16位,占2个字节.Nachos中大量整型数据的值不能用2个字节存放.例
如在Nachos代码中,向一个函数传递未知类型的参数时,都将参数定义为整型,然后在函
数内部再根据具体需要,对参数进行类型转换.这些参数往往被转换为指向一个对象的
内存指针,内存指针有32位,需要用4个字节表示,这就要求整型必须有4个字节.为了在
DOS下正确地编译Nachos代码,我们不得不手工改写这些整型数据的类型.此外,我们还
考虑到将来各方面条件改善了,Nachos又会用32位编译器重新编译,以便移植到更高级
的硬件上.尽管现有的Nachos已经是32位的,似乎不需要再把Nachos for DOS移植到32
位,但是我们今后大量工作都是在Nachos for DOS上进行的,Nachos for DOS将比现有
的Nachos更加完善,如果我们不想放弃这些宝贵的工作成果, 就只有把Nachos for DOS
移植到32位或更高的系统上.那么如何使Nachos的数据类型转换工作同时满足上述两方
面的要求呢?我们发现Windows的API(应用程序接口)也遇到与我们同样的问题,即需要
尽可能方便地移植到不同的编译器上,Windows的API在设计的时候就注意到这个问题,
所以它没有使用常规的C语言的基本数据类型来定义数据,而是自己定义了一套数据类
型,然后用C语言的define和typedef两种语句将自定义的数据类型对应到C语言的数据
类型.这样,如果C语言的数据类型因编译器的不同而改变时,只要改动少量的define和
typedef就可以保持不变.这种方法非常方便灵活.我们借鉴了Windows API的方法,定义
了下列几种数据类型:
        1.BYTE ,占1个字节.
        2.WORD ,占2个字节.
        3.DWORD,占4个字节.
    因为C语言标准库函数的参数和返回值的类型为C语言的标准数据类型,所以我们定
义了INT和CHAR两种类型,分别与C语言中的int和char相兼容.

    这些自定义的数据类型放在PUBLIC.H中,PUBLIC.H被Nachos原有的一个头文件
COPYRIGH.H包含,因为COPYRIGH.H被每一个Nachos的C++文件包含,所以PUBLIC.H也就被
全部C++文件包含了.我们在通读Nachos源代码的基础上,将Nachos原有的char,int类型
的数据根据其所需空间的大小和用途,改为自定义的类型.在改写的过程中,我们尽可能
用DWORD来改写int 类型的变量,给将来扩展系统带来方便.

  三.UNIX库向DOS的移植.
    DOS中没有的UNIX库函数可分为两类,第一类可以用其它库函数直接来实现相同的功
能.如bcopy可以用memcpy来代替,移植时只要重新编写这些函数即可.

    另一类无法直接移植到DOS下,它们主要集中在网络部分.Nachos使用UNIX的套接口
(socket)机制来实现不同工作站上的Nachos系统之间的网络通讯.DOS中没有类似功能,
而且国内部分高校尚未实现联网,考虑到这些实际情况,我们决定在单机上用一个文件
来模拟网络.具体的方法是在Windows下启动两个DOS仿真程序(运行Windows 的Program
Manager中的DOS PROMPT程序),这两个DOS仿真程序分别运行一个Nachos,这两个Nachos
程序一个把报文写入报文文件,另一个把报文从报文文件中读出.这样就可以模拟网络
的信息交换功能了.这种方法不仅适用于模拟单机上,两个Nachos程序之间的网络通讯,
还可以扩展到多个Nachos程序之间的网络通讯.只要内存足够大,Windows就可以运行多
个DOS仿真程序,每个DOS仿真程序上运行一个Nachos,每个Nachos系统都有一个标志号.
网络报文中含有发送方和接收方的标志号,Nachos程序只接收发给自己的报文.这样就
可以模拟一个多节点的网络了.此外,如果您是在一个真正的网络上工作,也可以把报文
文件放在网络的文件服务器上,让工作组的成员可以在不同的客户机上存取这个文件,
这样就实现了不同客户机上运行的Nacho之间模拟网络通讯.

    网络模拟的具体实现为:在Nachos开始运行时,用共享方式打开报文文件,其共享属
性设为SH_DENYNO,它允许在报文文件打开时,其它程序对它进行读写操作.在Nachos运
行期间报文文件一直处于打开状态.Nachos结束时,才关闭报文文件.我们知道,如果有
两个程序同时对报文文件进行读写会引起读写的混乱.为了避免这个问题,在单机运行
Nachos时先运行DOS提供的SHARE.EXE程序,它可以控制文件的读写,避免多个程序之间
的读写冲突.在网络运行Nachos时,文件服务器会提供文件读写互斥的服务.所以无论在
单机上,还是在网络上实现网络模拟时,都不会出现读写文件混乱的情况.
    用户通过模拟网络发送报文的过程为:
        1.保存报文文件的当前文件读写指针位置
        2.将报文文件的当前文件读写指针移到文件尾.
        3.把报文写入报文文件.
        4.把报文文件的当前文件读写指针移回原先的位置.
    用户查看报文文件中是否有发给自己的报文的过程为:

                  ↓
            ━━━━━━
             报文已收到       Y
              标志为真     ━━━━┓
            ━━━━━━           ┃
                 ┃                ↓
  ┏━━━━━→ ┃ N      ┏━━━━━━━━┓
  ┃             ↓        ┃   返回TRUE     ┃
  ┃        ━━━━━━   ┗━━━━━━━━┛
  ┃        已读到报文          Y
  ┃         文件尾部       ━━━━┓
  ┃        ━━━━━━            ┃
  ┃             ┃                 ↓
  ┃             ┃N        ┏━━━━━━━━┓
  ┃             ↓         ┃   返回FALSE    ┃
  ┃    ┏━━━━━━━━┓┗━━━━━━━━┛
  ┃    ┃  把一条报文读  ┃
  ┃    ┃  入报文缓冲区  ┃
  ┃    ┗━━━━━━━━┛
  ┃             ┃
  ┃             ┃
  ┃             ↓
  ┃       ━━━━━━━
  ┃ N      此报文的接收
  ┗━━     方为本节点
           ━━━━━━━
                 ┃
                 ┃Y
                 ↓
       ┏━━━━━━━━━┓
       ┃ 置报文已收到标志 ┃
       ┗━━━━━━━━━┛
                 ┃
                 ┃
                 ↓
        ┏━━━━━━━━┓
        ┃   返回TRUE     ┃
        ┗━━━━━━━━┛

    用户读取报文的过程为:
        1.调用报文查看函数,如果它的返回值为假,则返回.
        2.将报文从报文缓冲区中拷贝到调用者提供的内存区.
        3.清报文已收到标志.

四.Nachos应用程序解释器的移植.

    大多数模拟操作系统的应用程序使用的机器指令是模拟操作系统自己设计的,不是
宿主机的机器指令.这就要求应用程序必须用模拟系统特有的汇编语言编写,为了避免
给学生布置太多的工作,这些应用程序都是很简单,很短小的,很难用来充分测试操作系
统的功能.Nachos突破了这一限制,它的应用程序可以用C或C++语言编写,通过编译生成
宿主机的机器指令,Nachos能够解释执行这些机器指令,这样就大大减轻了编写应用程
序的工作强度.
    Nachos原有的编译器是GNU C++,它生成的是MIPS的机器指令,但是同学们对MIPS的
机器指令不太熟悉,在跟踪应用程序执行过程中会遇到困难,另一方面,DOS环境下也不
能运行GNU C++编译器,所以我们决定用Borland C++ 或MicroSoft C++编译应用程序.
这样就有三项移植工作要做:
        1.DOS编译器生成的是8086的机器指令,需要把原来的MIPS指令解码和解释执
                行部分改写为8086指令的解码和解释执行.
        2.将DOS编译器生成的可执行文件中的调用DOS系统功能的指令去掉.因为应用
                程序是在Nachos操作系统上运行的,不应调用DOS系统功能.
        3.将DOS编译器生成的可执行文件,按Nachos要求的格式进行改写,并移到
                Nachos的文件系统中去.
    对8086机器指令的分析执行分为两步,第一步读出机器指令进行解码,将解码结果
放入指令信息数据结构中,供下一步使用.

    8086中可供程序员使用的有14个16位寄存器,它们是8个通用寄存器AX,BX,CX,DX,
SP,BP,SI,DI,其中AX,BX,CX,DX的高8位和低8位还可以分别作为一个寄存器使用.例如
AX就可以分为AH和AL.指令寄存器IP指向指令地址的段内地址偏移量.标志寄存器FR中
有6个状态位,3个控制位.状态位分别为进位标志,奇偶标志,辅助进位标志,零标志,符
号标志,溢出标志.这些标志反映算术或逻辑运算结果的某些性质.控制位有:方向标志,
中断允许标志,跟踪标志.它们用来控制程序的运行.8086还有4个段寄存器,分别指向各
段的基址.它们是:代码段寄存器CS,堆栈段寄存器SS,数据段寄存器DS,附加段寄存器ES.
8086的寻址方式比较复杂,它分为立即寻址,寄存器寻址,存储器寻址,串操作寻址,外设
I/O寻址和程序转移操作寻址.其中变化最大的是存储器寻址.这种寻址方式又可分为直
接寻址,寄存器间接寻址,基址寻址,变址寻址,以及基址变址寻址.根据寻址方式计算而
得的地址只是段内偏移地址,还需与所在段的段基址组合才是20位的物理地址.
    8086采用变字节长指令,由1到6个字节组成,其格式如下:

      第一字节         第二字节         第三到六字节
┏━━━━━━━━┳━━━━━━━━┳━━━━━━━┓
┃ 7 6 5 4 3 2 1 0┃7 6 5 4 3 2 1 0 ┃              ┃
┗━━━━━━━━┻━━━━━━━━┻━━━━━━━┛
      操作码    D W  MOD  REG   R/M   地址位移量或立即数

    第一字节的高6位为操作码,指出指令的操作类型.D为方向位,当D=0时,表示REG字
段指出的寄存器为源操作数寄存器;当D=1时,表示REG字段指出的寄存器为目的操作数
寄存器,用来存放运算结果.W为操作位,当W=0时,表示参加运算的操作数为字节操作数;
当W=1时,为字操作数.

    第二字节指出所用操作数存放在何处(存储器还是寄存器),以及存储器操作数有效
地址的计算方法.7,6两位为MOD(方式)字段,指出是存储器操作数还是寄存器操作数;
5~3位为REG(寄存器)字段,指出寄存器的编号;2~0位为R/M(寄存器/存储器)字段,受MOD
字段控制,指出第二个操作数所在的寄存器的编号(当MOD=11时),或指出存储器操作数
的有效地址的计算方法.
    第三到六字节根据指令的不同而决定取舍,一般由其指出存储器操作数地址的位移
量或立即数.
    第二字节中MOD字段的编码表如下:
    ┏━━━━┳━━━━━━━━━━━━━━━┓
    ┃   MOD  ┃          方    式            ┃
    ┣━━━━╋━━━━━━━━━━━━━━━┫
    ┃   00   ┃    存储器方式,无位移量       ┃
    ┃   01   ┃    存储器方式,有8位位移量    ┃
    ┃   10   ┃    存储器方式,有16位位移量   ┃
    ┃   11   ┃    寄存器方式,无位移量       ┃
    ┗━━━━┻━━━━━━━━━━━━━━━┛

    REG字段的编码表如下:
    ┏━━━┳━━━━━━━━┳━━━━━━━━┓
    ┃ REG  ┃  W=0(字节操作) ┃  W=1(字操作)   ┃
    ┣━━━╋━━━━━━━━╋━━━━━━━━┫
    ┃ 000  ┃      AL        ┃       AX       ┃
    ┃ 001  ┃      CL        ┃       CX       ┃
    ┃ 010  ┃      DL        ┃       DX       ┃
    ┃ 011  ┃      BL        ┃       BX       ┃
    ┃ 100  ┃      AH        ┃       SP       ┃
    ┃ 101  ┃      CH        ┃       BP       ┃
    ┃ 110  ┃      DH        ┃       SI       ┃
    ┃ 111  ┃      BH        ┃       DI       ┃
    ┗━━━┻━━━━━━━━┻━━━━━━━━┛

    解码过程分析二进制的机器指令,将指令所占字节数,操作码类型,源目操作数的寻
址方式放入指令信息结构中.第二步根据指令信息结构的内容,从仿真8086机器的寄存
器或内存中取出操作数,根据操作码指明的功能运算后,将结果放回仿真机器中.

    8086的汇编级指令有106条(以助记符计),可分为数据传送指令.算术指令,位处理
指令,字符串指令,程序转移指令以及处理机控制指令等6大类.其中有5条指令不能模
拟.一类是对外设端口进行读写的指令IN,OUT.这是因为仿真机上并没有模拟外设端口.
另一类是中断指令INT,INTO,IRET,中断指令是用来调用DOS提供的系统功能的,所以
Nachos应用程序不应使用这些指令.

    在应用程序中出现I/O端口指令和中断指令的原因有两个,一是用户调用了一些包
含这些指令的C语言库函数.所以在编写应用程序时,只能使用一部分C语言库函数,如
strcpy,需要调用操作系统功能时,必须使用我们提供的库函数,而不能用C语言库函数,
例如,打开文件时,用我们提供的Open函数,而不能用标准库中的open函数.

    在应用程序中出现I/O端口指令和中断指令的另一个原因是编译器链接的时候会在
可执行文件中加入一些初始化程序以帮助应用程序装入内存.这些程序大量调用了DOS
中断,我们移植的时候要去掉这些程序.编译器的文档写明,这些初始化程序放在C0S.OBJ
文件里,编译时被链入可执行程序,于是我们重新改写了C0S程序,去掉了所有的DOS中断
调用.

    Nachos不能直接运行编译器生成的可执行程序.必须将可执行程序的头部转换成
Nachos要求的格式.然后把它拷入Nachos的文件系统.这样Nachos才能运行这些程序.
Nachos可执行文件的头部包含的信息有程序中有几个数据段,代码段和栈段,每段的长
度及在文件中的位置,指令指针和代码段寄存器的初值.这些信息都可以在编译器生成
的可执行文件中找到.

--

                   NACHOS编译

NACHOS建立在MIPS模拟机上，在编译NACHOS上运行的程序时需要编译成
MIPS指令。需要利用gcc的交叉编译。在LINUX下的MIPS机交叉编译的
gcc在202.120.5.60的/usr/local目录下。

--

            在NACHOS中有一个小错误.

    NACHOS用一个全局变量标志当前需要Destroy的Thread.这个标志在各线程进行
Switch时,可能被设置.实际上,这就是被调度下去的线程正要被Destroy.NACHOS的作
者在呼叫Switch函数后,立即检查这个标志是否设定了,如果设定了,那么就真正地完
成Destroy的动作.但此时,当前的活跃线程实际上是新调度上来的那个线程.如果新
调度上来的线程没有从Switch函数中出来(只有一种情况会这样,那就是这个线程是
刚刚启动的,所以进入了ThreadRoot,而非Switch),那么这个要被Destroy的线程就会
被搁置在那里,没有立即被删除调.当然,下一次Switch时,也有机会删除这个线程,但
是如果这个新被调度上来的线程正好也死去了,那么这个标志将会被覆盖,前面的那个
线程的Destructor不会被叫用.
    综合上述,我们可以知道,在下面的情况下,NACHOS会产生一个错误:
    1.一个线程死去了,而新调度上来的那个线程是一个刚刚创建的线程.
    2.这个刚刚创建的线程在下一次被调度下去时,也死去了.
    产生的错误是前面死去的那个线程的Destructor没有被叫用,它占用的资源没有
被释放.

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)