全国计算机四级考试复习纲要-第三第四章

卫文 1172分享

  自 1994 年开考以来,全国计算机等级考试 适应了市场经济发展的需要,考试持续发展,考生人数逐年递增,至 2013 年底,累计考生人数超过 5422 万,累计获证人数达 2067 万。下面是全国计算机四级考试第三第四章d 复习纲要,希望大家喜欢!

  

  全国计算机四级考试第三章考试要点

  一、数理逻辑

  (一) 命题逻辑基本概念数理逻辑是用数学方法研究抽象思维规律的数学学科,它研究的中心问题是推理,而推理的基本要素是命题。

  在数理逻辑中,将命题用符号表示,称为命题符号值。可用p,q,r…或pi ,qi ,ri …表示命题。将真值也用符号表示,用“1”表示“真”,用“0”表示“假”。

  (二) 命题公式及其分类

  简单命题又称为命题常项或命题常元。命题常项有确定的真值。在数理逻辑中,不仅要研究具体的逻辑关系,还要研究抽象的逻辑关系,因而不仅要有命题常项,还要有命题变项。称真值可以变化的简单陈述句为命题变项或命题变元,仍然用p,q,r,…表示命题变项。

  二、集合论

  集合的基本概念

  用朴素的语言描述,一些事物汇集在一起,称作一个集合。集合的每一个成员称作它的元素。往往用大写英文字母A,B,C,…表示集合。设A为一个集合。用x∈A表示x是A的元素,x∈A表示x不是A的元素。

  集合的表示方法很多,主要方法有列出集合全体元素的方法和用谓词表示集合中元素的性质的方法。

  三、代数系统

  代数运算及其性质

  抽象代数研究的对象是非特定的任意元素的集合和定义在这些元素之间的,满足若干条件或公理的代数运算。重要的代数系统有半群、群、环、域、格等。近年来代数在计算机科学中有许多重要应用。

  如无得到说明,在本章N表示自然数集,Z、Q、R、C分别表示整数集、有理数集、实数集、复数集、Z + 、Q+ 、R+ 分别表示正整数集、正有理数集、正实数集。

  全国计算机四级考试第四章考试要点

  一、操作系统的基本概念

  1.引言

  现代计算机系统由硬件和软件两部分构成。硬件指的是构成计算机系统的物理设备。操作系统控制和管理所有的系统硬件(如处理器、存储器、各种设备),也控制和管理系统中所有的软件,操作系统对计算机使用者提供了一种良好的操作环境,也为各种应用系统提供了基本的支持环境。操作系统在硬件之上建立了一个服务体系,为各种软件提供强有力的支持,呈现在用户面前的计算机是一个方便的、友好的环境界面。现代计算机系统中硬件与软件之间的关系可分成若干层次。硬件(裸机)在最里层,是计算机系统工作的物质基础,它的外面是操作系统,通过系统程序对计算机系统中各类资源(处理器、存储器、设备、数据等)进行管理和提供方便用户使用的多种服务功能,隐蔽对硬件的复杂操作,把裸机改造成功能更强,使用更方便的系统。

  2.什么是操作系统

  有几种不同的方法考察操作系统

  (1)用户观点操作系统是用户与计算机之间的接口,有了操作系统,用户可以方便地使用计算机;在功能上,操作系统提供功能很强的系统调用,用户软件使用这些系统调用(也称管态)运行。

  (2)资源管理观点操作系统是控制和管理计算机系统资源的程序,它的工作是当用户程序和其他程序争用这些资源时,提供有序的和可控的分配。

  (3)进程观点操作系统环境中,常同时运行着多个程序(称为并发),这些同时运行的程序称为“进程”(process),或“任务”(task)。每个进程都完成各自的特定任务(如用户程序的运行,处理某个设备的输入输出……)。操作系统则控制和协调这些进程的运行。它从系统各部分可以并行工作为出发点,考虑管理任务的分割和相互之间的关系,通过进程之间的通信解决共享资源时带来的竞争问题。通常,进程可以分为用户进程和系统进程两大类。

  (4)分层观点根据使用环境和对用户作业处理方式,操作系统的基本类型可能分为3大类:?批处理操作系统(batch processing operating system);?分时操作系统(time sharing system);?实时操作系统(real time system)随着网络技术的发展与普遍使用,共享网络资源的网络环境下的操作系统也已流行。网络环境下的操作系统又分成网络操作系统和分布式操作系统,网络操作系统是在各单机操作系统的基础上,按照网络体系结构的各个协议、标准进行开发,形成网络软件,包括网络管理、通信、资源共享、系统安全和多种网络应用等;分布式操作系统要求一个统一的操作系统,即废弃(或改造)各单机的操作系统,整个网络设有单一的操作系统。分布式操作系统负责全系统的资源分配和调度,为用户提供统一的界面。用户据此使用系统资源、完成所需任务。至于设备在何处用户是不必知道的,这称为位置透明性。分布式操作系统是一个逻辑上紧密耦合的系统。而网络操作系统用户则需指明欲使用哪一台计算机上的哪个资源。

  3.操作系统的功能

  操作系统的职能是管理和控制计算机系统中的全部硬件、软件资源,合理组织计算机工作流程,并为用户提供一个良好的工作环境和友好的接口,系统资源管理和提供用户界面是操作系统的功能要点。

  (1)处理器(处理机)管理处理器是计算机系统的心脏,在单用户系统或单道系统中,处理器为一个用户或一个作业服务,其管理简单。为提高系统资源利用率,引入多道程序技术,即多个程序(作业)同时运行,他们争用处理器,就要解决对处理器分配调度策略、实施分配和回收资源。许多操作系统是以作业和进程的方式进行管理,实现作业和进程的调度,分配处理器,控制作业和进程的执行。现代的操作系统更引入线程(Thread)作为分配处理器的基本单位。基于操作系统对处理器管理策略的不同,其提供的作业处理方式也就不同,如简单的批处理方式、分时处理方式、实时处理方式、多道成批处理方式和网络环境下的处理方式。从而,呈现在用户面前的就是不同的操作系统。

  (2)存储管理计算机系统中,存储器(一般称为主存或内存)是运行程序、存放工作数据的,存储管理的工作主要是对主存储器进行分配、扩充和保护。系统中有多个程序(操作系统,实用程序和用户程序)共享存储器,它们彼此之间不能相互干扰和破坏,这就是存储保护问题。当计算机系统中运行的程序所需要的主存容量超过系统所提供的主存容量时,如何利用外部存储器作为主存的后援,为用户提供一个容量比实存(实际内存)大得多的虚存(虚拟存储器),让用户可运行一个比实存大的用户作业,这就是内存扩充问题。

  (3)设备管理现代计算机系统常常配置很多种类的输入输出设备,它们的输入输出速度差别很大,计算机系统常常采用通道、控制器、设备三级控制方法管理这些设备,设备管理的任务就是监视这些资源的使用情况,根据一定的分配策略,把通道、控制器和设备分配给请求输入输出操作的程序,并启动设备完成所需的操作。为了发挥设备和处理机的并行工作能力,常常采用缓冲技术和虚拟技术。

  (4)文件管理(信息管理)用户使用计算机系统处理数据(信息),这些数据和程序作为文件储存在外部存储器(如磁盘、磁带、光盘等)上,文件管理的任务是管理文件的存储空间,提供信息的共享和保护,允许多个用户协同工作又不引起混乱。

  (5)用户接口(工作管理)上述四项功能是操作系统对硬、软件资源的管理,操作系统也必须为用户提供一个友好的用户接口———命令接口和图形接口。一般,用户通过两种命令接口请求操作系统的服务。一种接口是作业一级的接口,即提供一组操作命令,如UNIX和Linux的shell命令语言或作业控制语言(JCL)让用户组织和控制自己作业的运行。作业控制又分成两类;联机控制和脱机控制。另一种接口是编程接口,即提供一组系统调用命令(又称进管指令SVC)供各种程序(实用程序,应用程序和用户程序等)调用,请求操作系统的服务,这些服务常可分成:处理器服务(作业、进程、线程管理),存储服务,设备服务,文件服务,用户界面服务,异常处理服务,其他类型服务等。

  4.操作系统的工作原理

  操作系统的基本特征是并发和共享。并发的意思是存在许多同时的活动(或并行的活动);输入输出操作和处理器运行并行活动;在主存中同时驻留几道用户程序等都是并发的例子。并发活动会要求共享资源和信息,这就能提高资源的利用率。多道程序可以并发而共享资源,一个用户的任务也可以组织成几个子任务并发工作而提高运行效率。程序这样运行时,不能使输入设备,处理器和打印机并行工作,若忽略处理器加工数据的处理时间,则完成一批数据加工的时间为输入输出设备耗时的总和,若将这个计算任务分成3个子任务,并引入缓冲技术:输入子任务从输入设备读一批数据到输入缓冲区,处理子任务则把输入缓冲区中的数据处理后放入输出缓冲区,打印子任务则打印输出缓冲区中的内容,从而输入子任务可以与打印子任务并发工作,使完成一批数据加工的时间近似于较慢的设备速度。程序的并发执行,发挥了处理器与输入输出设备并发工作的能力,使系统的效率提高。多个计算程序同时驻留在主存储器中并行执行的程序设计方法称为多道程序设计,这种系统称为多道程序系统。多道程序系统能充分发挥处理器的利用效率,提高系统资源的利用效率。既然他们同处在一个系统中,一个任务(或子任务)的执行会受到其他任务(或子任务)的影响(又称为制约)。

  5.操作系统的硬件基础

  现代计算机系统设备的发展异常迅速,导致了控制技术的发展,设备控制的基本技术是中断。

  (1)中断的基本概念在计算机系统中,中断是改变处理器执行指令顺序的事件,被打断的程序可以在将来某个时候(可能在中断处理完成后立即或推迟,这是由操作系统控制的)恢复执行。计算机系统的中断既来自系统内部,也来自系统外部,分别称为内部中断和外部中断。①内部中断是系统本身在工作过程中出现的各种需要紧急处理的事件:一种是由于运行程序发生意外而产生的,另一种是运行程序需要发生的。内部中断也称为软件中断。②外部中断是由于硬件方面的原因,故也称为硬件中断,硬件中断往往是随机发生的,不是由正在运行的程序所控制的。外部中断和由于运行程序产生的例外中断常常称为强迫中断,而运行程序主动要求而产生的中断称为自愿中断。外部中断可进一步分成可屏蔽中断和不可屏蔽中断。不可屏蔽的中断是一些最紧急最重要的中断,如掉电等。可屏蔽的中断通过处理器内部的中断许可状态确定响应中断的次序或者不响应一些不重要(或不紧急)的中断请求。

  (2)中断的响应与处理引起中断的事件(即原因)称为中断源。目前,大多数系统都采用中断向量的技术,所谓中断向量,实际上是一种指针,就是由硬件对不同的中断源将控制转移到不同的中断处理程序入口地址。所有的中断向量构成一个中断向量表,它们通常存放在一个专门的存储区域中,这个区域的地址可以是固定的;相应的处理程序的入口地址通常是在系统引导过程中,通过对系统配置的检测,得到系统中设备配置的情况,在操作系统装入过程中,填写中断向量表中的指针内容。中断处理程序对中断事件的处理分两步进行。第一步是保护好被中断程序的现场信息,即保存被中断程序的寄存器以及PSW(程序状态字)的内容,以保证被中断程序以后能继续运行;第二步是具体处理中断。中断处理完成后,处理器分配给发生中断时正在运行的进程,还是分配给另一进程,这取决于被中断的进程是可剥夺的还是不可剥夺的。如果是不可剥夺的,它重新得到处理器,否则,可能被别的进程(如优先级更高)夺得处理器。

  二、进程管理

  1.程序、进程和处理器

  程序是指令的集合,每一程序完成确定的任务。在只允许一个程序运行的系统(称为单道系统)中,这个程序独占系统资源,而系统按程序的指令顺序运行,程序的顺序执行有两个基本特征,即程序的封闭性和程序的可再现性。封闭性是指程序运行时独占系统资源,只有程序本身能改变系统的状态;可再现性是指程序运行不受外部因素影响,只要初始条件相同,运行结果就相同。多道程序系统让多个程序在系统中轮流运行,当一个程序不用处理器时,另一个程序就使用。也就是说,处理器在程序间切换,从而获得宏观上的并行(微观上的串行),以提高处理器的利用率。这种切换,通常是由中断引起的。由于中断是以不可预测的次序发生,即程序的指令序列也以不可预测的次序前进,这样就会产生操作系统的另一特性:不确定性。即在多道程序系统中,顺序程序的封闭性和可再现性消失了。需要采用一个新的概念———进程来描述程序的执行,进程是运行中的程序。

  2.进程间的通信

  在操作系统中,进程是可以独立运行的程序单位,系统中的各个进程并不是相互隔离的:一方面它们相互竞争使用有限的资源,如处理器、存储器、设备或文件等;另一方面,它们可能相互协作以达到用户作业预期的目的。因此,进程之间需要某种形式的通信。进程之间直接发生联系的称为相交进程(又称相关进程),否则为不相交进程。相交进程需要协调彼此间的相对运行速度,存在着直接制约的关系。不相交进程之间的联系将表现在资源使用上的间接制约关系。

  (1)互斥多道系统中,各进程可以共享各类资源,但有些资源却一次只能供一个进程使用。这种资源常常称为临界资源,如打印机、公共变量、表格等。互斥是要保证临界资源在某一时刻只被一个进程访问。

  (2)同步一般一个进程相对于另一个进程的速度是不可预测的,也就是说,进程之间是异步运行的。为了成功地协同工作,有关进程在某些确定的点上应当同步它们的活动:一个进程到达了这些点后,除非另一进程已完成了某个活动,否则就停下来,以等待该活动结束。

  (3)死锁当若干进程竞争使用资源时,可能产生下述情况:每个进程要求的资源都已被另一进程占用,于是也就没有一个进程能继续运行。这种情况称为死锁。

  3.信号量与P,V操作

  用顺序程序设计技术处理同步与互斥是十分困难的,为此引入信号量概念:信号量是一种特殊的变量,它的表现形式是一个整型变量及相应的队列:除了设置初值外,对信号量只能施加特殊的操作:P操作和V操作,P操作和V操作都是不可分割的原子运行,也称为原语(有时分别记为down()和up()或wait()和signal())。P操作的作用是将信号量S的值减1,若S的值成负数,则调用P操作的进程暂停执行,直到另一个进程对同一信号量作V操作。V操作的作用是将信号量S的值加1,若S的值小于等于0,从相应队列(关于S的队列)中选一个进程,唤醒它。

  (1)互斥为了保护共享资源(如公共变量等),使它们不被多个进程同时访问,就要阻止这些进程同时执行访问这些资源的代码段,这些代码段称为临界区,这些资源称为临界资源。对临界资源访问的互斥要求可视作执行临界区的互斥要求。利用信号量可以方便地实现互斥临界区的管理要求。例如,令信号量mutex的初值为1,于是临界区就改写成下列形式的代码段。P(mutex);临界区V(mutex);由于mutex初值为1,P、V是原子操作,确实可以实现互斥。

  (2)同步最简单的同步形式是:进程A在另一个进程B已到达点L2以前,不应前进到超过点L1。对此,可以令信号量proceed初值为0,实现这种同步的程序形式是: 进程A L1:P(proceed); … …进程B L2:V(proceed); … …更复杂一点的同步问题是单缓冲的生产者、消费者问题。

  4.高级通信原语

  P、V操作是用来协调进程间关系的,编程较困难而且没有信息交换,故常称为低级通信原语。此外,P、V操作必须有共享存储器,而高级通信原语则提供两种通信方式:有缓冲区的通信和无缓冲区的通信。

  (1)有缓冲区的通信方式中,有原语:

  Write(Buffer_Name,Variable) 等缓冲区空再存入

  Read(Buffer_Name,Variable) 等缓冲区满再取出

  (2)无缓冲区的通信,又称为消息传递,有原语:

  Send(Who,Message) 发送消息给指定进程或一组进程

  Receive(Who,Message) 从约定进程接收消息有的系统还提供带标记的发送,有Send(Who,Message,Tag)用Tag可指定发送进程是否要等待接收进程取到内容以后再继续运行。一般接收者总是要等待消息到达后才继续运行。

  三、系统核心

  操作系统核心位于计算机硬件之上,核心的目的是提供一种进程赖以生存的环境,其主要任务是接收中断并作基本处理,在进程之间切换处理器,处理进程之间通信。

  1.基本硬件机构

  (1)中断机构

  为了使输入输出活动与处理器活动并行进行,当一台外部设备的传输操作结束时,应能中断正在运行的进程,由中断处理程序处理。

  (2)特权指令为使各并发进程不相互干扰,系统的部分指令集应保留仅供操作系统使用,这些指令称为特权指令,如允许与禁止中断,执行输入输出操作等。为了区分什么时候可以使用特权指令,什么时候不可以使用,系统至少具有两种工作状态,它们分别称为系统态和用户态,又称为管态和目态。特权指令只能在管态中运行。

  (3)主存保护多道程序系统中,必须对各进程使用的主存加以保护,以防止其他进程进行未经许可的操作。保护机制应包含在主存寻址硬件中。

  (4)时钟硬件的时钟以固定的时间间隔产生中断信号,这对于实现处理器的调度以及实现与时间有关的任务是不可缺少的

  2.进程

  (1)进程进程是一个程序关于某个数据集的一次运行。也就是说,进程是运行中的程序,是程序的一次运行活动。相对于程序,进程是一个动态的概念,而程序是静态的概念,是指令的集合。因此,进程具有动态性和并发性。在操作系统中进程是进行系统资源分配、调度和管理的最小单位,注意,现代操作系统中还引入了线程,它是处理器分配的最小单位。

  (2)进程的状态及其转换多道系统中,进程的运行是走走停停的,它在处理器上交替运行,使它的运行状态不断变化,最基本的状态有3种:运行、就绪和阻塞。?运行(running):正占用处理器。?就绪(ready):只要获得处理器即可运行。?阻塞(blocked):正等待某个事件(I/O完成)的发生。

  (3)进程控制块进程是一个动态的概念,如何表示一个进程?在操作系统中,引入数据结构———进程控制块(简记为PCB)标记进程。PCB是进程存在的惟一标志,PCB描述了进程的基本情况。从静态的观点看,进程由程序、数据和进程控制块组成;从动态的观点看,是计算机状态的一个有序集合。程序是进程运行所对应的运行代码,一个进程对应于一个程序;有的程序可以同时对应于多个进程,这个程序的代码在运行过程中不会被改变,常称为纯码程序或可重入程序,他们是可共享的程序。进程控制块保存进程状态、进程性质(如优先程序)、与进程有关的控制信息(如参数、信号量、消息等)、相应队列和现场保护区域等。进程控制块随着进程的建立而产生,随着进程的完成而撤消。PCB是操作系统核心中最主要的数据结构之一,它既是进程存在的标志和调度的依据,又是进程可以被打断并能恢复运行的基础。核心通过PCB管理进程,一般PCB是常驻内存的,尤其是调度信息必须常驻内存。

  3.进程管理

  在操作系统中有许多进程,它们对应着不同的或相同的程序,竞争地使用着系统的资源。进程管理涉及到进程控制、队列管理、进程调度等。

  (1)进程控制

  进程的生命过程是从它被创建开始,直到任务终止而撤消,其间会经历各种状态的转换,它们都是在操作系统控制下完成的,为此,操作系统提供了对进程的基本操作,也称为原语。这些原语包括:创建原语(create),阻塞原语(block),终止原语(terminal),优先级原语(chang_prioriˉty),调度原语(schedule)。它们可以被系统本身调用,有的也以软中断形式(系统调用)供用户进程调用。他们都涉及现场队列管理等。当一个进程创建一个新的进程时,创建者称为父进程,被创建者称为子进程。通常操作系统中设置一个运行队列,一个就绪队列和若干个阻塞队列。在单处理器系统中运行队列只有一个成员。一般阻塞队列的个数取决于等待事件(原因)的个数。调度原语是按照确定的算法,从就绪队列中选择一个就绪进程,将处理器分配给它,修改这个进程的PCB内容。在操作系统中进程生命的简单活动是这样的:一个进程可以由系统创建(如用户运行一程序),也可以由用户进程用创建原语建立。新建立的进程开始时处于就绪状态。该进程的运行也会因等待某个事件(如I/O完成)的发生而处于阻塞状态,转入相应的阻塞队列。一旦相应事件发生后,将被唤醒原语叫醒而回到就绪队列。重复上述过程直至运行完毕。经终止原语作一些记录工作并撤消这个进程。

  (2)进程调度

  进程调度即处理器调度,它的主要功能是确定在什么时候分派处理器,并确定分给哪一个进程。在分时系统中,一般有一个确定的时间单位(称为时间片),当一进程用完一个时间单位时,就发生进程调度(又称上下文转换),即让正在运行的进程改变状态并转入就绪队列尾,再由调度原语将就绪队列的首进程取出,投入运行。进程调度的方法基本上分为两类:剥夺调度与非剥夺调度。所谓非剥夺调度是指一旦某个作业或进程占有了处理器,这个进程就占用处理器直到主动放弃处理器为止,相反,如果其他进程可获得处理器的使用权则是剥夺调度。在有些进程(如高优先级进程)需要快速服务的系统中,剥夺调度是非常有用的。例如,在实时系统中丢失一个中断的后果将是灾难性的。交互式系统中,为保证用户可接受的响应时间,剥夺调度也十分重要。在非剥夺系统中,短的作业常常等待长的作业,但所有进程受到的服务是公平的,响应时间是可以预测的。对就绪队列的处理体现了调度策略,常用的是按优先级处理。有两种确定优先级的方法,即静态优先级和动态优先级。静态是指进程的优先级在进程开始运行前确定,运行过程中不变,而动态优先则可以在进程运行过程中改变。进程调度的算法是服务于系统目标的策略,对于不同的系统与系统目标,常采用不同的调度算法,如:?先来先服务(FCFS):又称先进先出(FIFO),就绪队列按先来后到原则排队。?优先数调度:优先数反映了进程优先级,就绪队列按优先数排队。?轮转法(round robin):就绪队列按FCFS方式排队。每个运行进程一次占有处理器时间都不超过规定的时间单位(时间片)。若超过,即调用调度原语而形成就绪进程轮流使用服务器。

  

相关文章

热门标签

495848