考研计算机操作系统学习笔记

1第一章操作系统引论操作系统的定义：是计算机系统中的一个系统软件，管理和控制计算机系统中的硬件和软件资源，合理的组织计算机的工作流程，以便有效利用这些资源为用户提供一个功能强大、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。1.1操作系统的目标与作用1.目标：有效性、方便性、可扩充性、开放性2.作用：a.OS作为用户与计算机硬件系统之间的接口；b.OS作为计算机系统资源的管理者；c.实现了对计算机资源的抽象3.操作系统为用户提供三种类型的使用接口：1.命令方式；2.系统调用方式；3.图形、窗口方式1.2操作系统的发展过程无操作系统的计算机系统、批处理系统（单道、多道）、分时系统、实时系统1.单道批处理系统特征：自动性、顺序性、单道性。多道批处理系统的优缺点：优点：资源利用率高、系统吞吐量大；缺点：平均周转时间长、无交互能力。2.分时系统和实时系统的特征：分时系统的特征：多路性、独立性、及时性、交互性、可靠性实时系统的特征：实时性、可靠性、安全性3.分时系统和实时系统的比较：a.及时性：实时信息处理系统对实时性的要求与分时系统类似都以人所能接受的等待时间来确定，但实时控制系统的及时性则是以控制对象所要求的开始截止时间或完成截止时间来确定的；b.交互性：实时信息系统虽然也具有交互性，但其交互性仅限于访问系统中某些特定的专用服务程序，不像分时系统能向终端用户提供数据处理和资源共享等服务；c.可靠性：分时系统虽然也要求系统可靠，但相比实时系统则要求系统具有高度的可靠性。1.3操作系统的基本特性基本特性：并发性、共享性、虚拟技术、异步性1.4操作系统的主要功能操作系统的主要任务：为多道程序的运行提供良好的运行环境，以保证多道程序能有条不紊的、高效的运行，并能最大程度的提高系统中各种资源的利用率和方便用户的使用。主要功能：处理机管理（进程管理、进程同步、进程通信、处理机调度）存储器管理（内存分配、内存保护、地址映射、内存扩充）设备管理（设备管理、设备分配、设备处理、虚拟设备）文件管理（文件存储空间的管理、目录管理、文件读/写管理和保护）1.5操作系统与用户之间的接口：1.用户接口：供用户组织和控制作业的执行和管理计算机系统；2.程序接口：供编程人员使用操作系统提供的系统调用来请求操作系统提供服务。1.6OS结构设计1.操作系统结构：无结构OS、模块化结构OS、分层式结构OS、微内核结构OS2.微内核技术：把操作系统中更多的成分和功能放到更高的层次（用户模式）中去运行，而留下一个尽可能小的内核，用它来完成操作系统最基本的核心功能，称之为微内核技术。补1.计算机操作系统的性能指标系统可靠性、系统吞吐量、资源利用率、周转时间、可移植性、可扩展性系统吞吐量：指系统在单位时间内处理的信息量；周转时间：指用户从提交作业到得到计算结果这段时间，又称系统响应时间。补2.硬件将处理机划分为两种状态即管态和目态2这样做对操作系统设计的作用：便于设计安全可靠的操作系统，管态和目态是为保护操作系统免受用户程序的干扰和破环而引入的两种状态。通常操作系统在管态下运行，可以执行所有机器指令；而用户进程在目态下运行，只能执行非特权指令。如果用户进程企图在目态下执行特权指令，将会引起保护性中断，终止该程序的执行，从而保护了操作系统。第二章进程管理2.1进程的基本概念1.进程:进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立的基本单位。2.进程的特征：动态性、并发性、独立性、异步性3.进程的结构：程序段、相关数据段、PCB（进程控制块）PCB是进程实体的一部分，是进程在系统中存在的唯一标识，是操作系统中重要的记录型数据结构，它记录了操作系统所需的一些用于描述进程的当前情况以及控制进程运行的全部信息。（PCB中包括：进程标识符，处理机状态、进程调度信息、进程控制信息）4.进程的三种基本状态：就绪、执行、阻塞5.进程和程序的比较：○1动态性：程是有一定的生命周期的动态实体，“它由创建而产生，由调度而执行，由撤销而消亡。”；程序则是一组有序指令的集合，是静态的实体。②并发性：进程有并发性，这也是进程的重要特性；程序是不能并发执行的；③独立性：进程是一个能独立运行、独立分配资源和独立接受调度的基本单位；程序不能作为一个独立的单位参与运行。2.2进程的控制1.原语：由若干条指令组成的，用于完成一定功能的一个过程，它是一个不可分割的基本单位，即在执行过程中不允许被打断。其作用是实现进程的通信和控制。P、V操作：wait(S):whileS=0dono-op;S:=S-1;signal(S):S:=S+1;2.进程的创建：a.申请空白PCB；b.为新进程分配资源；c.初始化进程控制块；d.将新进程插入就绪队列。3.引起进程阻塞（唤醒）的事件：a.请求系统服务；b.启动某种操作；c.新数据尚未到达；d.无新工作可做。2.3进程的同步1.进程同步：是对多个相关进程在执行次序上进行协调，以使并发执行的诸程序之间能有效地资源共享和相互合作，从而使程序的执行具有可再现性。2.临界资源、临界区：临界资源：诸进程间采取互斥方式实现对某资源的共享，该资源则为临界资源。即临界资源是指每次仅允许一个进程访问的资源。临界区：人们把在每个进程中访问临界资源的那段代码称为临界区。3.同步机制规则：a.空闲让进；b.忙则等待；c.有限等待；d.让权等待。34.信号量机制用于解决进程同步问题。信号量机制包括：a.整形信号量；b.记录型信号量；c.AND型信号量；d.信号量集2.4经典进程的同步问题生产者-消费者问题、哲学家进餐问题、读者-写者问题2.5进程通信高级进程通信机制分为三大类：a.共享存储器系统；b.消息传递系统；c.管道通信系统。1.共享存储器系统实现方式：相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。2.消息传递系统实现方式：进程间的数据交换以格式化的消息为单位。3.管道通信系统实现方式：通过“管道”（即一个共享文件）连接一个读进程和一个写进程以实现他们之间的通信。2.6线程1.引入进程、线程的目的：引入进程的目的：为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。引入线程的目的：减少程序在并发执行时的时空开销，使操作系统具有更好的并发性。2.线程与进程的比较：a.调度：线程作为调度和分派的基本单位；而进程作为资源拥有的基本单位。在同一进程中，线程的切换不会引起进程的切换，但从一进程中的线程切换到另一进程中的线程时，将会引起进程切换。b.并发性：不仅进程之间可以并发执行，而且在同一进程中的多个线程之间亦可以并发执行，使操作系统具有更好的并发性，从而有效提高系统资源的利用率和系统的吞吐量。c.拥有资源：进程拥有资源，进程是系统中拥有资源的一个基本单位；线程自己不拥有资源（也拥有一些自身必不可少的资源），但它可以访问其隶属进程的资源。d.系统开销：就切换代价而言，进程的系统开销远高于线程。3.线程的实现方式：内核支持线程、用户级线程、组合线程第三章处理机调度与死锁3.1处理机的调度层次高级调度、低级调度、中级调度1.高级调度：又称作业调度，根据某种算法，把存放在外存上处于后备队列中的作业调入内存，他的调度对象是作业。作业：包含了程序和数据，还配备一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，都是以作业为基本单位从外存调入内存。2.低级调度：又称进程调度，根据某种算法从就绪队列中选取进程，再由分派程序把处理机分配给该进程。进程调度方式：抢占方式和非抢占方式抢占方式的原则：a.优先权原则；b.短作业（进程）优先原则；c.时间片原则3.中级调度：把那些暂时不能运行的进程调至外存上去等待，当这些进程具备运行条件且内存中有空闲时，再由中级调度把外存上的这些进程又重新调入内存，挂在就绪队列上，等待调度。3.2调度队列模型和调度准则3.3调度算法【公式：周转时间=完成时间-到达时间=等待时间+运行时间；带权周转时间=周转时间/运行时间】先来先服务（FCFS）4短作业（进程）调度算法（SJ(P)F）高优先权优先调度算法（FPF）【高响应比优先调度算法】时间片轮转调度算法【时间片轮转法、多级反馈队列调度算法】实时调度算法【最早截止时间优先调度算法（EDF）、最低松弛度优先（LLF）】1.高响应比优先调度算法：如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高；如果要求服务的时间相同。作业的优先权决定于等待时间，等待时间愈长其优先权愈高。优点：该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。缺点：每次进程调度时，都须先做响应比的计算，这会增加系统开销。2.时间片轮转法：系统将对就绪进程按先来先服务的原则排成一个队列，每次调度时都把cpu分配给队首进程，并令其执行一个时间片，当执行的时间片用完时，由计时器发出中断请求来停止该进程的执行，并将其送往就绪队列末尾，然后把处理机分配给队列中新的队首进程。时间片的大小选为略大于一次典型的交互所需要的时间，这样可使大多是进程在一个时间片内完成。时间片轮转法可以使多个终端都能得到系统的及时响应。3.4实时调度3.5产生死锁的原因和必要条件1.死锁：死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态之下时，若无外力作用，他们都将无法再向前推进。2.产生死锁的原因：竞争资源、进程间推进顺序不当3.死锁产生的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路条件4.处理死锁的方法：预防死锁、避免死锁、检测死锁、解除死锁○1预防死锁：该方法是通过设置某些限制条件，去破环产生死锁的四个必要条件中的一个或几个，来预防死锁的发生。○2避免死锁：它并不事先采取各种限制性措施去破环死锁条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。○3检测死锁：允许系统在运行过程中发生死锁，但系统所设置的检测机构会及时地检测到死锁的发生，并确定发生死锁的有关进程和资源。○4解除死锁：与检测死锁相配套的一种措施，当检测到死锁发生时，须将进程从死锁状态中解脱出来。3.6预防死锁、避免死锁及解除死锁的方法1.预防死锁办法：摒弃“请求和保持”条件、摒弃“不剥夺”条件、摒弃“环路”条件2.避免死锁办法：银行家算法3.解除死锁的方法：○1剥夺资源：从其他进程处剥夺足够数量的资源给死锁进程，以解除死锁状态。○2撤销进程：a.使全部死锁进程都夭折掉；b.按照某种顺序逐个地撤销进程，直至有足够的资源可用，使死锁状态消除为止。第四章存储器管理54.1存储器的层次结构4.2程序的装入和连接程序的装入（方式）：绝对装入方式、可重定位装入方式、动态运行时装入方式程序的连接（方式）：静态连接方式、装入时连接方式、运行时动态连接方式4.3连续分配方式单一连续分配、固定分区分配、动态分区分配、可重定位分区分配动态分区分配的数据结构和分配算法：1.数据结构：空闲分区表和空闲分区链2.分配算法：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法、快速适应算法○1首次适应算法：以空间分区链为例，在分配内存时，从链首开始顺序查找，直至找到一个大小满足要求的分区为止，然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。优点：优先利用内存中低址部分的空闲分区，从而保留高址部分的大空闲区，为以后到来的大作业分配大的内存空间创造了条件。缺点：a.低址部分不断的被划分，留下许多难以利用的小的分区；b.每次查找又都是从低址部分开始，6增加查找可用分区时的开销。○2循环首次适应算法：该算法由首次适应算法演变而成，在分配空间时，不再是每次从链首开始查找，而是从上次找到的空间分区的下一个空间分区开始查找，直至找到一个满足要求的空闲分区，从中划出与请求大小相等的内存空间分配给作业。优点：使内存中空间分区分配的更均匀，且减少了查找分区空闲分区时的开销。缺点：会缺乏大的空闲分区。○3最佳适应算法：该算法总是把满足要求，又