计算机操作系统第六章

⑴集合结构。在集合结构中，数据元素间的关系是“属于 同一个集合”。集合是元素关系极为松散的一种结构。
单击此处添课程名 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。
⑶树型结构。该结构的数据元素之间存在着一对多的关系。
⑷图型结构。该结构的数据元素之间存在着多对多的关系， 图形结构也称作网状结构。
具有特殊的意义，称为栈顶。相应地，表尾 称为栈底。不含任何元素的栈称为空栈。
2. 栈的数学性质
假设一个栈S中的元素为an,an-1,..,a1，则 称a1为栈底元素，an为栈顶元 素。栈中的
元 时素 候按 ，单出a ,a栈击2,的..此,元an素-处1,都an添是的栈次课顶序程元进素栈名。。换在句任话何
第六章 数单据击结此构处添课程名
第6章 数据结构
• 数据结构是计算机软件和计算机应用专业的 核心课程之一，对于学习计算机专业的其他 课程，如操作系统、编译原理、数据库管理
系的统 。、 数软 据单件 结击工 构程主此、要处人研工究添智数能据课等表程都示是 与名十 存储分的有方益
法、抽象的逻辑结构及其上定义的各种基本 操作。数据的逻辑结构常常采用数学描述的 抽象符号和有关的理论。如使用串、表、数 组、图等结构和理论来表示数据在存储时的 逻辑结构，研究这些结构上定义的各种操作 。
本章内容
• 6.1 数据结构的概念 • 6.2 几种典型的数据结构 • 6.3 查找
• 6.4 单排序击此处添课程名
6.1 数据结构的概念
• 在系统地学习数据结构知识之前，先对一 些与数据结构相关的基本概念和术语赋予 确切的含义。
• 数 算机据单识（别D击at、a此）存是储处信和添息加的工课载处体理程，。名它它能是够计被算计机 程序加工的原料，应用程序处理各种各样 的数据。

1
2
3
为保证总线所传输的信息的有效性，总线 信息应具有单一性：在同一时刻至多只能有一 个部件向总线发送信息，但可以有多个部件同 时接收总线信息。
1. 总线电路： 输出挂在总线上的部件需通过“总线电路” 向总线发送信息。
总线电路由三态输出器件（TSL器件）承担。 input TSL control output
1. ISA总线：用于IBM PC/XT 微机系统，(8086)，一共６２根信号线， 其中２０根地址线，８根数据线，４个读写信号，６个中断请求线，３ 路ＤＭＡ请求，还包括时钟、电源线和地等，总线带宽 8.33 MB/s。
２．EISA总线 （80386）， 数据线扩展到了３２位，带宽达到了33.3MB/s。 3. PCI总线：（Peripheral component interconnection）（外围部 件互连） 总线频率为33 MHZ→66MHZ→133MHZ, 可以直接连接高速外部 设备。 同步时序总线，对地址信号和数据信号分时复用， 64根线，采用集中式的总线仲裁方式。 ４．AGP总线（加速图形接口总线） AGP总线把主存和显存连接起来，不再走PCI总线。 ５．USB总线（通用串行总线）主要用于连接低速输入输出设备。 带宽为1.5MB/s。
3. 控制总线CB（Control Bus） 控制总线用来传送各类控制/状态信号。
包括I/O读写命令，MEMR/W存储器读写命令，应答信号，总线请求与 总线使用信号，复位信号，时钟信号等。
4. 电源线
许多总线标准中都包含了电源线的定义，主要有+5V逻辑电源；GND逻 辑电源地；-5V辅助电源；±12V辅助电源。
２．计数器查询方式
在计数器查询方式中，总线上的任一设备申请使用总线时，通过 BR线发出总线请求。

第一章操作系统引论操作系统功能：1. 资源管理：协调、管理计算机的软、硬件资源，提高其利用率。

2. 用户角度：为用户提供使用计算机的环境和服务。

操作系统特征：1.并发性：指两个或多个事件在同一时间间隔内发生。

2.共享性：资源可供内存中多个并发执行的进程(线程)共同使用3.虚拟性：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物在操作系统中，虚拟的实现主要是通过分时使用的方法。

4.异步性：进程是以人们不可预知的速度向前推进，此即进程的异步性客户/服务器模式的优点：1.提高了系统的灵活性和可扩充性2.提高了OS的可靠性3.可运行于分布式系统中微内核的基本功能：进程管理、进程间通信、存储器管理、低级I/O功能。

第二章进程程序和进程区别：程序是静止的，进程是动态的，进程包括程序和程序处理的对象程序顺序执行：顺序性，封闭性，可再现性程序并发执行：间断性，无封闭性，可再现性进程：1.进程是可并发执行的程序的一次执行过程；2.是系统进行资源分配和调度的一个独立的基本单位和实体；3.是一个动态的概念。

进程的特征： 1.动态性：进程是程序的一次执行过程具有生命期；它可以由系统创建并独立地执行，直至完成而被撤消2.并发性；3.独立性；4.异步性；进程的基本状态：1.执行状态；2.就绪状态；3.阻塞状态；进程控制块PCB：记录和描述进程的动态特性，描述进程的执行情况和状态变化。

是进程存在的唯一标识。

进程运行状态： 1.系统态（核心态，管态）具有较高的访问权，可访问核心模块。

2.用户态（目态）限制访问权进程间的约束关系：1.互斥关系进程之间由于竞争使用共享资源而产生的相互约束的关系。

这种因共享资源而产生的制约关系称为进程的互斥。

—间接相互制约关系2.同步关系并发执行进程之间通过在执行时序上的某种限制而达到相互合作的这种约束关系称为进程的同步—直接相互制约关系临界资源：凡是以互斥方式使用的共享资源都称为临界资源。

临界资源具有一次只允许一个进程使用的属性。

操作系统重点知识总结操作系统》重点知识总结第一章引论1、操作系统定义：是一组控制和管理计算机硬件和软件资源，合理的对各类作业进行调度以及方便用户使用的程序的集合。

2、操作系统的作用1. os作为用户与计算机硬件系统之间的接口。

2. 作为计算机资源的管理者3. 实现了对计算机资源的抽象。

3、分时系统原理和特征原理：人机交互、共享主机特征：多路性、独立性、及时性、交互性4、脱机I/O 原理：程序和数据的输入和输出都是在外围机的控制下完成。

优点：减少了CPU 空闲时间、提高了I/O 速度。

5、操作系统四个基本特征；其中最重要特征是什么？（并发）并发、共享、虚拟、异步第二章进程管理1 、进程定义、进程特征（结构特征、动态性、并发性、独立性和异步性）1. 进程是程序的一次执行。

2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

3. 进程是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。

动态性、并发性、独立性、异步性。

2、进程的基本状态、相互转换原因及转换图（三态）就绪、阻塞、执行3、具有挂起状态的进程状态、相互转换原因及其转换图（五态）活动就绪、静止就绪、活动阻塞、静止阻塞、执行4、什么是进程控制块？进程控制块的作用进程控制块是用于描述进程当前情况以及管理进程运行的全部信息。

1. 作为独立运行基本单位的标志。

2. 能实现间断性运行方式。

3. 提供进程管理、调度所需要的信息4. 实现与其他进程同步与通信5、临界资源定义、临界区的定义一次只能为一个进程使用的资源称为临界资源。

每个进程访问临界资源的代码称为临界区。

6、同步机制应遵循的规则空闲让进、忙则等待、有限等待、让权等待7、记录型信号量的定义，信号量值的物理意义，wait 和signal 操作8、AND 型信号量的定义，Swait 和Ssignal 操作9、经典同步算法：①生产者－消费者问题算法；②不会死锁的哲学家就餐问题算法；③读者－写者问题算法10、利用信号量机制实现进程之间的同步算法（前驱关系、类经典同步问题）11、高级进程通信三种类型。