操作系统导论

1第0章操作系统导论内容：操作系统简介行程管理处理机排班内存管理虚拟内存管理输入/输出装置管理文件系统管理20-1操作系统简介内容何谓操作系统计算机系统的架构操作系统的功能操作系统的种类第0-1章操作系统简介3操作系统简介(1)0-1-1何谓操作系统？用户与计算机硬件间的沟通桥梁，提供使用者ㄧ个执行及操作程序的环境，让用户能够很方便且迅速的操作计算机主机与操作系统MS-DOS操作系统单一使用者/单一工作的工作平台Windows操作系统Win95.98.Me是单一使用者/多工作的平台WinNT开始是多使用者/多工作的平台Linux操作系统完全免费且于网络上公开原始码的操作系统Fedora4主机与操作系统5计算机系统的架构硬件（含韧体）硬件为计算机的实体装置，包含内存、磁盘驱动器、磁带机、屏幕、键盘、鼠标等设备；这些设备都需透过适当的驱动程序来操作ㄧ般计算机都将管理程序刻录在主板上的EPROM，并保持随时可以启动，称之为【韧体】(Firmware)核心依照韧体提供的功能，编写一些较容易链接的函数，以供其他程序链接并透过它来存取接口设备，这些函数的整合体称为【核心】(Kernel)外壳编写可以存取核心的程序，好让ㄧ般使用者操作，这就是【外壳】(Shell)应用程序用户利用核心与外壳的标准接口程序来编写应用软體(ApplicationProgram)，大部分情况与硬件无关，程序设计师可以完全不用理会周边硬件6计算机系统架构7系统程序与系统呼叫我们会将硬件控制程序与最基本的计算机运作程序整合成一个称之为【系统程序】(SystemProgram)，该程序提供计算机最根本的运作平台，再由此平台扩充功能，整合ㄧ个强大的【操作系统】系统程序提供许多关于外围设备的函数，一般称为【系统呼叫】(Systemcall)，藉由这些函数的呼叫，用户就可以轻易存取接口设备我们习惯将常驻于内存的库存函数称为『核心』，因为这些函数随时会被呼叫通常Unix/Linux的核心可让用户选择所欲加载的函数，这是Unix/Linux系统最引以为傲的地方，而widows就望尘莫及8操作系统的功能控制程序（Controlprogram）OS提供控制所有接口设备的功能人机界面（User-machineinterface）使用者透过OS所提供的人机接口工具方便的操作计算机此类型工具大多称之为【命令】(command)延伸机器（Extendedmachine）使用者不需利用0/1操作计算机，只要使用接近人类的语言就可以控制计算机，进一步让计算机更接近人类的逻辑思维来处理事务资源管理者（Resourcemanager）负责将CPU、内存空间、磁盘空间、打印机与数据等资源分配给用户程序，为了避免冲突发生，OS必须快速且合适地分配资源9操作系统的种类批处理系统（Batchprocessingsystem）早期计算机资源昂贵，多利用整批方式输入给系统一起处理多元处理系统（Multi-programmingsystem）多个程序同时存在内存中，CPU以某选定策略轮流执行这些程序用户会感觉好像多个程序同时被执行(实际某时刻只有ㄧ个程序执行)分时处理系统（Time-sharingsystem）将CPU运行时间平均分配给每一个用户，让多个程序可以共享CPU所以无论程序大小，只要ㄧ小段的时间用完，而不论工作是否执行完毕，都必须要换下一个程序使用10操作系统的种类多任务处理系统（Multi-tasksystem）多处理机系统（Multi-processorsystem）ㄧ部计算机中有多个CPU同时处理提供快速运算环境实时系统（Real-timesystem）每ㄧ个程序都有其优先权(优先顺序)，优先权高的工作有优先处理的特权必须在限定的时间内完成，否则逾时可能不具任何实质意义11行程管理(1)内容何谓行程？行程的生命周期行程的同步行程的死结行程的通讯12行程管理(2)何谓行程(Process)？行程--执行中的程序，属于主动组件程序–属于被动组件行程在执行当中，会根据需要产生其他子行程(ChildProcess)，交付给子行程所要执行的工作行程又可分为【操作系统行程】与【使用者行程】操作系统行程执行『系统程序代码』使用者行程执行『使用者程序代码』13行程的特性与现象行程的特性行程序一个动态的概念行程是程序与数据的结合体行程可并行处理CPU速度够快，可视为所有行程都正在执行中行程的现象以象棋为范例行程间会互相竞争因为CPUㄧ次仅能执行一个行程，所以系统中的行程可能需要经过竞争，才能得到CPU资源，所以会涉及行程的排班问题14行程生命周期因为同ㄧ时间仅有一个行程被选入执行，所以一个行程从产生到执行完毕通常需要几回合的执行周期才可以完成。执行状态(Runningstate)行程执行中预备状态（Readystate）行程已经取得所需的资源，正准备进入CPU执行等待状态（Waitstate）在执行当中可能因为无法获得某些资源或者逾时退出执行，就会进入等待停止状态（Stopstate）行程执行完毕，等待被注销死结状态（Deadlockstate）行程可能在等待一个永远无法获得的资源，并继续无止境等待15行程生命周期16行程生命周期挂起等待状态（Suspendwaitedstate）当CPU工作负荷过重且难以承受时，会选择某些行程将其挂起，并进入挂起等待状态。甚至行程的程序与数据可能会被置换出去到外部辅助内存(Swapout)挂起预备状态（Suspendreadystate）被挂起的行程欲再次进入运行时间，须先到挂起预备状态，然后等待进入预备状态。17行程的命令建立（fork）Fork系统呼叫会产生一个子行程(ChildProcess)，产生行程者称为父行程停止（stop）撤销（destroy）无论行程是正常停止或非正常停止，都需藉由撤销命令释回行程所占用的内存空间与相关资源阻断（block）行程从执行状态等待状态唤醒（wakeup）行程从等待状態预备状态挂起（suspend）激活（activate）藉由激活让系统重新配置内存空间以执行该行程18行程生命周期19临界区间(CriticalSection)临界区间就是指『共享区域』以交通系统为例，临界区间就是交叉入口以程序而言，临界区间就是整体变量(GlobalVariable)Ex.SUM变量ㄧ次只能允许ㄧ个行程执行，否则会有竞争条件(RaceCondition)出现测试与设定（Test-And-Set,TAS）K=flag;If(flag==0)flag=1; //flag=表示该资源已经被取用20行程同步号志与P/V操作(Semaphore)–多重资源S：可使用资源数量P(S)：取得共享资源ifS>0thenS=S-1elseWaiting…..V(S)：释放共享资源S=S+1wakeupprocess21行程的死结预防互斥（mutualexclusion）除非资源取之不尽用之不竭，否则不可能达到资源互斥的需求占用与等候（holdandwait）行程占用一个资源，而另ㄧ个行程在等待被占用的资源有可能发生【饥饿现象】不可抢先（nopre-emption）循环式等候（circularwait）ㄧ个行程等ㄧ个行程22行程的通讯阻断传送（BlockingSend）传送端一直等到接收端接收讯息为止无阻断传送（Nonblockingsend）传送端送出讯息，无须等待接收端接收，马上可以重新操作阻断接收（BlockingReceive）接收端一直等到有讯息出现无阻断接收（nonblockingReceive）接收端收到讯息或指示无有效数据Send(A,message)Receive(B,message)23讯息缓冲通讯讯息缓冲通讯分时系统的任一时间只有一个行程会被启动，欲达到两个行程直接通讯是不可能的。可以将传送行程欲传送给接收行程的讯息直接投入信箱内，接收行程再由信箱读取信息，所谓『信箱』就是主存储器的某ㄧ区块空间，又称为【讯息缓冲器】Send(A,message)Receive(A,message)24管道通讯管道通讯(Pipe)主要缺点是容量有所限制，针对大量传输往往会发生缓冲器空间不足的问题。原则上共享档案只允许相互通讯的两行程使用，并不分享给其他行程250-3处理机排班(1)内容何谓处理机排班？先到先服务排班最短工作优先排班最高等级优先排班循环点名排班多层次队列排班多层次反馈队列排班26处理机排班何谓处理机排班一部主机系统可以有很多个行程同时处于执行状态，但是CPU在任一时间内仅能处理一个行程，所以CPU如何由多个行程中选择一个行程执行排班的重要因素CPU使用率(Utilization)CPU的等待是资源浪费，所以使用率越高越好输出量(Throughput)回复时间(Turnaroundtime)行程工作进入计算机系统到执行完毕离开计算机这一段时间称之等候时间(Waitingtime) ㄧ般行程备CPU执行的时间不会太长，大部分都是花在排班等候CPU27处理机排班先到先服务排班(FirstComeFirstServed,FCFS)最基本也是最简单的排班方法系统只要挪出一个队列器(Queue)，将所有进入等待执行的行程依序排列，先进入者排在前面，后到者排在后面万一所选择的行程运行时间很长，或者甚至发生『死结』现象，将可能导致整个系统停顿28处理机排班最短工作优先排班(ShortestJobFirst,SJF)在目前所产生的行程当中，选择最短运行时间的行程优先处理所以必须有预估每一行程所需运行时间的能力，一但行程产生后，就会依照所预估运行时间的长短插入行程队列器中适当位置等待执行缺点预估行程的运行时间并不容易针对较长时间的行程可能需耗费更多的等待时间，甚至永远无法执行到，而产生『饥饿现象』29处理机排班最高等级优先排班(HighestPriorityFirst,HPF)依照优先权等级由高而低逐一执行当行程不断产生的同时，一些较低优先权的行程，可能会不断受到排挤，造成需要更长的等待时间，甚至在某些情况可能永远执行不到，这就是饥饿现象。30处理机排班(6)循环点名排班(Round-RobinTimesharing,RRT)无论FCFS、SJF、HPF都是完成一个行程之后，才选择下一个行程来执行，所以若是某一行程占用时间过久或者执行当中发生死结现象，将会导致系统效率低落每一个行程只会执行一小段时间，时间一到，系统会停止行程继续执行且储存该行程的所有状态，然后由Queue选择一个行程执行，以此类推，直到所有行程执行完毕为止分割时间片段够小，所有行程就会有并行的感觉，但先决条件是CPU速度要够快，否则太短的时间片段会造成耗费在行程前置作业时间比例太大导致效能严重低落31处理机排班多层次队列排班(Multi-LevelQueue,MLQ)依照优先等级分成几个不同型态每一个队列器内的行程具有相同等级的优先权系统依照其优先权高低逐一执行可想而知很容易造成肌饿现象32处理机排班多层次反馈队列排班(Multi-LevelFeedbackQueue,MLFQ)基于前者会产生饥饿现象，所以加上会自动提升优先等级的功能低优先权的会随时间慢慢提升等级，所以最后一定会被执行到33处理器排班范例分别就先到先服务、最短工作优先排班、循环点名排班(时间量=1)、优先权排班算出回复时间算出等候时间34回复时间等候时间350-4内存管理(1)内容内存种类基本概念内存分配分区管理分页管理分段管理段页式管理36内存种类主存储器主板上的半导体内存(SRAM、DRAM、ROM)CPU可以直接存取内存上的程序或数据外部内存大多指外接的磁盘、光盘、磁带等辅助内存，通常存放CPU暂不执行的程序或数据CPU无法直接执行外部内存所存取的程序一般而言当内存不足储存所有行程时，会将一些暂不执行的程序储存于外部内存，当需要使用时，再由外部内存移入主存储器让CPU执行370-4内存管理(3)0-4-2基本概念主要工作逻辑地址空間,而不受实际空间限制多个行程同时驻留于主存储器内，提升系统效能考虑四个问题主存储器分配地址映像 由逻辑地址对应至实体地址的方法主存储器保护分为系统程序与应用程序两种地址空间，前者以储存操作系统的核心程序或常驻系统呼叫为主，不允许使用者直接呼叫存取虚拟内存将外部辅助内存纳入与主存储器共同使用，让用户感觉主存储器地址空间犹如逻辑地址空间一般38内存分配分配策略最先适合(FirstFit,FF)选择第一个满足请求容量的空闲区最佳适合(BestFit,BF)找出能满足请求容量的最小空闲区最坏适合(WorstFit,WF)从所有空闲区找出能满足请求的最大空闲区390-4内存管理(5)0-4-3内存分配(2)地址映像与保护400-4内存管理(6)0-4-3内存分配(3)覆盖410-4内存管理(7)0-4-3内存分配(4)置换–主存储器与外部辅助内存间交换程序或数据置换出(Swapout)–程序由主存储器移至辅助内存行程由等待状态进入挂起状态时主存储器空间不足时置换入(Swapin)–程序由辅助内存移入主存储器行程由挂起状态进入等待状态时某些程序被重新呼叫而须唤起时42分区管理固定分区管理(静态分区管理) 运作方式是将主存储器分割成若干个固定区块，各个区块可以不相等容易产生内部碎片(InternalFragmentation)43分区管理可变分区管理(动态分区管理)系统一开始不会将内存分割成固定区块，而是作业欲加载时，再依照作业的大小分配一个适当的区块供其载入，且区块大小刚好符合作业大小440-4内存管理(10)0-4-5分页管理(1)分页管理之概念450-4内存管理(11)0-4-5分页管理(2)地址映像460-4内存管理(12)0-4-6分段管理(1)实现原理470-4内存管理(13)0-4-6分段管理(2)地址映像480-4内存管理(14)0-4-7段页式管理地址映像490-5虚拟内存管理(1)内容基本概念动态分页管理动态分段管理500-5虚拟内存管理(2)非虚拟内存系统之特性整体性一个行程的全部实体在执行之前必须加载主存储器内驻留性操作系统一但进入主存储器内，便一直驻留直到执行结束才离开连续性一个行程分配的是一连续的主存储器空间510-5虚拟内存管理(3)虚拟内存管理的三个基本概念局部性只需将局部程序存放在主存储器置换性目前暂时不使用或今后不再使用的部份程序先置换出内存离散性行程占据的主存储器空间可以不必完全连续三个管理策略载入策略-什么时候把需要的部份从外部存储器加载主存储器分配策略–决定把加载的行程放置在主存储器何处淘汰策略–置换策略(当主存储器空间已满或目前可用空间无法容纳)520-5虚拟内存管理(4)0-5-2动态分页管理(1)管理技巧主存储器划分若干区块(block)将程序划分为若干页(page)发生“页失误中断”,则置换入(swappingin)主存储器空间不足,则置换出(swappingout)分页表字段530-5虚拟内存管理(5)0-5-2动态分页管理(2)页失误中断程序54动态分页管理淘汰策略(算法)先进先出(FirstInFirstOut,FIFO)最先进入内存的那一页会被移出最佳替换希望被移出的分页是最久不会再被参考的那一页最近最少使用(LeastRecentlyUsed,LRU)淘汰最进最少使用的分页最近最不常使用(LeastFrequentlyUsed,LFU)将过去参考频率最低的分页置换出去550-5虚拟内存管理(7)0-5-3动态分段管理分段表增加一个“分段长”560-6输入/输出管理(1)内容基本概念输入/输出时机字符与成组设备缓冲器管理I/O存取界面Spooling管理570-6输入/输出管理(2)0-6-1基本概念580-6输入/输出管理(3)0-6-2输入/输出时机(1)

询问(Polling)让CPU周期性的询问I/O装置是否有数据进入，若有数据进入，CPU再读取该外围设备上的数据询问间隔的长短?590-6输入/输出管理(4)0-6-2输入/输出时机(2-1)

中断处理的运作程序接口设备需要服务时才提出请求，将可省去不必要的询问透过I/O装置送出一个中断讯号给CPU，确认中断需求后，会暂停目前正在执行的程序，并去执行事先已准备好中断程序中断服务完成后，CPU会回到原先被中断的地方继续执行未完成的程序600-6输入/输出管理(5)0-6-2输入/输出时机(2-2)

中断处理的硬件连接610-6输入/输出管理(6)0-6-2输入/输出时机(2-3)

中断处理的I/O处理器功能620-6输入/输出管理(7)0-6-2输入/输出时机(2-4)

多重外围设备的中断630-6输入/输出管理(8)0-6-2输入/输出时机(2-5)

内存直接存取(DMA)接口设备直接与内存之间做数据读取或写入DMA控制器利用C