《操作系统》

《操作系统》第一部分操作系统引论操作系统的目标:•方便性（用户的观点）：提供良好的、一致的用户接口，弥补硬件系统的类型和数量差别•有效性（资源管理的观点）：管理和分配硬件、软件资源，合理地组织计算机的工作流程•可扩充性（开放的观点）：硬件的类型和规模、操作系统本身的功能和管理策略、多个系统之间的资源共享和互操作•开放性:实现应用的可移植性和互操作性的要求作用和层次模型；1.OS是用户使用系统硬件、软件的接口2.OS是计算机硬件、软件资源的管理者。3.OS是扩展机(extendedmachine)/虚拟机(virtualmachine)。操作系统的发展过程；1.无操作系统时代2.单道批处理系统(simplebatchprocessing)3.多道批处理系统(multiprogrammingsystem)4.分时系统(time-sharingsystem)5.实时系统(real-timesystem)6.多处理操作系统(Multi-processorOS)7.网络操作系统(NOS,NetworkOS)8.分布式操作系统(DistributedOS)9.嵌入式操作系统(EmbeddedOS)10.个人计算机操作系统(PersonalComputerOS)多道程序设计的基本概念；多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下相互穿插地运行。操作系统的特征；1.3.1并发(concurrency)1.3.2共享(sharing)1.3.3虚拟(virtual)1.3.4异步性(asynchronism)操作系统的功能:1.4.1处理机管理1.4.2存储管理1.4.3设备管理1.4.4文件管理1.4.5用户接口第二部分进程管理前趋图的作用:是一个有向无循环图，记为DAG（DirectedAcyclicGraph),用于描述进程之间执行的前后关系。程序顺序执行和并发执行的特征；顺序执行：1.顺序性2.封闭性3.结果的可再现性并发执行：1.间断(异步)性：2.失去封闭性：3.不可再现性：进程的概念和特征、进程的基本状态及转换；在多道程序设计的环境下，为了使程序能并发执行，并描述和控制并发执行的程序，必须引人新的概念－－进程。结构特征：程序段、数据段和进程控制块（PCB）(也称进程映像,进程要素)构成进程实体；通常所说的创建/撤消进程实体，实质上是创建/撤消其PCB动态性：进程的实质是进程实体的一次执行过程，是动态的。并发性：多个进程实体同时存在内存中，能在同一段时间内同时运行独立性：各进程的地址空间相互独立，除非采用进程间通信手段；异步性：进程按各自独立的、不可预知的速度（异步）向前推进进程的基本状态进程在系统中的活动规律是：执行-暂停-执行进程的三种基本状态：就绪状态：执行状态；阻塞状态（又称等待状态）进程控制块的作用、包含信息和组织方式；A.概念：系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程B.作用：系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志C.进程与PCB是一一对应的包含信息：A.进程映像(进程要素)用户程序用户数据栈用于过程调用和参数传递进程控制块PCB(执行上下文)控制进程所需的数据(进程属性)，包括:进程标识符信息处理器状态信息进程调度信息进程控制信息B.PCB的内容：调度信息：调度和状态信息–进程状态(如:运行，就绪，阻塞...)–进程优先级–该进程在等待的事件(若被阻塞)–其他信息现场信息：记录了重要的寄存器；(虚)时钟等内容C.PCB中的信息1.进程标识符2.处理机状态3.进程调度信息4.存放与进程有关调度和进程对换有关的信息5.进程控制信息组织方式：A.链接方式:把具有同一状态的PCB,用其中的链接字链接成一个队列.B.索引方式:系统根据所有进程的状态建立几张索引表,并把各索引表在内存的首地址记录在内存的一些专用单元中.操作系统内核的主要功能；原语的概念和特点；原语(primitive)：由若干条指令构成的“原子操作(atomicoperation)”过程，作为一个整体而不可分割－－要么全都完成，要么全都不做。许多系统调用就是原语。线程的引进、线程的基本概念和属性，线程与进程的联系与区别:是轻量级进程是进程内的一个执行单元是进程中一个可调度实体是程序（或进程）中相对独立的一个控制流序列是执行的上下文，其含义是现场数据和其他调度所需信息是进程内一个相对独立、可调度执行单元线程是进程内一个相对独立、可调度的执行单元。线程基本上不不拥有资源，只拥有一点在运行时必不可少的资源（如：程序记数器、一组寄存器和栈），但他可以与同属一个进程的其他线程共享进程拥有的全部资源资源。线程和进程：单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程第三部分进程的同步与通信临界资源和临界区的概念临界资源(criticalresource)A.一次仅允许一个进程使用的资源称为临界资源。B.硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行－－有些共享资源可以同时访问，如只读数据。临界区（Criticalsection）一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区进程同步机制应遵循的准则；整型信号量和记录型信号量机制；1.整型信号量信号量只能通过初始化和两个标准的原语来访问－－作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数二进制信号量(binarysemaphore)：只允许信号量取0或1值P原语wait(s)：whiles=0；--s；只要s=0，就会不断测试，违反“让权准则”，使进程处于忙等状态.V原语signal(s)：++s；2.记录型信号量–信号量表示资源的实体。它由两个成员（s，q）构成：–s：为非负初值的整型变量，表示系统中某类资源的使用情况:•s0时,其值表示系统中当前可用资源的数目•s0时,其绝对值表示系统中请求该类资源而阻塞等待的进程数目–q：是一个初始状态为空的队列–除信号量的初值外,信号量的值只能由P、V操作改变。–structsemaphore{intcount;queueTypequeue;}–记录型信号量是一种不存在“忙等”的进程同步机制。–每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其是阻塞在该信号量的各个进程的标识P原语wait(s)--s.count;//表示申请一个资源;if(s.count0)//表示没有空闲资源;{调用进程进入等待队列s.queue;阻塞调用进程;}V原语signal(s)V原语通常唤醒进程等待队列中的头一个进程++s.count;//表示释放一个资源；if(s.count=0)//表示有进程处于阻塞状态；{从等待队列s.queue中取出一个进程P;进程P进入就绪队列;}利用信号量机制解决各种进程同步问题；1.利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏semaphoreS=1;main(){cobeginP1();P2();coend}P1(){…P(S);P1进入临界区；V(S);…}2.利用信号量来描述前趋关系main（）{p1；cobeginp2；p3；coendp4}管程的基本概念及组成:管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程的组成:名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码进程通信的类型:1、共享存储系统（Shared-MemorySystem）：（1）共享数据结构：进程公用某些数据结构，借以实现进程间的信息交换。低效，只适于相对少量的数据（2）共享存储区：相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换2、消息传递（MessagePassingSystem）：系统为进程提供了两个高级通讯原语send和receive(也有用read)send：当要进行消息传递时执行sendreceive：当接收者要接收消息时执行receive消息传递系统中的发送和接受原语。第四部分调度和死锁进程调度的类型，选择调度方式和算法的准则；1.按照调度的层次•作业：又称为宏观调度、高级调度。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。•内外存交换：又称为中级调度。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。•进程或线程：又称为微观调度、低级调度。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。2.按照调度的时间周期•长期(long-term)：将进程投入允许执行进程缓冲池中，或送到退出进程缓冲池中。进程状态：New－Readysuspend,Running－Exit•中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready－Readysuspend,Blocked－Blockedsuspend•短期(short-term)：选择哪个进程在处理机上执行。进程状态：Ready－Running•I/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。3.按照OS的分类•批处理调度－－应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）•分时调度、实时调度：通常没有专门的作业调度•多处理机调度调度方式：–非抢占方式（非剥夺方式）：某一进程正在执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行。直到该进程完成或发生某种事件而进入完成或阻塞状态，才把处理机分配给更为重要或紧迫的进程–抢占方式（剥夺方式）：某一进程正在执行时，当有某个更为重要或紧迫的进程进入就绪队列，立即暂停正在执行的进程。把处理机分配给该更为重要或紧迫的进程。抢占原则有：优先权原则短作业优先原则时间片原则（分时系统，多数实时系统，要求高的批处理系统）3.2调度算法通常将作业或进程归入各种就绪或阻塞队列。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。3.2.1先来先服务3.2.2短作业优先3.2.3时间片轮转算法3.2.4多级队列算法3.2.5优先级算法3.2.6多级反馈队列算法先来先服务、短作业（进程）优先、时间片轮转和高响应比优先调度算法；•3.2.5.4高响应比优先调度算法(HRRN,HighestResponseRatioNext)等待时间+要求服务时间高响应比优先权=————————————要求服务时间响应时间=—————————要求服务时间=Rp高响应比优先调度算法的特点：当作业等待时间相同短作业的优先权越高有利于短作业.当要求服务时间相同等待时间越长,优先权越高先来先服务.对于长作业等待时间的增加优先权提高也能获得CPU.响应比计算,会增加系统开销.实时系统中调度要求和调度算法；3