[科普中国]-非共享结构

简介

非共享结构抽象地表示系统中的非共享资源。这里资源可以是硬件资源和软件资源。典型非共享硬件资源如独占设备。非共享软件资源有很多，如操作系统的进程管理程序，中断处理程序，非共享文件，一些程序中功能模块。对于非共享结构，没有一个操作系统的资源管理模块，主要是功能的多样化。但对于共享数据结构，由代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，称之为管程。

数据结构数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。1

数据结构的形式定义为：数据结构是一个二元组DS=(D，R)，其中：D是数据元素的有限集，R是D上关系的有限集。若在数据结构的定义中出现本身的名，则称为递归的结构。数据结构的概念是N.沃思(N.Wirth)和C.A.R.霍尔(C.A.R.Hoare)在1966年首先提出的。在传统的程序设计语言(如PASCAL、C++等)中，定义数据结构的基本途径是采用数据类型，如整型、字符型、布尔型或实型等。在面向对象程序设计语言中，根据抽象数据类型理论，程序是将数据结构的逻辑结构和它的运算操作在一起定义的，并封装成一个整体。

根据不同的方法，可构造不同的数据结构。在程序设计中常用的数据结构有：①表结构：包括线性表、栈、队列、字符串、数组等。结构中元素之间存在一对一的关系，依次排列形成一条“锁链”;②树结构：结构中元素之间存在一对多的关系，具有分支、层次特性;③图结构：结构中元素之间存在多对多的关系，任何两个元素都可以邻接;④文件：文件中任何两个元素间都没有逻辑关系，组织形式松散。

每一数据结构都有逻辑的和物理的两个侧面。数据结构的逻辑描述，称为数据的逻辑结构；数据在物理介质上的表示，称为物理结构或存储结构。

数据结构按其状态特性可分为静态和动态两类。静态结构是在整个使用期间其大小保持不变的数据结构，而动态结构是在程序执行过程中大小有变化的数据结构。

独占设备是指在一段时间内只允许一个用户(进程)访问的设备，即临界资源。因而，对多个并发进程而言，应互斥地访问这类设备。系统一旦把这类设备分配给了某进程后，便由该进程独占，直至用完释放。应当注意，独占设备的分配有可能引起进程死锁。与之相反是共享设备。这是指在一段时间内允许多个进程同时访问的设备。当然，对于每一时刻而言，该类设备仍然只允许一个进程访问。显然，共享设备必须是可寻址的和可随机访问的设备。典型的共享设备是磁盘。对共享设备不仅可获得良好的设备利用率，而且它也是实现文件系统和数据库系统的物质基础。

管程管程 (Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件设备或一群变量。Hansan 为管程所下的定义是： “一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据” 。由上述的定义可知，管程由四部分组成：① 管程的名称；② 局部于管程内部的共享数据结构说明；③ 对该数据结构进行操作的一组过程；④ 对局部于管程内部的共享数据设置初始值的语句。2

管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。

管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：

(1) 模块化。管程是一个基本程序单位，可以单独编译。

(2) 抽象数据类型。管程中不仅有数据，而且有对数据的操作。

(3) 信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的， 供管程外的进程调用， 而管程中的数据结构以及过程(函数)的具体实现外部不可见。