操作系统基础知识专业课（计算机操作系统

操作系统知识点

2018-07-23  本文已影响387人  yunpiao

1. 基础知识

1.1、 基本概念、 功能

1.2、操作系统的发展与分类

1、手工操作阶段
2、脱机输入输出阶段
3、批处理阶段
批处理技术是指计算机系统对一批作业自动进行处理的一种技术。批处理阶段的特点是：用户不用与计算机直接打交道，而是通过专门的操作员来完成作业的输入输出。随着外围设备的迅速发展，后来又出现了脱机批处理系统，即主机直接与磁盘通信。
（1） 单道批处理系统
主要特点：自动性、顺序性、单道性。
（2） 多道批处理系统
多道程序设计技术是指在计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下相互交替的运行。其特征是：多道，宏观上并行，微观上串行。
4、分时操作系统
所谓分时系统就是把处理器的运行时间分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用。若某个作业再分配给他的时间片内不能完成其计算，则改作业暂时停止运行，把处理器让给其他作业使用，等待下一轮再继续运行，由于计算机速度很快，作业运行轮转的很快，给每个用户的感觉好像是自己独占一台计算机。
分时操作系统十多个用户通过终端同事共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而不互相干扰。所以，实现分时系统最关键的问题，是如何使用户能与自己的作业进行交互，即当用户在自己的中断上输入命令时，系统应能及时接收并及时处理该命令，再将结果返回用户。分时系统也是支持多道程序设计的系统，但它不同于多道批处理系统。多道批处理是实现作业自动控制而无需人工干预的系统，而分时系统是实现人机交互的系统，这使得分时系统具有与批处理系统不同的特征，其主要特征如下：
同时性，交互性，独立性，及时性。
5、实时操作系统
实时系统的主要特点是：实时性和可靠性。
6、网络操作系统和分布式计算机系统
7、个人计算机操作系统

1.3、 操作系统运行机制

计算机系统中，通常CPU执行两种不同性质的程序，一种是操作系统内核程序；另一种是用户自编程序或系统外城的应用程序。对操作系统而言，这两种程序的作用不同，前者是后者的管理者和控制者，因此“管理程序”要执行一些特权指令，而“被管理程序”出于安全性考虑，不能执行这些指令。所谓特权指令，是指计算集中不允许用户直接使用的指令，如IO指令、置中断指令。
操作系统在具体实现上划分了用户态和核心态，以严格区分两种类程序。
一些与硬件关联交紧密的模块，诸如时钟管理程序、中断处理程序、设备驱动程序等处于最底层。其次是运行频率较高的程序，诸如金城关里、存储器管理和设备管理等。这两部分内容构成了操作系统的内核。这部分内容的指令操作工作在核心态。
内核是计算机上配置的最底层软件，是计算机功能的延伸。不同系统对内核的定义稍有区别，大多数操作系统内核包括四个方面的内容。

2. 进程管理

  1. 高级调度：(High-Level Scheduling)又称为作业调度，它决定把后备作业调入内存运行；
  2. 中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。
  3. 低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；
  1. 非抢占式
    分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程调度进程调度某事件而阻塞时，才把处理机分配给另一个进程。
  2. 抢占式
    操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的调度方式。

CPU任务可以分为交互式任务和批处理任务，调度最终的目标是合理的使用CPU，使得交互式任务的响应时间尽可能短，用户不至于感到延迟，同时使得批处理任务的周转时间尽可能短，减少用户等待的时间。

semaphore fullBuffers = 0; /*仓库中已填满的货架个数*/
semaphore emptyBuffers = BUFFER_SIZE;/*仓库货架空闲个数*/
semaphore mutex = 1; /*生产-消费互斥信号*/
Producer() 
{ 
while(True)
{  
/*生产产品item*/
emptyBuffers.P(); 
mutex.P(); 
/*item存入仓库buffer*/
mutex.V();
fullBuffers.V();
}
}
Consumer() 
{
while(True)
{
fullBuffers.P(); 
mutex.P();    
/*从仓库buffer中取产品item*/
mutex.V();
emptyBuffers.V();
/*消费产品item*/
}
}
使用pthread实现的生产者－消费者模型：
#include <pthread.h>#include <stdio.h>
#include <stdlib.h>#define BUFFER_SIZE 10
static int buffer[BUFFER_SIZE] = { 0 };static int count = 0;
pthread_t consumer, producer;pthread_cond_t cond_producer, cond_consumer;pthread_mutex_t mutex;
void* consume(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == 0){
printf("empty buffer, wait producer\n");
pthread_cond_wait(&cond_consumer, &mutex); 
}
count--;
printf("consume a item\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_producer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
void* produce(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == BUFFER_SIZE){
printf("full buffer, wait consumer\n");
pthread_cond_wait(&cond_producer, &mutex);
}
count++;
printf("produce a item.\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_consumer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_consumer, NULL);
pthread_cond_init(&cond_producer, NULL);
int err = pthread_create(&consumer, NULL, consume, (void*)NULL);
if(err != 0){
printf("consumer thread created failed\n");
exit(1);
}
err = pthread_create(&producer, NULL, produce, (void*)NULL);
if(err != 0){
printf("producer thread created failed\n");
exit(1);
}
pthread_join(producer, NULL);
pthread_join(consumer, NULL);  
//sleep(1000);
pthread_cond_destroy(&cond_consumer);
pthread_cond_destroy(&cond_producer);
pthread_mutex_destroy(&mutex);
return 0;
}
  1. 本地进程间通信的方式有很多，可以总结为下面四类：
  2. 消息传递（管道、FIFO、消息队列）
  3. 同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
  4. 共享内存（匿名的和具名的）
  5. 远程过程调用（Solaris门和Sun RPC）
  6. 文件

2.2 疑难问题

3. 内存管理

程序可执行文件的结构

一个程序的可执行文件在内存中的结果，从大的角度可以分为两个部分：

只读部分

.text只读部分包括程序代码

.rodata程序中的常量

可读写部分（也就是变量）

.data： 初始化了的全局变量和静态变量

.bss： 即 Block Started by Symbol， 未初始化的全局变量和静态变量

heap： 堆，使用 malloc, realloc, 和 free 函数控制的变量，堆在所有的线程，共享库，和动态加载的模块中被共享使用

stack： 栈，函数调用时使用栈来保存函数现场，自动变量（即生命周期限制在某个 scope 的变量）也存放在栈中。

这两个概念都是很常见的概念，又经常在一起使用，很容易造成混淆。

全局变量：在一个代码文件当中，一个变量要么定义在函数中，要么定义在在函数外面。当定义在函数外面时，这个变量就有了全局作用域，成为了全局变量。全局变量不光意味着这个变量可以在整个文件中使用，也意味着这个变量可以在其他文件中使用（这种叫做 external linkage）。当有如下两个文件时；

a.c
#include <stdio.h>
int a;
int compute(void);
int main(){
    a = 1;
    printf("%d %d\n", a, compute());
    return 0;
}
b.c
int a;
int compute(void){
    a = 0;
    return a;
}

在 Link 过程中会产生重复定义错误，因为有两个全局的 a 变量，Linker 不知道应该使用哪一个。为了避免这种情况，就需要引入 static。

静态变量： 指使用 static 关键字修饰的变量，static 关键字对变量的作用域进行了限制，具体的限制如下：

<u>在函数外定义：全局变量，但是只在当前文件中可见（叫做 internal linkage）</u>

<u>在函数内定义：全局变量，但是只在此函数内可见（同时，在多次函数调用中，变量的值不会丢失）</u>

<u>（C++）在类中定义：全局变量，但是只在此类中可见</u>

对于全局变量来说，为了避免上面提到的重复定义错误，我们可以在一个文件中使用 static，另一个不使用。这样使用 static 的就会使用自己的 a 变量，而没有用 static 的会使用全局的 a 变量。当然，最好两个都使用 static，避免更多可能的命名冲突。

注意：'静态'这个中文翻译实在是有些莫名其妙，给人的感觉像是不可改变的，而实际上 static 跟不可改变没有关系，不可改变的变量使用 const 关键字修饰，注意不要混淆。

Bonus 部分 —— extern： extern 是 C 语言中另一个关键字，用来指示变量或函数的定义在别的文件中，使用 extern 可以在多个源文件中共享某个变量，例如这里的例子。 extern 跟 static 在含义上是“水火不容”的，一个表示不能在别的地方用，一个表示要去别的地方找。如果同时使用的话，有两种情况，一种是先使用 static，后使用 extern ，即：

static int m;extern int m;

这种情况，后面的 m 实际上就是前面的 m 。如果反过来：

extern int m;static int m;

这种情况的行为是未定义的，编译器也会给出警告。

这里我们提到的几个区，是指程序在内存中的存在形式。和程序在硬盘上存储的格式不是完全对应的。程序在硬盘上存储的格式更加复杂，而且是和操作系统有关的，具体可以参考这里。一个比较明显的例子可以帮你区分这个差别：之前我们提到过未定义的全局变量存储在 .bss 区，这个区域不会占用可执行文件的空间（一般只存储这个区域的长度），但是却会占用内存空间。这些变量没有定义，因此可执行文件中不需要存储（也不知道）它们的值，在程序启动过程中，它们的值会被初始化成 0 ，存储在内存中。

栈

栈是用于存放本地变量，内部临时变量以及有关上下文的内存区域。程序在调用函数时，操作系统会自动通过压栈和弹栈完成保存函数现场等操作，不需要程序员手动干预。

栈是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的。能从栈获得的空间较小。如果申请的空间超过栈的剩余空间时，例如递归深度过深，将提示stackoverflow。

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。

堆

堆是用于存放除了栈里的东西之外所有其他东西的内存区域，当使用malloc和free时就是在操作堆中的内存。对于堆来说，释放工作由程序员控制，容易产生memory leak。

堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，永远都不可能有一个内存块从栈中间弹出。

堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。

计算机底层并没有对堆的支持，堆则是C/C++函数库提供的，同时由于上面提到的碎片问题，都会导致堆的效率比栈要低。

3.1 内存分配

内存管理基础

3.1.2、虚拟内存的基本概念

由上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存空间。
要真正理解虚拟内存技术的思想，首先必须了解计算机中著名的局部性原理。著名的Bill Joy说过：“在研究所的时候， 我经常开玩笑的说高速缓存是计算机科学中唯一重要的思想。事实上，高速缓存技术确实极大地影响了计算机系统的设计。”快表、页高速缓存以及虚拟内存技术从广义上讲，都是属于高速缓存技术。这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，也适用于数据结构。

局部性原理表现在以下两个方面：
1）时间局部性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
2）空间局部性。一旦程序访问量某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

时间局部性是通过将进来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了“内存-外存”的两级存储器的结构，利用局部性原理实现高速缓存。
基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其与部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样，计算机好像为用户提供了一个比实际内存大的多的存储器，成为虚拟存储器。
之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后，给用户的感觉是好像存在一个比实际物理内存大得多的存储器。虚拟存储器有以下三个主要特征：
1）多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
2）对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
3）虚拟性 ，是指从逻辑上扩充内存的容量，是用户所看到的内存容量，远大于实际的内存容量。
虚拟内存中，允许将一个作业分多次调入内存。采用连续分配方式时，会是相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
虚拟内存的实现有以下三种方式：
l 请求分页存储管理
l 请求分段存储管理
l 请求段页式存储管理
不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：
l 一定容量的内存和外存。
l 页表机制或段表机制，作为主要的数据结构。
l 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
l 地址变换机构，逻辑地址到物理地址的变换。

3.2、连续分配管理方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。
内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的除系统外的内存空间。这种方式无需进行内存保护。
这种方式的优点是简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。

1）首次适应算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
2）最佳适应算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。
3）最坏适应算法：有称最大适应算法，空闲分区以容量递减次序链接。找到第一个能满足要求的空闲分区，也就是挑选最大的分区。
4）临近适应算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从此查找结束的位置开始继续查找。

在这几种方法中，首次适应算法不仅是最简单的，而且通常是最好和最快的。在UNIX系统的最初版本中，就是使用首次适应算法为进程分配内存空间，其中使用数组的数据结构（而非链表）来实现。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区。
临近适应算法试图解决这一问题，但实际上，它常常会导致在内存的末尾分配空间，分裂成小碎片。它通常比首次适应算法的结果要差。
最佳适应算法虽然称为最佳，但是性能通常很差，因为每次最佳的分配会留下最小的内存块，它会产生最多的碎片。
最坏适应算法与最佳适应算法相反，选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大的内存块，因此性能非常差。
以上内存分区管理方法有一共同特点，即用户进程在主存中都是连续存放的。

3.3、非连续分配管理方式

非连续分配方式允许一个程序分散的装入不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。
分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理和请求分页存储管理方式。
固定分区会产生内部碎片，动态分区会产生外部碎片，两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引出了分页思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

3.3.1、 分页存储

  1. 地址变换机构自动将有效地址分为页号和页内偏移量两部分，再用页号去检索页表。在执行检索之前，先将页号与页表长度比较，如果页号大于或等于页表长度，则表示地址越界并中断。
  2. 若未越界，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号。
  3. 与此同时，在将有效地址中的页内偏移量送入物理地址寄存器的块内地址字段中。
    以上整个地址变换过程均是由硬件自动完成的。
    下面讨论分页管理方式存在的两个主要问题：1每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低；2每个进程引入了页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。

3.3.2 分段存储

系统按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序、两个字程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段，每段从0开始编址，并采用一段连续的地址空间（段内要求连续，段间不要求连续），其逻辑地址由两部分组成：段号与段内偏移量，分别记为S、W。
段号为16位，段内偏移量为16位，则一个作业最多可有2*16=65536个段，最大段长64KB。
在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的；但在段式系统中，段号和段内偏移量必须由用户显示提供，在高级程序设计语言中，这个工作由编译程序完成。

页式存储管理能有效的提高内存利用率，而分段存储管理能反应程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

3.3.3 各种地址的定义

虚拟内存

· 请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入

页面置换算法

内存抖动现象：页面的频繁更换，导致整个系统效率急剧下降，这个现象称为内存抖动（或颠簸）。抖动一般是内存分配算法不好，内存太小引或者程序的算法不佳引起的。

Belady现象：对有的页面置换算法，页错误率可能会随着分配帧数增加而增加。

FIFO会产生Belady异常。

栈式算法无Belady异常，LRU，LFU（最不经常使用），OPT都属于栈式算法


image.png

4. 文件管理

4.4、本章疑难点
1、磁盘结构
引导控制块（Boot Control Block）包括系统从该分区引导操作系统所需要的信息。如果磁盘没有操作系统，那么这块内容为空。它通常为分区的第一块。UFS称之为引导块；NTFS称之为分区引导扇区。
分区控制块包括分区详细信息，如分区的块数、块的大小、空闲块的数量和指针、空闲FCB的数量和指针等。UFS称之为超级块；而NTFS称之为主控文件表。
2、内存结构
内存分区表包含所有安装分区的信息。
内存目录结构用来保存近来访问过的目录信息。对安装分区的目录，可以包括一个指向分区表的指针。
系统范围的打开文件表，包括每个打开文件的FCB复制和其他信息。
单个进程的打开文件表，包括一个指向系统范围内已打开文件表中适合条目和其他信息的指针。
3、文件系统实现概述
为了创建一个文件，应用程序调用逻辑文件系统。逻辑文件系统知道目录结构形势，它将分配一个新的FCB给文件，把相应目录读入内存，用新的文件名更新该目录和FCB，并将结果写回到磁盘。
一旦文件被创建，它就能用于IO，不过首先要打开文件。调用open将文件名传给文件系统，文件系统根据给定文件名搜索目录结构。部分目录结构通常缓存在内存中以加快目录操作。找到文件后，其FCB复制到系统范围的打开文件表。该表不但存储FCB，也有打开该文件的进程数量的条目。
然后，单个进程的打开文件表中会增加一个条目，并通过指针将系统范围的打开文件表的条目同其他域（文件当前位置的指针和文件打开模式等）相连。调用open返回的是一个指向单个进程的打开文件表中合适条目的指针。所以文件操作都是通过该指针进行。
文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不再使用文件名了。对于访问打开文件表的索引，UNIX称之为文件描述符；而Windows称之为文件句柄。因此，只要文件没有被关闭，所有文件操作通过打开文件表来进行。
当一个进程关闭文件，就删除一个相应的单个进程打开文件表的条目，系统范围内打开文件表的打开数也会递减。当打开文件的所有用户都关闭了一个文件时，更新的文件信息会复制到磁盘的目录结构中，系统范围打开的文件表的条目也将删除。
在实际中，系统调用open会首先搜索系统范围的打开文件表以确定某文件是否已被其他进程使用。如果是，就在单个进程的打开文件表中创建一项，并指向现有系统范围的打开文件表的相应条目。该算法在文件已打开时，能节省大量开销。
4、混合索引分配的实现
混合索引分配已在UNIX系统中采用。在UNIX System V的索引结点中，共设置了13个地址项，即iaddr（0）~iaddr（12）。在BSD UNIX的索引结点中，共设置了13个地址项，它们把所有的地址项分成两类，即直接地址和间接地址。
（1）直接地址
为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr（0）~iaddr（9）来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于40KB时，便可直接从索引节点中读出该文件的全部盘块号。
（2）一次间接地址
对于大、中型文件，只采用直接地址并不现实。可再利用索引节点中的地址项iaddr（10）来提供一次间接地址。这种方式的实质就是一级索引分配方式。一次间址块就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1024个盘块号，因而允许文件长达4MB。
（3）多次间接地址
当文件长度大于4MB+40KB时，系统还须采用二次间址分配方式。这是用地址项iaddr（11）提供二次间接地址。该方式的实质是二级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4GB。同理，地址项iaddr（12）作为三次间接地址，其所允许的文件最大长度可达4TB。

5. 输入输出系统

5.1、IO管理概述

5.2、IO核心子系统

5.3、本章疑难点

1）分配设备。首先根据IO请求中的物理设备名查找系统设备表（SDT），从中找出该设备的DCT，再根据DCT中的设备状态字段，可知该设备是否正忙。若忙，便将请求IO进程的PCB挂在设备队列上；空闲则按照一定算法计算设备分配的安全性，安全则将设备分配给请求进程，否则仍将其PCB挂到设备队列。
2）分配控制器。系统把设备分配给请求IO的进程后，再到其DCT中找出与该设备连接的控制器的COCT，从COCT中的状态字段中可知该控制器是否忙碌。若忙，便将请求IO进程的PCB挂在该控制器的等待队列上；空闲便将控制器分配给进程。
3）分配通道。在该COCT中又可找到与该控制器连接的通道CHCT，再根据CHCT内的状态信息，可知该通道是否忙碌。若忙，便将请求IO的进程挂在该通道的等待队列上；空闲便将该通道分配给进程。只有在上述三者都分配成功时，这次设备分配才算成功。然后，便可启动该IO设备进行数据传送。
为使独占设备的分配具有更强的灵活性，提高分配的成功率，还可以从以下两方面对基本的设备分配程序加以改进：
1）增加设备的独立性。进程使用逻辑设备名请求IO。这样，系统首先从SDT中找出第一个该类设备的DCT。若该设备忙，又查找出第二个该设备的DCT。仅当所有该类设备都忙时，才把进程挂在该类设备的等待队列上；只要有一个该类设备可用，系统便进一步计算分配该设备的安全性。
2）考虑多通路情况。为防止IO系统的“瓶颈”现象，通常采用多通路的IO系统结构。此时对控制器和通道的分配同样要经过几次反复，即若设备（控制器）所连接的第一个控制器（通道）忙时，应查看其所连接的第二个控制器（通道），仅当所有的控制器（通道）都忙时，此次的控制器（通道）分配才算失败，才把进程挂在控制器（通道）的等待队列上。而只要有一个控制器（通道）可用，系统便可将它分配给进程。

6. 常见考点

6.1 进程的平均周转时间

有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？

结果：详细如图 （7+14+20+24）/4=16.25

进程的堆栈、数据区、代码区在内存的映射

栈 存放局部变量 传递参数 存储函数的返回地址
堆 malloc 和new进行分配时 所得的地址就在堆中 程序员负责申请和销毁
数据区 全局、静态、常量是分配到数据区中的 数据区包括bbs 未初始化数据区 初始化数据区
堆向高内存地址生长 栈向高内存地址生长 两者相向而生

C语言中堆和栈的区别

一.前言：

C语言程序经过编译连接后形成编译、连接后形成的二进制映像文件由栈，堆，数据段（由三部分部分组成：只读数据段，已经初始化读写数据段，未初始化数据段即BBS）和代码段(文本常量区)组成，如下图所示：

image.png

1.栈区(stack):由编译器自动分配释放，存放函数的参数值，局部变量等值。其操作方式类似于数据结构中的栈。

2.堆区(heap):一般由程序员分配释放，若程序员不释放，则可能会引起内存泄漏。注堆和数据结构中的堆栈不一样，其类是与链表。

3.程序代码区：存放函数体的二进制代码。

4.数据段：由三部分组成：

1>只读数据段：

只读数据段是程序使用的一些不会被更改的数据，使用这些数据的方式类似查表式的操作，由于这些变量不需要更改，因此只需要放置在只读存储器中即可。一般是const修饰的变量以及程序中使用的文字常量一般会存放在只读数据段中。

2>已初始化的读写数据段：

已初始化数据是在程序中声明，并且具有初值的变量，这些变量需要占用存储器的空间，在程序执行时它们需要位于可读写的内存区域内，并且有初值，以供程序运行时读写。在程序中一般为已经初始化的全局变量，已经初始化的静态局部变量(static修饰的已经初始化的变量)

3>未初始化段（BSS）：

未初始化数据是在程序中声明，但是没有初始化的变量，这些变量在程序运行之前不需要占用存储器的空间。与读写数据段类似，它也属于静态数据区。但是该段中数据没有经过初始化。未初始化数据段只有在运行的初始化阶段才会产生，因此它的大小不会影响目标文件的大小。在程序中一般是没有初始化的全局变量和没有初始化的静态局部变量。

二.堆和栈的区别

1.申请方式

(1)栈（satck）:由系统自动分配。例如，声明在函数中一个局部变量int b;系统自动在栈中为b开辟空间。

(2)堆（heap）:需程序员自己申请（调用malloc,realloc,calloc）,并指明大小，并由程序员进行释放。容易产生memory leak.

eg:char p;

  p = (char *)malloc(sizeof(char));

但是，p本身是在栈中。

2.申请大小的限制

（1）栈：在windows下栈是向底地址扩展的数据结构，是一块连续的内存区域(它的生长方向与内存的生长方向相反)。栈的大小是固定的。如果申请的空间超过栈的剩余空间时，将提示overflow。

（2）堆：堆是高地址扩展的数据结构（它的生长方向与内存的生长方向相同），是不连续的内存区域。这是由于系统使用链表来存储空闲内存地址的，自然是不连续的，而链表的遍历方向是由底地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。

3.系统响应：

（1）栈：只要栈的空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

（2）堆：首先应该知道操作系统有一个记录空闲内存地址的链表，但系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的free语句才能正确的释放本内存空间。另外，找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。

说明：对于堆来讲，对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，

4.申请效率

（1）栈由系统自动分配，速度快。但程序员是无法控制的

（2）堆是由malloc分配的内存，一般速度比较慢，而且容易产生碎片，不过用起来最方便。

5.堆和栈中的存储内容

（1）栈：在函数调用时，第一个进栈的主函数中后的下一条语句的地址，然后是函数的各个参数，参数是从右往左入栈的，然后是函数中的局部变量。注：静态变量是不入栈的。

当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续执行。

（2）堆：一般是在堆的头部用一个字节存放堆的大小。

6.存取效率

（1）堆：char *s1=”hellow tigerjibo”;是在编译是就确定的

（2）栈：char s1[]=”hellow tigerjibo”;是在运行时赋值的；用数组比用指针速度更快一些，指针在底层汇编中需要用edx寄存器中转一下，而数组在栈上读取。

补充：

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。

7.分配方式：

（1）堆都是动态分配的，没有静态分配的堆。

（2）栈有两种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的。它的动态分配是由编译器进行释放，无需手工实现。


image.png 
//main.cpp 
int a = 0; 全局初始化区 
char *p1; 全局未初始化区 
int main() 
{ 
int b; 栈 
char s[] = "abc"; 栈 
char *p2; 栈 
char *p3 = "123456"; 123456在常量区，p3在栈上。 
static int c =0； 全局（静态）初始化区 
p1 = (char *)malloc(10); 
p2 = (char *)malloc(20); 
分配得来得10和20字节的区域就在堆区。 
strcpy(p1, "123456"); 123456放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。 
}

死锁

所谓死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

（1）因为系统资源不足。（2）进程运行推进的顺序不合适。（3）资源分配不当等。如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。（1）互斥条件：一个资源每次只能被一个进程使用。（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

进程状态

image.png
上一篇下一篇

猜你喜欢

热点阅读