王道考研-操作系统整理笔记

ChapterOne操作系统概述操作系统概念：操作系统是指控制和管理理整个计算机系统的硬件和软件资源，并合理理组织和调度计算机的⼯工作和资源分配，是昀基本的系统软件。特征：并发、共享（两个昀基本的特征）、虚拟、异步。并发：指同⼀一时间间隔内发⽣生，区别于并⾏行行。微观上分时地交替执⾏行行。功能：是计算机系统资源（处理理机、存储器器、⽂文件、设备）的管理理者⽤用户与计算机硬件系统之间的接⼝口：①命令接⼝口（允许⽤用户直接使⽤用）（1）联机（交互式）命令接⼝口（适⽤用于分时or实时）（2）脱机（批处理理）命令接⼝口②程序接⼝口（=系统调⽤用命令）③GUI（图形接⼝口调⽤用系统命令）注：在多道程序环境下，处理理机的分配和运⾏行行都以进程（或线程）为单位。系统调⽤用是由操作系统提供给⽤用户的，它只能通过⽤用户程序间接使⽤用。操作系统的发展：批处理—分时—实时—网络和分布式①批处理理（缺点：没有交互能⼒力力）单道批处理理—顺序性（CPU⼤大量量时间在空闲等待I/O）多道批处理理（失去封闭性）—制约性、间断性、共享性特点：多道、宏观上并⾏行行，微观上串串⾏行行。②分时系统：（以时间⽚片为单位）允许多个⽤用户以交互的⽅方式使⽤用计算机特点：同时性、交互性、独⽴立性、及时性分时系统能较快、及时接收并处理理命令，快速响应⽤用户。（通常采⽤用优先级+⾮非抢占式调度算法）分时系统中，时间⽚片⼀一定时，⽤用户数越多，响应时间越⻓长。③实时系统：在某个时间限制内完成某些紧急任务⽽而不不需时间⽚片排队特点：及时性、可靠性（通常采⽤用抢占式优先级⾼高者优先算法）④⽹网络（⽹网络资源共享）和分布式：区别是在分布式中，若⼲干计算机相互协同完成同⼀一任务系统调用（运行在核心态）（涉及设备、文件、进程、内存）⽤用户程序凡是与资源有关的操作（存储分配、I/O、管理理⽂文件）都必须通过系统调⽤用。过程：传递系统调⽤用参数—执⾏行行陷⼊入（trap）指令（⽤用户态）—执⾏行行系统调⽤用相应服务程序（核⼼心态）—返回⽤用户程序系统调⽤用功能是操作系统向⽤用户程序提供的接⼝口注：系统调⽤用是⼀一种特殊公共⼦子程序陷⼊入指令是唯⼀一⼀一个只能在⽤用户态执⾏行行，⽽而不不可在核⼼心态执⾏行行的指令。⼴广义指令：也就是系统调⽤用命令（可能在⽤用户态调⽤用，但处理理必须在核⼼心态）⽤用户程序（⽤用户⾃自编or系统外层应⽤用程序）⼯工作在⽤用户态；内核程序⼯工作在核⼼心态。特权指令：只能在核⼼心态运⾏行行的指令如：I/O指令、置中断指令、存取⽤用户内存保护的寄存器器、送程序状态字（可区分⽬目态、管态）到程序状态字寄存器器。（包括系统调⽤用类、时钟类、中断和原语指令，清内存、分配系统资源、修改虚拟存储⾥里里的⻚页表段表、修改⽤用户访问权限等）中断和异常：引入中断技术的初衷是提高多道程序运行环境中CPU的利用率中断的分类：①内中断（异常、例例外、陷⼊入trap）（不不可被屏蔽！） ⾃自愿中断—指令中断：访管指令（只能⽤用户态使⽤用） 强迫中断—硬件故障（缺⻚页） —软件中断（⾮非法操作码、地址越界、算数溢出、虚存系统缺⻚页以及专⻔门的陷⼊入） ②外中断（强迫中断） 外设请求：I/O结束、时钟中断 ⼈人的⼲干预：⽤用户按ESCor退出键注：区分内/外中断看信号来源：CPU内部/外部。访管中断：⽤用户程序在⽤用户态下要使⽤用特权指令（由访管中断引起）引起的中断。⽤用户程序需要输⼊入/输出时（I/O），调⽤用OS提供的接⼝口，此时引起访管中断。所有中断都是在核⼼心态下执⾏行行的！（进程切换、对资源的释放）⽤用户态（发⽣生中断or异常）—核⼼心态（通过硬件、系统调⽤用、访管指令实现）核⼼心态（使⽤用特权指令）—⽤用户态（通过中断返回指令） 注：中断系统（OS必需）和地址映射需要硬件⽀支持，进程调度不不需要。原语处于昀底层；不不可分割的指令序列列；运⾏行行时间短，调⽤用频繁PV操作是⼀一种低级的进程通信语⾔言，由两个不不可中断的过程组成，并⾮非系统调⽤用。体系结构：⼤大内核（⾼高性能；结构混乱）、微内核（内核功能少；在⽤用户态、核⼼心态之间切换频繁，性能低；结构清晰；添加系统服务时不不必修改内核；使系统更更可靠）ChapterTwo进程管理理进程概念：进程（动态）是资源分配的⼀一个独⽴立单位。程序：静态进程的特征：动态性（昀基本）、并发性（重要特征）、独⽴立性、异步性、结构性（进程实体（进程映像）由程序段、数据段、PCB三部分组成）注：进程的组织（结构性）：PCB、程序段（多个进程可运⾏行行同⼀一程序）、数据段PCB是进程存在的唯⼀一标志。主要包括了了：进程描述信息（ID）、进程控制（优先级）和管理理信息、资源分配和处理理机相关（不不重要）。⼆二进制代码和常量量放在正⽂文段；动态分配的存储区在数据堆段；临时⽤用的变量量在数据栈段。进程的状态：运行、就绪、阻塞、创建、结束运⾏行行—阻塞（等待）主动阻塞阻塞—就绪被动唤醒注：在可剥夺OS中，当有更更⾼高优先级的进程就绪时，调度程序将正在执⾏行行的进程—就绪态，让更更⾼高优先级的执⾏行行。就绪态：进程已处于准备运⾏行行的状态（只缺CPU了了！）进程切换：（区别于调度！切换是执⾏行行⾏行行为，⽽而调度是决策⾏行行为）：时间⽚片⽤用完、主动放弃处理理机、被更更⾼高优先级的进程剥夺注：进程切换的过程包括更更新PCB信息引起创建进程的操作：终端⽤用户登录系统、作业调度、系统提供服务、⽤用户程序的应⽤用请求注：⽤用户进程被创建后，随着运⾏行行的正常或不不正常结束⽽而撤销。（进程是有⼀一定⽣生命周期的！）进程的终⽌止：①异常结束：存储区越界、保护错、⾮非法指令、特权指令错、I/O故障②正常结束：任务已完成③外界⼲干预（⼈人为、OS⼲干预、⽗父进程的请求or终⽌止）阻塞（等待资源）：请求资源失败、等待某操作的完成、数据未到达、⽆无事可做等唤醒（资源到达）：I/O操作已完成or数据已到，调⽤用唤醒原语进程的通信⼀一个进程不不能直接访问另⼀一个进程的地址空间①共享存储（互斥访问）：低级⽅方式：基于数据结构的共享；⾼高级⽅方式：基于存储区②消息传递：直接通信⽅方式：接收进程从消息队列列中取得消息；间接通信⽅方式：将消息挂到某个中间实体（邮箱）③管道通信：利利⽤用⼀一种特殊的pipe⽂文件连接两个进程。管道只能采⽤用半双⼯工通信，某⼀一时间段内只能实现单向传输。如果要实现双向同时通信，则需设置两个管道。（原理理：Chapter5缓冲区）注：从管道读数据是⼀一次性操作，数据⼀一旦被读取，它就从管道中被抛弃线程线程的引⼊入：减⼩小程序的时空开销，提⾼高程序并发执⾏行行的程度，提⾼高系统效率线程是程序执⾏行行的昀⼩小单元，并不不拥有任何系统资源（进程才有），是独⽴立调度的基本单位。同⼀一进程中，线程的切换不不会引起进程的切换；切换到另⼀一进程中的线程才会切换。同⼀一进程或者不不同进程内的线程都可以并发执⾏行行。⽤用户级线程：所有⼯工作都由应⽤用程序完成，⽆无需内核⼲干涉。多线程模型：多对⼀一模型：缺点—⼀一个线程阻塞会导致整个进程都被阻塞注：线程包含CPU现场，可以独⽴立执⾏行行程序。只有内核级线程才是处理理机分配的单位！CPU调度①作业调度（⾼高级DD）：内存与辅存（外存）之间的DD；对于每个进程只调⼊入/调出⼀一次。调⼊入建⽴立PCB，调出才撤销PCB。②内存DD（中级DD）：将暂时不不运⾏行行的进程调⾄至外存等待。引⼊入中级DD为了了提⾼高内存利利⽤用率和吞吐量量（调到外存等待的进程状态为挂起态）③进程DD（低级DD）：内存—CPU，是OS中昀基本的⼀一种DD；⼀一般OS中必须配置，使⽤用频率很⾼高。带权周转时间=作业周转T/作业实际运⾏行行T不不能进⾏行行进程调度/切换的情况：①处理理中断过程中②进程在OS内核程序临界区—需要独占式访问共享资源（不不能进⾏行行进程DD但还是能进⾏行行CPU调度！前提：不不能破坏临界资源使⽤用规则）③需要完全屏蔽中断的原⼦子操作（不不可分割！连中断都要屏蔽，DD更更别说了了）（如：加锁、解锁、中断现场保护/恢复）应该进⾏行行进程调度/切换的情况：①发⽣生引起DD的条件且当前进程⽆无法继续执⾏行行下去（⾮非剥夺⽅方式）②中断ortrap处理理结束后，返回被中断进程的⽤用户态程序执⾏行行现场前，可以⻢马上进⾏行行DD与切换。（剥夺⽅方式）调度方式：剥夺式（抢占）、非剥夺式（非抢占）剥夺式：当某个更更紧急的进程要CPU时，⽴立即暂停正在执⾏行行的进程，先分给更更紧急的。（必须遵循⼀一定规则，如：优先权、SJFor时间⽚片）优点：提⾼高系统吞吐率和响应效率⾮非剥夺式：⼀一旦CPU分配给⼀一个进程，该进程保持CPU直到终⽌止or转换到等待态。特点：实现简单、系统开销⼩小；适⽤用于批处理理，不不能⽤用于分时or实时！调度算法：FCFS、SJF、优先级DD、⾼高响应⽐比优先、时间⽚片轮转、多级反馈队列列DD。FCFS：属于不不可剥夺算法！特点：算法简单；有利利于CPU繁忙型作业，不不利利于I/O繁忙型作业。SJF：会产⽣生饥饿现象，是调度策略略问题。（默认”⾮非抢占”，也有抢占式）特点：平均等待时间、平均周转时间昀少！优先级DD：①静态优先级：优先级在创建进程时确定，整个运⾏行行期间不不变②动态优先级：随着进程执⾏行行时间增加，其优先权下降。⾼高响应⽐比优先：Rp=(waitT+ServeT)/ServeT时间⽚片轮转（队列列的思想）：主要适⽤用于分时系统；绝对可抢占；时间⽚片过⼤大时，相当于FCFS注：I/O型作业优先权⾼高于计算型作业！I/O作业要及时完成，⽆无法⻓长期保存输⼊入/输出的数据。处理理机DD算法不不影响作业执⾏行行或输⼊入/输出操作的时间，只影响作业在就绪队列列中等待所花的时间。（即DD算法优劣只需考虑等待时间）进程同步临界资源（独占资源）：⼀一次仅允许⼀一个进程访问使⽤用的资源（如：打印机、共享变量量、共享缓冲区、公⽤用队列列）共享资源：磁盘存储介质、可重⼊入代码（⼀一次可供多个进程使⽤用，不不允许任何修改的代码—共享程序）临界区：进程中访问临界资源的那段代码注：进程处于临界区时，不不能进⾏行行进程DD，但是能进⾏行行处理理机/CPU调度！但要不不能破坏临界资源使⽤用规则同步机制遵循的原则：①空闲让进②忙则等待③有限等待④让权等待④：当进程不不能进⼊入临界区时，应释放处理理器器实现临界资源互斥的基本方法：（以下都不满足”让权等待”！）软件：①单标志法（只能按顺序进⼊入）②双标志法（同时进⼊入临界区）③双标后检测（可能造成饥饿）④Peterson’s算法（双重，主动谦让，将”钥匙”送给对⽅方，昀终只有⼀一个可通过）P73⽅方四⾏行行代码硬件：TestAndSet（原⼦子操作）orSwap（简单了了解）特点：实现简单；适⽤用于多处理理机；不不满⾜足”让权等待”信号量①整型信号量量：表示资源数量量（不不满⾜足”让权等待”）②记录型信号量量：s.value0时（=0也不不算是等待！），|s.value|代表链表中已被阻塞的该信号进程的数⽬目（即等待进⼊入临界区的）遵循了了”让权等待”原则信号量机制实现同步与互斥①互斥：设置互斥信号量量mutex，初值为1。semaphoremutex=1;②同步：必须保证”⼀一前⼀一后”（前V后P）执⾏行行的操作。设置同步信号量量S，初值为0。注：同步：要为每⼀一对前驱关系各设置⼀一个信号量量。P、V操作必须成对出现题型：①生产者消费者：semaphoremutex=1;//互斥信号量semaphoreempty=n;//同步信号量，空闲缓冲区的数量semaphorefull=0;//同步信号量，产品的数量（非空缓冲区的数量）多生产者多消费者：P081吃苹果吃橘子②吸烟者问题：P085semaphoremutex=1;//（桌子）互斥信号量—但是此题不需要！semaphoreoffer1=0;//同步互斥量，桌子上组合1的数量semaphor