1、1第第0章章 操作系统导论操作系统导论内容内容：操作系统简介操作系统简介行程管理行程管理处理机排班处理机排班内存管理内存管理虚拟内存管理虚拟内存管理输入输入/输出装置管理输出装置管理文件系统管理文件系统管理20-1操作系统简介操作系统简介内容内容何谓操作系统何谓操作系统计算机系统的架构计算机系统的架构操作系统的功能操作系统的功能操作系统的种类操作系统的种类第0-1章 操作系统简介3操作系统简介操作系统简介(1)0-1-1何谓操作系统何谓操作系统 ？用户与计算机硬件间的沟通桥梁，提供使用者个执行及操作程序的环境，让用户用户与计算机硬件间的沟通桥梁，提供使用者个执行及操作程序的环境，让用户能够很方
2、便且迅速的操作计算机能够很方便且迅速的操作计算机主机与操作系统主机与操作系统MS-DOS操作系统操作系统 单一使用者单一使用者/单一工作单一工作 的工作平台的工作平台Windows操作系统操作系统 Win95.98.Me是单一使用者是单一使用者/多工作多工作 的平台的平台 WinNT开始开始 是多使用者是多使用者/多工作多工作 的平台的平台Linux操作系统操作系统 完全免费且于网络上公开原始码的操作系统完全免费且于网络上公开原始码的操作系统 Fedora4主机与操作系统主机与操作系统5计算机系统的架构计算机系统的架构硬件（含韧体）硬件（含韧体）硬件为计算机的实体装置，包含内存、磁盘驱动器、磁
3、带机、屏幕、键盘、鼠标硬件为计算机的实体装置，包含内存、磁盘驱动器、磁带机、屏幕、键盘、鼠标等设备；这些设备都需透过适当的驱动程序来操作等设备；这些设备都需透过适当的驱动程序来操作般计算机都将管理程序刻录在主板上的般计算机都将管理程序刻录在主板上的EPROM，并保持随时可以启动，称之为，并保持随时可以启动，称之为【韧体韧体】(Firmware)核心核心依照韧体提供的功能，编写一些较容易链接的函数，以供其他程序链接并透过它依照韧体提供的功能，编写一些较容易链接的函数，以供其他程序链接并透过它来存取接口设备，这些函数的整合体称为来存取接口设备，这些函数的整合体称为【核心核心】(Kernel)外壳外
4、壳编写可以存取核心的程序，好让般使用者操作，这就是编写可以存取核心的程序，好让般使用者操作，这就是【外壳外壳】(Shell)应用程序应用程序用户利用核心与外壳的标准接口程序来编写应用软用户利用核心与外壳的标准接口程序来编写应用软體體(Application Program)，大部，大部分情况与硬件无关，程序设计师可以完全不用理会周边硬件分情况与硬件无关，程序设计师可以完全不用理会周边硬件6计算机系统架构计算机系统架构7系统程序与系统呼叫系统程序与系统呼叫我们会将硬件控制程序与最基本的计算机运作程序整合成一个称之为我们会将硬件控制程序与最基本的计算机运作程序整合成一个称之为【系系统程序统程序】(
5、System Program)，该程序提供计算机最根本的运作平台，再由，该程序提供计算机最根本的运作平台，再由此平台扩充功能，整合个强大的此平台扩充功能，整合个强大的【操作系统操作系统】系统程序提供许多关于外围设备的函数，一般称为系统程序提供许多关于外围设备的函数，一般称为【系统呼叫系统呼叫】(System call)，藉由这些函数的呼叫，用户就可以轻易存取接口设备，藉由这些函数的呼叫，用户就可以轻易存取接口设备我们习惯将常驻于内存的库存函数称为我们习惯将常驻于内存的库存函数称为核心核心，因为这些函数随时会被，因为这些函数随时会被呼叫呼叫通常通常Unix/Linux的核心可让用户选择所欲加载的
6、函数，这是的核心可让用户选择所欲加载的函数，这是Unix/Linux系统最系统最引以为傲的地方，而引以为傲的地方，而widows就望尘莫及就望尘莫及8操作系统的功能操作系统的功能控制程序（控制程序（Control program）OS提供控制所有接口设备的功能提供控制所有接口设备的功能人机界面（人机界面（User-machine interface）使用者透过使用者透过OS所提供的人机接口工具方便的操作计算机所提供的人机接口工具方便的操作计算机此类型工具大多称之为此类型工具大多称之为【命令命令】(command)延伸机器（延伸机器（Extended machine）使用者不需利用使用者不需利用
7、0/1操作计算机，只要使用接近人类的语言就可以控制计操作计算机，只要使用接近人类的语言就可以控制计算机，进一步让计算机更接近人类的逻辑思维来处理事务算机，进一步让计算机更接近人类的逻辑思维来处理事务资源管理者（资源管理者（Resource manager）负责将负责将CPU、内存空间、磁盘空间、打印机与数据等资源分配给用户程序，、内存空间、磁盘空间、打印机与数据等资源分配给用户程序，为了避免冲突发生，为了避免冲突发生，OS必须快速且合适地分配资源必须快速且合适地分配资源9操作系统的种类操作系统的种类批处理系统（批处理系统（Batch processing system）早期计算机资源昂贵，多利
8、用整批方式输入给系统一起处理早期计算机资源昂贵，多利用整批方式输入给系统一起处理多元处理系统（多元处理系统（Multi-programming system）多个程序同时存在内存中，多个程序同时存在内存中，CPU以某选定策略轮流执行这些程序以某选定策略轮流执行这些程序用户会感觉好像多个程序同时被执行用户会感觉好像多个程序同时被执行(实际某时刻只有个程序执行实际某时刻只有个程序执行)分时处理系统（分时处理系统（Time-sharing system）将将CPU运行时间运行时间平均分配平均分配给每一个用户，让多个程序可以共享给每一个用户，让多个程序可以共享CPU所以无论程序大小，只要小段的时间用完
9、，而不论工作是否执行完毕，所以无论程序大小，只要小段的时间用完，而不论工作是否执行完毕，都必须要换下一个程序使用都必须要换下一个程序使用10操作系统的种类操作系统的种类多任务处理系统（多任务处理系统（Multi-task system）多处理机系统（多处理机系统（Multi-processor system）部计算机中有多个部计算机中有多个CPU同时处理同时处理 提供快速运算环境提供快速运算环境实时系统（实时系统（Real-time system）每个程序都有其优先权每个程序都有其优先权(优先顺序优先顺序)，优先权高的工作有优先处理的特权，优先权高的工作有优先处理的特权必须在限定的时间内完成，
10、否则逾时可能不具任何实质意义必须在限定的时间内完成，否则逾时可能不具任何实质意义11行程管理行程管理(1)内容内容何谓行程何谓行程 ？行程的生命周期行程的生命周期行程的同步行程的同步行程的死结行程的死结行程的通讯行程的通讯12行程管理行程管理(2)何谓行程何谓行程(Process)？行程行程-执行中的程序，属于主动组件执行中的程序，属于主动组件 程序程序属于被动组件属于被动组件行程在执行当中，会根据需要产生其他子行程行程在执行当中，会根据需要产生其他子行程(Child Process)，交付给子，交付给子行程所要执行的工作行程所要执行的工作行程又可分为行程又可分为【操作系统行程操作系统行程】与
11、与【使用者行程使用者行程】 操作系统行程执行操作系统行程执行系统程序代码系统程序代码 使用者行程执行使用者行程执行使用者程序代码使用者程序代码13行程的特性与现象行程的特性与现象行程的特性行程的特性行程序一个动态的概念行程序一个动态的概念行程是程序与数据的结合体行程是程序与数据的结合体行程可并行处理行程可并行处理 CPU速度够快，可视为所有行程都正在执行中速度够快，可视为所有行程都正在执行中行程的现象行程的现象以象棋为范例以象棋为范例行程间会互相竞争行程间会互相竞争 因为因为CPU次仅能执行一个行程，所以系统中的行程可能需要经过竞争，次仅能执行一个行程，所以系统中的行程可能需要经过竞争，才能得
12、到才能得到CPU资源，所以会涉及行程的排班问题资源，所以会涉及行程的排班问题14行程生命周期行程生命周期因为同时间仅有一个行程被选入执行，所以一个行程从产生到执行完毕因为同时间仅有一个行程被选入执行，所以一个行程从产生到执行完毕通常需要几回合的执行周期才可以完成。通常需要几回合的执行周期才可以完成。执行状态执行状态(Running state) 行程执行中行程执行中预备状态（预备状态（Ready state） 行程已经取得所需的资源，正准备进入行程已经取得所需的资源，正准备进入CPU执行执行等待状态（等待状态（Wait state） 在执行当中可能因为无法获得某些资源或者逾时退出执行，就会进入
13、等待在执行当中可能因为无法获得某些资源或者逾时退出执行，就会进入等待停止状态（停止状态（Stop state） 行程执行完毕，等待被注销行程执行完毕，等待被注销死结状态（死结状态（Deadlock state） 行程可能在等待一个永远无法获得的资源，并继续无止境等待行程可能在等待一个永远无法获得的资源，并继续无止境等待15行程生命周期行程生命周期16行程生命周期行程生命周期挂起等待状态（挂起等待状态（Suspend waited state） 当当CPU工作负荷过重且难以承受时，会选择某些行程将其挂起，并进入挂起等待状工作负荷过重且难以承受时，会选择某些行程将其挂起，并进入挂起等待状态。甚至行
14、程的程序与数据可能会被置换出去到外部辅助内存态。甚至行程的程序与数据可能会被置换出去到外部辅助内存(Swap out)挂起预备状态（挂起预备状态（Suspend ready state） 被挂起的行程欲再次进入运行时间，须先到挂起预备状态，然后等待进入预备状态。被挂起的行程欲再次进入运行时间，须先到挂起预备状态，然后等待进入预备状态。17行程的命令行程的命令建立（建立（fork）Fork系统呼叫会产生一个子系统呼叫会产生一个子行程行程(Child Process)，产生行程者称为父行程，产生行程者称为父行程停止（停止（stop）撤销（撤销（destroy）无论行程是正常停止或非正常停止，都需藉
15、由撤销命令释回行程所占用的无论行程是正常停止或非正常停止，都需藉由撤销命令释回行程所占用的内存空间与相关资源内存空间与相关资源阻断（阻断（block）行程从执行状态行程从执行状态 等待状态等待状态唤醒（唤醒（wakeup）行程从等待状行程从等待状態態预备状态预备状态挂起（挂起（suspend）激活（激活（activate）藉由激活让系统重新配置内存空间以执行该行程藉由激活让系统重新配置内存空间以执行该行程18行程生命周期行程生命周期19临界区间临界区间(Critical Section)临界区间临界区间就是指就是指共享区域共享区域 以交通系统为例，临界区间就是交叉入口以交通系统为例，临界区间就
16、是交叉入口 以程序而言，临界区间就是整体变量以程序而言，临界区间就是整体变量(Global Variable) Ex.SUM变量次只能允许个行程执行，否则会有竞争条件变量次只能允许个行程执行，否则会有竞争条件(Race Condition)出现出现测试与设定（测试与设定（Test-And-Set, TAS） K=flag; If (flag = 0) flag = 1;/flag =表示该资源已经被取用表示该资源已经被取用20行程同步行程同步号志与号志与P/V操作操作(Semaphore)多重资源多重资源S：可使用资源数量：可使用资源数量P(S)：取得共享资源：取得共享资源 if S 0 th
17、en S = S-1 else Waiting .V(S)：释放共享资源：释放共享资源 S = S +1 wakeup process21行程的死结预防行程的死结预防互斥（互斥（mutual exclusion）除非资源取之不尽用之不竭，否则不可能达到资源互斥的需求除非资源取之不尽用之不竭，否则不可能达到资源互斥的需求占用与等候（占用与等候（hold and wait）行程占用一个资源，而另个行程在等待被占用的资源行程占用一个资源，而另个行程在等待被占用的资源有可能发生有可能发生【饥饿现象饥饿现象】不可抢先（不可抢先（no pre-emption）循环式等候（循环式等候（circular wa
18、it）个行程等个行程个行程等个行程22行程的通讯行程的通讯阻断传送（阻断传送（Blocking Send）传送端一直等到接收端接收讯息为止传送端一直等到接收端接收讯息为止无阻断传送无阻断传送 （Nonblocking send）传送端送出讯息，无须等待接收端接收，马上可以重新操作传送端送出讯息，无须等待接收端接收，马上可以重新操作阻断接收（阻断接收（Blocking Receive）接收端一直等到有讯息出现接收端一直等到有讯息出现无阻断接收（无阻断接收（nonblocking Receive）接收端收到讯息或指示无有效数据接收端收到讯息或指示无有效数据 Send (A, message) Re
19、ceive (B, message)23讯息缓冲通讯讯息缓冲通讯讯息缓冲通讯讯息缓冲通讯分时系统的任一时间只有一个行程会被启动，欲达到两个行程直接通讯是不可能的。分时系统的任一时间只有一个行程会被启动，欲达到两个行程直接通讯是不可能的。可以将传送行程欲传送给接收行程的讯息直接投入信箱内，接收行程再由信箱读取信可以将传送行程欲传送给接收行程的讯息直接投入信箱内，接收行程再由信箱读取信息，所谓息，所谓信箱信箱就是主存储器的某区块空间，又称为就是主存储器的某区块空间，又称为【讯息缓冲器讯息缓冲器】 Send (A, message) Receive (A, message)24管道通讯管道通讯管道通
20、讯管道通讯(Pipe)主要缺点是容量有所限制，针对大量传输往往会发生缓冲器空间不足的问主要缺点是容量有所限制，针对大量传输往往会发生缓冲器空间不足的问题。题。原则上共享档案只允许相互通讯的两行程使用，并不分享给其他行程原则上共享档案只允许相互通讯的两行程使用，并不分享给其他行程250-3处理机排班处理机排班(1)内容内容何谓处理机排班？何谓处理机排班？先到先服务排班先到先服务排班最短工作优先排班最短工作优先排班最高等级优先排班最高等级优先排班循环点名排班循环点名排班多层次队列排班多层次队列排班多层次反馈队列排班多层次反馈队列排班26处理机排班处理机排班何谓处理机排班何谓处理机排班一部主机系统可
21、以有很多个行程同时处于执行状态，但是一部主机系统可以有很多个行程同时处于执行状态，但是CPU在任一在任一时间内仅能处理一个行程时间内仅能处理一个行程，所以所以CPU如何由多个行程中选择一个行程如何由多个行程中选择一个行程执行执行排班的重要因素排班的重要因素 CPU使用率使用率(Utilization) CPU的等待是资源浪费，所以使用率越高越好的等待是资源浪费，所以使用率越高越好 输出量输出量(Throughput) 回复时间回复时间(Turnaround time) 行程工作进入计算机系统到执行完毕离开计算机这一段时间称之行程工作进入计算机系统到执行完毕离开计算机这一段时间称之 等候时间等候
22、时间(Waiting time) 般行程备般行程备CPU执行的时间不会太长，大部分都是花在排班等候执行的时间不会太长，大部分都是花在排班等候CPU27处理机排班处理机排班先到先服务排班先到先服务排班(First Come First Served, FCFS)最基本也是最简单的排班方法最基本也是最简单的排班方法系统只要挪出一个队列系统只要挪出一个队列器器(Queue)，将所有进入等待执行的行程依序排，将所有进入等待执行的行程依序排列，先进入者排在前面，后到者排在后面列，先进入者排在前面，后到者排在后面万一所选择的行程运行时间很长，或者甚至发生万一所选择的行程运行时间很长，或者甚至发生死结死结现
23、象，将可现象，将可能导致整个系统停顿能导致整个系统停顿28处理机排班处理机排班最短工作优先排班最短工作优先排班(Shortest Job First, SJF)在目前所产生的行程当在目前所产生的行程当中中，选择最短运行时间的行程优先处理，选择最短运行时间的行程优先处理所以必须有预估每一行程所需运行时间的能力，一但行程产生后，就会所以必须有预估每一行程所需运行时间的能力，一但行程产生后，就会依照所预估运行时间的长短插入行程队列器中适当位置等待执行依照所预估运行时间的长短插入行程队列器中适当位置等待执行 缺点缺点 预估行程的运行时间并不容易预估行程的运行时间并不容易 针对较长时间的行程可能需耗费更
24、多的等待时间，甚至永远无法执针对较长时间的行程可能需耗费更多的等待时间，甚至永远无法执行到，而产生行到，而产生饥饿现象饥饿现象29处理机排班处理机排班最高等级优先排班最高等级优先排班(Highest Priority First, HPF)依照优先权等级由高而低逐一执行依照优先权等级由高而低逐一执行当行程不断产生的同时，一些较低优先权的行程，可能会不断受到排挤，当行程不断产生的同时，一些较低优先权的行程，可能会不断受到排挤，造成需要更长的等待时间，甚至在某些情况可能永远执行不到，这就是造成需要更长的等待时间，甚至在某些情况可能永远执行不到，这就是饥饿现象。饥饿现象。30处理机排班处理机排班(6
25、)循环点名排班循环点名排班(Round-Robin Timesharing, RRT)无论无论FCFS、SJF、HPF都是完成一个行程之后，才选择下一个行程来都是完成一个行程之后，才选择下一个行程来执行，所以若是某一行程占用时间过久或者执行当中发生死结现象，执行，所以若是某一行程占用时间过久或者执行当中发生死结现象，将会导致系统效率低落将会导致系统效率低落每一个行程只会执行一小段时间，时间一到，系统会停止行程继续执每一个行程只会执行一小段时间，时间一到，系统会停止行程继续执行且储存该行程的所有状态，然后由行且储存该行程的所有状态，然后由Queue选择一个行程执行，以此选择一个行程执行，以此类推
26、，直到所有行程执行完毕为止类推，直到所有行程执行完毕为止 分割时间片段够小，所有行程就会有并行的感觉，但先决条件是分割时间片段够小，所有行程就会有并行的感觉，但先决条件是CPU速度要够快，否则太短的时间片段会造成耗费在行程前置作速度要够快，否则太短的时间片段会造成耗费在行程前置作业时间比例太大导致效能严重低落业时间比例太大导致效能严重低落31处理机排班处理机排班多层次队列排班多层次队列排班(Multi-Level Queue, MLQ)依照优先等级分成几个不同型态依照优先等级分成几个不同型态每一个队列器内的行程具有相同等级的优先权每一个队列器内的行程具有相同等级的优先权系统依照其优先权高低逐一
27、执行系统依照其优先权高低逐一执行 可想而知很容易造成肌饿现象可想而知很容易造成肌饿现象32处理机排班处理机排班多层次反馈队列排班多层次反馈队列排班(Multi-Level Feedback Queue, MLFQ)基于前者会产生饥饿现象，所以加上会自动提升优先等级的功能基于前者会产生饥饿现象，所以加上会自动提升优先等级的功能 低优先权的会随时间慢慢提升等级，所以最后一定会被执行到低优先权的会随时间慢慢提升等级，所以最后一定会被执行到33处理器排班范例处理器排班范例分别就先到先服务、最短工作优先排班、循环点名排班分别就先到先服务、最短工作优先排班、循环点名排班(时间量时间量=1)、优先、优先权排
28、班权排班算出回复时间算出回复时间算出等候时间算出等候时间34回复时间回复时间等候时间等候时间350-4内存管理内存管理(1)内容内容内存种类内存种类基本概念基本概念内存分配内存分配分区管理分区管理分页管理分页管理分段管理分段管理段页式管理段页式管理36内存种类内存种类主存储器主存储器主板上的半导体内存主板上的半导体内存(SRAM、DRAM、ROM)CPU可以直接存取内存上的程序或数据可以直接存取内存上的程序或数据外部内存外部内存大多指外接的磁盘、光盘、磁带等辅助内存，通常存放大多指外接的磁盘、光盘、磁带等辅助内存，通常存放CPU暂不执行暂不执行的程序或数据的程序或数据CPU无法直接执行外部内存
29、所存取的程序无法直接执行外部内存所存取的程序一般而言当内存不足储存所有行程时，会将一些暂不执行的程序储存一般而言当内存不足储存所有行程时，会将一些暂不执行的程序储存于外部内存，当需要使用时，再由外部内存移入主存储器让于外部内存，当需要使用时，再由外部内存移入主存储器让CPU执行执行370-4内存管理内存管理(3)0-4-2基本概念基本概念主要工作主要工作 逻辑地址空間逻辑地址空間,而不受实际空间限制而不受实际空间限制 多个行程同时驻留于主存储器内，提升系统效能多个行程同时驻留于主存储器内，提升系统效能考虑四个问题考虑四个问题 主存储器分配主存储器分配 地址映像地址映像 由逻辑地址对应至实体地址
30、的方法由逻辑地址对应至实体地址的方法 主存储器保护主存储器保护 分为系统程序与应用程序两种地址空间，前者以储存操作系统的核心分为系统程序与应用程序两种地址空间，前者以储存操作系统的核心程序或常驻系统呼叫为主，不允许使用者直接呼叫存取程序或常驻系统呼叫为主，不允许使用者直接呼叫存取 虚拟内存虚拟内存 将外部辅助内存纳入与主存储器共同使用，让用户感觉主存储器地址将外部辅助内存纳入与主存储器共同使用，让用户感觉主存储器地址空间犹如逻辑地址空间一般空间犹如逻辑地址空间一般38内存分配内存分配分配策略分配策略最先适合最先适合(First Fit, FF) 选择第一个满足请求容量的空闲区选择第一个满足请求
31、容量的空闲区最佳适合最佳适合(Best Fit, BF) 找出能满足请求容量的最小空闲区找出能满足请求容量的最小空闲区最坏适合最坏适合(Worst Fit, WF) 从所有空闲区找出能满足请求的最大空闲区从所有空闲区找出能满足请求的最大空闲区390-4内存管理内存管理(5)0-4-3内存分配内存分配(2)地址映像与保护地址映像与保护400-4内存管理内存管理(6)0-4-3内存分配内存分配(3)覆盖覆盖410-4内存管理内存管理(7)0-4-3内存分配内存分配(4)置换置换主存储器与外部辅助内存间交换程序或数据主存储器与外部辅助内存间交换程序或数据 置换出置换出(Swap out) 程序由主存
32、储器移至辅助内存程序由主存储器移至辅助内存 行程由等待状态进入挂起状态时行程由等待状态进入挂起状态时 主存储器空间不足时主存储器空间不足时 置换入置换入(Swap in) 程序由辅助内存移入主存储器程序由辅助内存移入主存储器 行程由挂起状态进入等待状态时行程由挂起状态进入等待状态时 某些程序被重新呼叫而须唤起时某些程序被重新呼叫而须唤起时42分区管理分区管理固定分区管理固定分区管理(静态分区管理静态分区管理)运作方式是将主存储器分割成若干个固定区块，各个运作方式是将主存储器分割成若干个固定区块，各个区块可以不相等区块可以不相等 容易产生内部碎片容易产生内部碎片(Internal Fragmen
33、tation)43分区管理分区管理可变分区管理可变分区管理(动态分区管理动态分区管理)系统一开始不会将内存分割成固定区块，而是作业欲加载时，再依系统一开始不会将内存分割成固定区块，而是作业欲加载时，再依照作业的大小分配一个适当的区块供其载入，且区块大小刚好符合照作业的大小分配一个适当的区块供其载入，且区块大小刚好符合作业大小作业大小440-4内存管理内存管理(10)0-4-5分页管理分页管理(1)分页管理之概念分页管理之概念作業 A - 分頁 0作業 A - 分頁 1作業 A - 分頁 2作業 A - 分頁 3作業 A - 分頁 4作業 A - 分頁 0作業 B - 分頁 0作業 B - 分頁
34、 1作業 B - 分頁 2作業 B - 分頁 3作業 B - 分頁 4010分頁表分頁表主記憶體主記憶體12610.215316425.012113245332424作業 B - 分頁 012.作業 B - 分頁 113作業 A - 分頁 215.作業 A - 分頁 316作業 B - 分頁 424.作業 A - 分頁 425作業 B - 分頁 332.作業 B - 分頁 245.作業 A作業 A作業 B作業 B外部記憶體外部記憶體 (硬碟) (硬碟)作業 A - 分頁 126450-4内存管理内存管理(11)0-4-5分页管理分页管理(2)地址映像地址映像CPU主記憶體主記憶體1220020
35、PTCRPTCRPdP (12)P (12)P (12)P (12).111001214513240.PMT145200dLALAPAPA145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷程式範圍：00000 20FFF程式範圍：00000 20FFF460-4内存管理内存管理(12)0-4-6分段管理分段管理(1)实现原理实现原理作業 A - 分段 0作業 A - 分段 1作業 A - 分段 2作業 A - 分段 3作業 A - 分段 0作業 B - 分段 0作業 B - 分段 1作業 B - 分段 2010分段表分段表主記憶體主記憶體12610.2153160121132
36、45作業 B - 分段 012.作業 B - 分段 113作業 A - 分段 215.作業 A - 分段 316.作業 B - 分段 2 26作業 A作業 A作業 B作業 B外部記憶體外部記憶體 (硬碟) (硬碟)分分段段大大小小不不一一定定相相等等.作業 B - 分段 245470-4内存管理内存管理(13)0-4-6分段管理分段管理(2)地址映像地址映像CPU主記憶體主記憶體1220020STCRPdP (12)P (12).1010012145SMT145200dLAPA145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷.100300SLbSNb越界中斷越界中斷dd48
37、0-4内存管理内存管理(14)0-4-7段页式管理段页式管理地址映像地址映像sdLALA 邏輯位址 邏輯位址 實體位址 實體位址分段表分段表作業 A作業 A.作業 B作業 B分頁表分頁表p.dspPAPACPU主記憶體主記憶體490-5虚拟内存管理虚拟内存管理(1)内容内容基本概念基本概念动态分页管理动态分页管理动态分段管理动态分段管理500-5虚拟内存管理虚拟内存管理(2)非虚拟内存系统之特性非虚拟内存系统之特性整体性整体性 一个行程的全部实体在执行之前必须加载主一个行程的全部实体在执行之前必须加载主存储器内存储器内驻留性驻留性 操作系统一但进入主存储器内，便一直驻留操作系统一但进入主存储器
38、内，便一直驻留直到执行结束才离开直到执行结束才离开连续性连续性 一个行程分配的是一连续的主存储器空间一个行程分配的是一连续的主存储器空间510-5虚拟内存管理虚拟内存管理(3)虚拟内存管理的三个基本概念虚拟内存管理的三个基本概念局部性局部性 只需将局部程序存放在主存储器只需将局部程序存放在主存储器置换性置换性 目前暂时不使用或今后不再使用的部份程序先置换出内存目前暂时不使用或今后不再使用的部份程序先置换出内存离散性离散性 行程占据的主存储器空间可以不必完全连续行程占据的主存储器空间可以不必完全连续三个管理策略三个管理策略载入策略载入策略-什么时候把需要的部份从外部存储器加载主存储器什么时候把需
39、要的部份从外部存储器加载主存储器分配策略分配策略决定把加载的行程放置在主存储器何处决定把加载的行程放置在主存储器何处淘汰策略淘汰策略置换策略置换策略(当主存储器空间已满或目前可用空间无法容纳当主存储器空间已满或目前可用空间无法容纳)520-5虚拟内存管理虚拟内存管理(4)0-5-2动态分页管理动态分页管理(1)管理技巧管理技巧 主存储器划分若干区块主存储器划分若干区块(block) 将程序划分为若干页将程序划分为若干页(page) 发生发生 “页失误中断页失误中断”,则置换入则置换入(swapping in) 主存储器空间主存储器空间不足不足,则置换出则置换出(swapping out)分页表
40、字段分页表字段駐留位元駐留位元主記憶體區塊主記憶體區塊外部儲存體位址外部儲存體位址控制訊息控制訊息530-5虚拟内存管理虚拟内存管理(5)0-5-2动态分页管理动态分页管理(2)页失误中断程序页失误中断程序主記憶體有空閒區塊虛擬頁不在主記憶體阻塞請求行程依照演算法選擇淘汰某一分頁 F該分頁是否修改過將分頁 F 寫入外部記憶體從外部記憶體讀入 P修改分頁表的駐留位元與位址喚醒請求行程是是是是否否否否54动态分页管理动态分页管理淘汰策略淘汰策略(算法算法)先进先出先进先出(First In First Out, FIFO) 最先进入内存的那一页会被移出最先进入内存的那一页会被移出最佳替换最佳替换
41、希望被移出的分页是最久不会再被参考的那一页希望被移出的分页是最久不会再被参考的那一页最近最少使用最近最少使用(Least Recently Used, LRU) 淘汰最进最少使用的分页淘汰最进最少使用的分页最近最不常使用最近最不常使用(Least Frequently Used, LFU) 将过去参考频率最低的分页置换出去将过去参考频率最低的分页置换出去550-5虚拟内存管理虚拟内存管理(7)0-5-3动态分段管理动态分段管理分段表分段表 增加一个增加一个 “分段长分段长”駐留位元主記憶體區塊外部儲存體位址控制訊息分段長560-6输入输入/输出管理输出管理(1)内容内容基本概念基本概念输入输入
42、/输出时机输出时机字符与成组设备字符与成组设备缓冲器管理缓冲器管理I/O存取界面存取界面Spooling管理管理570-6输入输入/输出管理输出管理(2)0-6-1基本概念基本概念CPUCPU中中央央處處理理單單元元主記憶體 輸入/輸出裝置Data BusAddress Bus週邊裝置(如鍵盤)每一週邊設備對應一個 IO 裝置每一週邊設備對應一個 IO 裝置580-6输入输入/输出管理输出管理(3)0-6-2输入输入/输出时机输出时机(1) 询问询问(Polling) 让让CPU周期性的询问周期性的询问I/O装置是否有数据进入，若有数据进入，装置是否有数据进入，若有数据进入，CPU再读取该外围
43、设备上的数据再读取该外围设备上的数据 询问间隔的长短询问间隔的长短?監督程式 (Monitor)IO 裝置(A)Add_AAdd_AData BusData BusIO 裝置(B)IO 裝置(C)IO 裝置(D)Add_BAdd_BAdd_CAdd_CAdd_DAdd_DData BusData BusScannerKeyboardMouseFaxCPU 詢問次序 :Add_A, Add_B, Add_C, ., Add_DCPU 詢問次序 :Add_A, Add_B, Add_C, ., Add_D590-6输入输入/输出管理输出管理(4)0-6-2输入输入/输出时机输出时机(2-1) 中断
44、处理的运作程序中断处理的运作程序 接口设备需要服务时才提出请求，将可省去不必要的询问接口设备需要服务时才提出请求，将可省去不必要的询问 透过透过I/O装置送出一个中断讯号给装置送出一个中断讯号给CPU，确认中断需求后，会暂停目前正，确认中断需求后，会暂停目前正在执行的程序，并去执行事先已准备好中断程序在执行的程序，并去执行事先已准备好中断程序 中断服务完成后，中断服务完成后，CPU会回到原先被中断的地方继续执行未完成的程序会回到原先被中断的地方继续执行未完成的程序CPU 接受中斷CPU 接受中斷暫停主程式暫停主程式TimeTime主程式主程式中斷中斷副程式副程式CPU 回復CPU 回復原來程式
45、原來程式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) 多重外围设备的中断多重外围设备的中断CPUCPU中中央央處處理理單單元元Data BusAddress Bus中斷中斷控制器控制器中斷訊號中斷訊號 INT0INT0INT7IO IO 處理器處理器(0)(0)IO IO 處理器處理器(1)(
46、1)IO IO 處理器處理器(7)(7)INT1INT3INT7KeyboardFaxHub630-6输入输入/输出管理输出管理(8)0-6-2输入输入/输出时机输出时机(2-5) 内存直接存取内存直接存取(DMA) 接口设备直接与内存之间做数据读取或写入接口设备直接与内存之间做数据读取或写入 DMA控制器利用控制器利用CPU不使用总线的空闲时不使用总线的空闲时間間，取得其控制权并做数据的输，取得其控制权并做数据的输入与输出动作，称为入与输出动作，称为周期偷取周期偷取(Cycle Stealing)CPUCPU中中央央處處理理單單元元主記憶主記憶體體Data BusData BusAddres
47、s BusAddress BusDMADMA控制器控制器IO 處理器IO 處理器(磁碟控制(磁碟控制卡)卡)磁碟機磁碟機Control BusControl Bus640-6输入输入/输出管理输出管理(9)0-6-3字符与成组设备字符与成组设备区块输入区块输入/输出装置输出装置 串行或并列传输串行或并列传输字符输入字符输入/输出装置输出装置 串行或并列传输串行或并列传输CPUIO處理器週邊設備(印表機)區塊或字元區塊或字元讀寫讀寫串列或並列串列或並列傳輸傳輸650-6输入输入/输出管理输出管理(10)0-6-4缓冲器管理缓冲器管理输入缓冲器输入缓冲器输出缓冲器输出缓冲器CPUIO處理器週邊設備
48、主記憶體輸入緩衝器(1)Ri暫存器(2)(3)CPUIO處理器週邊設備主記憶體輸出緩衝器(1)Ri暫存器(2)(3)(1) 輸入緩衝器(1) 輸入緩衝器(2) 輸出緩衝器(2) 輸出緩衝器660-6输入输入/输出管理输出管理(11)0-6-5存取界面存取界面open(device_name) 开取装置开取装置read(device_name, address, size) 从装置读出数据从装置读出数据write(device_name, address, size) 写入数据至装置写入数据至装置close(device_name) 关闭装置关闭装置670-6输入输入/输出管理输出管理(12)0
49、-6-6 Spooling管理管理(在线同时周边处理在线同时周边处理)无无spooling管理的共享打印机管理的共享打印机區域網路telnet AAtelnet Atelnet ABDCUser_BUser_CUser_DUser_Adata_b1data_b2data_b3printdata_c1data_c2data_c3printdata_d1data_d2data_d3printdata_a1data_a2data_a3printdata_a1data_a2data_b1data_c1data_c2data_d1data_b2.印表機輸出共享印表機680-6输入输入/输出管理输出管理(
50、13)0-6-6 Spooling管理管理(2)具有具有spooling管理的共享打印机管理的共享打印机data_b1data_b2data_b3data_b1data_b2data_b3data_b1data_b2data_b3ABDCdata_b1data_b2data_b3printdata_c1data_c2data_c3printdata_d1data_d2data_d3printdata_a1data_a2data_a3print印表機輸出共享印表機共享印表機虛擬印表機虛擬印表機區域網路虛擬印表機虛擬印表機虛擬印表機虛擬印表機虛擬印表機虛擬印表機data_a1data_a2data
