中山大学操作系统复习提纲.doc

操作系统复习提纲1）： 什么是OS？，目的，功能 操作系统是一种管理计算机硬件的程序，为应用程序提供了基本的运行条件，在计算机用户和计算机硬件之间扮演着中介的角色。 操作系统是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。2）中断形式，process获取CPU的形式，双模，特权非特权，中断形式：软中断（trap）和硬中断通过指定一些能够造成伤害的机器指令作为特权指令可以实现这种保护，特权指令只能在监控模式下执行，在用户模式下运行会自陷给os。通过调用特权指令，可以执行只有操作系统才能执行的任务。完成与操作系统的交互。 为了阻止用户执行非法的 I/O 操作，我们将所有的I/O 指令定义为特权指令。 在系统引导时，硬件以监控模式开始运行。然后装入操作系统并以用户模式开启用户进程。无论自陷和中断何时发生，硬件都会从用户模式转向监控模式（将模式位的状态转为0）。这样，不管操作系统何时获得计算机的控制权，它都处于监控模式。在将控制转给用户程序前系统总是要转为用户模式（通过将模式位设置为1）。指具有特殊权限的指令。这类指令只用于操作系统或其他系统软件，一般不直接提供给用户使用。 在多用户、多任务的计算机系统中特权指令必不可少。它主要用于系统资源的分配和管理，包括改变系统工作方式，检测用户的访问权限，修改虚拟存储器管理的段表、页表，完成任务的创建和切换等。 常见的特权指令有以下几种:（1）有关对I/O设备使用的指令 如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。（2）有关访问程序状态的指令 如对程序状态字（PSW）的指令等。（3）存取特殊寄存器指令 如存取中断寄存器、时钟寄存器等指令。（4）其他指令这得从CPU指令系统(用于控制CPU完成各种功能的命令)的特权级别说起。在CPU的所有指令中，有一些指令是非常危险的，如果错用，将导致整个系统崩溃。比如：清内存、设置时钟等。如果所有的程序都能使用这些指令，那么你的系统一天死机n回就不足为奇了。所以，CPU将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统及其相关模块使用，普通的应用程序只能使用那些不会造成灾难的指令。形象地说，特权指令就是那些儿童不宜的东东，而非特权指令则是老少皆宜。3）communication model 图的好处和用途Common system components 进程管理，主存管理，辅存管理，文件管理，网络，I/O系统管理，保护系统，命令解释系统。Communication model 包括两种模型：消息传递模型，共享存储器模式。 消息传递模式：建立连接，知道通信名称（同一台机的不同进程，或者通过通信网络连接的不同主机上的进程），主机名称，或进程被os引用为等效标示符，在同一主机上，用文件系统调用（open，close），不同主机？（系统调用船体）。接受连接的进程为os提供特定用途的“守护进程”，接受连接进程要发确认信息。通过读写信息系统来完成信息交换。主要特点：交换数据量小，计算机间连接更容易实现共享存储器模式：进程利用map memory调用访问其他进程的内存。请求解除限定，他们可以在这些共享空间上读写数据来交换信息。主要特点：最高速度传递，便利，完成计算机内的复杂同步。第四章：process定义，上下文切换，PCB，例子的分析。父子进程。 Process，program in execution。一个工作单元。程序是静态实体（就像是存储在磁盘上的文件），进程是动态实体，它有一个程序计数器指明下一条要执行的指令，并且拥有一组相关的资源。进程的不同状态：新：进程正被创建。运行：（进程的）指令正被执行。等待：进程正在等待发生一些事件（如I/O 完成或接收一个信号）。就绪：进程正等待分配处理器。终止：进程结束运行PCB（进程控制块） 进程状态：该状态可能是新、就绪、运行、等待、停止等等。l 程序计数器：该计数器指明了该进程要执行的下一条指令的地址。l CPU 寄存器：基于计算机体系结构，这些寄存器的数量和类型很不相同。这包括了累加器、变址寄存器、栈指针、通用寄存器，以及条件信息（condition-code information）。连同程序计数器，在中断发生时必须要保存这些状态信息，这样便于后来进程继续正确执行（图4.3）。l CPU 调度信息：包括进程优先权、指向调度队列的指针和其它的调度参数。（第六章描述进程调度。）l 存储器管理信息：可能包括诸如基址寄存器和界限寄存器值、页表或段表，这取决于操作系统所选用的存储系统（第九章）。l 记账信息（accounting information）：包括CPU 数量和实时使用量、时间限制、账户数目、作业或进程数目等等。l I/O 状态信息：包括分配给该进程的I/O 设备的列表、打开的文件的列表等等。PCB 只是存储信息，而进程间的这些信息是不同的。处理器每次只处理一个process，PCB与program counter 之间切换。上下文切换： 当CPU转换到另外一个进程时，系统发配程序将旧进程的状态存储在PCB中，然后将新进程状态载入。上下文转换时间是纯粹的开销，因为在转换进行时系统不能做任何有用的工作。需求时间依硬件设施的支持。父子进程进程在运行期间通过调用创建进程系可以创建多个新进程，创建进程的进程称作：父进程，而产生的新进程称作为：子进程。当一个进程创建了一个新进程时，会以两种可能的方式执行：1. 父进程（继续执行）与子进程并行执行。2. 父进程等待部分或全部子进程终止执行。新进程的地址空间也有两种可能：1. 子进程是父进程的一个拷贝。2. 载入一个程序运行。在新（子）进程中fork 的返回码是零，而父进程中fork 的返回码是子进程的进程号（非零）也就是说当pid0的话那么就是在父进程里面。进程运行完毕后，由操作系统将其删除，并回收所有资源、结果返回父进程（可能）。父进程终止，其子进程也必须终止。父进程可能会出于某个原因而结束它的一个子进程，例如：l 子进程需要更多的资源。（The child has exceeded its usage of some of the resources that it has beenallocated.）这需要父进程能够检查其子进程的状态。l 分配给子进程的任务已经不再需要。l 父进程退出，而且操作系统禁止子进程在父进程终止后继续执行。在这样的系统中，如果一个进程（正常或非正常）终止，那么它的所有子进程也必须要终止。这种级联式的进程终止通常是操作系统发起的。第五章：many to one ， one to one，的理解与画图。程序段的分析。 线程是CPU的调度对象，是CPU上运行的最小单元。由堆栈和寄存器，以及program counter组成。一个进程包括多条线程，因此线程分享DATA，Code，OS资源。线程是最小运行单元，而进程是最小资源分配单元。 分清user thread 和 kernel thread的区别。User thread是由线程库创建，管理以及调度。更快。而内核线程有内核创建，管理，以及调度。一个user thread必须和一个内核线程一起，才能在CPU上运行。 多线程： Many to one 是指多个用户线程映射到一个内核线程，适用于不支持多内核线程的os。而0ne to one是指一个进程中的每个线程都对应一个kernel thread。再由os调度CPU处理kernel thread。 图见ppt。 Java 是提供了线程的建立于管理的一种语言，它不属于用户线程，也不属于内核线程。通过创建一个继承thread类的新类，然后重载其run的方法。 任何一个Java程序都至少有一个控制执行序列。即当只有主函数时也将其当做一线程处理。由于继承类方法不显明的创建了线程，实际中用Start的方法。1. 在 JVM 中为新线程分配内存并初始化该线程。2. 调用 run 方法，使该线程能够在JVM 中运行。（注意：永远不要直接调用run 方法。而是调用start方法，然后由它调用run 方法。） 这个问题的程序段，一般理解为继承thread的新类，并且重载其run方法/程序段解释类似于此法：当 Summation 程序运行时，JVM 创建两个线程。第一个是与应用程序关联的线程该线程在主函数中开始执行。第二个线程是由start 方法直接创建的Summation 线程。Summation 线程在它的run 方法中开始执行。当该线程从run 方法中退出时就终止运行。第六章：抢占型，非抢占型 调度算法，平均时间 6.15 优先级 round robine？ 一个I/O 繁忙型程序通常有很多非常短的CPU burst。一个CPU 繁忙型程序可能有少数非常长的CPU burst。这种分布（distribution）能够帮助我们选择一个合适的CPU 调度算法。 在如下的四种情况下可能会进行 CPU 调度：1. 当进程从运行状态转换到等待状态时（ 例如：I/O 请求或等待一个子进程的终止）（for example, I/Orequest, or invocation of wait for the termination of one of the child processes ）2. 当进程从运行状态转换到就绪状态时（例如：当发生中断时）3. 当进程从等待状态转换到就绪状态时（例如：I/O 完成）4. 当进程终止时在出现了CPU调度的前提下才有抢占型与非抢占型之分。第一和第四种情况为非抢占型（即只能从就绪队列中调出一个新的进程来）。而其他未抢占型。因为可选择。进程运行包括： CPU burst I/O burst。交互式进行，最后一个由CPU burst 结束。调度程序停止一个进程并开始运行另一个进程所需的时间被称为调度时间（Dispatch latency）。调度程序（dispatcher）的：其工作包括：l 转换上下文l 转换到用户摸式l 跳转到用户程序中的正确位置重新开始该程序调度算法一些准则： CPU utilization , Throughput(吞吐量)：对工作量的一种测量是单位时间内完成的进程数， Turnaround time（周转时间）：从进程提交到进程完成的时间间隔。Waiting time : 等待时间是进程在就绪队列中耗费时间的总和 Response time：进程提交请求到首次响应时间。护送效应（convoy effect）：即短进程在长进程之后。1） FCFS 即先来先到原则,计算等待时间，长进程放后面比较有效率2） SJF短作业优先：即利用下一个CPU burst的时间，分配给长度最小的进程，如果有两个进程的CPU burst 一样，则采取FCFS原则。还分为抢占式与非抢占式。抢占式（Preemptive）就是当一个进程正在运行，此时一个新的进程进来，他的CPU burst时间比正在运行的进程剩余时间短，则抢占执行。非抢占则允许执行完即在最短作业优先的前提下不打扰。3） 优先级（priority）调度，抢占型即优先级高的达到时抢占当前的进程。（本书中小数字代表高的优先级。）缺点是：优先级低的有可能永远得不到cpu，解决办法，aging（老化）即：等待时间越长，优先级也随之提高4） RR （round robin）（轮转调度法） ：即将就绪队列看成一个循环队列。每隔一个时间单元就转换一次，分配给不同进程。就绪队列满足FCFS原则。新进的进程放入队列末尾，当一个进程运行完一个时间量之后，由进程调度程序进行进程调度，将此进程中断放入到此队列末尾。如此循环。超过一个时间量，中断处理。一个原则是百分之八十的进程的CPU burst 应该短于时间量。第七章：管理java同步，机器指令，打断，数据不一致性 临界段的作用，实现方法。忙等待，非忙等待的实现代码7.39。信号量，实现代码等。 协作进程同时对共享数据进行操作，会造成数据的不一致性。 进程的同步解决两个进程同时访问数据，造成数据的不一致性。 当一个进程在其临界区内执行时就不允许其它进程在它的临界区内执行 进入区，临界区，推出区，剩余区。 临界区必须满足三个条件：1 互斥，2有空让进，3 有限等待 算法1：是共享了一个整数变量。记录哪个进程进入临界段，而不能达到有空让进的功能。 算法2：用数组boolean flag2代替了turn。将flag初始化为false。但是此算法没有满足有限等待的条件。当两个flag都为true时，都在等待while，即对方变为false、所以一直循环。 算法3：利用法1，与法2的变量 boolean flag2; int turn; 初始化 flag0 = flag1 = false，turn 的值无关紧要（但是0 或者是1）。 public void enteringCriticalSection(int t) int other = 1 - t; flagt = true; turn = other; while ( (flagother = true) & (turn = = other) ) Thread.yield();此段代码只要满足flag的要求，注意此段代码 信号量： 信号量S 是一个整形数，除初始化以外，对它的访问只能通过两个标准原子操作：wait和signal。其是用来解决n个信号量的临界区问题。一个被阻塞而等待信号量 S 的进程应该能够在其它进程执行signal 操作后被重新开始。wakeup 操作重新开始进程，它把进程的状态从等待状态转为就绪状态。信号量S只能被两个原子操作：wait (S) signal (S) S+;while (S = 0) ; /no-op S-; )每个信号量有一个整形数和一个进程列表block 操作将一个进程置入与该信号量关联的等待队列中并将进程状态设为等待。wakeup 操作重新开始进程，它把进程的状态从等待状态转为就绪状态。signal 操作将进程从等待进程列表中移除并唤醒该进程。wait 操作定义如下：void wait(semaphore S) S.value-;if (S.value 0) add this process to S. L;block( );signal 操作定义如下：void signal(semaphore S) S.value+;if (S.value = 0) remove a process P from S. L;wakeup (P);block 操作将挂起调用它的进程。wakeup(P)操作恢复执行一个被阻塞的进程。这两个操作由操作系统作为基本的系统调用提供。 两个或多个进程无休止的等待发生一个事件，而这个事件只能由等待中的某个进程引发。问题中的这个事件是指signal 操作的执行。当达到这样的一个状态时，我们称这些进程被死锁（deadlock）。饥饿 ，操作系统是指一个进程一直得不到资源。忙等待Do sth;while( condition ) ;Do sth;非忙等待Do sth;if( condition ) release CPU and waiting Do sth;在producer 与 consumer 的经典问题时候， 注意empty是指空缓存区的数目，而full指满缓存区的数目，而操作produce是指生产满缓存区的，而consume是生产空缓存区的。因此下面代码好理解。 读者与写者的问题（多个进程共享一个数据对象）只分析而不是写代码，要看懂！ 读者无需等待。因为不会造成数据不一致性，而写者会，所以要求互斥，也即有一写者时，则无其他任何操作。在上面P操作等价与wait 而V操作等价去signal操作。读是读取这个数据结构的内容，而写是更新这个数据结构的内容（而不是写入），因此在write代码实现的过程中，public void startWrite() db.P();public void endWrite() db.V();所以在开始写的时候要先占用数据，因此调用P函数。 管程： 管程一次只执行一个线程，而程序员可以自己设定条件 第七章半桶水，有时间再看一遍，没时间抓考试重点。第八章：死锁的预防，避免（不破坏）的区别在多道程序设计环境中，多个进程可能要为有限的资源展开竞争。进程请求资源；如果当前这些资源不可用，那么该进程进入等待状态。正在等待的进程可能不会再改变状态，因为它所请求的资源一直被其它进程所持有。这种情况被称为死锁（deadlock）资源被分为三个过程：请求 使用，释放。发生死锁的四个必要条件：1：互斥条件，即同时只有一个进程使用该资源。2：持有并等待，即进程必须持有一个资源并且等待下一个资源。3：不抢占：即一个进程执行完后会释放该资源4：循环等待。即一个等待一个。 死锁预防：死锁预防算法通过对约束资源请求来预防死锁的发生。这种约束确保了至少有一个死锁的必要条件不会发生，从而达到预防死锁的目的，造成资源利用率低。 就是让发生死锁的四个条件有一个不发生，或者说破坏发生死锁的四个条件之一，便可以预防死锁的发生。1） 破坏互斥，2） 破坏持有并等待，1：即在一个进程要申请其他资源的时候必须释放前面所拥有的资源，2：必须一次性申请所有必要的资源。3） 不抢占，当一个进程需要等待其他资源的时候，那此时他所拥有的资源放入等待序列中，可以被抢占。4） 循环等待，每个资源对应一个正整数，当一个进程拥有一个资源的时候，再需要申请另外一个资源的时候，此资源的正整数必须大于先前的资源。死锁避免有了这个进程的请求和释放资源的完整队列我们就可以确定请求进程是否应该等待。为了判断当前的请求是应该满足还是延迟以避免可能发生的死锁们就可以确定请求进程是否应该等待。为了判断当前的请求是应该满足还是延迟以避免可能发生的死锁、第九章 1：实程管理虚存管理的区别，2：page解决连续存放的什么问题，3：外部分割 4：swapping overlay 不考 ，5：往年只考段共享 shared page 9-52 why？9-34，9-40 内存的管理方法有：分页，与分段。其由大量字与字节队列构成，每个字与字节都有其相应的地址。由于程序在运行过程中，要经过编译，连接，编入等，每次所对应的地址空间都不一样，这就涉及到一个地址映射问题。 CPU 产生的地址通常被称为逻辑地址（虚拟地址）。而物理地址则是内存单元的地址，也就是被装入内存的内存地址寄存器（memory-address register）的地址。 内存管理单元（MMU）为：逻辑地址到物理地址的映射机制。Swapping：进程必须在内存中才能执行。然而，可以暂时把一个进程从内存换出到后备存储器（backing store）中，然后将它换回继续执行 进程必须在内存中才能执行。然而，可以暂时把一个进程从内存换出到后备存储器（backing store）中，然后将它换回继续执行。利用重定位寄存器和界限寄存器，可以实现内存保护。内存分配方法：首先适应策略：分配第一个足够大的连续空间。可以从连续空间列表的最开头开始搜寻，也可以从上一次搜寻的结尾