独立任务最优调度 C++程序

实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容1、①设a[0:n-1]是已排好序的数组。

请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

②写出三分搜索法的程序。

三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。

如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。

如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。

上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。

五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。

（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。

六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

七、附录：（源代码）二分搜索法：#include<iostream.h>#include<stdio.h>int binarySearch(int a[],int x,int n){int left=0;int right=n-1;int i,j;while(left<=right){int middle=(left+right)/2;if(x==a[middle]){i=j=middle;return 1;}if(x>a[middle])left=middle+1;else right=middle-1;}i=right;j=left;return 0;}int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9};int n=10;int x=9;if(binarySearch(a,x,n))cout<<"找到"<<endl;elsecout<<"找不到"<<endl;return 0;}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

1、（C）是长期存储在计算机内的有组织、可共享的数据集合。

A.数据库管理系统B.数据库系统C.数据库D.文件组织2、在手工管理阶段，数据是（B）A.有结构B.无结构C.整体无结构，记录有结构D.整体结构化的3、在文件系统管理阶段，数据（B）A.无独立性B.独立性差C.具有物理独立性D.具有逻辑独立性4、在数据库系统管理阶段，数据是（D）A.有结构的B.无结构的C.整体无结构，记录内有结构D.整体结构化5、数据库系统管理阶段，数据（D）A.具有物理独立性，没有逻辑独立性B.具有物理独立性和逻辑独立性C.独立性差D.具有高度的物理独立性和一定程度的逻辑独立性6、数据库系统不仅包括数据库本身，还要包括相应的硬件、软件和（D）A 数据库管理系统B数据库应用系统C相关的计算机系统D各类相关人员7、DBMS通常可以向（B）申请所需计算机资源。

A数据库B操作系统C计算机硬件D应用程序8、在DBS中，DBMS和OS之间的关系是（D）A .并发运行B.相互调用C. OS调用DBMSD. DBMS调用OS9\数据库管理系统（DBMS）是（C）A一个完整的数据库应用系统B一组硬件C一组系统软件D既有硬件，又有软件10、描述数据库全体数据的全局逻辑结构和特性是（A）A模式B内模式C 外模式D用户模式11、（D）不是DBA数据库管理员的职责。

A完整性约束说明B定义数据库模式C数据库安全D数据库管理系统设计12、关系数据库的数据及更新操作必须遵循（D）等完整性规则。

A实体完整性和参照完整性B参照完整性和用户定义完整性C实体完整性和用户定义完整性D实体完整性、参照完整性和用户定义完整性13、现实世界中事物的特性在信息世界中称为（D）A实体B键C记录D属性14、E-R模型用于建立数据库的（A）A概念模型B结构模型C物理模型D 逻辑模型15、数据模型的三要素是（D）A外模式、模式和内模式B关系模型、层次模型、网址模型C实体、属性和联系D数据结构、数据操作和完整性约束16、设某学校中，一位教师可讲授多么课程，一门课程可由多位教师讲授，则教师与课程之间的联系是（D）A一对一联系B一对多联系C多对一联系D多对多联系17、逻辑模式（A）A有且仅有一个B最多只能有一个C至少两个D可以有多个18、数据独立性是指（C）A用户与数据分离B用户与程序分离C程序与数据分离D人员与设备分离19、在数据库三级模式间引入二级映像的主要作用是（A）A提高数据与程序的独立性B提高数据与程序的安全性C保持数据与程序的一致性D提高数据与程序的可移植性20、在数据库中，产生数据不一致的根本原因是（D）A没有严格保护数据B数据冗余量太大C未对数据进行完整性控制D数据冗余21、关系数据库建立在关系数据库模型基础上，借助（A）等概念和方法来处理数据库中的数据。

操作系统的基本类型操作系统（Operating System，简称 OS），通常也称作系统软件，是控制计算机硬件与软件资源的计算机程序，也是计算机系统中最基本、最重要的系统软件之一。

操作系统具有宏观掌控计算机各种资源的功能，包括管理处理器、存储器、输入输出设备、文件系统等，可以大大提高计算机的效率和安全性。

操作系统按照其功能和特征可以分为以下几种类型：一、单任务操作系统单任务操作系统（Single Tasking Operating System），指的是一次只能处理一个任务的操作系统。

在单任务操作系统中，只有一个应用程序能在同一时间运行，其他程序必须等待当前程序结束才能启动。

单任务操作系统中系统资源分配的方式往往是先到先服务（First Come First Serve），即当一个进程到来后，系统会保留一定的资源给它，并等待进程完成后才为下一个进程分配资源。

单任务操作系统简单、易用、稳定，往往运行速度较快，适合于单一应用、资源受限的环境。

目前单任务操作系统已经很少使用，被多任务操作系统取代。

典型的单任务操作系统包括 MS-DOS、Windows 1.0。

多任务操作系统（Multi-Tasking Operating System），指的是能同时运行多个任务的操作系统。

在多任务操作系统中，每个程序都有自己的内存空间和系统资源，它们可以相互独立运行，互不影响。

多任务操作系统可根据进程优先级和任务特点，通过任务调度算法来实现多任务的分时使用。

多任务操作系统可以提高计算机的利用率，增加计算机的并发处理能力。

它适用于高负荷、多功能的环境。

操作系统分时分配资源，可以平衡各个任务之间的资源争用，提高计算效率。

目前主流的操作系统都是多任务操作系统，如微软的Windows系列、Linux、Unix等。

三、多用户操作系统多用户操作系统（Multi-User Operating System），是指多个用户同时使用同一台计算机，每个用户都可以独立地进入操作系统，并且操作系统可以为每个用户提供独立的资源和环境。

计算机操作系统试题题库及答案一、选择题1. 下列哪个不是操作系统的特征？A. 并发B. 共享C. 有序D. 异步答案：C2. 操作系统的主要功能不包括以下哪项？A. 处理机管理B. 存储器管理C. 设备管理D. 文件管理答案：D3. 下列哪种类型的操作系统用于实现多任务处理？A. 单用户单任务B. 单用户多任务C. 多用户单任务D. 多用户多任务答案：B4. 在操作系统中，进程和线程的区别是什么？A. 进程是系统进行资源分配和调度的基本单位，线程是进程的组成部分B. 线程是系统进行资源分配和调度的基本单位，进程是线程的组成部分C. 进程和线程都是系统进行资源分配和调度的基本单位D. 进程和线程没有区别答案：A5. 下列哪个进程调度算法可能会导致“饥饿”现象？A. 先来先服务（FCFS）B. 最短作业优先（SJF）C. 优先级调度D. 最高响应比优先答案：C二、填空题6. 操作系统中的进程与程序的区别是：进程是______的实例，而程序是______的实例。

答案：进程；程序7. 在操作系统中，为了解决进程之间的同步问题，通常使用______机制。

答案：信号量（Semaphore）8. 虚拟存储器的作用是扩大______，提高______。

答案：物理存储器；存储器的利用率9. 文件系统的主要功能包括：文件的______、______、______和______。

答案：创建；删除；读写；权限管理10. 设备驱动程序的作用是实现对______的______。

答案：设备；控制三、判断题11. 进程和线程是操作系统的基本单位，它们都可以独立执行程序。

答案：错误。

进程是基本单位，线程是进程的组成部分，线程可以独立执行程序。

12. 在操作系统中，所有的进程都可以并发执行。

答案：错误。

在单处理器系统中，进程不能同时执行，而是分时执行。

13. 虚拟存储器的容量仅受物理存储器的限制。

答案：错误。

虚拟存储器的容量受物理存储器和硬盘空间的限制。

C语言的多核编程与并行执行概述C语言是一种广泛使用的编程语言，可以用于开发各种类型的应用程序。

在当今计算机硬件技术的快速发展中，多核处理器已经成为主流。

多核处理器具有多个独立的CPU核心，可以同时执行多个任务。

为了充分利用多核处理器的潜力，开发人员需要使用适当的技术和编程模型来进行多核编程和并行执行。

本文将介绍C语言中的多核编程和并行执行的基本概念和技术，并提供一些实例来帮助读者理解。

什么是多核编程和并行执行多核编程是指在多核处理器上编写代码以利用多个CPU核心并行执行任务的过程。

在单核处理器上，程序的执行是线性的，即一次只能执行一个指令。

而在多核处理器上，不同的CPU核心可以同时执行不同的代码片段，从而加快程序的执行速度。

并行执行是指多个任务同时进行，每个任务在一个独立的线程中执行。

通过在不同的CPU核心上创建线程，可以实现多个任务的并行执行。

多核编程的挑战虽然多核处理器有助于提高计算机系统的性能，但多核编程也带来了一些挑战。

以下是一些常见的挑战：数据共享和同步在多核编程中，多个线程可以同时访问和修改共享的数据。

这可能导致数据竞争和不一致的结果。

为了解决这个问题，开发人员需要使用同步机制来确保线程之间的正确协同工作，例如使用互斥锁、条件变量等。

负载平衡在多核处理器上，任务的负载应该平衡在不同的CPU核心上。

如果负载不平衡，某些核心可能一直处于空闲状态，而其他核心却忙于处理更多的任务。

开发人员需要设计和实现合适的调度算法来平衡任务的负载。

可扩展性多核编程要求程序能够有效地扩展到多个CPU核心上。

如果程序的设计和实现不具备可扩展性，增加CPU核心的数量可能无法提高性能。

开发人员需要使用可扩展的算法和数据结构来实现可扩展的程序。

C语言中的多核编程技术C语言提供了一些用于多核编程的技术和库。

以下是一些常用的技术：线程库C语言提供了线程库（pthread）来创建和管理线程。

线程库提供了创建线程、销毁线程、同步线程等功能。

第一章引论1操作系统：操作系统是管理和控制计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

2管态：当执行操作系统程序时，处理机所处的状态3目态：当执行普通用户程序时，处理机所处的状态。

4多道程序设计：在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替的执行。

这些作业共享CPU和系统中的其他资源。

5并发：是指两个或多个活动在同一给定的时间间隔中进行。

它是宏观上的概念。

6并行：是指两个或多个活动在同一时刻同时执行的情况。

7吞吐量：在一段给定的时间内，计算机所能完成的总工作量。

8分时：就是对时间的共享。

在分时系统中，分时主要是指若干并发程序对CPU时间的共享。

9实时：表示“及时”或“既时”。

10系统调用：是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。

每一个子功能称作一条系统调用命令。

它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。

11特权指令：指指令系统中这样一些指令，如启动设备指令、设置时钟指令、中断屏蔽指令和清内存指令，这些指令只能由操作系统使用。

12命令解释程序：其主要功能是接收用户输入的命令，然后予以解释并且执行。

13脱机I/O：是指输入/输出工作不受主机直接控制，而由卫星机专门负责完成I/O，主机专门完成快速计算任务，从而二者可以并行操作。

14联机I/O：是指作业的输入、调入内存及结果输出都在CPU直接控制下进行。

15资源共享：是指计算机系统中的资源被多个进程所功用。

例如，多个进程同时占用内存，从而对内存共享；它们并发执行时对CPU进行共享；各个进程在执行过程中提出对文件的读写请求，从而对磁盘进行共享等等。

第二章进程和线程1顺序性：是指顺序程序所规定的每个动作都在上个动作结束后才开始的特性。

2封闭性：是指只有程序本身的动作才能改变程序的运行环境。

3可再现性：是指程序的执行结果与程序运行的速度无关。

计算机操作系统（第四版）汤小丹课后习题答案第一章1.设计现代OS的主要目标是什么？答：（1）有效性；（2）方便性；（3）可扩充性；（4）开放性。

2.OS的作用可表现在哪几个方面？答：(1)OS作为用户与计算机硬件系统之间的接口；(2)OS作为计算机系统资源的管理者；(3)OS实现了对计算机资源的抽象；3.为什么说OS实现了对计算机资源的抽象？答：OS首先在裸机上覆盖一层I/O设备管理软件，实现了对计算机硬件操作的第一层次抽象；在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。

OS通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由它们共同实现了对计算机资源的抽象。

4.试说明推动多道批处理系统形成和収展的主要动力是什么？答：主要动力来源于四个方面的社会需求与技术发展；(1)不断提高计算机资源的利用率；(2)方便用户；(3)器件的不断更新换代；(4)计算机体系结构的不断发展。

5.何谓脱机I/O和联机I/O？答：脱机I/O是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机，在外围机的控制下，把纸带或卡片上的数据或程序输入到磁带上。

该方式下的输入输出由外围机控制完成，是在脱离主机的情况下进行的。

而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。

6.试说明推动分时系统形成和发展的主要动力是什么？答：推动分时系统形成和发展的主要动力是更好地满足用户的需要。

主要表现在：CPU的分时使用缩短了作业的平均周转时间；人机交互能力使用户能直接控制自己的作业；主机的共享使多用户能同时使用同一台计算机，独立地处理自己的作业。

7.实现分时系统的关键问题是什么？应如何解决？答：关键问题是当用户在自己的终端上键入命令时，系统应能及时接收并及时处理该命令，在用户能接受的时延内将结果返回给用户。

解决方法：针对及时接收问题，可以在系统中设置多路卡，使主机能同时接收用户从各个终端上输入的数据；为每个终端配置缓沖区，暂存用户键入的命令或数据。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.17, No.11, November 2006, pp.2352−2361 DOI: 10.1360/jos172352 Tel/Fax: +86-10-62562563© 2006 by Journal of Software. All rights reserved.∗树型网格计算环境下的独立任务调度林伟伟+, 齐德昱, 李拥军, 王振宇, 张志立(华南理工大学计算机科学与工程学院,广东广州 510640)Independent Tasks Scheduling on Tree-Based Grid Computing PlatformsLIN Wei-Wei+, QI De-Yu, LI Yong-Jun, WANG Zhen-Yu, ZHANG Zhi-Li(School of Computer Science and Engineering, South China University of Technology, Guangzhou 510640, China)+ Corresponding author: Phn: +86-20-38257397, E-mail: linweiwei2004@, Lin WW, Qi DY, Li YJ, Wang ZY, Zhang ZL. Independent tasks scheduling on tree-based grid computingplatforms. Journal of Software, 2006,17(11):2352−2361. /1000-9825/17/2352.htmAbstract: Task scheduling is a fundamental issue in achieving high performance in grid computing systems.However, it is a big challenge for efficient scheduling algorithm design and implementation. In this paper, theproblem of scheduling independent tasks on tree-based grid computing platforms, where resources have differentspeeds of computation and communication, is discussed. In contrast to minimizing the total execution time, which isNP-hard in most formulations, an integer linear programming model for this problem is presented. Using the model,the optimal scheduling scheme that determines the optimal number of tasks assigned to each computing node isobtained. With the optimal scheduling scheme, two demand-driven and dynamic heuristic algorithms for taskallocation are proposed: OPCHATA (optimization-based priority-computation heuristic algorithm for task allocation)and OPBHATA(optimization-based priority-bandwidth heuristic algorithm for task allocation). The experimentalresults show that the proposed algorithms for the scheduling problem obtain better performance than otheralgorithms.Key words: task scheduling; grid computing; integer linear programming; optimal scheduling scheme; heuristicalgorithm摘要: 任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案 各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristicalgorithm for task allocation)和OPBHATA(optimization-based priority-bandwidth heuristic algorithm for taskallocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.∗Supported by the Natural Science Foundation of Guangdong Province of China under Grant No.05300200 (广东省自然基金); theGuangdong-Hong Kong Technology Cooperation Funding Scheme of China under Grant No.2005A10307007 (粤港关键领域重点突破项目)Received 2006-06-06; Accepted 2006-08-25林伟伟等:树型网格计算环境下的独立任务调度2353关键词: 任务调度;网格计算;整数线性规划;最优任务分配方案;启发式算法中图法分类号: TP393文献标识码: A随着互联网的飞速发展,利用互联网上大量计算资源的网格计算将成为解决规模庞大、复杂的问题的必由之路.要实现高效的网格计算需要处理许多复杂的问题,其中,任务调度问题是网格研究中所必须解决的一个关键问题,也是网格应用的基础.高效的任务调度策略和算法可以充分利用网格系统的处理能力,从而提高网格应用程序的性能,以便更好地利用网格资源.然而,一般网格任务调度问题已经被证明是一个NP完全问题[1],因此,它引起了众多学者的关注,成为目前网格计算研究领域中的一个焦点[2].在任务调度方面,已有人做了大量研究:最有影响的网格计算项目SETI@home[3]是采用主-从模式任务调度;文献[1,4,5]中指出,在异构网格和分布式并行计算环境下的大部分任务调度问题都是NP难题;讨论树型结构计算环境下的任务调度问题也有一些[6−9],它们都是针对特定问题的各种类型任务的调度,如文献[7,8]讨论了在分布式多层树结构下考虑任务通信延迟的可分任务调度问题;与本文的研究最相近的文献[4]讨论了在异构树型多处理器计算平台下,独立相同任务调度问题的复杂性,并证明了该问题是NP难题,因此,不存在多项式时间复杂性的算法以找到全局最优解.为了获得近优解,存在许多启发式算法[10],如Min-Min[10],Max-Min[10]、遗传算法[11,12]等.然而,本文利用线性规划建模任务调度问题,以获得最优任务分配方案来构造任务分配启发式算法.我们针对在网格资源计算能力和网络通信速度异构的树型计算网格环境下独立相同任务的调度问题进行深入研究和分析,提出将该调度问题转化为线性规划问题,并根据线性规划模型获得网格中各计算节点的最优任务分配方案,然后以最优任务分配方案为基础,构造两种动态的需求驱动的任务分配启发式算法.通过实验与其他任务分配算法的比较,所提出的任务分配算法性能优于其他算法.本文第1节给出本文讨论的问题的描述.第2节分析并给出单层树型结构网格计算平台下任务调度的线性规划模型.第3节重点给出多层树型结构网格计算平台下任务调度的线性规划模型,并分析任务调度实例.第4节给出两个基于最优任务分配方案的任务分配启发式算法.第5节对所提出算法进行实验和比较分析.最后是总结以及对未来工作的展望.1 问题描述本文研究在网络速度和网格计算节点处理能力不同的网格计算平台下的独立任务调度问题,而且该网格计算平台采用层次化树型覆盖网络模型.以树型作为网格计算环境的通信模型,可以简化网格计算的实现,降低节点通信的复杂度,因为各节点只需要负责与父亲和儿子通信,根节点到所有后代节点的路由是唯一的.而且,树型适用于许多编程范型,如主/从、RPC(remote procesdure call)、分而治之等.在树型网格计算平台中,每个网格计算节点有一个或多个儿子节点,但仅有一个父亲节点.我们考虑主/从模型(master-slave)网格任务调度问题,即任务只在根节点处理器产生,并由根节点负责传输任务给它的各个儿子节点.儿子节点接收到任务后,在开始处理任务的同时,继续转发部分任务给它的儿子节点,它接收父亲节点传输任务的同时可以转发任务给儿子,但只能给其中一个儿子节点传输任务,即服从单口模式(single-port model)[12].本文讨论任务调度问题的前提是:1) 树型异构的网格计算平台;2) 考虑任务迁移代价,即任务传输是需要时间的;3) 调度的任务是相同大小的独立任务;4) 一个任务只能由一个节点完成计算,一个计算节点只能同时执行一个任务;5) 采用单口主/从模式的任务调度;6) 所有需要调度的任务都在根节点上输入.图1给出一个由5个计算能力不同的计算节点组成树型网格计算平台下的简单任务调度示例.在该示例中:树的节点权表示节点计算能力,其值为节点计算单位任务所需的单位时间,即计算节点速度的倒数;树的边权表示节点间通信能力,其值为在节点间传输单位任务所需的单位时间,即两节点间网络速度的倒数.在这个调度示例中,在树型网格计算平台执行了5个大小相同的任务,所有这些任务都由担任Master的根节点n0来分配,同时,根节点也可以计算任务.在如图1所示右边的调度图中,垂直虚线表示单位时间,水平虚线表示计算节点,带箭头的水平线表示任务的执行,带箭头的斜线表示任务的传输.该任务调度示例服从单口模式,根节点n0在没2354 Journal of Software 软件学报 V ol.17, No.11, November 2006有完成一个任务传输之前不会启动另一个任务的传输,而且节点n 2在接收根节点n 0传送任务的同时,可以传输任务给一个儿子节点n 3或n 4,根节点n 0和节点n 2在传输任务的同时可以计算一个任务,但不能同时计算两个任务.在该任务调度示例中,调度5个相同大小的独立任务所需的总的执行时间为15.当然,该调度不是最优调度,在本文的后续部分中我们会对其进行更加详细的分析.Fig.1 A tree-based grid computing platform and a task scheduling example图1 树型网格计算平台和任务调度示例2 单层树型结构下任务调度模型2.1 基本模型图2给出了一般的单层树结构网格计算平台,该网格计算环境由k 个计算节点组成:n 0,n 1,…,n k −1,它们计算单位任务所需的时间分别为w 0,w 1,…,w k −1,根节点n 0作为Master,负责传输任务给各儿子节点,但一次只能与一个儿子节点通信,它传输单位任务给各儿子节点所需时间分别为c 0,c 1,…,c k −1.在该单层树型结构网格计算平台下调度M 个大小相等的独立任务,为了使完成任务的总时间最小,根节点n 0需要决定自己计算多少个任务,以及需要传输多少个任务给各儿子节点,以实现一个最优的任务分配.我们可以把该任务调度问题转化为线性规划问题:a) 我们假定每个节点n i 所执行的任务数为x i ,所有节点执行的任务之和应该等于M ,由此约束条件可以得到下面的等式(1);b) 对于任意节点,计算任务个数都小于等于总的任务个数M ,由该约束条件可以得到不等式(2);c) 根节点n 0计算任务的时间应小于等于总的任务完成时间,即有不等式(3); d) 除根节点以外的每个节点n i 计算任务的总时间必然小于等于总的任务完成时间(T )减去该节点最早启动任务计算时间(最早启动任务计算时间:单个任务从根节点到该任务计算节点的传输时间),可以得到下面的不等式(4);e) 因为根节点不能同时给几个儿子节点传输任务,所以它与各儿子节点传输任务的总时间必然小于等于总任务完成时间,即可得到下面的不等式(5);f) 由于我们这里所讨论问题的性质,有式(6).由上面的分析我们可以得到在单层树型网格计算平台下任务调度数学模型如下:Fig.2 A single level tree grid computing platform图2 单层树结构网格计算平台Minimize T 满足:≤⋅−≤≤−≤⋅≤⋅−≤≤≤≤=∑∑=−=, , , , , , )6( )5(11for (4) )3(10for 0 )2( )1(1001均为正整数i i i ij j j i i i i k i i x k w c T M Tx c k i c T x w Tx w k i M x M x林伟伟 等:树型网格计算环境下的独立任务调度2355其中:M ,c i ,w i ,k 均为已知量;x i 为变量;T 表示任务的完成时间;Minimize T 为目标函数.通过上面的分析,我们将单层树任务调度问题转化为上述线性规划问题.容易发现,该模型属于整数线性规划问题.该问题可以由Karmarkar 算法[13]在多项式时间内获得近似最优解,求解结果即为单层树任务调度的最优任务分配方案,即获得每个节点的最优分配任务数. 2.2 任务调度实例考虑一个只有4个计算节点的小型单层树型网格计算环境,各计算节点的计算能力及网络通信速度都不同,如图3所示.如果在该环境下完成8个单位任务,用上述的线性规划模型建模该任务调度问题,结果如下:在使用Linguo 或者Matlab 工具获得该问题的最优解为{x 0,x 1,x 2,x 3}={1,2,2,3}时,T 的最优值为17.Fig.3 A single-level tree grid computing platform图3 一个单层树型网格计算环境Minimize T 满足:. , , , , )7(23 )6(24 )5(35 (4)18 )3(01 )2(8 )1(321032132103210≤++−≤−≤−≤≤=+++均为正整数x x x x T Tx x x T x T x T x T x x x x x 由于该问题涉及的任务数和计算节点个数都比较小,故容易得到一个最优任务调度,如图4所示.图中每个计算节点都有两条时间轴(任务计算和通信):带箭头的粗线表示任务的执行;不带箭头的粗线表示任务通信.由图4可以看出,该最优调度方案为{x 0,x 1,x 2,x 3}={1,2,2,3},任务的总完成时间为18,它与线性规划模型得到最优值17最接近.但是,如果我们给每个计算节点平均分配任务,那么该任务调度总的完成时间至少为20.n 3 n 2n 1 n 0图4 最优任务调度2356 Journal of Software 软件学报 V ol.17, No.11, November 20063 多层树型结构下的任务调度模型3.1 相关符号说明图5为一个多层树型网格计算平台,每个网格计算节点只与父亲节点及其儿子节点通信,各计算节点的计算速度(或计算能力)和各节点之间网络通信速度都异构.下面给出在该平台下进行任务调度所用到概念的符号说明.(1) N ={n 0,n 1,…,n k −1}表示树型网格计算平台的网格计算节点(或称为树节点)集,其中,k 为树的节点总个数;(2) x i 表示给树节点n i 安排的任务数;(3) w i 表示树节点n i 计算单位任务所需要的时间,即网格计算节点处理任务的速度的倒数;(4) c i 表示节点n i 的入边传输单位任务所需要的时间,即节点n i 的入边的任务传输速度的倒数;(5) M 表示需要调度任务的总个数;(6) N ′表示树中的非叶子节点集,则有N ′⊂N ; (7) s i 表示节点n i 的最早启动任务计算时间;(8) Y i 表示节点n i 的后代节点的序号集,其中n i ∈N ; (9) Z i 表示节点n i 的儿子节点的序号集,其中n i ∈N .Fig.5 A multi-level tree grid computing platform图5 多层树型网格计算平台3.2 多层树型结构下的任务调度模型前面的单层树型结构计算平台下的任务调度相对比较简单,然而,它的一些结论可以用于多层树中.当然,两种环境下的任务调度也有不同之处:a) 首先,在多层树结构任务调度中,除了根节点外,其他非叶子节点不但要计算任务,而且同时可以传输任务给它的儿子节点;b) 对于多层树中的每个中间节点,需要考虑其任务到达的速度,即在一定的时间范围内,它所获得的任务应该等于其己身计算的任务数与传输给儿子节点的任务数之和;c) 在单层树结构中,我们只需要考虑从根节点到各儿子节点的带宽分配情况,而在多层树结构中,需要考虑每一个子树中带宽分配问题,即任意一个非叶子节点传输任务给它的儿子的总时间是一定的;d) 每个节点的最早启动任务计算时间(S i )应该是父亲节点的最早启动任务计算时间加上它与父亲节点传输单位任务的时间,因此,每个节点计算任务的时间的约束条件式必须修改为下面的线性规划模型中的不等式(4).由a),b)和c)可知,在多层树型结构的任务调度中,每个子树都有一个带宽分配的约束条件,因此有不等式(5).下面以树根节点所在的子树为例进行分析,树根节点分配给所有儿子节点的传输任务的时间之和应小于等于总的任务完成时间T ,其 中:树根节点分配给每个儿子的传输任务的时间为任务传输速度的倒数与传输任务个数的乘积,可以表示为,其中:Z ∑∑∈∈+⋅0Z j Y p p j j j x x c +∑∈j Y p j x x 0为根节点n 0的所有儿子节点的序号组成的集合;Y j 为节点n j 所有后代节点的序号组成的集合,为根节点np 0传输给儿子节点n j 的任务数,x j 为儿子节点n j 计算的任务数,为儿子节点n ∑∈jY p p x j 的后代节点计算的任务数总和.由上面的分析我们可以得到多层树型结构网格计算平台下任务调度的数学模型如下: Minimize T 满足:林伟伟 等:树型网格计算环境下的独立任务调度2357, , , , , , )6(for )5(10for (4) )3(10for 0 )2( )1(1001′∈∀−≤+⋅−≤≤−≤⋅≤⋅−≤≤≤≤=∑∑∑=∈−=均为正整数i i i ii i j Y p p j j i i i i k i i x k w c T M N n s T x x c k i s T x w Tx w k i M x M x j 其中:M ,w i ,c i ,S i ,Y i ,Z i 均为已知量;x i 为变量;T 表示任务完成时间;Minimize T 为目标函数.上面的整数线性规划问题的求解与单层树任务调度模型相同,它可以在多项式次时间内得到近似最优解,所获得的近似最优解即为多层树任务调度的最优任务分配方案. 3.3 任务调度实例考虑如图1所示的由5个计算节点组成的树型网格计算平台下的任务调度问题.用上面的线性规划模型求解该任务调度问题,我们可以得到下面的整数线性规划问题.如果在该环境下调度任务数M 为8和50,则可以很容易地获得两个任务调度问题的最优解,分别为:{x 0,x 1,x 2,x 3,x 4}={1,1,2,2,2},最优值T 为17;{x 0,x 1,x 2,x 3,x 4}= {7,9,12,8,14},最优值T 为77.Minimize T 满足:. , , , , , , )9(33 )8()(2 )7(55 )6(37 )5(26 (4)18 )3(01 )2( )1(43210434321432103210−≤+≤+++−≤−≤−≤−≤≤=+++均为正整数x x x x x M T T x x T x x x x T x T x T x T x T x M x x x x 4 基于最优任务分配方案的任务分配启发式算法经过前面的讨论,我们容易建立树型网格计算平台下任务调度的线性规划模型,且求解线性规划模型可以获得最优任务分配方案,即获得各节点的最优任务分配数.然而,各父亲节点具体以什么顺序或优先级给多个儿子节点分配任务仍然无法确定,寻找该问题的最优任务分配算法是NP 难题.但是,可以构造基于最优任务分配方案的任务分配启发式算法,即以最优任务分配数为启发信息来实现任务分配算法.下面给出基于最优任务分配方案的两个启发式算法:计算速度优先启发式算法(optimization-based priority-computation heuristic algorithm for task allocation,简称OPCHATA)和带宽优先启发式算法(optimization-based priority-bandwidth heuristic algorithm for task allocation,简称OPBHATA).在给出OPCHATA 和OPBHATA 算法之前,需要实现两种算法:一种是模型预处理算法PREModel,用来获得模型中需要的节点计算能力和节点间的通信能力.考虑到网格节点的动态性和异构性,在每批任务调度之前采用相对量化的方式来获得当前网格环境所有节点的计算能力和节点间的通信能力.PREModel 算法的具体实现是:在调度每批任务之前,将单位任务在树型网格环境的各节点上执行,以获得当前各节点的相对计算能力;将单位任务在树型网格环境的所有边上传输,以获得当前各节点间的相对通信能力;另一种是模型求解算法SoveModel,用来求解任务分配的线形规划模型,它可以参照Karmarkar 算法来实现.2358 Journal of Software软件学报 V ol.17, No.11, November 20064.1 计算速度优先启发式算法该启发式算法首先使用PREModel和SoveModel算法求得每个节点的最优任务分配数,然后按照最优任务分配数和节点计算能力来优先为节点分配任务,即对于每个非叶子节点:当有儿子节点的任务请求时,首先检查该儿子节点是否还有未分配的任务,如果有,则分配一个任务给它;当有多个儿子节点的任务请求时,首先检查这些儿子节点是否还有未分配的任务,然后按照计算节点的计算速度以从大到小顺序来分配任务,即按照w i从小到大的顺序来确定任务分配优先级.该算法的伪码描述如下:Procedure task_assign_OPCHATA()//节点n i为根的子树任务分配算法PREModel()//模型预处理算法,只需在总根节点n0部署SoveModel()//模型求解算法,只需在总根节点n0部署GetNodeTaskNum()//从树根节点获得各节点任务分配数InitNodeTaskNum(array)//初始化子树各节点任务分配数While (Receive_task())//当从父亲节点收到任务时Add_task(Queue)//将新任务放到队列中End WhileWhile (Receive_REQ())//当收到儿子节点任务请求时Add_req(Queue2(n x))//将任务请求放到队列中End WhileIf (Exist_task(Queue1))//任务队列是否存在任务If (array(n i)>0)//节点n i是否有未分配的任务Execute_task(Queue)//执行一个任务End If//给请求任务的各儿子节点分配任务Select_compute(Queue2(n x))//从任务请求队列中选择计算能力最大的节点If (array(n x)>0)//该节点是否有未分配的任务TransTask(n x)//传输任务给节点n xDel_req(Queue2(n x))//删除任务请求End IfElse//发送任务请求给父亲节点,树根节点则不需要Send_req(n i)End IfEnd4.2 带宽优先启发式算法与第1种启发式算法不同的是,当有多个儿子节点的任务请求时,首先检查这些儿子节点是否还有未分配的任务,然后按照计算节点与父亲节点的网络通信速度以从大到小的顺序来分配任务,即按照c i从小到大的顺序来确定任务分配优先级.该算法的伪码描述如下:Procedure task_assign_OPBHATA()//节点n i为根的子树任务分配算法…//与OPCHATA算法内容相同//给请求任务的各儿子节点分配任务Select_bandwidth(Queue2(n x))//从任务请求队列中选择与根节点n i网络通信速度最大的节点…//与OPCHATA算法内容相同End林伟伟 等:树型网格计算环境下的独立任务调度23595 实验与结果5.1 相关算法为了验证所提出的基于最优任务分配方案的任务分配启发式算法(OPCHATA 和OPBHATA)的性能,需要与其他任务分配算法进行比较.在同类算法中,Min-Min 算法具有较好的性能,常用作调度算法的评测基准[5,10],因此,本文另外设计了两种任务调度算法:FCFS 算法和Min-Min 算法.FCFS 算法使用所有网格计算节点,其思想是:按照任务请求的到达顺序给各儿子节点分配任务,即先请求任务的先获得任务.该算法可能使各节点获得的任务数与最优任务分配方案求解的结果不一致.Min-Min 算法使用所有网格计算节点,其思想是:尽量把更多的任务分配到执行它的速度最快并能最早完成它的机器上,当任务请求队列有多个任务请求时,首先给计算速度最快的节点分配任务. 5.2 实验方法与结果本文采用SimGrid [14]来模拟和实现以上4种任务分配启发式算法.SimGrid 提供了一系列核心函数,用以建立和模拟异构分布计算环境,并能满足特定应用需求和实现多种算法,特别适合于网格任务调度的模拟和研究.我们分别模拟了3个树型网格计算平台:(1) 图2描述的由4个节点组成的单层树型网格计算平台;(2) 图1描述的由5个节点组成的2层树型网格计算平台;(3) 图6由8个节点组成的4层树型网格计算平台.然后,在这3个平台上分别用FCFS,Min-Min,OPCHATA,OPBHATA 这4种算法实现10个、50个、250个、1250个相同大小独立任务的调度,任务执行完成的时间分别如图7、图8和图9所示.FCFS Min-Min OPCHATA OPBHATAFig.7 The results of task scheduling on the single-leveltree grid computing platform图7 单层树型网格计算平台下的任务调度结果Fig.6 A multi-level grid computing platform图6 3层树结构网格计算环境FCFS Min-Min OPCHATA OPBHATANumber of tasksNumber of tasks Number of tasksFig.8 The results of task scheduling on thetwo-level tree grid computing platform 图8 2层树型网格计算平台下任务调度结果Fig.9 The results of task scheduling on the three-level tree grid computing platform 图9 3层树型网格计算平台下任务调度结果2360 Journal of Software 软件学报 V ol.17, No.11, November 2006为了验证所提出的模型和算法的普遍性,随机生成具有50个不同拓扑结构的树型网格计算平台,其中:树节点数在[2,20]范围内;节点权的值在[10,50]范围内;边权的值在[1,10]范围内.然后,在这些平台上分别用FCFS, Min-Min,OPCHATA,OPBHATA 这4种算法实现1 000个单位任务的调度,任务执行完成时间如图10所示.2520151050N u m b e r o f n o d e sFCFS Min-Min OPCHATA 0 5000 10000 15000 20000Execution time (s)Fig.10 The experimental results of task scheduling on random tree-based grid computing platforms图10 多个随机树型网格计算平台下任务调度的实验结果5.3 实验结果的分析由实验测试结果(如图7~图10所示)可以得出下面的结论:1) 在3种模拟网格计算平台下完成独立任务调度,OPCHATA 和OPBHATA 算法的总完成时间小于FCFS 和Min-Min 算法,特别是当调度的任务数量比较大时,OPCHATA 和OPBHATA 算法性能明显优于FCFS 和Min-Min 算法.也就是说,本文提出的基于最优任务分配方案的任务分配算法有明显优势.2) 在如图6所示的8个节点组成的3层树型网格计算平台下进行任务调度时,4种算法的总处理时间比较接近,这是因为带宽对调度结果的影响.也就是说,当网络通信速度相对于任务计算速度比较快时,4种算法的性能较为接近;反之,当带宽非常有限时,由于OPCHATA 和OPBHATA 算法只使用通信速度快的计算节点,结果实现更好的调度,因此性能更加优于FCFS 和Min-Min 算法(如图7和图8调度结果).3) 从3个平台下的实验结果还可以看出,OPBHATA 性能略优于OPCHATA 算法,说明网络通信速度对任务调度结果的影响更大.因为OPBHATA 算法尽量给网络通信速度快的节点优先分配任务,所以性能更好.4) 图10的结果显示,在随机产生的多个不同结构的树型网格计算平台下进行任务调度时,本文所提出算法的性能普遍优于FCFS 和Min-Min 算法,说明了本文给出的任务调度模型和算法的普遍性. 5.4 算法评价PREModel 算法需要在n 个节点上循环执行单位任务,并在这些节点间传输单位任务,因此,它的时间复杂度为O (n ).SoveModel 算法是参照经典线性规划求解算法Karmarkar 算法[13]实现的,所以其时间复杂度为O (n 3.5L ),其中n 为计算节点个数,L 为线性方程组输入的规模.对于OPCHATA 和OPBHATA 算法,由于每个非叶子节点的最大分配任务数为m ,从请求任务的节点队列中选择一个节点任务最多需要n 次,因此,OPCHATA 和OPBHATA 算法的时间复杂度为O (n 3.5L +mn ),其中n 为主机数量,m 为需要执行的任务数量.与Min-Min 算法(调度m 个大小相同任务,其时间复杂度为O (mn ))相比,OPCHATA 和OPBHATA 算法的时间复杂度要高一些,但当 m >n 2.5L (任务数量比较大)时,它们的时间复杂度比较接近.而且,在网格环境下,任务粒度一般比较大,与任务的执行时间相比,任务调度算法的执行时间经常可以忽略.另一方面,OPCHATA 和OPBHATA 算法考虑带宽限制对任务传输时间的影响,通过线形规划模型获得最优的任务分配方案;而且在网格环境下,任务的传输时间往往对任务的最终完成时间有很大影响.因此,它们与Min-Min,Max-min,FCFS 算法相比,能够获得更好的调度性能.6 结束语为了提高网格计算的性能,高效的任务调度和分配算法是其中一个主要途径.本文讨论了在异构树型网格计算环境下独立任务的调度问题,通过对该调度问题的深入研究和分析,针对单层和多层树型网格计算平台下的最小总任务处理时间的任务调度问题分别建立了线性规划模型,并通过求解线性规划模型获得最优任务分配方案,即获得网格中各计算节点最佳的任务分配数,然后提出基于最优任务分配方案的两个启发式算法:。

填空题1.操作系统的特征是（并发）,（共享）和（异步性）还有（虚拟）.2.按照用户界面的使用环境和功能特征的不同,一般可以把操作系统分为三种基本类型,即:（批处理系统）,（分时系统）和实时系统.3. 软件系统分为系统软件,（支撑软件）和（应用软件）.4.多数计算机系统将处理器的工作状态划分为（管态）和目态.后者一般指用户程序运行时的状态,又称为普通态或（用户态）.5. 存储器一般分成高速缓冲器,（内存）和（外存）三个层次,其中高速缓冲器是造价最高,存取速度最快.6.文件的物理结构有:顺序结构,（链接结构）和（索引结构）.8. 在单CPU系统中有n(n>1)个进程,在任一时刻处于就绪的进程最多是（n-1）个,最少是（0）个.9. 系统为每一台设备确定一个编号,以便区分和识别,这个确定的编号称为设备的（绝对）号.由用户在程序中定义的设备编号称为设备的（相对）号.10. 一个作业可划分成若干个（相对独立）的部分,每个部分称为一个（作业步）.11. 在批处理兼分时的系统中,往往由分时系统控制的作业称为（前台）作业,而由批处理系统控制的作业称为（后台）作业.12. 操作系统为用户提供两种类型的使用接口,它们是（操作员)接口和（程序员) 接口.13. 操作系统中,进程可以分为（系统）进程和（用户）进程两类.15. 除了新建状态与撤销状态，进程的基本状态有(运行)、（就绪）、（阻塞）。

16. 在响应比最高者优先的作业调度算法中,当各个作业等待时间相同时,（计算时间短）分母的作业将得到优先调度;当各个作业要求运行的时间相同时, （等待时间长）分子的作业得到优先调度.17. 当一个进程独占处理器顺序执行时,具有两个特性: （封闭）性和（可再现性）.18. Linux的shell有两层含义,一是指由（shell命令）组成的Shell 命令语言;二是指（该命令的解释）程序.19. 操作系统的主要设计目标是（方便用户使用）和（资源利用率高）.20. 当一个进程完成了特定的任务后,系统收回这个进程所占的（资源）和取消该进程的（进程控制块PCB），就撤消了该进程.21. 每个索引文件都必须有一张（索引）表,其中每个登记项用来指出一个逻辑记录的（存放位置或指针或首地址）.22. 实现SPOOL系统时必须在磁盘上辟出称为（输入#）和（输出#)的专门区域,以存放作业信息和作业执行结果.23. 一个理想的作业调度算法应该是既能（提高系统效率）又能使进入系统的作业（周转时间短）.24. 死锁的四个必要条件是（互斥使用资源）,（占用并等待资源）,不可抢夺资源和循环等待资源.25. 操作系统一般为用户提供了三种界面,它们是(命令界面),(图形界面)和系统调用界面.26. 进程间相互合作的关系是(同步)关系,而对资源争用的关系是(互斥)关系.若干进程使用同一临界资源时必须互斥执行.27. 处理机调度可分为三级,它们是作业调度,(进程调度)和CPU交换调度;在一般操作系统中,必须具备的调度是(进程调度).28. 一般说来,用户程序中所使用的地址是逻辑地址,而内存中各存储单元的地址是(物理地址或绝对地址);将前者转变为后者的过程称作(重定位).29. 在段页式存储管理系统中,面向(用户)的地址空间是段式划分,面向(物理实现)的地址空间是页式划分.30. 在Linux系统中,基本的文件类型分为(普通)文件,目录文件和文件, 所有的I/O设备按其物理特性分为(字符)设备和块设备.33. 操作系统的设备管理应具备的主要功能是(监视设备状态),(进行设备分配),完成I/O操作和缓冲管理与地址转换.34. 对信号量S每执行一次P操作,则信号量S的值就减1.当S的值小于0时,执行P操作的进程的状态就置为阻塞态,把相应的PCB连入该信号量队列的(末尾),并且该进程放弃处理机,由(进程调度程序)调度合适进程.35. 把逻辑地址转变为内存的物理地址的过程称作重定位,它分为(静态重定位)和(动态重定位)两种形式,在现代操作系统中都采用动态重定位形式来实现这种地址转换.37. SPOOLing的中文含义为（同时外围联机操作）或（假脱机操作）。

第一章os引论1. 设计现代OS的主要目标是什么方便性，有效性，可扩充性和开放性.2. OS的作用可表现为哪几个方面 a. OS作为用户与计算机硬件系统之间的接口；b. OS作为计算机系统资源的管理者；c. OS作为扩充机器.3. 试说明推动多道批处理系统形成和发展的主要动力是什么不断提高计算机资源利用率和系统吞吐量的需要；4. 何谓脱机I/O和联机I/O a. 脱机输入输出方式(Off-Line I/O)是为了解决人机矛盾及CPU 和I/O设备之间速度不匹配而提出的.它减少了CPU的空闲等待时间，提高了I/O速度.具体内容是将用户程序和数据在一台外围机的控制下，预先从低速输入设备输入到磁带上，当CPU 需要这些程序和数据时，在直接从磁带机高速输入到内存，从而大大加快了程序的输入过程，减少了CPU等待输入的时间，这就是脱机输入技术;当程序运行完毕或告一段落，CPU需要输出时，无需直接把计算结果送至低速输出设备，而是高速把结果输出到磁带上，然后在外围机的控制下，把磁带上的计算结果由相应的输出设备输出，这就是脱机输出技术.b. 若这种输入输出操作在主机控制下进行则称之为联机输入输出方式.5. 试说明推动分时系统形成和发展的主要动力是什么用户的需要.即对用户来说，更好的满足了人-机交互，共享主机以及便于用户上机的需求.6. 试说明实时任务的类型和实时系统的类型.a. 实时任务的类型按任务执行时是否呈现周期性来划分，分为周期性实时任务和非周期性实时任务；---根据对截止时间的要求来划分，分为硬实时任务和软实时任务;b. 通常把要同达行实时控制的系统统称为实时控制系统,把要求对信息进行实时处理的系统成为实时信息处理系统.7. 实现多道程序应解决哪些问题 a. 处理机管理问题；b. 内存管理问题；c. I/O设备管理问题；d. 文件管理问题；e. 作业管理问题.8. 试比较单道与多道批处理系统的特点及优缺点.a. 单道批处理系统是最早出现的一种OS，它具有自动性，顺序性和单道性的特点；---多道批处理系统则具有调度性，无序性和多道性的特点；b. 单道批处理系统是在解决人机矛盾及CPU和I/O设备之间速度不匹配的矛盾中形成的，旨在提高系统资源利用率和系统吞吐量，但是仍然不能很好的利用系统资源；---多道批处理系统是对单道批处理系统的改进，其主要优点是资源利用率高，系统吞吐量大；缺点是平均周转时间长，无交互能力.9. 实现分时系统的关键问题是什么应如何解决 a. 关键问题：及时接收，及时处理;b. 对于及时接收，只需在系统中设置一多路卡，多路卡作用是使主机能同时接收用户从各个终端上输入的数据；---对于及时处理，应使所有的用户作业都直接进入内存，在不长的时间内，能使每个作业都运行一次.10 为什么要引入实时操作系统更好地满足实时控制领域和实时信息处理领域的需要.11 OS具有哪几大特征它的最基本特征是什么 a. 并发(Concurrence),共享(Sharing),虚拟(Virtual),异步性(Asynchronism).b. 其中最基本特征是并发和共享.12 内存管理有哪些主要功能它们的主要任务是什么 a. 主要功能: 内存分配，内存保护，地址映射和内存扩充等.b. 内存分配的主要任务是为每道程序分配内存空间，提高存储器利用率，以减少不可用的内存空间，允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要.---内存保护的主要任务是确保每道用户程序都在自己的内存空间中运行，互不干扰.---地址映射的主要任务是将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址.---内存扩充的主要任务是借助虚拟存储技术，从逻辑上去扩充内存容量.13 处理机管理具有哪些功能它们的主要任务是什么 a. 进程控制，进程同步，进程通信和调度.b. 进程控制的主要任务是为作业创建进程，撤销已结束的进程，以及控制进程在运行过程中的状态转换.---进程同步的主要任务是对诸进程的运行进行调节.---进程通信的任务是实现在相互合作进程之间的信息交换.---调度分为作业调度和进程调度.作业调度的基本任务是从后备队列中按照一定的算法，选择出若干个作业，为它们分配必要的资源;而进程调度的任务是从进程的就绪队列中，按照一定的算法选出一新进程，把处理机分配给它，并为它设置运行现场，是进程投入运行.14 设备管理有哪些主要功能其主要任务是什么 a. 主要功能: 缓冲管理，设备分配和设备处理，以及虚拟设备等.b. 主要任务: 完成用户提出的I/O请求，为用户分配I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；以及方便用户使用I/O设备.15 文件管理有哪些主要功能其主要任务是什么 a. 主要功能: 对文件存储空间的管理，目录管理，文件的读，写管理以及文件的共享和保护.b. 主要任务: 对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性.16 试在交互性，及时性和可靠性方面，将分时系统与实时系统进行比较.a. 分时系统是一种通用系统，主要用于运行终端用户程序，因而它具有较强的交互能力；而实时系统虽然也有交互能力，但其交互能力不及前者.b. 实时信息系统对实用性的要求与分时系统类似，都是以人所能接收的等待时间来确定；而实时控制系统的及时性则是以控制对象所要求的开始截止时间和完成截止时间来确定的.c. 实时系统对系统的可靠性要求要比分时系统对系统的可靠性要求高.17 是什么原因使操作系统具有异步性特征 a. 程序执行结果是不确定的,即程序是不可再现的.b. 每个程序在何时执行，多个程序间的执行顺序以及完成每道程序所需的时间都是不确定的,即不可预知性.18 试说明在MS-DOS 3.X以前的版本中，其局限性表现在哪几个方面 a. 在寻址范围上，DOS 只有1MB，远远不能满足用户需要.b. DOS试单用户单任务操作系统，不支持多任务并发执行,与实际应用相矛盾.19 MS-DOS由哪几部分组成每部分的主要功能是什么略.20 为什么Microsoft在开发OS/2时，选中了80286芯片设计OS/2的主要目标之一是既能充分发挥80286处理器的能力，又能运行在8086处理器环境下开发的程序.因为在80286内部提供了两种工作方式: 实方式和保护方式，使得Intel 80286处理器不仅提供了多任务并发执行的硬件支持，而且还能运行所有在8086下编写的程序。

第1章算法引论11.1 算法与程序11.2 表达算法的抽象机制11.3 描述算法31.4 算法复杂性分析13小结16习题17第2章递归与分治策略192.1 递归的概念192.2 分治法的基本思想262.3 二分搜索技术272.4 大整数的乘法282.5 Strassen矩阵乘法302.6 棋盘覆盖322.7 合并排序342.8 快速排序372.9 线性时间选择392.10 最接近点对问题432.11 循环赛日程表53小结54习题54第3章动态规划613.1 矩阵连乘问题62目录算法设计与分析(第2版)3.2 动态规划算法的基本要素67 3.3 最长公共子序列713.4 凸多边形最优三角剖分753.5 多边形游戏793.6 图像压缩823.7 电路布线853.8 流水作业调度883.9 0-1背包问题923.10 最优二叉搜索树98小结101习题102第4章贪心算法1074.1 活动安排问题1074.2 贪心算法的基本要素1104.2.1 贪心选择性质1114.2.2 最优子结构性质1114.2.3 贪心算法与动态规划算法的差异1114.3 最优装载1144.4 哈夫曼编码1164.4.1 前缀码1174.4.2 构造哈夫曼编码1174.4.3 哈夫曼算法的正确性1194.5 单源最短路径1214.5.1 算法基本思想1214.5.2 算法的正确性和计算复杂性123 4.6 最小生成树1254.6.1 最小生成树性质1254.6.2 Prim算法1264.6.3 Kruskal算法1284.7 多机调度问题1304.8 贪心算法的理论基础1334.8.1 拟阵1334.8.2 带权拟阵的贪心算法1344.8.3 任务时间表问题137小结141习题141第5章回溯法1465.1 回溯法的算法框架1465.1.1 问题的解空间1465.1.2 回溯法的基本思想1475.1.3 递归回溯1495.1.4 迭代回溯1505.1.5 子集树与排列树1515.2 装载问题1525.3 批处理作业调度1605.4 符号三角形问题1625.5 n后问题1655.6 0\|1背包问题1685.7 最大团问题1715.8 图的m着色问题1745.9 旅行售货员问题1775.10 圆排列问题1795.11 电路板排列问题1815.12 连续邮资问题1855.13 回溯法的效率分析187小结190习题191第6章分支限界法1956.1 分支限界法的基本思想1956.2 单源最短路径问题1986.3 装载问题2026.4 布线问题2116.5 0\|1背包问题2166.6 最大团问题2226.7 旅行售货员问题2256.8 电路板排列问题2296.9 批处理作业调度232小结237习题238第7章概率算法2407.1 随机数2417.2 数值概率算法2447.2.1 用随机投点法计算π值2447.2.2 计算定积分2457.2.3 解非线性方程组2477.3 舍伍德算法2507.3.1 线性时间选择算法2507.3.2 跳跃表2527.4 拉斯维加斯算法2597.4.1 n 后问题2607.4.2 整数因子分解2647.5 蒙特卡罗算法2667.5.1 蒙特卡罗算法的基本思想2667.5.2 主元素问题2687.5.3 素数测试270小结273习题273第8章 NP完全性理论2788.1 计算模型2798.1.1 随机存取机RAM2798.1.2 随机存取存储程序机RASP2878.1.3 RAM模型的变形与简化2918.1.4 图灵机2958.1.5 图灵机模型与RAM模型的关系297 8.1.6 问题变换与计算复杂性归约299 8.2 P类与NP类问题3018.2.1 非确定性图灵机3018.2.2 P类与NP类语言3028.2.3 多项式时间验证3048.3 NP完全问题3058.3.1 多项式时间变换3058.3.2 Cook定理3078.4 一些典型的NP完全问题3108.4.1 合取范式的可满足性问题3118.4.2 3元合取范式的可满足性问题312 8.4.3 团问题3138.4.4 顶点覆盖问题3148.4.5 子集和问题3158.4.6 哈密顿回路问题3178.4.7 旅行售货员问题322小结323习题323第9章近似算法3269.1 近似算法的性能3279.2 顶点覆盖问题的近似算法3289.3 旅行售货员问题近似算法3299.3.1 具有三角不等式性质的旅行售货员问题330 9.3.2 一般的旅行售货员问题3319.4 集合覆盖问题的近似算法3339.5 子集和问题的近似算法3369.5.1 子集和问题的指数时间算法3369.5.2 子集和问题的完全多项式时间近似格式337 小结340习题340第10章算法优化策略34510.1 算法设计策略的比较与选择34510.1.1 最大子段和问题的简单算法34510.1.2 最大子段和问题的分治算法34610.1.3 最大子段和问题的动态规划算法34810.1.4 最大子段和问题与动态规划算法的推广349 10.2 动态规划加速原理35210.2.1 货物储运问题35210.2.2 算法及其优化35310.3 问题的算法特征35710.3.1 贪心策略35710.3.2 对贪心策略的改进35710.3.3 算法三部曲35910.3.4 算法实现36010.3.5 算法复杂性36610.4 优化数据结构36610.4.1 带权区间最短路问题36610.4.2 算法设计思想36710.4.3 算法实现方案36910.4.4 并查集37310.4.5 可并优先队列37610.5 优化搜索策略380小结388习题388第11章在线算法设计39111.1 在线算法设计的基本概念39111.2 页调度问题39311.3 势函数分析39511.4 k 服务问题39711.4.1 竞争比的下界39711.4.2 平衡算法39911.4.3 对称移动算法39911.5 Steiner树问题40311.6 在线任务调度40511.7 负载平衡406小结407习题407词汇索引409参考文献415习题1-1 实参交换1习题1-2 方法头签名1习题1-3 数组排序判定1习题1-4 函数的渐近表达式2习题1-5 O(1) 和 O(2) 的区别2习题1-7 按渐近阶排列表达式2习题1-8 算法效率2习题1-9 硬件效率3习题1-10 函数渐近阶3习题1-11 n !的阶4习题1-12 平均情况下的计算时间复杂性4算法实现题1-1 统计数字问题4算法实现题1-2 字典序问题5算法实现题1-3 最多约数问题6算法实现题1-4 金币阵列问题8算法实现题1-5 最大间隙问题11第2章递归与分治策略14 习题2-1 Hanoi 塔问题的非递归算法14习题2-2 7个二分搜索算法15习题2-3 改写二分搜索算法18习题2-4 大整数乘法的 O(nm log(3/2))算法19习题2-5 5次 n /3位整数的乘法19习题2-6 矩阵乘法21习题2-7 多项式乘积21习题2-8 不动点问题的 O( log n) 时间算法22习题2-9 主元素问题的线性时间算法22习题2-10 无序集主元素问题的线性时间算法22习题2-11 O (1)空间子数组换位算法23习题2-12 O (1)空间合并算法25习题2-13 n 段合并排序算法32习题2-14 自然合并排序算法32习题2-15 最大值和最小值问题的最优算法35习题2-16 最大值和次大值问题的最优算法35习题2-17 整数集合排序35习题2-18 第 k 小元素问题的计算时间下界36习题2-19 非增序快速排序算法37习题2-20 随机化算法37习题2-21 随机化快速排序算法38习题2-22 随机排列算法38习题2-23 算法qSort中的尾递归38习题2-24 用栈模拟递归38习题2-25 算法select中的元素划分39习题2-26 O(n log n) 时间快速排序算法40习题2-27 最接近中位数的 k 个数40习题2-28 X和Y 的中位数40习题2-29 网络开关设计41习题2-32 带权中位数问题42习题2-34 构造Gray码的分治算法43习题2-35 网球循环赛日程表44目录算法设计与分析习题解答（第2版）算法实现题2-1 输油管道问题（习题2-30) 49算法实现题2-2 众数问题（习题2-31) 50算法实现题2-3 邮局选址问题（习题2-32) 51算法实现题2-4 马的Hamilton周游路线问题（习题2-33) 51算法实现题2-5 半数集问题60算法实现题2-6 半数单集问题62算法实现题2-7 士兵站队问题63算法实现题2-8 有重复元素的排列问题63算法实现题2-9 排列的字典序问题65算法实现题2-10 集合划分问题（一）67算法实现题2-11 集合划分问题（二）68算法实现题2-12 双色Hanoi塔问题69算法实现题2-13 标准二维表问题71算法实现题2-14 整数因子分解问题72算法实现题2-15 有向直线2中值问题72第3章动态规划76习题3-1 最长单调递增子序列76习题3-2 最长单调递增子序列的 O(n log n) 算法77习题3-7 漂亮打印78习题3-11 整数线性规划问题79习题3-12 二维背包问题80习题3-14 Ackermann函数81习题3-17 最短行驶路线83习题3-19 最优旅行路线83算法实现题3-1 独立任务最优调度问题（习题3-3) 83算法实现题3-2 最少硬币问题（习题3-4) 85算法实现题3-3 序关系计数问题（习题3-5) 86算法实现题3-4 多重幂计数问题（习题3-6) 87算法实现题3-5 编辑距离问题（习题3-8) 87算法实现题3-6 石子合并问题（习题3-9) 89算法实现题3-7 数字三角形问题（习题3-10) 91算法实现题3-8 乘法表问题（习题3-13) 92算法实现题3-9 租用游艇问题（习题3-15) 93算法实现题3-10 汽车加油行驶问题（习题3-16) 95算法实现题3-11 圈乘运算问题（习题3-18) 96算法实现题3-12 最少费用购物（习题3-20) 102算法实现题3-13 最大长方体问题（习题3-21) 104算法实现题3-14 正则表达式匹配问题（习题3-22) 105算法实现题3-15 双调旅行售货员问题（习题3-23) 110算法实现题3-16 最大 k 乘积问题（习题5-24) 111算法实现题3-17 最小 m 段和问题113算法实现题3-18 红黑树的红色内结点问题115第4章贪心算法123 习题4-2 活动安排问题的贪心选择123习题4-3 背包问题的贪心选择性质123习题4-4 特殊的0-1背包问题124习题4-10 程序最优存储问题124习题4-13 最优装载问题的贪心算法125习题4-18 Fibonacci序列的Huffman编码125习题4-19 最优前缀码的编码序列125习题4-21 任务集独立性问题126习题4-22 矩阵拟阵126习题4-23 最小权最大独立子集拟阵126习题4-27 整数边权Prim算法126习题4-28 最大权最小生成树127习题4-29 最短路径的负边权127习题4-30 整数边权Dijkstra算法127算法实现题4-1 会场安排问题（习题4-1) 128算法实现题4-2 最优合并问题（习题4-5) 129算法实现题4-3 磁带最优存储问题（习题4-6) 130算法实现题4-4 磁盘文件最优存储问题（习题4-7) 131算法实现题4-5 程序存储问题（习题4-8) 132算法实现题4-6 最优服务次序问题（习题4-11) 133算法实现题4-7 多处最优服务次序问题（习题4-12) 134算法实现题4-8 d 森林问题（习题4-14) 135算法实现题4-9 汽车加油问题（习题4-16) 137算法实现题4-10 区间覆盖问题（习题4-17) 138算法实现题4-11 硬币找钱问题（习题4-24) 138算法实现题4-12 删数问题（习题4-25) 139算法实现题4-13 数列极差问题（习题4-26) 140算法实现题4-14 嵌套箱问题（习题4-31) 140算法实现题4-15 套汇问题（习题4-32) 142算法实现题4-16 信号增强装置问题（习题5-17) 143算法实现题4-17 磁带最大利用率问题（习题4-9) 144算法实现题4-18 非单位时间任务安排问题（习题4-15) 145算法实现题4-19 多元Huffman编码问题（习题4-20) 147算法实现题4-20 多元Huffman编码变形149算法实现题4-21 区间相交问题151算法实现题4-22 任务时间表问题151第5章回溯法153习题5\|1 装载问题改进回溯法（一）153习题5\|2 装载问题改进回溯法（二）154习题5\|4 0-1背包问题的最优解155习题5\|5 最大团问题的迭代回溯法156习题5\|7 旅行售货员问题的费用上界157习题5\|8 旅行售货员问题的上界函数158算法实现题5-1 子集和问题（习题5-3) 159算法实现题5-2 最小长度电路板排列问题（习题5-9) 160算法实现题5-3 最小重量机器设计问题（习题5-10) 163算法实现题5-4 运动员最佳匹配问题（习题5-11) 164算法实现题5-5 无分隔符字典问题（习题5-12) 165算法实现题5-6 无和集问题（习题5-13) 167算法实现题5-7 n 色方柱问题（习题5-14) 168算法实现题5-8 整数变换问题（习题5-15) 173算法实现题5-9 拉丁矩阵问题（习题5-16) 175算法实现题5-10 排列宝石问题（习题5-16) 176算法实现题5-11 重复拉丁矩阵问题（习题5-16) 179算法实现题5-12 罗密欧与朱丽叶的迷宫问题181算法实现题5-13 工作分配问题（习题5-18) 183算法实现题5-14 独立钻石跳棋问题（习题5-19) 184算法实现题5-15 智力拼图问题（习题5-20) 191算法实现题5-16 布线问题（习题5-21) 198算法实现题5-17 最佳调度问题（习题5-22) 200算法实现题5-18 无优先级运算问题（习题5-23) 201算法实现题5-19 世界名画陈列馆问题（习题5-25) 203算法实现题5-20 世界名画陈列馆问题（不重复监视）（习题5-26) 207 算法实现题5-21 部落卫队问题（习题5-6) 209算法实现题5-22 虫蚀算式问题211算法实现题5-23 完备环序列问题214算法实现题5-24 离散01串问题217算法实现题5-25 喷漆机器人问题218算法实现题5-26 n 2-1谜问题221第6章分支限界法229习题6-1 0-1背包问题的栈式分支限界法229习题6-2 用最大堆存储活结点的优先队列式分支限界法231习题6-3 团顶点数的上界234习题6-4 团顶点数改进的上界235习题6-5 修改解旅行售货员问题的分支限界法235习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树237 习题6-7 电路板排列问题的队列式分支限界法239算法实现题6-1 最小长度电路板排列问题一（习题6-8) 241算法实现题6-2 最小长度电路板排列问题二（习题6-9) 244算法实现题6-3 最小权顶点覆盖问题（习题6-10) 247算法实现题6-4 无向图的最大割问题（习题6-11) 250算法实现题6-5 最小重量机器设计问题（习题6-12) 253算法实现题6-6 运动员最佳匹配问题（习题6-13) 256算法实现题6-7 n 后问题（习题6-15) 259算法实现题6-8 圆排列问题（习题6-16) 260算法实现题6-9 布线问题（习题6-17) 263算法实现题6-10 最佳调度问题（习题6-18) 265算法实现题6-11 无优先级运算问题（习题6-19) 268算法实现题6-12 世界名画陈列馆问题（习题6-21) 271算法实现题6-13 骑士征途问题274算法实现题6-14 推箱子问题275算法实现题6-15 图形变换问题281算法实现题6-16 行列变换问题284算法实现题6-17 重排 n 2宫问题285算法实现题6-18 最长距离问题290第7章概率算法296习题7-1 模拟正态分布随机变量296习题7-2 随机抽样算法297习题7-3 随机产生 m 个整数297习题7-4 集合大小的概率算法298习题7-5 生日问题299习题7-6 易验证问题的拉斯维加斯算法300习题7-7 用数组模拟有序链表300习题7-8 O(n 3/2)舍伍德型排序算法300习题7-9 n 后问题解的存在性301习题7-11 整数因子分解算法302习题7-12 非蒙特卡罗算法的例子302习题7-13 重复3次的蒙特卡罗算法303习题7-14 集合随机元素算法304习题7-15 由蒙特卡罗算法构造拉斯维加斯算法305习题7-16 产生素数算法306习题7-18 矩阵方程问题306算法实现题7-1 模平方根问题（习题7-10) 307算法实现题7-2 集合相等问题（习题7-17) 309算法实现题7-3 逆矩阵问题（习题7-19) 309算法实现题7-4 多项式乘积问题（习题7-20) 310算法实现题7-5 皇后控制问题311算法实现题7-6 3-SAT问题314算法实现题7-7 战车问题315算法实现题7-8 圆排列问题317算法实现题7-9 骑士控制问题319算法实现题7-10 骑士对攻问题320第8章NP完全性理论322 习题8-1 RAM和RASP程序322习题8-2 RAM和RASP程序的复杂性322习题8-3 计算 n n 的RAM程序322习题8-4 没有MULT和DIV指令的RAM程序324习题8-5 MULT和DIV指令的计算能力324习题8-6 RAM和RASP的空间复杂性325习题8-7 行列式的直线式程序325习题8-8 求和的3带图灵机325习题8-9 模拟RAM指令325习题8-10 计算2 2 n 的RAM程序325习题8-11 计算 g(m,n)的程序 326习题8-12 图灵机模拟RAM的时间上界326习题8-13 图的同构问题326习题8-14 哈密顿回路327习题8-15 P类语言的封闭性327习题8-16 NP类语言的封闭性328习题8-17 语言的2 O (n k) 时间判定算法328习题8-18 P CO -NP329习题8-19 NP≠CO -NP329习题8-20 重言布尔表达式329习题8-21 关系∝ p的传递性329习题8-22 L ∝ p 330习题8-23 语言的完全性330习题8-24 的CO-NP完全性330习题8-25 判定重言式的CO-NP完全性331习题8-26 析取范式的可满足性331习题8-27 2-SAT问题的线性时间算法331习题8-28 整数规划问题332习题8-29 划分问题333习题8-30 最长简单回路问题334第9章近似算法336习题9-1 平面图着色问题的绝对近似算法336习题9-2 最优程序存储问题336习题9-4 树的最优顶点覆盖337习题9-5 顶点覆盖算法的性能比339习题9-6 团的常数性能比近似算法339习题9-9 售货员问题的常数性能比近似算法340习题9-10 瓶颈旅行售货员问题340习题9-11 最优旅行售货员回路不自相交342习题9-14 集合覆盖问题的实例342习题9-16 多机调度问题的近似算法343习题9-17 LPT算法的最坏情况实例345习题9-18 多机调度问题的多项式时间近似算法345算法实现题9-1 旅行售货员问题的近似算法（习题9-9) 346 算法实现题9-2 可满足问题的近似算法（习题9-20) 348算法实现题9-3 最大可满足问题的近似算法（习题9-21) 349 算法实现题9-4 子集和问题的近似算法（习题9-15) 351算法实现题9-5 子集和问题的完全多项式时间近似算法352算法实现题9-6 实现算法greedySetCover（习题9-13) 352算法实现题9-7 装箱问题的近似算法First Fit（习题9-19) 356算法实现题9-8 装箱问题的近似算法Best Fit（习题9-19) 358算法实现题9-9 装箱问题的近似算法First Fit Decreasing（习题9-19) 360算法实现题9-10 装箱问题的近似算法Best Fit Decreasing（习题9-19) 361算法实现题9-11 装箱问题的近似算法Next Fit361第10章算法优化策略365 习题10-1 算法obst的正确性365习题10-2 矩阵连乘问题的 O(n 2) 时间算法365习题10-6 货物储运问题的费用371习题10-7 Garsia算法371算法实现题10-1 货物储运问题（习题10-3) 374算法实现题10-2 石子合并问题（习题10-4) 374算法实现题10-3 最大运输费用货物储运问题（习题10-5) 375算法实现题10-4 五边形问题377算法实现题10-5 区间图最短路问题（习题10-8) 381算法实现题10-6 圆弧区间最短路问题（习题10-9) 381算法实现题10-7 双机调度问题（习题10-10) 382算法实现题10-8 离线最小值问题（习题10-11) 390算法实现题10-9 最近公共祖先问题（习题10-12) 393算法实现题10-10 达尔文芯片问题395算法实现题10-11 多柱Hanoi塔问题397算法实现题10-12 线性时间Huffman算法400算法实现题10-13 单机调度问题402算法实现题10-14 最大费用单机调度问题405算法实现题10-15 飞机加油问题408第11章在线算法设计410习题11-1 在线算法LFU的竞争性410习题11-4 多读写头磁盘问题的在线算法410习题11-6 带权页调度问题410算法实现题11-1 最优页调度问题（习题11-2) 411算法实现题11-2 在线LRU页调度（习题11-3) 414算法实现题11-3 k 服务问题（习题11-5) 416参考文献422。

独立任务最优调度问题【问题描述：】用2台处理机A和B处理n个作业。

设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。

由于各作业的特点和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j,j≠i，有aj <bj。

既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。

设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。

研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。

【编程任务】：对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。

【数据输入】：由文件input.txt提供输入数据。

文件的第1行是1个正整数n, 表示要处理n个作业。

接下来的2行中，每行有n个正整数，分别表示处理机A和B 处理第i个作业需要的处理时间。

【结果输出】:程序运行结束时，将计算出的最短处理时间输出到文件output.txt中。

【算法思路】：对于算法来说，没有最好，只有更好，算法的结果不一定是最佳答案，但至少是最接近最佳答案的。

在权衡算法时间复杂度和空间复杂度的情况下，找到一个在时间和空间都能接受的算法才是上上之策。

本例采样贪心算法的思想，但又不是严格意义上的贪心算法。

思路：1）、把n个任务按一定规则分别存储到二维数组a[][] 和 b[][] 中，规则，对任意i满足a[i][0]<a[i][1] 级数组a[][] 存储在机器 A 上处理需要时间小于在机器 B 上处理时间的任务，数组 B 则相反。

时间复杂度为O（n）。

2）、对数组 a[][] & b[][] 排序：数组 a[][] 按 a[i][0] 的大小进行降序排列，对于a[i][0]==a[i+1][0] 时按 a[i][1] 进行降序排列。

1、什么是操作系统？它有什么基本特征？操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

操作系统的基本特征是：并发、共享和异步性。

2、操作系统的含义及其功能是什么？1）、含义：OS是一组系统软件，它是软硬件资源的控制中心，它以尽量合理有效的方法组织多个用户共享计算机的各种资源。

2）功能：管理计算机的软硬件资源（包括：处理机管理，作业管理，存储管理，设备管理，文件管理）、提高资源的利用率、方便用户。

3、什么是多道程序设计技术多道程序设计技术就是在系统（内存）中同时存放并运行多道相互独立的程序（作业），主机以交替的方式同时处理多道程序。

它是一种宏观上并行，微观上串行的运行方式。

4、分时系统和实时系统有什么不同？答：分时系统通用性强，交互性强，及时响应性要求一般（通常数量级为秒）；实时系统往往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率，而更关心及时响应性（通常数量级为毫秒或微秒）、可靠性等。

5、SPOOLing的含义是什么？试述SPOOLing系统的特点、功能。

答：SPOOLing是Simultaneous Peripheral Operation On-Line （即并行的外部设备联机操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。

SPOOLing技术是在通道技术和多道程序设计基础上产生的，它由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作。

SPOOLing系统由专门负责I/O的常驻内存的进程以及输入井、输出井组成；它将独占设备改造为共享设备，实现了虚拟设备功能。

6、作业与进程有何不同？它们之间有什么关系？（1）、不同：作业：是用户在一次上机活动中，要求计算机系统所做的一系列工作的集合。

也称作任务（task）。