一个小型操作系统的实现

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,13,章 一个小型操作系统的实现,本章知识点：,13.1 MINIX,概述,13.2,进程,13.3 I/O,任务,13.4,内存管理,13.5,文件系统,为了了解到一个“真正”的操作系统是怎样一步步构造出来的，我们将以,MINIX,操作系统为例，对其设计方法进行介绍,并对其源代码进行简单分析。,因为,MINIX,的源代码是公开的，有兴趣的读者还可以自己动手加以改造。,13.1 MINIX,概述,MINIX,操作系统最早出现于,20,世纪,80,年代，由美国著名学者,A.S.Tanenbaum,用,c,语言编制。,它从外部看来和,UNIX,非常相似，但实际上，,MINIX,的内部完全是经过重新设计的。它的主体部分设计为几个相对独立的模块，模块间依赖消息进行通讯，这样的模块化结构使得对它的理解和修改都更方便。,本章中将介绍基于,POSIX,（国际标准,9945-1,）的,MINIX2.0,版本，它可以运行于基于,80x86,结构的兼容机系列。,13.1.1 MINIX,的组成结构,1,MINIX,的四层结构,MINIX,的整个系统被分为,4,个层次：,13.1.1 MINIX,的组成结构,需要特别介绍的是位于用户进程层次的,MINIX,的命令解释器,shell,。,命令解释器并不是操作系统的一部分，它本身就是一个计算机程序，用,C,语言编写，为协助用户与操作系统之间通讯而设计，管理用户与核心,(kernel),之间的对话，并把操作系统指令换成机器代码。,13.1.1 MINIX,的组成结构,Shell,通常利用终端作为标准输入输出设备。但是我们也可以利用以下的命令改变输入输出：,ver,fileb,这条命令的意思是调用程序,ver,，从,filea,文件取输入，送输出到,fileb,文件。,如果再利用管道，则可以将一个程序的输出作为另一个程序的输入，例如：,ver, /dev/,lp,，是将执行,ver,程序的结果从,/dev/,lp,文件上输出。,启动,shell,将首先显示系统提示符,$,然后等待，假设用户输入命令,move,，,shell,读取该命令后，自动创建一个新进程来执行这个命令。命令执行完毕后，它再执行一个系统调用来终止这个进程，继续等待用户的下一个输入。,13.1.1 MINIX,的组成结构,shell,还可以用来进行程序设计，它定义了各种变量和参数，并提供了包括循环与分支在内的，许多在高级语言中才具有的控制结构。,使用,shell,编程类似于编辑,DOS,中的批处理文件，我们可以将一组我们想要执行的命令放在一个文件中，然后像执行其他程序一样运行这个文件。这个文件就被称为,shell,程序或,shell,命令文件，又被称为,shell script,。当这个文件被运行时，,shell,就会像执行输入命令那样一条条的自动执行文件里保存的命令。,13.1.1 MINIX,的组成结构,2.,源代码组织方式,MINIX,的源代码在逻辑上一般分为两个目录,/,usr,/include,和,/,usr/src,/(,为叙述方便，将简记为,include/,和,src,/),。,13.1.1 MINIX,的组成结构,程序在内存中运行时，各个模块的分布情况,:,13.1.2,头文件,在编程的过程中，有许多常量、宏以及结构类型的定义会经常被不同文件用到，通常把这些定义按照某种规则或需要组织在一起，于是就构成了头文件（,header,）,以后缀,.h,标识。,1, 公共头文件,在头文件中，有一些是完全通用的，它们不是被源文件直接引用，而是被其它的头文件引用。,MINIX,中的三个主要部分：内核、文件系统和内存管理分别对应有三个主控头文件,src/kernel/kernel.h,、,src/mm/mm.h,和,src/fs/fs.h,。,13.1.2,头文件, 在,include/,目录下，有三个被主控目录包含的头文件：,ansi.h,：用来测试编译器是否符合标准,c,的规定。整个文件的构造以,#,ifndef_ANSI_H,为开始，并以,#,endif,结束；,limits.h:,定义了一些基本的数据值的大小，比如：数据类型中的整形数所占位数的值等；,errno.h,:,包含了全局变量,errno,返回的错误码，用于系统调用失败时通知用户程序。,13.1.2,头文件,include/sys,目录下主要的头文件。,由于同一种数据类型在,16,位和,32,位处理器上所占的字长可能存在差异，因而可能因错误理解在特定情况下使用的基本数据结构而引发问题。,在文件,types.h,中定义了许多,MINIX,使用的数据类型及其相关的数值，从而可以避免这种情况的发生。,通常紧跟在,types.h,之后的是,ansi.h,头文件，它们都被所有主控头文件包含。,13.1.2,头文件,2,专有头文件,除了公共头文件之外，在,include/,minix,中存放的是在任何平台上实现,MINIX,都需要的头文件，而,include/,ibm,中则存放了在,IBM,兼容机上实现,MINIX,所需的数据结构和宏的定义。,在,include/,ibm,目录中主要有两个文件：,diskparm.h,文件由软盘系统任务使用；,partition.h,定义了,IBM,兼容机上的硬盘分区表和有关常量。,在,/,minix,/,目录中首先要注意到的是,config.h,文件，它被所有主控头文件所包含，且必须列在第一位。,第三个要提到的头文件是,type.h,，它被主控头文件所包含，定义了很多重要的类型及其数量值。,13.1.2,头文件,消息由如下几个部分组成：,m-source,域：用于指明消息的发送进程；,m-type,域：用于标识出消息的类型；,数据域：包括定义为整型,(,int,),或长型,(long),的整数、字符、字符串、字符数组、指针以及函数等。,13.2,进程,13.2.1,概述,计算机中的所有软件，被组织成一定的顺序运行，这就形成了进程的概念。,在,MINIX,和进程有关的部分主要负责解决以下的问题：,怎样创建和终止一个进程，并使之处于合适的队列中（进程管理）；,怎样有效调度众多进程，使之在兼顾充分利用资源和进程特权级、优先级要求的同时保证有序运行（进程调度），这里也包括了对中断引起的进程状态改变的处理（中断处理）；,进程之间怎样交互（进程通信）等等。,13.2.1,概述,1, 进程管理,整体来看所有用户进程构成一棵大的进程树，初始化进程,init,是它们的根节点,:,计算机开机以后，固化在硬件的程序从引导盘（可以是硬盘或软盘）上将第一道第一扇区（也就是所谓的,0,磁道）中的内容读入内存并从开始执行。,在系统装入完成前，所有涉及磁盘,I/O,的操作都要由,boot,完成。,装入完成后，,boot,的使命就结束了。接下来就由内核启动各项任务，然后就是,MM,、,FS,以及位于第三层的其它服务纷纷登场。,在用户成功登录以后，可执行文件,login,将执行用户命令解释器,shell,，,shell,负责接收用户命令，为每一条命令的执行创建一个子进程。,13.2.1,概述,Shell,接收命令创建进程的大概框架如下所示：,13.2.1,概述,2.,进程调度,中断在操作系统中具有特殊的意义，它保证多道程序系统能够连续工作。,MINIX,的底层软件采用将中断转换为消息的方法来隐藏中断。,每次处理中断时，都需要通过进程调度来确定哪一个进程重新获得运行机会。,MINIX,中的进程调度采用三级排队系统，分别对应第,2,、,3,、,4,层。进程所处层次越低其优先级越高，,2,、,3,层的进程可以一直运行到其自己阻塞，而第四层的用户进程则采用时间片轮转调度。,13.2.1,概述,3.,进程通信,MINIX,以消息来实现进程间的通信，并且对消息的发送存在一些限制：每个进程,(,任务,),可以和同层或下一层中的进程,(,任务,),通信，但用户进程不能直接和,I/O,任务通信。,MINIX,中发送和接收消息主要通过三条原语：,send(a,&message):,向进程,a,发送一条消息；,receive(b,&message):,从进程,b,处接收一条消息；,send_rec(c,&message,):,发送消息给进程,c,，并等待它的回答。,这些原语都可以通过,c,库函数来调用，第二个参数,&message,表示的是消息数据的内存地址，消息将从发送者复制到接收者，对于第三条原语来说，应答的消息将覆盖在原消息的地址上。,13.2.2,具体实现,1.,系统启动与初始化,开机后，硬件（实际上指的,ROM,中的一个程序）读取引导盘的第一个扇区，执行其中的代码，这部分代码又引导,boot,程序的执行。,执行,boot,的目的是得到操作系统的映象。这个映象保存在位于,/,minix,/,目录下的文件中，是由内核、,MM,、,FS,和,init,被分别编译后，再将它们链接在一起得到的。,Boot,本身并不是操作系统的组成部分，在操作系统被装入后，控制权即被转移给内核的有关代码。,13.2.2,具体实现,系统启动和初始化流程,:,13.2.2,具体实现,2.,中断处理,中断处理是由硬件和软件共同完成的，为了避免对于烦琐硬件细节（主要是,CPU,的内部工作原理）的过多涉及，我们只简单介绍硬件完成的工作，主要侧重于软件的处理过程。,13.2.2,具体实现,硬件中断和软件中断的处理流程,:,13.2.2,具体实现,3.,进程调度,进程的调度相对来说比较简单，对照第,2,、,3,、,4,层建立了三个运行进程队列。,在头文件,proc.h,中定义了两个数组,rdy_head,和,rdy_tail,它们的作用就是分别指向队列的队首进程和队尾进程。只有就绪进程才参与排队，而被阻塞的和取消的进程，则不会出现在这三个运行进程队列中。,13.2.2,具体实现,4.,进程通信,因为中断处理到了最后，也归结到进程间通过消息传递信息，所以我们将从处理中断的两个函数开始，了解,MINIX,中的进程间通信过程。,在,3.6.2,节中曾经介绍过三种进程间利用消息通信时所采用的同步机制，,MINIX,中采用的第一种组合方法，“阻塞发送，阻塞接收”，也就是所谓的会合原理。,13.2.2,具体实现,与进程通信有关的函数和过程都在文件,proc.c,中。,interrupt,函数负责将硬件中断转换成消息，并把这条消息发送给与该设备对应的系统任务，它将按顺序完成以下工作：,通过判断变量,k_reenter,，来检查在接收当前中断时是否有中断正在处理。若是，则将当前中断放入中断队列排队，等待以后调用,unhold,操作处理；,检查目标任务是否正在等待中断，若是则发送消息，否则就将该任务的,p_int_blocked,标志设置为,1,；,完成消息的发送：向目标任务消息缓冲区中的,resourc,域和,type,域写入内容，并将该任务的,receive,标志复位，解除该任务的阻塞，当消息复制完成后，任务就被调度执行。,13.2.2,具体实现,处理软中断的工作是由,sys_call,完成的。和硬件中断不同，软中断的消息来源和去向更加复杂，因此要利用,proc.h,中提供的两个宏,isoksrc_dest,和,isokprocn,协同工作，检查并保证消息的源进程和目标进程都是合法的。,检查通过后，若需要发送消息，则调用,mini_send,需要接收消息则调用,mini_rec,。这两个负责发,/,收的进程是,MINIX,消息传递机制的核心，,Mini_send,的参数主要有三个：调用的进程名、目标进程名以及消息地址的指针。在发送之前，它还需要先进行以下的测试：,宏,isuserp,测试参数,caller_ptr,；,检查确认目标进程不是一个空进程，否则就报错；,进行死锁测试；,上述测试通过后将进行最重要的测试：检验目标进程表项中,p_flags,域中的,receiving,标志，以判断该进程是否在等待消息,.,13.3 I/O,任务,13.3.1 I/O,任务概述,I/O,系统在,MINIX,中是必不可少的，它要为,I/O,设备配备驱动程序（实际上是一个通信程序）以实现设备与上层之间的通信和交互，同时负责处理由,I/O,操作引起的中断。,此外，由于有些,I/O,设备是一种独占性的资源，对它的使用有可能引起死锁，这也是,I/O,系统要考虑的。,13.3.1 I/O,任务概述,I/O,层次及其功能,:,进程利用消息实现数据读取,:,13.3.1 I/O,任务概述,前面我们多次提到进程通过消息通讯，但用户进程是不能直接和,I/O,进程通信的。,进程向,FS,发送消息请求一个文件，而,FS,则向设备驱动程序（磁盘驱动）发送消息来请求该文件的数据块，,FS,也是唯一向设备驱动程序发送消息的进程。,13.3.1 I/O,任务概述,MINIX,中对死锁的处理比较简单，即忽略它（鸵鸟算法）。但是，这不意味着放任死锁的发生。,MINIX,中，除了,FS,启动时可以向,MM,发送“请求”消息报告,RAM,盘大小而外，其它任何情况下都不允许,FS,向,MM,发送“请求”消息。,因为有可能存在这样的情况：执行,EXEC,调用时，,MM,向,FS,发送消息试图执行可执行文件，若此时,FS,忙，则,MM,阻塞，此后若,FS,也试图向,MM,发送消息，则,FS,也阻塞，形成循环等待从而发生死锁。,