操作系统期中复习资料.doc

操作系统（期中）1. 操作系统是在计算机用户和计算机硬件之间起媒介作用的一种程序。设计操作系统的目标：使得计算机系统更容易使用。 以一种有效的方式使用计算机硬件。2. 操作系统的用途提供用户执行程序的环境。资源分配器：管理和分配资源，要尽可能公平。 （资源有：处理机、存储器、I/O设备、文件）控制程序：控制用户程序的执行I/O设备的操作和控制3. 计算机系统部件硬件：提供基本的计算资源（CPU，内存，I/O设备）操作系统：在各种应用程序和用户之间控制与协调对硬件的使用应用程序：定义解决用户问题的资源使用方式（编译、数据库、视频游戏、事务程序等）用户：人、机器、其他计算机4. 引导程序来初始化系统中的所有部分。用硬件或软件中断来表示事件的发生。中断通过中断向量把控制转移到中断服务程序中，该中断向量包含了所有服务程序的地址。现代操作系统是中断驱动的。5. 多处理器系统：（并行系统、紧耦合系统） 增加吞吐量、规模经济、增加可靠性(适度退化、容错)集群系统：（由两个或多个独立的系统耦合起来，共享数据） 提供高可用性、高性能计算。非对称集群：一台机器运行应用程序，而其他机器处于热备份模式。对称集群：多个主机都运行应用程序。分布式系统：（将计算任务分布在多个处理器上。松耦合系统：每个处理器都有自己的内存；通过各种通信设施，如高速总线、电话线等进行处理器之间的通信）资源共享、加速计算 负载均衡、可靠、通信、需要网络支持。 实时嵌入式系统：（种类变化大、具有特定的任务、操作系统仅提供有限功能）对处理器操作或数据流动有严格时间要求。明确和固定的时间约束。多媒体系统：主要处理多媒体数据，必须根据确定的时间限制来传输（流）手持系统：内存少、处理器速度慢、有限尺寸、I/O问题 分时系统：快速在CPU间切换，用户感觉随时都在交互。多路性、独立性、及时性、交互作用性并行：两个或多个事件在同一时刻发生。发生在多个CPU或CPU和I/O设备之间。 如：CPU在计算，打印机在打印。并发：两个或多个事件在同一时间间隔内发生。发生在只有一个CPU的计算机系统中，多个任务可以并发执行。 如：多个进程并发执行（单CPU）6. 微内核将所有非基本部分从内核中移走，并将它们实现为系统程序或用户程序。只有最基本的操作系统功能才放在内核中，其它的服务和应用构造在微内核之上并在用户态执行。微内核提供：存储管理，进程间通信，I/O以及中断管理。微内核的优点：便于扩充操作系统（添加新的服务，无需改变内核）、便于移植、更加安全可靠问题：由于用户空间和内核空间通信的增加会导致性能下降7. 进程 执行中的程序。进程的执行必须以顺序的方式进行。一个进程包括：代码部分、程序计数器、堆栈、数据段8. 进程与程序的区别程序是指令的有序集合，静态；进程是程序在处理机上的一次执行过程，动态。程序是永久的；进程是有生命周期的。程序的组成是指令集合；进程由代码部分，程序计数器，堆栈，数据段等组成。两者不一一对应：同一程序可在不同数据集合上多次运行（多进程）；同一进程可执行多个程序。9. 进程状态（作业）新的：进程正在被创建运行：指令正在被执行等待：进程等待一定事件的出现就绪：进程等待被分配给某个处理器终止：进程已完成执行10. 进程控制块(PCB)：操作系统通过PCB感知和管理进程包含与特定进程相关的信息：进程状态、程序计数器、CPU寄存器、CPU调度信息、内存管理信息、 记帐信息、I/O状态信息11. 长期调度程序（作业调度程序） 选择可以进入就绪队列的进程。短期调度程序（CPU调度程序） 从就绪队列选择进程，为之分配CPU。中期调度程序将进程从内存中移出，降低多道程序设计的程度。（内存不够，进程长期等待无响应）区别：短期调度程序频繁的被调用(ms) （必须要快） 长期调度程序执行的并不频繁(sec, min) （可能较慢） 长期调度程序控制多道程序设计的程度。12. 上下文切换当CPU切换到其他进程，系统需要保存原来进程的状态（CPU寄存器的值，进程状态，内存管理信息）并装入新进程的保存状态。内核将旧进程的状态保存在其PCB中。上下文切换时间是额外开销，此时系统不能做什么有用的工作。上下文切换时间与硬件支持密切相关。13. 创建进程称为父进程，而新进程称为子进程。父进程创建多个子进程，这些子进程可以再创建其他进程，从而形成了进程树。进程创建：提交进程终止：执行完最后的语句；调用exit（）；指针，数组越界；014. 进程间的通信共享内存直接通信需要通信的进程必须明确的命名：send (P, message) 发送消息到进程Preceive (Q, message) 接收来自进程Q的消息通信线路的属性：自动建立线路。一个线路只与两个进程相关。每对进程之间只有一个线路。线路可以是单向的，但通常是双向的消息传递间接通信消息通过邮箱或端口来发送和接收。每个邮箱都有一个唯一的标识符。如果两个进程共享一个邮箱，那它们可以进程通信。通信线路的属性：只要一对进程共享一个邮箱，通信线路就建立了。一个线路可以与两个或更多的进程相关联。两个通信的进程之间可有多个不同的线路。线路可以是单向的，也可以是双向的15. 线程（轻型进程）是CPU运行的基本单元。它包含：程序计数器、寄存器集、栈空间 线程是进程的一部分。线程是CPU使用的基本单元。属于同一进程的所有线程共享进程的所有资源。如果一个进程拥有多个线程，这些线程之间可以并发。16. 线程与进程的比较调度：线程是调度的基本单位，同一进程中的线程切换不会引起进程切换并发：线程可以提高系统的并发性资源：进程拥有资源，是资源分配的基本单位；线程不拥有资源，但它共享创建它的进程所拥有的资源上下文切换：线程的上下文切换代价比进程小17. 用户线程：线程的管理由用户级线程库实施。内核看不到用户线程，线程的创建和调度在用户空间，不需内核干预。内核线程：由内核支持。创建和调度在内核空间，需内核干预。18. CPU调度程序调度程序从内存中就绪可执行的进程里选择一个，并为之分配CPU。CPU调度在如下环境下发生：1.从运行状态切换到等待状态； 2.从运行状态切换到就绪状态；3.从等待状态切换到就绪状态； 4.进程终止。发生在1和4环境下的调度称为非抢占式调度。其他环境下，称为抢占式调度。（“新”状态到就绪队列发生的调度）19. 调度准则CPU使用率：使得CPU尽可能忙。吞吐量：一个时间单元内所完成进程的数量。周转时间：从进程提交到进程完成的时间间隔。等待时间：进程在就绪队列中等待所花时间之和。响应时间：进程从提交请求到产生第一响应的时间。是开始响应所需时间，而不是输出响应所需时间。20. 调度算法先到先服务调度FCFS 如果短进程晚于长进程到达，就会产生护航效果最短作业优先调度SJF 非抢占式：一旦进程拥有CPU，它的使用权只能在该CPU区间结束后才让出。抢占式： 当一个新进程到达，它的CPU区间比当前正在执行的进程剩余的CPU区间要短，则新进程抢占CPU。（最短剩余时间优先调度(SRTF)）。优先权调度 CPU被分派给优先权最高的进程（数值最小 ，优先权最高） 问题：饥饿 低优先权的进程可能永远得不到执行。解决方案：老化 视进程等待时间的延长而增加进程的优先权。轮转法调度(RR) 每个进程得到一小段CPU时间（时间片），通常为10-100ms。当时间片用完，进程被抢占并插入到就绪队列的末尾。21. 进程同步背景对共享数据的并发访问可能导致数据的不一致性。要保持数据的一致性，就需要一种保证并发进程的顺序执行的机制。有界缓冲问题的共享内存解决方案允许在缓冲内同时最多只有BUFFER_SIZE 1项。 竞争条件：多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关。为了防止竞争条件，并发进程必须实现同步。22. 临界区问题n个进程竞争使用某个共享数据。每个进程有一个代码段，称为临界区，在该区中进程访问共享数据。问题 确保当一个进程在临界区内执行时，没有其他进程被允许在临界区内执行。通用结构：do entry sectioncritical sectionexit sectionreminder section while (1);准则：互斥。如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行。有空让进。如果没有进程在其临界区内执行且有进程希望进入临界区，那么只有那些不在剩余区内执行 的进程能参与决策，以选择谁能下一个进入临界区，且这种选择不能无限推迟。有限等待。在一个进程做出进入其临界区的请求到该请求被允许期间，其他进程被允许进入其临界区的次数存在一个上限。假定每个进程的执行速度不为0。不能对n个进程的相对速度作任何假设。23. 二进制信号量: 值仅限于0和1,称为互斥锁 mutex = 1;do wait(mutex);/ critical sectionsignal(mutex);/ remainder section注意：wait(mutex)和signal(mutex)必须成对出现！计数信号量：值域不受限制。控制访问具有若干实例的某种资源，初始化为可用资源数量申请资源wait() 释放资源signal() 信号量计数为0，申请资源的进程阻塞计数信号量的物理含义：S 0表示有S个资源可用；S = 0表示无资源可用；S 0则| S |表示S等待队列中的进程个数。wait(S):表示申请一个资源; signal(S):表示释放一个资源；信号量的初值应该大于等于0wait和signal操作必须成对出现，有一个wait操作就一定有一个signal操作。当为互斥操作时，它们处于同一进程。当为同步操作时，则不在同一进程中出现。如果wait(S1)和wait(S2)两个操作在一起，那么wait操作的顺序至关重要,一个同步wait操作与一个互斥wait操作在一起时同步wait操作在互斥wait操作前。而两个signal操作无关紧要。24. 死锁的特征四个条件同时出现，死锁将会发生：互斥：一段时间内某资源只由一个进程占有。占有并等待：一个进程保持至少一个资源，又提出新的资源要求，而该资源已被其他进程占有。非抢占：资源只能在进程完成后，由占有资源的进程主动释放。循环等待：有一个等待状态的进程集合P0, P1, , Pn，P0正在等待一个P1占用的资源，P1正在等待P2占用的资源，Pn1正在等待Pn占用的资源，Pn正在等待P0占用的资源。25. 处理死锁的方法确保系统永远不会进入死锁状态。运行系统进入死锁状态，然后恢复。忽略这个问题，假设系统中从未出现死锁。这个方法被大多数OS使用，包括UNIX。26. 银行家算法每类资源有多个实例。每个进程必须事先申明资源的最大使用量。当一个进程请求资源时，它可能需要等待。当一个进程得到所有资源，它必须在有限时间内释放。数据结构n为进程数，m为资源类型数Available: 含有m个元素的数组。Available j = k表示系统中现有k个Rj类资源。Max: n x m的矩阵。Max ij = k表示Pi进程需要Rj类资源的最大数目为k。Allocation: n x m的矩阵。Allocation ij = k表示Pi进程目前已分配了Rj类资源k个。Need: n x m矩阵。Need ij = k表示Pi进程还需要Rj类资源k个才能完成其任务。Need ij = Maxij Allocation ij安全性算法1. 设置Work和Finish两个数组，长度分别是m和n。初始化为： Work = Available Finish i = false(for i = 1,2, , n)2. 找到i，满足： (a) Finish i = false (b) Needi =Work 如果没有找到这样的i，执行步骤4。3. Work = Work + Allocationi; Finishi = true; go to step 2;4. 如果所有进程的Finish i = true，则系统处于安全状态。进程Pi的资源请求算法Requesti是进程Pi的资源请求向量。Requesti j = k表示进程Pi需要k个Rj类型的资源。1. 如果Requesti = Needi，转向步骤2；否则，认为出错，因为进程需要的资源数超过了它宣布的最大量。2. 如果Requesti 正式将资源分配给进程Pi。如果是不安全的 =Pi必须等待，并恢复原先的资源分配状态。27. 死锁检测每种资源类型有多个实例Available: 长度为m的向量，表示每类资源的可用数目。Allocation: n x m的矩阵，表示当前每个进程分配到的各类资源的数目。Request: n x m的矩阵，当前每个进程请求各类资源的数目。例如，Request ij = k表示进程Pi现在请求Rj类型的资源k个。检测算法1. 设置Work和Finish两个向量，长度分别是m和n，初始化为： (a) W