华南理工大学《高级操作系统》复习资料

华南理工大学《高级操作系统》复习资料Ch1.【linux内核特点】Linux是单内核，但汲取了微内核的精华，其特点如下：(1)支持动态加载内核模块，可动态的卸除和加载部分内核代码；(2)支持对称多处理机制（SMP）；(3)内核可抢占，允许内核执行高优先级的任务；(4)独特的线程实现，内核不区分线程和其他一般进程，一样都是task；(5)设备管理中提供具有设备类的面向对象的设备模型、热插拔事件、以及用户空间的设备文件系统；(6)抛弃了Unix中拙劣的stream特性，忽略了一些实际上已经不会使用的过时标准；(7)自由，公开开发模型自由务实发展。【单内核】单内核就是把它从整体上作为一个单独的大过程来实现，并同时运行在一个单独的地址空间。即所有内核服务都在一个大的内核空间中运行，内核可以直接调用函数。Linux是一个单内核，它运行在单独的内核地址空间。单内核模式具有简单和高性能的特点。【内核版本号】从版本号为偶数，则为稳定版；否则为开发版。Ch2.【LINUX内核开发特点】(1)不能访问C库，对内核而言C库太大了，但大部分常用C库函数在内核中都有实现；(2)必须使用GNUC；(3)缺乏内存保护机制，内核中的内存都不分页；(4)浮点数很难使用，复杂繁琐，原则是不要在内核中使用浮点数；(5)只有容积很小且定长的堆栈；(6)内核支持异步中断、抢占和SMP，所以容易出现竞争条件，要求时刻注意同步和并发，设置同步机制保证不出现竞争条件，通过自旋锁和信号量解决竞争条件；(7)要注重可移植性。*【内联函数】工作方式：函数会在它所调用的位置上展开，可以消除函数调用和返回所带来的开销(寄存器储存与恢复)。但这样会使代码变长，占用更多的内存空间或者指令缓存。通常对时间要求高、长度较短的函数定义为内联函数。定义方法：以static为关键字，用inline限定，例如：Ch3.【进程、线程、内核线程】进程：一个进程就是处于执行期的程序以及它所包含的资源的总称。这些资源包括：打开的文件、挂起的信号、内核内部数据、处理器状态、地址空间及一个或多个执行线程等。线程：线程是在进程中活动的对象，它为共享一个地址空间的程序提供多个执行线索，它可以共享打开的文件和其他资源。内核调度的对象是线程而不是进程，每个线程拥有一个独立的程序计数器、进程栈和一组进程寄存器。在Linux中每个线程和进程一样有唯一（唯一隶属自己）的task_struck，在内核看来与一般进程没有什么区别，当进程间选择性的共享地址空间时它可视为线程。内核线程：是标准的进程，只存在于内核空间；没有地址空间；只能由其他内核线程创建；可以被调度，也可以被抢占。【进程和线程的区别】(1)进程有独立地址空间，线程没有(2)进程是处于执行期的代码以及它包含的资源的总称，线程是进程中活动的对象。(3)进程是资源管理的最小单位，线程是程序执行的最小单位，内核调度的对象是线程而不是进程。【线程的实现】Linux实现线程的机制非常独特，内核把所有的线程都当做进程来实现，线程只被视为一个与其它进程共享某些资源的进程。每个线程拥有独立的程序计数器、进程栈和一组进程寄存器，并且和进程一样拥有唯一隶属于自己的task_struct。【进程状态】(1)TASK_RUNNING(运行)—进程是可执行的。或者正在执行，或者在等待队列中(2)TASK_INTERRUPTIBLE(可中断)—进程正在睡眠，等待某些条件的达成。(3)TASK_INTERRUPTIBLE(不可中断)—接收到信号也不会被唤醒后者投入运行(4)TASK_TRACED—被其他进程跟踪(5)TASK_STOPPED—进程停止执行【进程状态转换图】*【进程描述符和TaskStructure】内核把所有进程放在一个双向链表中---tasklist：图中的每一个节点都是一个很大的数据结构task_struct-进程描述符，其包含：进程状态、进程的地址空间、PID、指向父进程的指针、打开的文件。【进程上下文】系统提供给进程的处于动态变化的运行环境总和称为进程上下文，这些资源包括CPU的所有寄存器中的值、进程的状态以及堆栈中的内容，当前进程上下文均保存在进程的任务数结构中。程序在用户空间运行，它执行了系统调用或者触发了某个异常，它就陷入了内核空间，此时我们称“内核代表进程执行”并处于进程上下文。进程没有其他进入内核空间的方法。在进程上下文中，内核可以休眠，并且可以被抢占。【current宏】在Linux平台下，每一个进程都有一个task_struct数据结构，用来存储该进程的相关信息。在内核模块中，可以通过调用current来获取当前进程的task_struct数据结构。*【进程家族树】所有的进程都是init进程的子孙,其PID是1，进程只有一个父母，在进程的task_struct中的parent表示，进程可以有0个以上的子女，在进程的task_struct中的children表示。获得父亲代码：访问子进程代码：下一个/上一个进程：进程遍历：【进程创建的步骤】两个主要步骤：(1)创建一个子进程即复制当前的任务–fork()函数-新进程与其父进程的区别仅在于PID,PPID以及特定的资源-当进程执行一个系统调用或触发一个例外时，进入内核空间-进程除此之外再没有其他方式进入内核空间(2)将一个程序装入地址空间并执行–exec()-内核线程是标准的进程，只存在于内核空间-内核线程没有地址空间-内核线程只能由其他内核线程创建Linux通过clone()系统调用实现fork()，由clone()去调用do_fork()，do_fork()调用copy_process()函数Vfork()与fork区别在于，创建完成后父进程阻塞，直至子进程结束或执行exec()【写时拷贝】写时拷贝是指在需要写入的时候才进行资源复制，是一种可以推迟甚至免除拷贝数据的技术。Linux的fork()使用写时拷贝数据实现，创建子进程时不需要立即给子进程拷贝数据，而是让父子进程以只读的方式共享没有修改的数据和空间，而当父子进程之一修改数据时则进行拷贝。【进程的终结】结束的起因：进程结束其工作，或者收到一个信号，或者发生了它自己不能处理的异常。结束过程：进程开始执行exit()函数-释放进程的地址空间-释放进程使用的资源-给其父进程发送一个信号，并标示自己的状态为TASK_ZOMBIE-调用调度程序，执行其他进程进程结束后还保留内核栈、thread_info结构、task_struct结构。存在的唯一目的就是向父进程提供信息。父进程检索到信息后，或通知内核那是无关信息，内存释放。*【孤儿进程】其父进程已经终止，系统试图给子进程安排一个父进程，若失败，由init进程收养。孤儿进程组：该组中每个成员的父进程要么是该组的一个成员，要么不是该组所属会话的成员。一个进程组不是孤儿进程组的条件是：该组中有一个进程，其父进程在属于同一会话中的另一个组中。Ch4.【进程时间片】进程时间片是指，进程在被抢占前所能持续运行的CPU时间，它是一个有系统调度策略设定的数值。Linux采用了预加载调度策略，每个进程只运行很短的时间：200毫秒；同时Linux调度程序还能根据进程的优先级动态调整分配给它的时间片，来保证高优先级的进程执行的高频率和长时间。一个进程不一定一次必须用完自己的时间片。当进程的时间片用完时，进程不再执行，直到其他进程也使用完了自己的时间片。【进程优先级】Nice值：从-20到19，值越小优先级越高。实时优先级：从0到99，值越大优先级越高。任何实时进程的优先级都高于普通进程。【CFS思想】允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程。【Linux调度实现四个主要部分】时间记账、进程选择、调度器入口、睡眠和唤醒【O(1)调度器】所有的算法在规定的时间内运行完，其数据结构：运行队列和优先级矩阵。执行调度时，速度很快新增的特性：改善了SMP可扩展性，包括NUMA.较好的处理器亲和力。SMT调度.【linux2.6调度程序的目标】有效性：完成尽可能多的工作；交互性：尽快响应用户；公平性：不允许任何进程饥饿。(1)充分实现O(1)调度。不管有多少进程，新调度程序采用的每个算法都能在恒定时间内完成；(2)全面实现SMP的可扩展性。每个处理器拥有自己的锁和自己的可执行队列；(3)强化SMP的亲和力。尽量将相关一组任务分配给一个CPU进行连续执行；(4)加强交互性能。即使在系统处于相当负载的情况下，也能保证系统的相应,并立即调度交互式进程；(5)保证公平。在合理设定的时间范围内，没有进程会处于饥饿状态，也没有进程能不公平的得到大量时间片；(6)虽然常见的优化情况是系统中只有1-2个可运行进程，但是优化它也完全有能力扩展到具有多处理器每个处理器上运行多个进程的系统中。【运行队列】给定处理器上可执行进程的链表.对运行队列进行操作前要先锁住.运行队列中的数据:用于解决并发问题的锁.指向当前任务和空任务的指针.优先级数组.统计信息【优先级数组】维护两个优先级矩阵：活跃的和过期的矩阵。过期的：所有用完了时间片的进程实际的：没有用完时间片的进程当一个进程用完了时间片时，重新计算其时间片，并放入到过期队列中当实际进程队列为空时，交换过期队列和实际队列【睡眠和唤醒】睡眠：置标志为睡眠,把自己放于等待队列,把自己从运行队列中删除，调用schedule()选择新进程执行。唤醒：置标志为可运行，从等待队列中删除，加到运行队列的后面。【任务调度过程】【优先级和时间片的计算】动态优先级用于计算优先级:nice+进程交互性的奖励或罚分为了确定一个进程是否是交互性的,Linux记录了一个进程用于休眠和用于执行的时间（0-MAX_SLEEP_AVG，默认10ms）。一个进程从休眠恢复到执行时，增加；运行一段时间后会减小。静态优先级用于计算时间片:进程创建时，子进程与父进程均分父进程剩余的时间片.任务的时间片用完时，基于任务的静态优先级重新计算时间片。【负载平衡程序的操作步骤】Linux为对称多处理器（SMP）系统中的每个处理器准备了单独的可执行队列和锁，而负载平衡程序则负责保证这些可执行队列之间的负载处于均衡状态。负载平衡程序由load_balance()函数实现，它所完成的操作步骤归结如下：(1)找最繁忙的可执行运行队列；(2)从最繁忙的队列中选择一个优先级数组（过期的优先）以便抽取进程；(3)选择含有进程并且优先级最高（值最小）的链表；(4)选择一个不是正在运行的且不在高速缓冲的进程，可移动的进程抽取；(5)重复上述步骤，直至平衡。【调度程序状态之间的关系】【进程抢占的时机】当一个进程的优先级高于当前正在运行的进程的优先级当一个进程的时间片为0.【内核抢占/抢占】内核抢占：当进程位于内核空间，若有一个更高优先级的任务出现时，可以将当前任务挂起，切换去执行优先级更高的进程，而这个强制挂起的动作叫抢占。可抢占的前提需要确保重新调度是安全的，即当前的任务没有持有锁，在这种情况下内核可以在任何时间抢占正在执行的任务。2.6版本后的Linux内核是可抢占式内核，具有上述允许内核优先执行高优先级任务的能力。【用户抢占发生在什么情况】在内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占：1）从系统调用返回用户空间；2）从中断处理程序返回用户空间。【内核抢占发生在什么情况】(1)中断处理程序正在执行，且返回内核空间之前；(2)内核代码再一次具有可抢占性的时候（preemt_count重新为0）；(3)内核中的任务显示的调用schedule()；（处于核心态的任务直接调用schedule()）(4)内核中的任务阻塞时（这同样也会导致调用schedule()）。【上下文切换】从一个可执行的进程切换到另一个可执行的进程。由context_switch()函数负责完成，它完成了两项基本工作：(1)调用switch_mm()，把虚拟内存从上一个进程影射