2023年12月20日发(作者：)
Operating System ReviewCS-081Chapter 4Processes and Threads进程和线程到目前为止进程的两个特点：1、Resource ownership：资源所有权2、Scheduling/execution：调度/执行the unit of dispatching is usually referred to as a thread线程, or lightweight process.将分派的单位称为线程或轻量级进程。线程同步：一个进程的所有线程共享一个地址空间(address space)和其他资源，因此需要同步各种线程的活动User-Leveland Kernel-LevelThreads用户级和内核级线程User-Level Threads：·All of the word of thread management is done by the application and the kernel isnot aware of the existence of threads.有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在·使用用户级线程而不是内核级线程的优点：1、Thread switching does not require kernel mode privileges线程切换不需要内核态特权2、Scheduling can be application specific.调度可以是应用程序相关的3、ULTs can run on any operating system.用户级线程可以在任何操作系统上运行Kernel-Level Threads：·all of the word of thread management is done by the kernel.所有线程管理的工作由内核完成Threads : Processes线程与进程的关系1:1M:11:M传统的UNIXWindows NT，Solaries，LinuxRS（Clouds）A threadthat can move among address spaces.线程可以在地址空间中移动（thread migration）TRIXM:N1
Operating System ReviewCS-081Symmetric Multiprocessing对称多处理SISD单指令单数据流：单处理器执行单个指令流SIMD单指令多数据流：每条指令由不同的处理器在不同的数据集合上执行MISD多指令单数据流：从未被实现过MIMD多指令多数据流：一组处理器同时在不同的数据集上执行不同的指令序列In a symmetric multiprocessor, the kernel can execute on any processor, and typicallyeach processor does self-scheduling from the pool of available processes.内核可以在任何处理器上执行，并且通常是每个处理器从可用的进程或线程池中进行自己的调度工作Microkernel微内核·monolithic operation system单体结构的操作系统·layered operation system分层的操作系统·microkernel operation微内核结构·The philosophy underlying the microkernel is that only absolutely essentialcoreoperating system functions should be in the kernel. Less essential services andapplications are built on the microkernel and execute in user mode.只有最基本的操作系统功能才能放在内核中，非基本的服务和应用程序在为微内核之上构造，并在用户态下执行·微内核结构的优点：uniform一致接口extensibility可扩展性flexibility灵活性portability可移植性reliability可靠型distributed system support分布式系统支持object-oriented operating system面向对象操作系统·微内核的一个潜在缺点是性能问题Microkernel Design微内核设计Low-Level Memory Management低级存储管理：three microkernel operations that can support external paging and virtualmemory management.用于支持内核外部的页面调度和虚存管理的三个微内核操作：·Grant授权·Map映射·Flush刷新Interprocess Communication进程通信：通信的基本形式是消息（messages）2
Operating System ReviewCS-081Chapter 5Race Condition竞态条件Race condition is a situation where two or more processes are reading or writingsame share data and the final result depends on the particular order in which theaccess takes s Interaction进程间的相互作用·Processes unaware of each other：competition·Processes indirectly aware of each other：cooperation·Process directly aware of each other：cooperation进程间的制约关系直接制约：进行协作——等待来自其他进程的信息,“同步”进程间的相互联系是有意识的安排的间接制约：进行竞争——独占分配到的部分或全部共享资源，“互斥”。进程间要通过某种中介发生联系,是无意识安排的Mutual Exclusion (进程互斥): synchronization mechanism toavoid race conditionsby ensuring exclusive execution of critical sections.它是指进程之间互相排斥地使用临界资源，即你在使用时我不能使用，我在使用时你不能使用。Synchronization (进程同步) :指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。因此，进程互斥也是一种同步，因为它也是进程之间的一种协调。Critical Regions（临界区）·When a process executes code that manipulates shared data (or resource), we saythat the process is in it’scritical section·The section of code implementing this request is called theentry section·The critical section (CS) might be followed by anexit section·The remaining code is theremainder section·The critical section problem is to design a protocol that the processes can use sothat their action will not depend on the order in which their execution is interleaved (possiblyon many processors)3
Operating System ReviewCS-081Requirements for ME（同步机制应遵循的规则）Mutual Exclusion（忙则等待）：At any time, at most one process can be in its criticalsection.,or, no two processes can be in the critical section at same timeProgress（空闲让进）：No process running outside its critical section may blockanother process. Only processes that are not executing in their RS can participate inthe decision of who will enter next in the CSBounded Wait（有限等待）：After a process has made a request to enter it’s CS, thereis abound on the number of times that the other processes are allowed to enter their CS,otherwise the process will suffer from starvationSpeed and Number of CPUs：No assumption may be made about speeds ornumber of CPUsApproaches to solving ME (synchronization)involves:Software solutionsHardware solutionsdisable interruptSpecial-purpose machine instructions: TSI, EXCOS solutionsSemaphores: Synchronization Primitives (P, V)4
Operating System ReviewCS-081monitorsmessage passingSemaphore（信号量）Semaphore is a variable that has an integer value·May be initialized to anonnegative number·semWait operation decrements the semaphore value·semSignal operation increments semaphore valuesemwait就是P操作，信号量减1semSignal就是V操作，信号量加1Binary (mutex) Semaphore Primitives(二元或互斥信号量)s表示资源的数量Counting semaphores: 0..NBinary semaphores: 0,1P原语The P operation is used to acquire a resource and decrements count.P原语:对应着down操作或semWaits--; //表示申请一个资源;if (s < 0) //表示没有空闲资源;{将该进程置入到与该信号量对应的等待队列中;阻塞该进程;}V原语V原语通常唤醒进程等待队列中的头一个进程The V operation is used to release a resource and increments count.V原语：对应着up操作或semSignals + +; //表示释放一个资源；if (s <= 0) //表示有进程处于阻塞状态；{从等待队列中唤醒一个等待进程;将该进程置入就绪队列中;}5
Operating System ReviewCS-081Using semaphores for solving Critical Sectionproblems·为临界资源设置一个互斥信号量mutex (MUTual EXclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间·必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏Monitors (管程机制)基本概念管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。其基本思想是把信号量及其操作原语封装在一个对象内部Classic Problems of SynchronizationThe Producer/Consumer Problem (PCP)Problem description：A producer process produces information that is consumed by aconsumer process. We need a buffer to hold items that are produced and eventuallyconsumed.若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作方法一：使用互斥信号量6
Operating System ReviewCS-081方法二：使用多元信号量7
Operating System ReviewCS-081The Readers-Writers Problem问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个·“读－写”互斥·“写－写”互斥·“读－读”允许方法：8
Operating System ReviewCS-081The Sleeping Barber Problem (SBP)问题描述：理发店有一位理发师和一把理发椅，理发时顾客坐在此椅上，不理发时理发师在此椅上睡觉。室内还有N张椅子，供顾客等待理发时用。当一顾客走进理发店后发现椅子上坐满了人，则离开理发店；若理发师正为他人理发，则找个空位坐下等待；若理发师正在休息（睡眠），则要求他为自己理发解答：9
Operating System ReviewCS-08110
Operating System ReviewCS-081Chpater 6Resource资源·Reusable可重用资源：Used by one process at atime and not depleted by that , CPU, memory, disk space, I/O devices, files.每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用·Consumable可消耗资源: produced by a process, destroyed by a process; e.g.,messages, buffers of information, interrupts.可以动态生成和消耗，一般不限制数量Deadlock死锁A process is deadlocked if it is waiting for an event that will never occur.死锁是指系统中多个进程无限制地等待永远不会发生的条件Starvation饥饿A process is starved ifit is delayed repeatedly over a long period of time while theattention of the system is given to other processes.饥饿是指系统中某个进程长时间等待某个资源。通常是因为分配算法不公平导致的。Resource Allocation Graph资源分配图（重点，必考）a图：进程A获得了资源Rb图：进程A请求资源Rc图：资源分配图出现了环路11
Operating System ReviewCS-081Contidions of Deadlock死锁的条件·Mutual exclusion互斥·Hold and wait保持和请求·No preemption非抢占式·Circular wait环路等待需要注意的是，在资源分配图中出现环路并不代表一定构成死锁。当每个资源只有一个可分配项时，出现回路则一定存在死锁DeadlockPrevention死锁预防Disallow 1 of the 4 necessary conditions of deadlock occurrence·Indirectmethodsof deadlock prevention间接： to disallow one of the 3 policyconditions通过禁止死锁条件的前三项Mutual Exclusion：不能禁止，操作系统必须支持12
Operating System ReviewCS-081·Direct methods of deadlock prevention直接：to prevent the occurrence of circularwait防止出现回路DeadlockAvoidance死锁避免We allow the 3 policy conditions but makejudicious choices to assure that thedeadlockpoint is never reached.允许死锁的前三个条件，但是通过一定的算法保证死锁不会发生The system needs to know the resource ahead of time.系统必须提前知道资源数量Allows more concurrency than prevention.相比死锁预防允许更多的并发量·银行家算法（重点，必考）Safe State安全状态·There is some scheduling order in which every process can run tocompletion even if all of them suddenly request their maximum number ofresources immediately.至少存在一种调度方法使得所有进程能够执行完毕·From safe state, the system can guaranteethat all processes will finish.安全状态下，系统确保所有的进程都能够完成Unsafe state：no such guarantee.·Not deadlocked state.非安全状态不代表当前存在死锁·Some process may be able to complete.某些进程可能执行完毕原则：·分配资源前，测试此次分配是否会导致非安全状态·只要存在一种调度顺序使得所有进程能执行完毕，则视为安全状态·否则，拒绝分配请求例：A B C资源总数分别为10 5 5，目前分配情况如下图，现在P1请求（1 0 2），系统是否允许？分析如下：13
Operating System ReviewCS-081，则分配图如下，那么现在是否是安全状态呢？如果P1请求最大资源，将剩余资源分配给P1可使它执行完毕，释放资源后A B C剩余数为5 3 2现在，P3也可以请求资源并完成。14
Operating System ReviewCS-081接下来是完成P4P215
Operating System ReviewCS-081最后是P0，那么根据执行P1 P3 P4 P2 P0的调度顺序可以使所有进程执行完毕而不发生死锁，那么当前状态是安全状态。于是系统批准分配资源 1 0 2.如果在以下状态，P0请求资源 0 2 0，是否允许分配？假设分配给P0，判断当前是否为安全状态16
Operating System ReviewCS-081分配后，剩余 2 1 0，发现剩余进程均无法执行完毕，说明此时处于不安全状态，于是拒绝分配给P0，保持在安全状态DeadlockDetection &Recovery死锁检测和解除Always grant resource request when possible. But periodically check for the presence17
Operating System ReviewCS-081of deadlock and then recover from it. After a deadlock has been detected, clear theproblem, allowing the deadlocked processes to complete and the resources to be y involves destroying the affected processes and starting them over.始终允许资源请求。每隔一段时间检测当前是否存在死锁并恢复。Recovery From Deadlock·Abort all deadlocked processes (one of the most common solution adopted in OS!!)终止死锁的所有进程·Rollback each deadlocked process to some previously defined checkpoint andrestart them·Successively abort deadlock processes until deadlock no longer exists (each timewe need to invoke the deadlock detection algorithm)·Successively preempt some resources from processes and give them to otherprocesses until deadlock no longer exists.从某些进程中抢占资源然后分配给其他进程直到死锁消失。·A process that has a resource preempted must be rolled backprior to its the 2 last approaches: a victim process needs to be selected according to：死锁恢复时选择“牺牲者”的原则·least amount of CPU time consumed so far目前使用CPU时间最少的·least amount of output produced so far目前产生输出最少的·most estimated time remaining预计剩余执行时间最长的·least total resources allocated so far目前已分配资源最少的·lowest priority优先级最低的Chapter 7Memory Management内存管理The concept of Memory Management satisfies five requirement:内存管理的5点需求：·Relocation重定位·Protection保护·Sharing共享·Logical organization逻辑组织·Physical organization物理组织Overlaying(覆盖):The program and data are organized in such a way that variousmodules can be assigned the same region of memory.不同的模块被分配到内存中同一块区域18
Operating System ReviewCS-081Memory Partitioning内存分区Fixed Partitioning固定分区·equal-size fixed partition大小相等的分区小于分区大小的进程可装入任何分区，造成分区内部的空间浪费，称为内部碎片internal fragmentation·unequal-size fixed partition大小不等的分区分区大小不等，可产生较少的内部碎片·由于分区数的固定，因而可装入的进程数也固定Dynamic Partitioning动态分区·分区长度和数目可变，但随着进程的不断装入换出，会产生越来越多的空洞，称为外部碎片external fragmentation·Placement Algorithm放置算法1、Best-fit最佳适配：选择与要求的大小最接近的块，通常性能最差2、First-fit首次首配：从头扫描内存，选择大小足够的第一个块3、Next-fit下次适配：从上一次放置的位置扫描，选择大小足够的第一个块·Compaction压缩技术：用于克服外部碎片，将空闲空间连成一片Buddy System伙伴系统·固定分区和动态分区的折衷方案·将内存空间不断分成两个大小相等的伙伴，直至产生大于或等于所需大小的最小块Relocation重定位·logical address逻辑地址：与物理分配地址无关的访问地址，访问前需转换·relative address相对地址：相对某些已知点的存储单元·physical address物理地址：数据在内存中的实际位置Paging简单分页·将内存划分为大小固定相等的块，每个进程也氛围同样大小的块，在进程中称为页pages的块可以指定到内存中称为页帧frames的可用块。·操作系统需为每个进程维护一个页表page table，页表给出了进程每一页对应的页帧位置·Paging is invisible to the programmer分页对程序员来说是透明的·类似于固定分区，但是分页技术的分区相当小，一个程序可占用多个分区，并且这些分区不需要连续·消除了外部碎片，仅在占据的最后一页的最后部分产生很小的内部碎片Segmentation简单分段·把程序和相关数据划分到几个段segments。段有最大长度限制，但不要求段的长度19
Operating System ReviewCS-081都相等·段表segment table：给出段在内存中的起始地址和段的长度·Segmentation is visible and is provided as a convenience for organizing programsand data.分段对程序员可见·Segmentation eliminates internal fragmentation,but it suffers from externalfragmentation.消除了内部碎片，但是会产生外部碎片Chapter 8Virtual Memoryresident set进程常驻集：The portion of a process that is actually in main memory at anytime is defined to be the resident set of the process.进程执行中的任何时候都在内存中的部分被定义为进程的常驻集。thrashing系统抖动：The system spend most time of its time swapping pieces rather thanexecuting instructions.处理器的大部分时间都用在交换块，而不是执行指令。Paging虚拟内存分页page table entry(PTE)页表项：比起简单分页，多了控制位
表示它所对应的页当前是否在内存中，
Operating System ReviewCS-081Combined Paging and Segmentation段页式A user's address space is broken up into a number ofvariable-sizesegments,andeach segment is broken up into a numberof fixed-size pages.化分成大小不等段，每个段依次划分成固定大小的页，页的长度等于内存中页帧的大小。Fetch Policy读取策略demand paging请求分页：A page is brought into main memory only when a reference ismade to a location on that page.只有当访问到某页中的一个单元时才将该页取入内存（只调入缺页时所需要的页）prepaging预先分页：More efficient to bring in pages that reside contiguously on the ingexploits the characteristics of most secondary memory.在发生缺页需要调入某页时，一次调入该页以及相邻的几个页，利用了辅存设备的特性Replacement Policy置换策略（重点、大题）·Optimal最佳算法：选择置换下次访问距当前时间最长的那些页，不可能实现的算法，用来评估其他算法的性能。·FIFO先进先出：选择内存中驻留时间最长的页面被置换。性能较差，较早调入的页往往是经常访问的页。Belady现象：For some page replacementalgorithms, the page fault rate may increase asthe number of allocated frames increase.采用FIFO算法时，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。原因是被置换的页面并不是进程不会访问的·LRU最近最少使用：把最长时间未被访问过的页面置换掉。基于程序局部性原理·CLOCK时钟策略：给每一页帧添加一个使用位，当某一页被装入内存中时，使用位置1，当该页随后被访问到时，也置为1。将页帧的集合看成一个循环缓冲区，需要置换时，扫描缓冲区，查找下一个使用位为0的页，遇到使用位为1的页帧时，将其置为0。Page Fault：前几个页帧为空的情况也视为缺页Resident Set Management驻留集管理Resident Set Size驻留集大小：·fixed-allocation固定分配策略21
Operating System ReviewCS-081·variable-allocation可变分配策略Replacement Scope置换范围：·local replacement policy局部置换策略：choose only among theresident pages ofthe process that page fault in selecting a page to replace.仅仅在产生这次缺页的进程的驻留页中选择·global replacement policy全局置换策略：consider all unlocked pages in mainmemory as candidates for replacement，regardless of which process owns a particularpage.把内存中所有为被锁定的页都作为置换的候选页Cleaning Policy清除策略demand cleaning请求式清除：该页被置换之前才调出，把清除推迟到最后一刻precleaning预约式清除：该页被置换之前就调出，可以成批调出多个页面Linux内存管理三级页表结构：Page directory页目录、Page middle directory页中间目录、页表Windows内存管理页尺寸4KB-64KB每个进程允许4GB的存储空间，每个用户实际上有2GB的可用虚拟地址空间Chapters 9 & 10SchedulingMultiple processes/threads ready to run. Multipleprocesses are competing for ling: which one to occupy the resourcesCPU scheduler selects one of the processes from the ready queue and allocatesCPU to one of themReady queue = FIFO queue, tree queue, or unordered linked list, or priorityqueue;Elements in the ready queue are PCBs of processes22
Operating System ReviewCS-081Types of processor schedulingThree level scheduling:Long-term(Admission Scheduling): which process to admitMedium-term(MemoryScheduling): which process to swap in or outShort-term(CPU Scheduling): which ready process to execute nextScheduling Algorithms基本概念Response Time (反应时间): Elapsed time from the submission of a request to thebeginning of responseTurnaround Time (周转时间): Elapsed time from the submission of a process to ound Time（周转时间）=作业完成时间–作业提交时间Normalized Turnaround Time（带权周转时间或规格化周转时间）=周转时间/运行时间Throughput (吞吐量): number of process completed per unit timeCharacterization of Scheduling PoliciesNonpreemptive非抢占式23
Operating System ReviewCS-081Once a process is in the running state, it will continue until it terminates or blocksitself for I/OPreemptive抢占式Currently running process may be interrupted and moved to the Ready state bythe OSAllows for better service since any one process cannot monopolize the processorfor very longScheduling Algorithms in Batch Systems1、First Come First Served (FCFS,先来先服务)2. Shortest Job First（SJF,短作业优先）24
Operating System ReviewCS-0813. Shortest Remaining Time Next (SRTN,最短剩余时间作业优先）25
Operating System ReviewCS-081Scheduling
Systems)in Interactive Systems(Time-sharingRound Robin (RR,时间片轮转算法)Priority Scheduling (优先权调度算法)Each process is assigned a priority (integer number)The CPU is allocated to the process with the highest priority (smallest integer ≡highest priority) .26
发布评论