1.2 操作系统的形成与发展
1.2.1 顺序处理（手工操作阶段）
早期的计算机（20世纪的40年代～50年代中期），程序员直接与计算机硬件打交道，没有操作系统。计算机由CPU、主存、某种类型的输入设备（卡片输入机）、一台打印机，以及装有显示灯、乒乓开关的操作控制台组成。用机器代码或汇编或高级语言编写的程序通过输入设备装入计算机，再由程序员或操作员从控制台上通过设置乒乓开关启动汇编或编译或装入程序运行等。程序处理过程中，若出现错误，则通过控制台上的指示灯指示错误产生的条件并停止运行。经修改后可再次运行。如果程序正常完成，将输出结果送打印机打印。然后，将计算机转让给另一个程序员使用。
早期的这种操作方式，操作员或程序员要花费大量时间操作计算机，导致系统昂贵资源的无效使用，这主要由下面两方面问题造成。
1.人工负责计算机的调度
计算机各资源的使用是通过一张纸登记的。一般的做法是，各用户说明他大约使用计算机多长时间，由机房负责人为他安排上机时间。如果一个用户预约1 小时，结果用45 分钟完成了，剩余的15 分钟被浪费了。另一方面，若用户程序运行过程中出现问题，由于要检查错误和解决问题，被迫暂停，等待下一次进行预约后才能运行。
2.人工负责编排作业的运行顺序
程序，又叫作业。在操作系统中，通常把用户在一次算题过程中要求计算机所做工作的集合叫做一个作业。以现在执行一个作业为例，用户在计算机上进行算题时，通常要经历以下几步：
① 采用某种语言按算法编写源程序，将源程序通过某种手段（如卡片输入机等）送入计算机；
② 调用某语言的汇编或编译程序，对源程序进行汇编或编译，产生目标代码程序；
③ 调用链接装配程序，将目标代码及调用的各种库代码连接装配成一个可执行程序；
④ 装入可执行程序和运行时所需数据，运行该程序并产生计算结果。
由此可见，一个算题任务的完成通常要经历建立、编译、连接装配和运行，才能得到计算结果。把这些相对独立的每一步骤叫做作业步。一个作业的各作业步之间总是相互联系的，在逻辑上是顺序执行的。下一作业步能否执行，完全取决于上一作业步是否成功完成。比如，若汇编或编译失败，则不可能进行连接装配。
一次运行可能只是编译一个程序。为此要将编译程序和一个用高级语言编写的源程序装入主存，保存被编译好的目标程序。然后连接和装入目标程序和公共库函数。其中，每一步都涉及安装和卸下磁带或卡片叠等。如果在一次处理中出现错误，用户不得不返回到编排序列的开始重新运行，因此，大量时间用在编排程序运行上了，导致系统效率极低。这种操作方式叫顺序处理。
1.2.2 简单的批处理系统
早期计算机造价昂贵，上述的那种人工调度和编排作业的方式浪费了大量的计算机时间。简单的批处理系统（Simple Batch System）正是在20 世纪50 年代后期到60 年代中期，伴随第二代计算机的出现而研制成功的。
简单的批处理模式的中心思想是使用一个监控程序软件，各个用户将各自作业的卡片叠或纸带交给机房的操作员，再由操作员将这些作业的卡片或纸带按序成批地放在一个输入设备上，由监控程序自动控制输入设备将各个作业读入到磁带上。之后，监控程序按照顺序自动地把一个个作业装入内存进行处理。
监控程序常驻主存，工作非常简单，就是将CPU的控制权自动地从一个作业转换到另一个作业。很清楚，手工操作阶段的两个问题已得到圆满解决：一方面由监控程序处理调度问题，各作业以尽可能快的速度执行，从而不存在空闲的机器时间；另一方面由监控程序处理作业编排问题。为了使监控程序能代替用户完成对作业的编排控制，系统向用户提供了一套作业控制命令。每当用户提交作业时，将对作业的控制意图用作业控制卡或作业说明书的形式提交给监控程序。下面是监控程序使用的几个典型的控制卡。控制卡以“$”开头，以区别其他一般的卡片。
控制卡 功能
$JOB启动一个新程序
$FORTRAN调用FORTRAN编译程序
$LOAD调用装入程序，装入要执行的程序
$RUN运行程序
$END作业结束卡
图1.2给出了以卡片形式提交的一个用FORTRAN语言编写的程序及程序所用数据，以及控制作业执行的控制指令卡。
图1.2 一个典型的输入作业的结构
为了执行这个作业，监控程序首先读入控制 卡 $FORTRAN，从外存磁带上装入FORTRAN编译程序。编译程序翻译紧跟其后的FORTRAN源程序为目标代码，并存入主存或外存磁带上。如果它存入主存，这个操作叫“编译、装入和执行”。如果它存入磁带上，只编译不装入执行，那么当要执行程序时，还需要读入一个$LOAD卡。监控程序读入该卡片后，通过执行装入程序将目标程序及其调用的标准函数装入主存。接着读$RUN卡，启动执行用户程序。在用户程序执行期间，用户程序的每个输入指令都引起读一张数据卡。一个用户作业的成功或错误完成，都引起监控程序扫描输入卡，直到遇到下一个作业的控制卡$JOB为止。
当计算机运行中发生错误或意外时，监控程序通过控制台打字机输出信息向操作员报告。这种输出信息不仅比亮灯显示所表达的更为丰富，而且便于操作员理解。总之，用这种半自动方式控制计算机不仅提高了效率，而且方便了使用。这种简单的批处理在硬件结构上有两种不同的控制方式。
1.早期的联机批处理
早期的联机批处理的硬件控制方式是：作业的输入、计算和输出都是在CPU直接控制下进行的。这样，在输入或输出过程中，主机的速度降低为慢速的输入或输出设备的速度。图1.3给出了联机批处理的模型。
图1.3 早期的联机批处理模型
2.早期的脱机批处理
为了提高CPU的利用率，使CPU从慢速的外设控制中解脱出来，引入了早期的脱机批处理方式。该方式下，系统增设一台小型卫星机专门用来控制外部设备的输入/输出。其模型如图1.4所示。
图1.4 早期的脱机批处理模型
在这种模型中，小型卫星机的作用如下。
① 把卡片输入机上的作业逐个地记到输入磁带上，以便主机执行。
② 控制打印机输出由主机送入输出磁带上的作业的执行结果。
由此可见，采用这种脱机技术后，主机的所有输入/输出都是通过磁带进行的，而且主机与慢速外部设备可以并行，从而提高了主机运行效率。从20世纪50年代后期到60年代中期，脱机批处理运行得相当成功。脱机技术的实质是用快速的输入/输出设备代替慢速的设备。
1.2.3 多道成批处理系统
1.多道程序设计（Multiprogrammed System）
进入20世纪60年代中后期，计算机的硬件有了突飞猛进的发展，产生了硬件通道、中断和缓冲技术，从而使得计算机在组织结构上发生了重大变革。原先以CPU为中心的体系结构，转变为以主存为中心，其结构模型如图1.5所示。
图1.5 多道程序系统的计算机模型
所谓通道，实际是一种比CPU速度较慢、价格较便宜的硬件。它是比小型卫星机更经济的、独立于CPU的、专门用于控制输入/输出设备的I/O处理机。通道连接着主存和外设，具有与主存直接交换数据的能力。当需要输入/输出时，CPU只要向通道发一个命令，通道就独立地控制相应的外部设备完成指定的传输任务。通道通过中断机构向CPU报告其完成情况。这样，利用缓冲技术，通道控制输入/输出传输任务，使CPU与外部设备的操作可以更充分地并行执行，提高了CPU的利用率。有关通道、中断和缓冲技术，将在本书后面章节介绍。
简单的批处理系统提供了作业自动定序处理。通道和中断的出现，使CPU摆脱了对慢速设备的控制，从而提高了系统的处理效率。但由于主存只存放一个用户作业，当作业请求输入/输出时，CPU空闲等待输入/输出完成。如果能在主存同时放多个用户作业，当一个作业等待数据传输时，CPU转去执行其他作业，从而保证CPU与系统中的输入/输出设备并行操作。
这种在主存中同时存放多个作业，使之同时处于运行状态的程序设计方法，叫做多道程序设计。对于一个单处理机的系统来说，“多作业同时处于运行状态”是从宏观上理解的，其含义是指每个作业都已开始运行，但都尚未完成。而从微观上看，各个作业是串行执行的。在任何特定时刻，只有一个作业在处理机上运行。
引入多道程序设计技术的根本目的是提高CPU的利用率，充分发挥系统设备的并行性。这包括程序之间、CPU与设备之间、设备与设备之间的并行操作。为了更好地理解引入多道程序的好处，下面用两个例子进行说明。
（1）主存只有一道程序。这个程序每处理文件中的一个记录，平均需要执行100 条指令。假定读一个记录需0.0015 秒，执行100 条指令需0.0001 秒，写一个记录需0.0015秒，则
平均处理一个记录的时间：0.0015+0.0001+0.0015=0.0031（秒）
处理一个记录CPU的利用率：
处理机执行100条指令时间/平均处理一个记录的时间=0.0001 / 0.0031=3.2%
由这个例子可看出，处理一个记录时，CPU的利用率仅为3.2%。也就是说，CPU有96.8%的时间在等待I/O设备进行记录的读和写，这显然是对CPU的极大浪费。
（2）主存同时放三个程序。当主存容量足够大时，为提高CPU的利用率，应在主存放足够多的作业，以便当一个作业等待I/O时，处理机转去执行其他作业。假设一个计算机系统，它有256K主存（不包含操作系统）、一个磁盘、一个终端和一台打印机，主存装有三个作业，分别命名为JOB1、JOB2、JOB3，它们对资源的使用情况如表1.1所示。
表1.1 三个作业的执行特点
由表1.1可见，作业2主要使用终端进行作业的输入，作业3主要使用磁盘和打印机。JOB2和JOB3需要较少的CPU时间。
对于简单批处理，这些作业将按顺序执行。作业1运行5分钟完成，作业2等待5分钟再用15分钟完成。20分钟后，作业3开始执行。30分钟后三个作业全部完成。
若采用多道程序设计技术，让三个作业并行运行。由于它们运行中几乎不同时使用同类资源，故三个程序可同时运行。在作业1 进行计算的同时，作业2 可在终端上进行输入/输出，作业3使用磁盘和打印机。这样，作业1仍需5分钟完成，但在作业1结束时，作业2 已完成三分之一，而作业3 已完成一半。这样，这三个作业在15 分钟内将全部完成。显然整个系统处理效率明显提高。
为了更好地理解引入多道程序的好处，下面先引入衡量批处理计算机系统性能指标的几个重要概念：
● 资源利用率：指在给定时间内，系统中某一资源，如CPU、存储器、外部设备等，实际使用的时间所占的比率。显然，要提高资源利用率，就必须使资源尽可能忙碌。
● 吞吐量（Throughput）：指单位时间内系统所处理的信息量。它通常以每小时或每天所处理的作业个数来度量（这里以小时作为度量单位）。
● 周转时间（Turnaround Time）：指从作业进入系统到作业退出系统所经历的时间。即作业在系统中的等待时间加运行时间。而平均周转时间是指系统运行的几个作业周转时间的平均值。
依据上述定义的三个概念，分别计算上述三个作业单道和多道运行时，处理机和存储器等资源的利用率：
① 单道运行时，只有JOB1占有处理机，三个作业运行完成需要30分钟。
处理机的利用率为：5 / ( 5+15+10 )=17%
存储器的利用率为：( 50 / 256+100 / 256+80 / 256 ) / 3=30%
② 多道时，15分钟三个作业都完成，其中处理机使用5分钟。
处理机的利用率为：5 / 15=33%
三个作业共享主存，主存利用率为：( 50+100+80 ) / 256=90%
三个作业单道运行和多道运行时的各资源利用率见表1.2中。
表1.2 多道程序与单道程序时平均资源利用率情况对比
由表可知，多道程序运行，使得系统资源的利用率、吞吐量和作业的平均周转时间大大优于单道程序运行，系统性能的改善是明显的。因此，将多道程序设计技术用于批处理系统就构成了多道成批处理系统。
2.多道程序设计技术的实现
与简单批处理系统相比，多道批处理的实现必须解决好以下三个问题：
（1）存储器的分配和存储保护。采用多道程序设计技术，主存储器为几道程序所共享。因此，必须提供存储分配手段，使各个程序在主存拥有自己的一个区域。同时各程序在运行时，硬件必须提供必要的存储保护手段，限制它们只能正确地访问自己所占的区域，以避免相互干扰和破坏。特别是不能破坏操作系统。否则，整个系统将无法运行。
现在的微型机中，有些系统，如MS-DOS没有存储器保护技术，致使计算机的病毒泛滥成灾，系统遭受严重破坏。
另外，随着程序道数的不断增加，出现了主存容量不够用的问题。为此，必须解决存储器的扩充技术。这就是以后将要介绍的覆盖与交换技术，以及虚拟存储技术等存储器管理技术。
（2）处理机的管理和调度。在单处理机系统中，系统中的多道程序都要竞争使用处理机，处理机管理的主要任务就是实施处理机的分配和调度，以便解决好多道程序之间的转接和有效的运行。现代的计算机系统虽然广泛采用多CPU技术，但使用最多的还是集中式处理系统，即系统中只有一个功能强大的主CPU，并由它完成系统主要的处理任务。因此，处理机管理主要涉及的是对处理机的分配调度策略、实施具体的分配等问题。
（3）系统其他资源的管理和调度。采用多道程序设计技术，系统的资源为多道程序所共享。系统资源除了上面提到的存储器、处理机之外，还有外部设备资源和一些软件即文件资源。因此，系统也要解决好这些资源的管理和调度问题，以使各道程序都能有条不紊地运行下去。
多道程序设计技术的出现，标识着操作系统渐趋成熟，具备了相应的处理机管理、存储器管理、外部设备和文件管理等功能。
1.2.4 分时系统
批处理系统使用多道程序技术后卓有成效地提高了系统资源的利用效率。但这样的系统仍存在以下几个问题：
（1）不能直接控制作业运行。用户一旦把其作业提交给计算机系统，便失去了对作业的控制能力。对于许多作业，如事务处理和一些短小作业的修改，用户希望能提供与系统交互的能力，以便直接控制作业的运行。
（2）作业的周转时间太长。在批处理系统中，用户提交的作业通常要经几小时甚至几天的延迟才能得到所需的结果。这对于仅需要计算时间很短的作业是不利的。
现在，交互计算设施特别是微型计算机已经满足这种要求，但在20世纪60年代这种情况是不可能的，那时大多数计算机很庞大，价格非常昂贵，代之的是开发了分时系统（Time-Sharing System）。
在分时系统中，一台计算机系统连接有若干台远近终端（通常终端是带有CRT显示的键盘输入设备），多个用户可以同时在各自的终端上以交互方式使用计算机。分时系统又叫做多用户多任务操作系统。
1.分时概念
所谓分时，在引入多道程序技术时就已经有了这个概念，它是以CPU与通道、通道与通道、通道与设备并行操作作为条件的。而并行操作又是以分时共享系统资源为基础的：CPU与通道并行是通过分时使用主存和数据通路等来实现的；通道与通道并行是分时使用CPU、主存及通道的公用控制部分；同一通道控制的多台I/O设备又是分时共享使用主存、通道等的。这种分时是分时使用硬件，属于硬件设计技术。
这里的分时，是指将CPU的单位时间（比如1秒钟）划分成若干个时间段，每个时间段称为一个时间片（Time slice），并按时间片轮流把CPU分配给各联机用户使用，这样，每个用户都能在很短时间内得到计算机的服务，彼此感觉不到别的用户存在，好像整个系统为他独占。这样的系统叫分时系统。
早期的分时系统之一是兼容的分时系统（CTSS），与后来的分时系统相比，CTSS非常简单，它的操作控制很容易理解。当CPU的控制分配给一个交互用户时，用户的程序和数据装入主存，每0.2s（时间片）产生一个时钟中断。每个时钟中断产生时，操作系统获得控制，将处理机分给另一个用户。这样，以规定的间隔，当前用户被抢占，另一个用户被装入。为了使被抢占用户以后恢复运行，它的程序和数据被写到磁盘后才装入新用户的程序和数据。利用交换技术，使各个作业在主存与外存之间换入换出，以保证向用户提供合理的响应时间。将多道程序技术应用于分时系统就是功能完善的多道分时系统。
2.分时系统的特点
分时系统允许多个用户同时共享计算机，它具有以下几个特点：
（1）同时性。若干个终端用户可同时使用计算机。
（2）独立性。各用户之间彼此独立地占有一台终端工作，互不干扰。
（3）交互性。用户从终端键盘上输入各种控制作业的命令，系统响应和处理这些命令，并将处理结果输出显示，用户根据系统显示结果再继续输入。亦即采用一问一答形式控制作业运行。
（4）及时性。用户的请求能在较短时间内得到响应。分时系统的响应时间（response time）是指从用户发出终端命令到系统响应并开始进行应答所需的时间，是衡量分时系统的主要性能指标。它可以简单地表示为T=nq，其中T代表响应时间，n代表同时上机的用户数，q代表时间片。通常的响应时间为2～3s。显然，通过修改n和q，可以获得合理的响应时间。
上述的4个特点为程序设计人员提供了比较理想的开发环境，他们可以直接使用计算机，边开发，边调试，边思考，边修改，从而显著地提高了程序开发、调试的效率。
批处理系统与分时系统又称为作业处理系统。用户是以作业为单位提交系统进行处理的。分时系统与批处理系统是为了适应不同需要而开发的：
● 批处理系统的自动化程度高，通过将各种不同类型的作业进行合理搭配，大大提高系统资源的利用效率。该系统适合处理的作业具有如下性质：比较成熟的、需要耗费较长处理时间的大型作业。
● 分时系统的目标是对用户请求的快速响应。该系统适合处理短小作业。因此，它广泛应用于各种事务处理，并为进行软件开发提供了一个良好环境。
1.2.5 实时系统
计算机不仅能用于科学计算、数据处理等方面，也广泛地用于工业生产的自动控制，军事上的飞机导航、导弹发射，各种票证的预订、查询，银行系统的借贷，以及情报检索等系统。通常把上述系统称为实时控制和实时信息处理系统，这两个系统统称为实时系统（Real-Time System）。
所谓实时，是指计算机对随机发生的外部事件能做出及时的响应和处理。这里的及时是指系统对特定输入做出反应所具有的速度，足以控制发出实时信号的那个设备。
实时系统不同于作业处理系统，它不以作业为处理对象，而以数据或信息作为处理对象，它不接收用户作业，只有几个由外部事件触发的任务。实时系统是一个专用系统，主要用于实时过程控制和实时信息处理。用于实时控制的计算机系统要确保在任何时候，甚至在满负荷时都能及时响应。因此，设计实时系统时，首先要考虑响应的实时性，其次才考虑资源的利用率。
实时操作系统能够在限定的时间内执行完所规定的功能，并能在限定的时间内对外部的异步事件做出响应。执行完规定的功能和响应外部异步事件所需时间的长短，是衡量实时操作系统实时性强弱的指标。有两种类型的实时系统：硬实时和软实时。在硬实时系统中，系统的所有可能的延迟是一定的。对于关键的任务，必须在指定时间范围内完成，否则，可能出现不可预知的错误和危险。在软实时中，即使任务没有在规定时间内完成，也还是允许的。例如，信息查询、多媒体和虚拟现实就属于这一类。
1.实时系统的主要特点
（1）实时性。由于实时系统接收来自现场的事件，对这种事件的响应速度直接影响到现场过程控制的质量或服务的质量。与分时系统相比，实时系统对响应时间有更严格的要求。分时系统的响应时间通常是以人们能够接受的等待时间来确定的（2～3s），而实时系统则是以被控制过程或信息处理时能接受的延迟来确定的，通常可能是秒的数量级，也可能是毫秒级甚至微秒级。也即系统的正确性不仅依赖于计算的逻辑结果的正确性，而且依赖于结果产生的及时性。
（2）可靠性。实时系统要求硬件和软件措施有非常高的可靠性。因此实时系统要具有容错能力，往往采用双工机制。一台作为主机，用于实时现场控制或实时信息处理，另一台作为后备机与主机并行运行。一旦主机发生故障，后备机便立即代替主机继续工作，以保证系统不间断运行。
（3）确定性。可确定性主要取决于系统响应中断的速度，其次取决于系统是否有足够的能力在要求的时间内处理完指定的请求。实时性通常与确定性密切相关。实时性是指系统内核应该保证系统尽可能快地对外部事件产生响应，而确定性是指系统对外部事件的响应性的最坏时间是可以预知的。
2.实时系统的功能
（1）实时时钟管理。实时系统的主要设计目标是提供对实时任务进行实时处理的能力。通常，实时任务分两类：一类是定时任务，它是根据用户规定的时间启动该任务的执行，并按照规定的循环周期重复启动执行该任务。另一类是延迟任务，这类任务是推迟一规定的时间后再执行。这两类任务的控制时间，是由实时时钟进行计时控制的。
（2）简单的人机对话。由于实时系统是专用系统，其交互能力不及分时系统，它一般仅允许与系统中的特定实时任务进行有限制的交互能力，仅允许操作员通过终端访问有限的专用软件，不允许对现有系统软件进行修改。
（3）过载处理。虽然实时系统设计时，考虑了系统对所有实时任务的实时处理能力，但由于被处理任务进入系统时带有很大的随机性，使得某一时刻系统中的任务数超过了它的处理能力，而产生过载。为此，系统应按照任务的紧急程度排成一个队列，优先处理更紧急的任务，以保证系统在即使出现过载时，仍能正常运行。
1.2.6 嵌入式系统
嵌入式系统（Embedded System）是面向用户、产品、应用的系统，可以定义为以应用为中心、以计算机技术为基础、软硬件可裁剪、适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。凡是将计算机的主机嵌埋在应用系统或设备之中，不为用户所知的计算机应用方式，都是嵌入式应用。嵌入式系统运行的几乎都是实时操作系统。
1.嵌入式系统的技术特点
嵌入式处理器的应用软件是实现嵌入式系统功能的关键。软件要求固化存储，具有高质量、高可靠性，操作系统的高实时性是基本要求。制造工业、过程控制、通信、仪器、仪表、汽车、船舶、航空、航天、军事装备、消费类产品等，均是嵌入式计算机的应用领域。
2.嵌入式系统的功能
嵌入式系统是形式多样、面向特定应用的软硬件综合体，其硬件和软件都必须高效地进行量体裁衣式设计。嵌入式系统的运行环境和应用场合决定了嵌入式系统具有区别于其他操作系统的一些特点。
大多数嵌入式操作系统通常是一个多任务可抢占式的实时操作系统核心，只提供基本的功能，如任务的调度、任务之间的通信与同步、主存管理、时钟管理等。其他的应用组件，如网络功能、文件系统、图形用户界面（GUI）系统等均工作在用户态，以函数调用的方式工作。因而系统都是可裁剪的，用户可以根据自己的需要选用相应的组件，构造自己的专用系统。