Posts 操作系统与Linux简介
Post
Cancel

操作系统与Linux简介

操作系统的基本原理

操作体系概论

1.1 操作系统的定义

应用程序->实用程序->操作系统->硬件

单向调用的关系

1.2 操作系统的形成与发展

顺序处理、简单的批处理

多道批处理系统:以主存为中心,与CPU相连,用通道与I/O设备相连,存放多个作业,在主存中同时存放多个作业,根本目的是提高PCU的利用率,充分发挥并行性。通过资源利用率(实际使用时间/给定时间)、吞吐量(单位时间内系统处理的信息量)、周转时间(作业进入系统到退出系统所经历的时间)

批处理系统使用多道程序技术后,存在问题:不能直接控制作业运行、作业的周转时间长,提出了分时系统

分时系统:将CPU单位时间划分为多个时间片,分时系统具有的特点是:同时性(若干个终端同时使用计算机)、独立性(各个用户独立占有一台终端)、交互性(与用户交互)、及时性(用户的请求能够在短时间得到响应)

实时系统:实时性(响应时间要求严格)、可靠性(要求软硬件高可靠)、确定性(系统内核保证系统尽可能快响应外部事件)

1.3 操作系统的功能、服务和特性

操作系统的功能:处理机管理、存储器管理、设备管理、文件管理

操作系统提供的服务:用户接口、执行程序、I/O操作、文件操作、通信服务、资源分配、错误检测等

操作系统的特性:并发性(同时处在活动状态的相互独立的程序竞争系统各种资源)、共享性(分配调度资源)、虚拟性(把物理实体资源变为逻辑上的对应物)、异步性(进程之间相互制约关系)

1.4 操作系统的进一步发展

个人操作系统-》多处理机操作系统-〉网络操作系统-》分布式操作系统

1.5 用户与操作系统的接口

两种接口:一种是提供给操作计算机的用户的操作接口、另一种是提供给编程人员使用的低级接口

用户与操作系统的操作接口:1. 命令解释程序(以命令行的形式,通过命令解释程序解释执行,如shell;命令解释程序有两种实现方法:(1)本身包含了执行这些命令的代码;(2)操作系统核心实现命令要求的功能)。2. 图形用户接口。 3. 作业运行的控制命令(批处理系统和分时系统):解释执行的脱机控制命令(负责的是命令解释程序),或者是交互式的作业控制命令

系统调用接口:处理机在处理机状态字中增加一个执行方式位,区分用户态和核心态,处理机的执行状态决定了所能进行的操作(1. 执行指令的特权性 2. 存储器访问的特权性)

系统调用的功能:进程控制、文件管理、设备管理等

用户程序执行到途中的时候,遇到系统调用的时候,切换到核心态,然后操作系统内核执行核心态代码,进行系统调用命令程序,结束后再返回到用户态。

导致切换的两个原因:中断、异常

系统调用的执行过程:1. 通过中断、异常使系统切换到核心态,CPU进入核心态,按照特权的方式运行。 2. 将程序计数器和处理机的当前状态存入任务的堆栈中。3. 将系统调用号存入核心堆栈中。4. 执行汇编代码来保存通用寄存器中的内容。5. 调用相应的操作系统例程来完成系统调用。6. 返回到用户方式

1.6 操作系统的运行环境

中断:是一些外部设备向CPU放出的一个硬件信号,如外部设备的I/O完成中断、时钟中断等,和当前执行的指令无关,是异步发生的,而且是可以被屏蔽的。当中断产生的时候,CPU响应中断,转入对应的中断处理程序执行

异常:也叫做陷入,是执行程序自己产生的,是同步发生的,而且是不可屏蔽的。产生条件是:1. 程序错误如程序非法操作码、地址越界、除数为0,存储器管理中的页面失效等;2. 由于程序请求操作系统服务和请求系统资源等使用系统调用。

除了内核少部分代码再核心态运行以外,大部分操作系统功能以独立系统进程运行在用户态,这就是微内核操作系统

1.7 操作系统的设计规范与结构设计

进程管理

2.1 进程的引入和概念

程序的并行执行:(1)失去了程序的封闭性和可再现性(资源是共享的而非独占)(2)并行执行的程序之间产生了相互制约的关系(3)程序与CPU执行的活动之间不再一一对应。

进程:(1)是程序的一次执行过程;(2)是程序在一个数据集合上顺序执行时发生的活动。它是系统进行资源分配和调度的独立单位。

进程和程序:1. 进程是程序的一次执行,具有动态性;2. 晋城市系统进行资源分配的一个独立单位,具有独立性,而程序则不是,资源分配是以进程为单位的,而不是以程序为单位的;3. 一个进程可以与其他进程并发执行,具有并发性;4. 进程具有结构性。为描述进程的运行变化过程,系统为每一个进程都要建立一个结构——进程控制块。从结构上看,进程是由程序、数据和进程控制块三部分组成的。

线程就是处理机调度的基本对象,就是减少程序并发执行时系统付出的时间空间开销,使得系统的运行更加有效。而进程是只作为除CPU外的系统资源的分配对象。进程是指完成一个作业,而线程就是完成作业的许多可能的字任务,线程是进程中的一个可执行实体,是被操作系统调度的一个独立单位,一个进程可以有多个线程的,多线程共享进程的所有资源。

2.2 进程的描述

进程控制块PCB(也叫进程描述符PD):描述进程的运行变化情况,操作系统为每个进程定义的数据结构。

PCB包括:1.进程标识数:进程的唯一标识,一般为整数;2. 进程的状态以及调度和存储器管理信息(进程状态、进程优先级、程序在主存的入口地址、在外存的地址、信息允许的存取保护方式);3. 进程使用的资源信息(分配给进程的I/O设备、当前进程打开的文件等);4. CPU现场保护区(进程挂起的时候就放在这里,等待下次调度运行的时候恢复现场继续运行,通常CPU的现场信息包括:程序计数器、程序状态字PSW、通用寄存器、堆栈指针等);5. 记账信息:使用的CPU的时间量、账号等;6. 进程之间的家族关系:记录本进程的父进程是谁、子进程是谁;7. 进程的链接指针:用于将相同状态的进程链接在一起

进程的状态:1. 创建态、终止态、就绪态、运行态、等待态;2. 就绪态的通过进程调度变为运行态;3. 运行态的进程主动改变,比如启动了I/O设备,使得自己变成了等待态,等待I/O完成;4. 等待态由于外界事件引起编程就绪态,比如I/O完成时候的请求中断;5. 处于运行态的进程被剥夺CPU时引起的,比如时间片用完了,或者优先级调度的时候有更高优先级的进程变为就绪态,那么当前进程就被迫放弃CPU,使自己变成就绪态,之后转处理机调度。

进程的组织:不同的进程有着不同的状态,而系统需要对每个进程进行统一管理,因此出现了进程的组织管理问题

(1)线性表:将所有进程的PCB组成一个数组,系统通过数组下标访问每一个PCB。优点是简单、节省存储空间,缺点是系统查找开销大,早期UNIX系统采用。

(2)链接表:处于同一状态的进程PCB按照一定方式链接成一个队列,每一个队列有一个专用队列指针指出该队列中第一个PCB的位置。形成了就绪队列、等待队列。各种进程可以按照某种策略排成多个队列,比如等待磁盘I/O队列、等待磁带I/O队列等。

在单CPU中任何时刻只有一个进程处于运行状态,因此系统专门设置一个指针指向当前运行进程的PCB。UNIX系统中就有一个CURPRO指针,指向当前运行的进程的PCB

2.3 进程的控制

进程控制是由不允许被中断的程序,或叫其执行过程不可分割的原语实现的。

  1. 创建原语:扫描系统PCB结合表,找到空闲的PCB,并获得该PCB的内部名称作为标识符。若进程的程序和数据等不在主存,也要去分配主存,并调入主存,然后把调用者提供的参数:进程名、优先级、实体所在主存的起始位置等填入PCB结构,并将进程状态设置为就绪状态,插入就绪队列中。

  2. 撤销原语:(进程已经完成任务或者由于故障无法继续运行,需要让进程控制块从系统中消失)在PCB集合中找到所要撤销的进程,若找到,检查该进程是否有子进程,若有,则递归进去,将子进程所占用资回收给系统,并撤销子进程的控制块。之后把进程的资源还给系统,撤销PCB。
  3. 阻塞原语:处于运行态的进程中断CPU,将其运行现场保存在PCB中,将状态设置为阻塞,然后插入对应事件的等待队列中,最后转处理机调度。
  4. 唤醒原语:情况一:等待I/O完成时,硬件提出中断请求,CPU响应中断,暂停当前进程的执行,进行中断处理,检查队列中的等待着,将其唤醒,放入就绪态。结束中断处理,要么返回被中断进程继续执行,要么转处理机调度,重新选择进程投入运行;情况二:事件是等待某进程发一个信息,当信息发送给该等待进程的时候,由发送进程把该等待者唤醒,并设置为就绪态,插入就绪队列。
  5. 挂起原语:如果是分时系统中,假设是进程时间片用完,从主存换到磁盘中的时候,进程就处于静止就绪状态;假设是阻塞进程从主存调出到磁盘,它由活动阻塞的变为禁止阻塞。这就是挂起。
  6. 解挂原语:如上对应关系

2.4 处理机的调度

处理机调度的级别(1)高级调度,也叫作业调度,一般是多道批处理系统而非分时系统,通常将IO量大的和CPU量大的作业结合在一起进行调度,控制作业进入内存的个数;(2)低级调度,也叫进程调度,进程调度是比较频繁的,控制CPU的利用;(3)交换调度,充分利用系统资源,将处于主存就绪或主存阻塞的进程换到外存交换区,将外存中就绪状态具备运行条件的进程换到主存。

进程调度:也叫处理机调度,按照某种算法把CPU动态地分配给某一就绪进程的过程,通过处理机调度程序来完成,主要功能描述如下:(1)管理系统中各个进程的的执行状况,通过PCB变化掌握的;(2)选择进程去占有CPU;(3)进行进程上下文的切换,进程的上下文是指操作系统为运行进程设置的对应的运行环境和进程的物理实体,由用户级(进程中的程序和数据)、寄存器级(CPU现场信息)、系统级(进程控制块、进程运行时的系统环境,进程状态、存储器管理)的上下文组成。

进程调度的方式:非抢先方式(只有到不能执行的时候才会调度,对于紧急任务及时处理的情况无法做到)、抢先方式(更多用在分时系统、实时系统、多任务操作系统)

进程调度的时机:1. 现行进程执行出现错误中止运行;2. 进程提出IO请求;3. 分时系统时间片用完;4. 优先级调度下,更高优先级的进程就绪了;5. 进程执行了阻塞原语、唤醒原语也可能引起。

处理机调度算法:(1)FCFS,先来先服务;(2)最短作业的进程优先调度:长进程会饿死;(3)响应比高优先:响应比=1+(作业等待时间/作业估计运行时间);(4)优先级调度法:静态优先级创建时确定;动态优先级可根据占用CPU时间长短、等待时间等进行调配;(5)轮转法:分时系统中,轮流调度;实现的时候利用一个定时时钟,发出中断。(6)多级反馈队列轮转法:有很多个队列,几个队列采用前后台运行,前台队列采用轮转法调度,后台队列采用先来先服务法调度。前台进程优先级高于后台进程,前台各种队列优先级也不一样,高优先级队列时间片短,低优先级队列时间片长。(比如刚创建的进程、因请求IO未用完时间片的进程排在最高优先级队列)系统调度时候,按照优先级高去调度,当队列为空才调度次优先级的,不论什么时候,只要高优先级队列有进程进入,立刻转处理机调度,及时调度高优先级队列的进程。

对于实时系统有下面的算法:

时钟驱动法:硬实时系统的任务所有参数固定且可知,常用的选择就是以规则的间隔时间进行调度决策

加权轮转法:与轮转法不同,进程给予不同的权值,中途可调整

2.5 线程的引入

线程就是处理机调度的基本对象,就是减少程序并发执行时系统付出的时间空间开销,使得系统的运行更加有效。而进程是只作为除CPU外的系统资源的分配对象。进程是指完成一个作业,而线程就是完成作业的许多可能的字任务,线程是进程中的一个可执行实体,是被操作系统调度的一个独立单位,一个进程可以有多个线程的,多线程共享进程的所有资源。

线程控制块:(1)唯一的标识符;(2)有表示处理机状态和运行现场的一组寄存器,CPU现场信息;(3)两个堆栈,用于用户态和核心态调用时的参数传递;(4)又一个独立的程序计数器,或叫做一个私有的存储区;(5)关联的进程和线程指针。

image-20210406003700644

系统对线程的支持:

(1)用户级线程:指有关管理线程的工作都由用户程序通过调用用户态运行的线程库来完成,系统内核并不知道线程的存在。应用程序根据需要,在同一个进程中创建线程,自己设计带哦度算法调度线程运行,由于内核是单线程,所以任何一个用户级线程的阻塞,都会导致进程的阻塞。用户态的多线程对应核心态的一个线程或进程。

用同步的方式写异步的代码,让读代码写代码的人皆大欢喜。

开销小

(2)核心级线程:线程管理工作交给系统内核,用户应用程序通过调用线程的应用程序编程接口API来管理线程。用户态的一个线程对应核心态的一个线程或进程。对创建线程的数量有限制。

(3)两级组合:略

进程并发控制与死锁

3.1 并发进程的特点

(1)资源共享引起的互斥关系(2)协作完成同一任务引起的同步关系(3)进程之间的前序关系

3.2 进程之间的低级通信

1. 进程互斥

(1) 临界区、临界资源

进程之间互斥是由于共享资源引起的,为了描述这类情况,引入临界资源和临界区的概念。临界资源,就是一次仅仅允许一个进程使用。临界区就是并发进程对N变量必须互斥操作的那段程序段。

并发进程进入临界区需要遵循的准则:1. 互斥使用;2. 让权等待(等待进入临界区的进程,应该释放处理机后阻塞等待);3. 有空让进(临界区外的进程不能阻止其他进程进入临界区);4. 有限等待;

(2) 解决进程之间互斥的硬件实现方法

(1)关中断,即一个进程在临界区执行的时候,关闭所有的中断。但多处理机下面不灵,因为关中断只针对一个CPU。

(2)使用测试和设置硬件指令(test and set):测试和设置是一条不会被中断的机器指令,为了使用测试和设置指令实现进程互斥,要为相应的临界资源设置一个锁位变量w,执行该test and set指令的时候,它测试w的值。如果为0,设置为1,表示进程获得临界资源的使用权,如果w=1,表示资源被占用,此时进程重复执行该指令不断测试w,直到可以获取该临界资源为止。这种方式保证了互斥,但是浪费了大量CPU时间,造成了忙等待。

2. 进程之间同步

进程同步指的是一组共行进程,各自以独立的、不可预知的速度向前推进,在前进过程中彼此之间需要相互协调步伐,才能正确地完成同一项任务。

3. 信号量和P、V操作

用信号量实现互斥

1
2
3
4
5
6
7
8
9
Wait(s){
	s.value--;
	if(s.value<0) {add this process to s.list; block();}
}

Signal(s){
	s.value++;
	if(s.value <= 0){remove a process from s.list; wakeup();}
}

用信号量实现同步

计算和打印进程的例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int s1 = 1, s2 = 0;
// s1表示缓冲区为空的数量,s2表示缓冲区中是否有可供打印的数据
Pcomputer: 
	begin
  compute next number;
	P(s1);
	add number to buffer;
	V(s2);
	end
  
Pprinter:
	begin
  P(s2);
	take next number from buffer;
	V(s1);
	print the numebr;
	end;

4. 利用信号量解决计算机中的经典问题

生产者和消费者的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int mutex = 1; //互斥信号量 
int empty = k;//同步信号量,空缓冲区可用个数
int full = 0;// 同步信号量,装满产品的缓冲区个数
int array[n];
int i = 0, j = 0;//送产品和取产品的指针变量
Item x, y;//要送和取的产品

producer:begin
  produce a producer to x;
	P(empty);
	P(mutex);
	array[i]=x;
	i=(i+1)mod k;
	V(full);
	V(mutex);
end;

consumer:begin
  P(full);
	P(mutex);
	y = array[j];
	j = (j+1)mod k;
	V(empty);
	V(mutex);
end;

不能交换P的顺序

读者和写者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int rmutex;//控制读者互斥修改计数器readcount
int wmutex = 1;//读写进程互斥和写写进程互斥访问共享文件
int readcount = 0;//记录同时读的读着数量

reader:begin
  P(rmutex);
	if(readcount=0)then
    P(wmutex);
	end if;
	readcount=readcount+1;
	V(rmutex);
	......
  P(rmutex);//读完退出
	readcount = readcount-1;
	if(readcount=0)then//最后一个读者释放文件使用权
    V(wmutex);
	......
	end;

writer:begin
  P(wmutex);
	向文件写;
	V(wmutex);
	end;

这是读者优先,只要有一个读者在读,其他读者都可以读,但写者不能有优先去写,可能导致饿死
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
写者优先:
int readcount = 0, writecount = 0;
semaphore mutex1 = 1(mutex 1控制readcount的互斥), mutex2 = 1mutex 2控制writecount互斥), mutex3 = 1;//mutex3控制只允许一个读进程在r上排队,而其他读进程在等待r之前,在信号量mutex3上排队
semaphore w = 1, r = 1;

Reader:
P(mutex 3);
   P(r);
      P(mutex 1);
         readcount++;
         if (readcount == 1 ) 
            P(w);
      V(mutex 1);
    V(r);
V(mutex 3);
      reading is performed
P(mutex 1);
    readcount --;
    if (readcount == 0 )
             V(w);
V(mutex 1);

Writer:
P(mutex 2);
    writecount++;
    if (writecount == 1 )
           P(r);
V(mutex 2);
P(w);
    writing is performed
V(w);
P(mutex 2);
    writecount --;
    if (writecount == 0)
           V(r);
V(mutex 2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
读写公平
int readcount=0; 
semaphore mutex=1, rw=1 w=1; 
 
读者进程:
        wait (w);
        wait (mutex);
        if (readcount == 0)
	       wait(rw);
    	readcount++;	
    	signal (mutex);
        signal (w);
		
    	   reading is performed
		 
    	wait (mutex);
    	readcount--;
    	if (readcount == 0)
    		signal (rw);
    	signal (mutex);
 
 
写者进程:     
    wait(w);
    wait(rw);
	    
         writing is performed
	    
    signal(rw);
    signal(w);
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
哲学家就餐
方法一:最多只让4个哲学家同时拿左筷子
semaphore chopstick[5]={1,1,1,1,1};
smaphore r = 4;
do:
think();
P(r);
P(chopstick[i]);
P(chopstick[(i+1)mod5]);
eat();
V(chopstick[(i+1)mod5]);
V(chopstick[i]);
think();

方法二:要么两只筷子举起来,要么就都不分配
semaphore chopstick[5]={1,1,1,1,1};
do:
think();
P(chopstick[i], chopstick[(i+1)mod5]);
eat();
V(chopstick[(i+1)mod5], chopstick[i]);
think();

3.3 管程

管程就是将共享变量以及对共享变量进行的所有操作过程集中在一个模块中。定义:管程师关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。

一般三部分:1. 局部于该管程的共享数据的说明;2. 对共享数据执行的一组操作过程说明;3. 局部于该管程的共享数据初始化。

管程中的数据只能由管程过程存取,不允许进程和其他管程存取。其实就是一次封装过程。

3.4 进程的高级通信

低级消息通信速度快,但传送信息量小且效率低,偏向于一个控制过程,而高级通信就需要传送更多的通信了,操作系统隐藏了通信的底层细节,我们更多还是放在逻辑上的处理。

消息缓冲通信

方法一(消息通信):系统建立一个消息缓冲池,其中每个缓冲区可以存放一个消息,每当进程欲发送消息的时候,向系统申请一个缓冲区,将消息存入缓冲区,让后把该缓冲区链接到接收进程的消息队列上。消息队列通常放在进程控制块中。

发送消息:1. 在自己的地址空间形成消息发送区,将消息写入;调用发送原语;发送原语的作用是,在系统缓冲区申请一个消息缓冲区,将消息从发送区传入其中,并将发送者进程名、接收者进程名、消息始址(接收到的消息的消息存放地址)、消息长度填入缓冲区。之后将消息缓冲区挂到接收进程的消息链上。

接收消息:1. 检查消息链上是否有消息,若无,自行决定下一步方式;2.若有,则将消息接收到接收区,若之后消息缓冲区为空,则释放消息缓冲区(消息缓冲区是接收进程PCB的消息队列!)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
消息缓冲区:
  type message buffer = record
  	sender;
		receiver;
		size;
		text;
		next;//指向下一个缓冲区的指针
end;

PCB增加字段:
  mq:消息队列头指针
  mutex:互斥使用消息队列;
	sm:消息队列中消息个数
    
发送原语:
// 发送之前自己内存空间开辟一个发送区a
send(receiver, a)// 接收者和发送区首地址
  {
    getbuf(a.size, i);
    i.sender = a.sender; i.size = a.size; i.text = a.text; i.next = 0;
    getid(PCB set, receiver, j);//获取接受者PCB的标识j
    P(j.mutex);
    Insert(j.mq, i);
    V(j.mutex);
    V(j.sm);
  }

// 同理开辟接收区b
receive(b)//b为接收区的首地址
{
  j=get caller's internal name;
  P(j.sm);
  P(j.mutex);
  Remove(j.mq, i);//从队列取走消息i
  V(j.mutex);
  b.sender = i.sender;
  b.size = i.size;
  b.text = i.text;
}

方法二(信箱通信):每个进程设立一个信箱,每个信箱可以容纳多封信件。信件由系统执行的发送原语将信件投入指定信箱,由接收者自行选择接收信件并处理。发送进程要制定接收进程的名字,接收进程接收消息要指明发送进程的名字。

发送进程发消息不指定接收进程的名字,而是指定中介信箱,一个信箱可以容纳各种信件

Send(A, Msg);//发送一个信件到信箱A

Receive(A, Msg);//接收一个信件Msg从信箱A

有进程发送信件,调用send,若指定信箱未满,则将信件msg送入指定位置,否则发送失败

有进程接收信件,调用receive,若指定信箱中有信则取走;若有发送者在等待,若有则唤醒

管道通信

后面Linux中

共享存储区

后面Linux中

3.5 死锁

计算机资源分为可抢占和不可抢占资源;可抢占:当资源从占用进程被夺走时,对进程不产生破坏性影响如主存CPU,不可抢占资源也叫做临界资源,比如慢速设备、共享变量、队列;

死锁设计的都是不可抢占资源。

死锁:一组进程是死锁的,是指这一组中的每个进程都正在等待这一组中其他的进程所占有的资源时,可能引起的一种错误现象。

死锁产生的条件:1. 互斥条件(资源不可共享);2. 保持和等待条件(进程请求资源而被阻塞等待时,对已经分配给它的资源保持不放);3. 不剥夺条件:进程所获得的资源在未使用完之前,不能被其他进程强行剥夺,只能由获得资源的进程自己释放;4. 循环等待条件:存在一个进程循环链(画进程对资源请求的环路图),链中有两个或多个进程,每一个进程正在等待链中下一个成员保持的资源。

上述四个条件同时存在就会死锁,只要有一个不存在,死锁就不可能存在。

解决死锁的方法

鸵鸟算法:不理他,过一段时间之后再去解决

死锁的预防

破坏保持和请求条件:进程开始运行之前,必须获得全部资源,若不能满足,则等待。这种方式效率低。

破坏循环等待条件:采用资源的有序分配法。将系统全部资源按类进行全局编号排序,例如输入机器=1,打印机=2,绘图机器=3,磁带机器=4,磁盘=5.所有进程请求资源必须严格按照序号递增顺序进行。但是,找到能满足所有进程要求的资源编号组合很麻烦且复杂。

目前没有有效方式预防死锁。

死锁的避免

银行家算法:(1)当一个进程提出一个资源请求时,假定分配给它,并调用检查系统状态安全性的算法,如果系统安全,那就给它实际分配,否则就推迟他的请求,阻塞等待;(2)系统检查安全算法,就是根据系统剩余的资源,检查满足请求要求后,能否让系统中所有进程都能正常完成,即找到一个进程完成的序列。如果能就是安全的。

死锁的检测和恢复

该技术目的就是指系统不试图防止死锁发生,代之的是让它发生,当它发生时再设法检测,然后采取措施恢复。

(1)死锁检测:画出进程对资源的请求序列构造图,资源指向进程就是进程保持该资源,进程指向资源就是进程请求资源。画出之后执行死锁检测算法如下:

对每个节点进行深度优先搜索,用一个空表记录走过的节点,如果节点重复了那就说明出现了死锁

(2)死锁的恢复:

1
2
1. 故障终止一些进程。尽可能选择刚启动的进程。
 	2. 资源剥夺:从一个进程取走资源给其他进程;或者回滚一些进程,进程设置检查点。

存储器管理

4.1 概述

地址空间,也叫逻辑地址空间,虚地址空间

存储空间,也叫物理地址空间,绝对地址,实地址

地址重定位

(1)程序的链接:将汇编/编译产生的一个或多个目标代码与所需要的库函数装配成一个可执行的程序。程序静态和动态链接两种方式。静态链接:程序装入内存之前,将目标模块与语言支持的库例程事先链接成可执行文件,即将使用的被调用模块的符号地址修改为可直接访问的地址。动态链接分为装入和运行两种。装入时动态链接,是将目标程序装入主存的时候,边装入边链接;运行时链接就是对目标模块的链接要推迟到程序运行的时候才开始。运行时链接可以便于模块的共享。

(2)静态重定位:在装入进程时,由装入程序把用户程序中的指令和数据的地址全部转换成存储空间的绝对地址。

(3)动态重定位:设置一个重定位寄存器。在存储器管理为程序分配主存之后,将起始地址放入重定位寄存器,在程序执行时,对每一个存储器访问,都要将相对地址转换为主存的绝对地址。

4.2 单用户单道程序的存储器管理

每次只能运行一个用户进程。

操作系统驻留在RAM的0-m的低地址部分,或ROM的高地址部分。对于存储的保护就是对地址越界的处理

4.3 多用户多道程序的存储器分配——分区分配

固定式分区

把主存用户区划分为几个大小不等的分区,当进程到达的时候,选择一个适合进程要求的最小空闲分区,没有的时候就等待。

image-20210406003725470

可变式分区

当系统运行时,系统从空闲的存储空间划分出大小正好等于进程大小的一个存储区分配给进程。

进行管理的数据结构:分区说明表、空闲区链

分区说明表记录已经分配和没有分配的分区的情况。两张表,始址、长度、占用标志

已分配区的信息放在各个进程的PCB表中,空闲区的信息则采用空闲区链进行管理。

分配算法:

首次适应法:从空闲区表或链上地址最小的开始找到第一个适合的

最佳适应法:找到空间最小的

最坏适应法:找到空间最大的。

释放的时候要进行合并操作。

通过MMU存储器管理部件负责检查和映射地址,这个机构。

4.4 覆盖和交换技术

覆盖

指同一个主存区可以被一个或多个作业(进程)的不同程序段重复使用。公用同一个主存区相互覆盖的程序段叫覆盖段,他们共享的主存区叫做覆盖区。

交换

系统根据需要把主存中暂时不运行的进程的某个部分或全部信息移到外存,而把外存中的某个进程移动到相应的主存区,并使其投入运行。打破了程序一旦进入主存就要一直运行到结束的限制。

4.5 页式存储器管理

把主存分成大小相等的若干块,也叫做页框,块的大小一般为1024或4096字节。与此同时,运行进程的地址空间也划分成与主存块同样大小的页或虚页。为了实现分页,硬件把CPU产生的地址分解为页号和页内地址两部分。为了管理,系统为进入主存的进程建立一个页表,记录该进程的逻辑页与主存块的映射关系,页表放在主存,且页表在主存的始址和页表长度记录在进程控制块中。

页式动态地址变换

image-20210406003734428

快表和联想存储器

通常设置一个专门的硬件高速缓冲寄存器组,也叫联想存储器TLB。在TLB中,包含了最近用过的大多数的页表项,把存放在高速缓冲寄存器中的页表叫快表。一般8-16个寄存器实现。快表包括内容:页号、块号、访问位、状态位。

快表使用的时候转换非常快,大大减少了地址变换时间,是跟之前的动态地址变换同时开启的(2个变换过程),一旦快表找到了相匹配的页号,将立即停止正常的访问主存页表过程。

页式管理的主存分配与保护

页式管理的主存分配与保护:

  1. 页表:每个进程一个,放在主存的专门区域
  2. 进程控制块:增加信息是该进程的页表在主存的始址和页表长度(进程地址空间大小)
  3. 存储空间使用情况表
    1. 存储分块表:记录那些块空闲,哪些被占用。表的第一项指出当前主存空闲块总数,第二项指向第一个空闲块的指针。分配时先检查是否能满足。
    2. 位示图:每一个存储块对应位示图的一位,0是空闲,1是占用。

页式管理的存储器共享与保护:

共享的代码,比如命令解释程序、编译程序、编辑程序,为了实现存储器保护,需要硬件提供与每个页框相关的读写或只读或只执行等保护标识位。

4.6 段式存储器管理

进程的地址空间是一个二位的地址空间,一个逻辑地址就由<段号S,段内地址W>组成

1.实现原理

为进程的每一个分段都分配一个连续的主存区,各段之间可以不连续。系统在主存设置一个专门区域,即段表,用来记录一个进程各个分段分配的主存的始址、本段的长度和允许的访问方法。并将该进程的段表在主存的始址和长度记录到进程控制块中。与页式管理一样,系统为每个处理机设立一个控制寄存器,用以记录现在运行的进程的段表始址和段表长度。每个进程被调度运行时,操作系统负责恢复现场的程序把该进程的段表始址和段表长度送入控制寄存器,以便进行地址转换。

2.段式动态地址变换

逻辑地址就是段号S和段内偏移w

image-20210406003743884

3.存储器保护和共享:

检查段号、段内地址的合法性。

段的共享是各进程的段指向共享段在主存的物理地址来实现的。

4.段式和页式管理的比较

段是信息的逻辑单位,它是由用户划分的,因此段对用户是可见的;页是信息的物理单位,是为了方便管理由硬件划分的,对用户是透明的。段向用户提供二位地址空间,页向用户提供一维地址空间。

->ps: 一维和二维的问题解答:

(从图中我们可以看出逻辑地址空间如果采用分页机制,那么第0页的最后一个地址和第1页的第一个地址在数值上是连续的。因此分页机制的逻辑地址空间是一维的。

相对应的如果采用分段机制,那么这段程序就会被编译程序编译成多个段,比如数据段、代码段、附加段等,每个段的段号是编译器自动分配的,每个段的长度不定(一般最长64k)。如下图所示。从下图中我们可以看到,由于每个段的长度不一,因此虽然数据段、代码段的段号是连续的,但是数据段的最后一个地址和代码段的第一个地址是不连续,因此分段机制中的地址不是一维的,而是二维的。)

4.7 虚拟存储器管理

概念:允许进程的地址空间不必全部进入主存就可以允许,当系统提供给用户程序的寻址范围与主存大小无关时,该机器提供了虚拟存储管理技术。

程序访问的局部性原理:

时间局部性:重复执行同样的代码

空间局部性:只有一部分程序会执行,很多程序不会去执行

物质基础

系统采用了多级存储结构(主存+外存),以及相应的地址转换机构(MMU)。

页式虚拟存储器管理

也叫做请求页式管理。与页式管理的主要区别是:将进程信息的副本存放在磁盘等的快速副主存储器中,并为其建立一个外页表,指出各页对应的辅存地址。当进程被调度运行时,只将进程当前需要的较少页装入主存,在执行过程中,访问不在主存页时,再将其调入。

需要硬件支持,以区分进程的哪个页在贮存,哪个页不在主存,可以在页表增加一个有效位。检查主存分页表是否有空闲页,如果有的话就分配,如果没有的话就启动淘汰算法。

页面淘汰算法:

  • 最佳置换算法OPT:以后最长时间不访问的页面
  • 先进先出淘汰算法FIFO:
  • 最近最少使用的页面淘汰算法LRU
  • 时钟页面置换算法(也叫二次机会算法)

交换区的管理:1.可以用来保存进程运行的整个映像;2.简单地存储分页系统可能被淘汰的页面。

交换空间的设置有两种方法:1.可以从文件系统中分割一部分空间作为一个大文件使用;2.用一个磁盘分区或独立的磁盘。

页面尺寸:虚拟地址空间被分成页,页是硬件级保护的最小单位。

页的共享:通常只读页,如程序文本可以被共享,而可读写的数据页不可共享。需要一个专门的数据结构记录共享页面,或者一种较为有效的方法是将被共享页锁在主存,并在页表中增加引用计数项,仅当引用计数为0的时候,才允许调出或释放共享页占用的空间。

多级页表的结构

是因为现代计算机支持很大的地址空间,页表本身会变得非常庞大,不可能为这些页表分配这么大的连续的物理空间。解决的办法就是采用多级页表结构,使页表不再占用连续的主存空间,且页表在使用的时候才被装入。

写时复制:当两个进程读相同的内容的主存时,系统给主存区赋予写时复制的页面保护,若没有进程向共享区写,那就两个进程共享主存,如果一个进程要向某页写,系统就把此物理页复制到主存的另一个页框中,并更新该进程的页指向此复制的页框。

段式虚拟存储器管理

也叫做请求段式管理。段式虚存管理把进程的所有段的副本存放在磁盘一类的辅助存储器中。修改段表,增加有效位标识是否在主存中,增加访问位和修改位、动态增长位。

页式和段式的实存管理通常采用静态链接的方法实现。段式虚存管理采用段的动态链接,在程序装入或运行时进行的链接。通常被链接的共享代码称为动态链接库或共享库。在一个程序运行开始,只将主程序段装配好装入主存即可,在主程序段运行过程中,用到哪些子程序和数据时,再将新段装配好并与主程序段连接上。

动态链接实现

需要新增:间接编址字的概念;为了便于管理,可以将每一段的间接编址字这些可变单元集中放在一个专门的段中。编译程序的时候,若该段的指令是访问本段地址,则编译成直接型指令;若访问外段指令,则编译成间接型指令。

如下的例子:

image-20210406003754292

段的共享:为了便于多进程共享公用子程序,可以在主存中设置一个共享段段表,其内可包括共享段名、在主存的始址、段长、调用该段的进程数和进程名。

段页式虚拟存储器管理

在x86系统中,CPU产生以段为单位的逻辑地址(段号,段内地址)。存储器管理单元(MMU)通过一个段硬件管理机构将每个逻辑地址(段号和段内地址)转换成一维的线性地址(虚地址),再通过页硬件管理机构将线性地址转换成主存的物理地址。

CPU->段管理机构->页管理机构->主存

image-20210406003802808

x86系统中,进程的地址空间是4GB,其中,进程的私有部分占3GB,所有进程共享的操作系统部分占1GB。进程的私有部分被局部描述符表LDT记录,所有进程共享部分被全局描述符表GDT记录。每个表的最大段数为8k。表中的每一项都代表一个段描述符,占8B,描述相应段的有关控制信息,如该段的基地址、段长以及该段的保护方式等。

x86系统中的分段:程序里面使用的是逻辑地址(就是段选择子sgp+32位段内地址w)

image-20210406003812367

段的逻辑地址转换为线性地址:

  1. 根据段寄存器给出的段选择子中的g标识判断s时在GDT还是LDT表中。
  2. 再以s为索引,在相应表中找到该段的段描述符
  3. 由段描述符的段的特权级标识p检查操作是否合法,弱不合法则错误终止
  4. 由段描述符的段长检查段内地址w的合法性。不合法则错误终止;合法则将其与段的基地址相加转换为线性地址

x86系统中的分页:x86允许一个页的大小为4KB或者4MB,对于4KB的页,使用两级页表来索引。

操作:

  1. 由CR3(目录表的起始地址)找到页目录表起始地址,以页目录索引pd为索引找到页目录表项
  2. 检查该项的页大小标识是否设置,若设置,则该项给出的是4MB页对应的页框地址,且线性地址的低22位就是4MB页框中的页内地址。使页框地址与页内地址相加,得到主存的物理地址。若没有设置页大小标识,转3
  3. 若检查该项的页大小标识没有设置,该项指向一个页表地址,再以p为索引,再该页表中找到对应的主存页框
  4. 页框地址与页内地址w相加,生成主存的物理地址

文件系统

5.1 文件和文件系统

一个文件由文件控制块+文件体两部分组成,操作系统通过文件控制块管理文件,用户关心和使用的是文件体,即文件的实际内容。为了便于管理,操作系统将文件的控制块保存在一个文件目录的结构中。每个文件在其中占有一项。

UNIX系统中,文件分为三类:普通文件、目录文件(用来维护文件系统结构)、特别文件(输入输出设备如终端、打印机叫做字符型特别文件,把输入、输出型的设备如磁带、磁盘、光盘叫做块特别文件)

文件系统:负责为管理磁盘、磁带等组成的文件存储器;实现用户的按名存取;提供灵活多样的文件结构和存取方法;提供一套方便、简单地文件操作命令;保证文件信息的安全性;便于文件的共享;

5.2 文件目录结构

文件目录——指的是记录文件的名字及其存放物理地址的一张映射表,表中包括了许多文件控制块。

一级目录表结构:一张表,文件名-第一个物理块号-其他管理和控制信息

二级目录表结构:为每一个用户建立一个独立的目录,叫做用户文件目录;一级(主目录)维护的是用户-目录的映射表,二级(用户的目录表)维护的就是一级目录表一样的结构

多及目录结构:

(1)树形目录:有一个主目录根目录,在根目录下有许多用户目录和普通文件目录项。

(2)当前目录:

(3)无环图形目录结构:

5.3 文件的逻辑结构和存取方法

文件结构指的是文件的组织形式。

文件的逻辑结构分为两种形式:无结构的字节流式文件+有结构的记录式文件,记录式结构文件又分为定长和变长,记录式文件按照记录出现的逻辑顺序进行编号0,1,2……

文件的存取方法:1. 顺序存取:系统设置两个指针指向读写的字节为止或记录位置,每次存取都要基于上一次存取;2. 直接存取:也叫做随机存取,直接指出存取的记录号或记录中的一个关键字,定长记录式文件这样高效,不定长的时候很低效。对于变长的记录文件通常采用顺序存取。

5.4 文件的物理结构和存储介质

物理结构

1.连续文件

连续文件也叫顺序文件,把逻辑上连续的文件信息存储在连续的物理块(一个物理块可以包括一个扇区或者几个连续的扇区,为了有效的管理文件存储器的空间,通常把它们划分成若干个大小相等的块)中的一种组织方式。系统为已经存储的文件建立一个目录表,记录各个文件的控制信息。

image-20210406003830730image-20210406003849819

2.链接文件

用目录表存储开始块的信息,但在文件块中存放的信息包括一个指针指向下一个块,文件的最后一个物理块的指针通常为0,以指示该块是链尾。它也就是一个链表的形式。缺点是只能进行顺序存取。

当然也可以盘文件映射表或文件分配表去解决顺序存取的问题。也就是说,可以把指针字从文件的各个物理块中拿出来放在一张顺序表中,或者在存储器中建立一个索引。

3.索引文件

也就是说是首先有一张文件目录表指出:文件名-索引表块号-文件长度,根据索引表块号找到一个文件的索引表,这个索引表就是顺序存放的!

image-20210406003902040

当然也就可以进行扩展为多层级的索引。一级索引表指向二级索引表,二级索引表再指向文件块

4.索引顺序文件

存储介质

扇区、磁道、柱面、主轴、磁头

5.5 文件记录的组块与分解

  1. 记录的组块:把多个逻辑记录放在一个物理块的工作叫做记录的组块。把一个块中存放的逻辑记录个数叫做块因子。当主存缓冲区写满的时候,才真正启动磁盘进行实际写。
  2. 记录的分解:从一个物理块中将一个逻辑记录分离出来的工作叫做记录的分解

5.6 文件存储器存储空间的管理

常用的对于磁盘存储空间的管理方式有如下的三种:

1.空白文件目录

适合静态分配(即连续结构的文件分配)

系统为连续未用的空闲盘块区,所有的空白文件建立一张表,叫做空白文件目录。每个空白文件占用其中的一个表目。第一物理块号-空白块个数

2.空闲块链

适合动态分配

主存保留一个链头指针,把所有空闲块链接成一个链,即空闲块链。最后一个空闲块指针为0;但是这种链条方式不太好,效率低。

所以就改进:采用空白块成组链表,即利用盘中的空闲块自己管理空闲块,每个磁盘块记录尽可能多的空闲块而组成一组,各组之间用指针再链接再一起!而不是每一个块都用指针链接起来。

3.位映像表或位示图

适合文件静态和动态分配

使用一个位向量,磁盘中的每个块都占用其中的一位。具有n个磁盘块的磁盘,其位映像表有n位。

5.7 文件的共享与保护

文件的共享

  • 硬链接: 与普通文件没什么不同,inode 都指向同一个文件在硬盘中的区块

  • 软链接: 保存了其代表的文件的绝对路径,是另外一种文件,在硬盘上有独立的区块,访问时替换自身路径。

    硬链接是指针,所有的硬链接都是指向同一个磁盘块。 删除一个指针不会真正删除文件,只有把所有的指针都删除才会真正删除文件。 软连接是另外一种类型的文件,保存的是它指向文件的全路径, 访问时会替换成绝对路径

共享文件的目录的目录项中增加“连访”熟悉,即用户计数字段

文件的保护

文件的复制:全量转存或者增量转储

文件的存取控制

  1. 保护域:一个域就是一组(对象,存取权限)偶对,每个偶对说明一个对象和允许对其施加的操作。因此可以创建一张存取控制矩阵,列头就是域1,域2……,行头就是对象A,B,C,矩阵里面存放的就是对该文件的权限,如rw, rwx
  2. 存取控制表ACL:也就是(uid,gid,权限)这样的形式就是文件的存取控制表

5.8 文件的操作命令

创建文件:fd = create(path, 文件属性);

删除文件:delete(path);

打开文件:fd = open(path, 打开时的操作方式);// 打开文件就是按照文件路径名找到文件目录项,进而找到FCB文件控制块信息,把FCB复制到内存,并记录到系统打开文件表。

关闭文件:close(fd);

读写文件:n=read(fd, buf, nbytes) n = write(fd, buf, nbytes);

追加文件:append

随机存取:seek将文件的当前位置指针定位到指定位置

得到文件属性:make命令

5.9 文件系统的组织结构

应用程序接口-》逻辑文件系统-》文件组织模块-》基本文件系统-》I/O调度及控制模块

5.10 存储器映射文件

似乎mmap就是这么实现的。

让进程分配虚存的一部分地址空间,然后将磁盘的一个文件映射到该空间,对文件块的存取是通过访问虚存的一个页来实现的。映射一个文件到虚存是操作系统提供的一个系统调用。将文件映射到虚存的一个区域之后,返回包含文件复制的字节数组的虚拟地址。仅当需要对存储器映射文件存取的时候,实际的数据才进行传输。程序员buyon关心文件命令去读写,而是使用存储器映射文件读写许村。

设备管理

6.1 I/O硬件组成

分类:字符设备(人机交互设备)、块设备(外部存储器)、网络通信设备(网络、调制解调器)

设备控制器

数据传输需要数据通路,称为总线,任何I/O设备有且只能连接一条总线。下面讨论所有PC体系结构设计的I/O通路中的基本概念:

I/O端口:连接到I/O总线上面的设备的IO地址集

IO接口:IO端口和对应的设备控制器之间的硬件电路

IO总线:CPU和IO设备之间的通路

CPU-》总线-》IO端口(地址嘛)-》IO接口-》IO设备

IO数据传输的控制方式

  1. 程序查询(polling)方式:CPU直接向设备控制器发启动设备写的IO命令,CPU一直循环查询设备是否已经完成输出的状态标志。
  2. 中断(interrupt)方式:启动设备后,CPU区执行零一个程序,设备完成后向CPU提出终端请求。CPU执行完当前指令,响应中断,去执行中断处理程序。处理设备的输入,中断返回,CPU继续执行被中断程序。
  3. 直接存储器访问(DMA)方式:中断方式让PCU多次干预,经常打扰CPU;DMA方式,允许DMA控制器接管地址线的控制权,DMA控制器直接控制设备与主存的数据交换。DMA控制器直接配合主存进行工作,DMA中有数据缓冲寄存器、控制状态寄存器、数据缓冲存储区、主存地址寄存器、传送字节个数计数器。CPU只会在传输开始和结束的时候进行建档案与,大大减轻负担。

通道

主存和IO通道相连接,IO通道用不同的通道(选择通道等)域对应的IO设备控制器连接,IO设备控制器再与具体的IO设备相连接。

通道的类型:

  1. 字节多路通道:以字节为传输单位,可以分时执行多个通道程序,连接大量慢速设备
  2. 选择通道:以成组的方式工作,每次传送一批数据,一段时间只执行一个通道程序,已婚徐一台设备进行数据传输
  3. 数组多路通道:先为一台设备执行一条通道指令,然后自动转接,为另一台设备执行一条通道指令。这样,对于连接多台磁盘机的数组多路通道,它可以启动它们同时执行移臂定位操作,按序交叉传输一批批的数据。

通道命令:

通道比DMA更强的IO处理能力,故称为IO处理机。通道有自己的指令系统。

接受CPU的委托,独立的执行自己的通道程序,管理和控制输入输出操作。相关的寄存器:存放通道程序的内存地址的通道地址字CAW寄存器,存放通道指令的通道命令字CCW寄存器。

通道的工作过程:

  1. CPU向控制设备的通道发出启动IO指令,并将 要执行的通道程序首地址发送CAW,一级要访问的IO设备
  2. 通道启动成功后,按照CAW到主存取一条条通道命令送CCW执行通道程序,控制设备进行数据传输,直到通道程序执行完和设备也完成了指定的IO任务时,才向CPU发中断请求,等待CPU进行处理。

6.2 I/O软件的组成

6.3 磁盘管理

磁盘调度,寻道方式:

  1. 先来先服务FCFS调度算法:
  2. 最短寻道时间优先算法:将磁头移动到下一磁道的时候,选择移动距离最短的磁道
  3. 扫描法:随时处理所到达的任何磁道上的服务请求,移动到另一端为止。
  4. 循环扫描法:当到另一端,立刻返回开始处,循环!
  5. 查询、循环查询:移动方向没有请求的时候,磁头就反向移动

Linux操作系统

Linux进程管理

7.1 Linux进程的组成

进程的定义

每个进程都有一个独立的地址空间,在用户态运行的时候,进程映像含有代码段、数据段和私有用户栈

系统内核时可重入得纯代码。进程在核心态运行的时候,访问内核的代码段和数据段,并使用各自的核心栈,从而形成几个内核控制路径的交替执行。

进程控制块,也称为进程描述符,用一个task_struct类型的数据结构标识,它包含了进程相关的所有信息,比如进程当前状态、进程的标志、当前进程的基本信息、优先级等等

进程唯一标识符pid,新创建的通常是前一个+1,最大pid时32767

Linux把每个进程的核心栈和基本信息thread_info存放在两个连续的页框中(8KB)

image-20210406003922671

esp寄存器存放的是核心栈的栈顶指针

进程的状态

执行态、就绪态、暂停态(收到信号之后进入的,收到唤醒信号再出来)、不可中断等待态、可中断的等待态(睡眠等待)

僵死态(等待父进程进行善后处理)、死亡状态

7.2 Linux进程链表

传统进程链表:所有进程链表、可运行、子进程链表、兄弟进程、等待进城链表

哈希链表:4类:进程的pid、线程组领头进程的pid,进程组领头的pid、会话领头进程的pid

image-20210406003931038

7.3 Linux进程控制

UNIX的机制:写时复制、轻量级进程允许共享内核的很多数据结构、vfork共享父进程的地址空间

  1. 创建轻量级进程clone():调用的是sys_clone() -> do_fork()完成
  2. 创建子进程fork():sys_fork()->do_fork()来完成,子进程采用写时复制
  3. vfork():调用后暂时挂起父进程
  4. Kernel_thread():内核线程函数,以周期性的方式执行系统任务(刷新磁盘高速缓存、交换出不用的页),效率不高。因此交给核心态的线程。

0号进程就是内核线程,静态分配的数据结构。0号是所有进程的祖先,每个CPU都有一个0号进程。

1号进程是0号创建的内核线程init。创建后执行init函数。

do_fork()函数:负责处理clone、fork、vfork系统调用

主要功能:pid位图区分配一个pid;检查父进程的ptrace,字段看是否有跟踪父进程。写子进程的对应标识;调用copy_process()函数复制进程描述符,返回创建的进程描述符地址;设置子进程是否为暂停状态(看参数);如果设置了vfork,则挂起父进程,直到子进程结束或者运行了新的程序;do_fork()函数结束运行,返回子进程的pid

进程撤销

  1. 进程终止:
    1. Exit(),系统调用只终止某一个线程
    2. Exit_group(),终止整个线程组
  2. 进程删除:若父进程在子进程前结束,子进程会成为孤儿进程,处于僵死状态,描述符占用RAM,系统强迫孤儿进程称为init进程的子进程,init进程在调用wait类系统调用检查其终止子进程时,会撤销所有僵死子进程。

7.4 Linux进程切换

80x86用任务状态段TSS的特殊段类型存放进程的硬件上下文。进程切换只发生在核心态,用户态进程使用的所有寄存器值都会保存在进程的核心栈中。

进程切换两步:1. 切换页目录表以安装一个新的地址空间;2. 切换核心栈和硬件上下文。schedule函数

7.5 Linux进程调度

函数:scheduler_tick():负责维持当前进程的时间片计数;try_to_wake_up():唤醒睡眠进程

7.6 内核同步

内核控制路径(kernel control path):

表示内核处理系统调用,异常或者中断所执行的指令序列。

内核同步就是确保任意时刻只有一个内核控制路径处于临界区。

Linux存储器管理

8.1 进程地址空间的分配

进程地址空间管理

1.分段

x86下的地址空间为4GB,0-3GB为进程的私有空间,后1GB为内核虚空间,为进程的公有空间,只有运行在核心态的进程才能寻址。内核虚空间的前896MB映射物理内存前896MB,剩下的128MB实现对超过896MB空间的映射。

逻辑地址通过分段单元变成线性地址,线性地址通过分页单元变成物理地址,分段单元和分页单元都是属于内存管理单元(MMU),逻辑地址为端选择符(16位)+段内偏移量(32位),线性地址为32位无符号整数,寻址4GB,所有段描述符存放在全局段描述符表GDT中,每个段由一个8字节的段描述符表示。

段描述符字段:32位的段的起始线性地址,20位段的长度,段的类型和保护方式,段描述符的特权级,段是否存在于主存的标志等。

段寄存器中存放段选择符,Linux中逻辑地址中的段偏移量的值总是和相应的线性地址的值是相通的。

Linux的四个主要段的描述符是用户代码段、用户数据段、内核代码段、内和数据段,base都是0开始,limit为4GB

每个CPU有一个GDT表,除了用户态和核心态下的代码段和数据段外,还有任务状态段TSS,用户态切换到核心态,需要从TSS中获取核心态堆栈的地址。大多数用户态下的Linux进程不使用LDT,所以内核定义了一个默认的LDT供大多数进程共享。

image-20210406003941300

  • BSS段
  • BSS段包含了程序中未初始化的全局变量,在内存中 bss 段全部置零。

2.虚拟内存区域

对于进程的地址空间,是一些通过为程序的可执行代码、程序的初始化数据、程序的未初始化数据、用户栈、所需共享库的可执行代码和数据、由程序动态请求内存的堆等分配保留的虚空间。内核通过一组虚拟内存区域描述符来描述进程地址空间的使用情况,虚拟内存区域描述符的结构类型vm_area_struct定义。

Linux系统对进程的已分配的虚拟内存区域采用:单向链和红黑树进行管理。进程通过一个单链表把拥有的各个虚拟内存区域按照地址递增顺序链接在一起。虚拟内存区域数量少,很方便。当进程需要的虚拟内存区域加多的时候,成百上千,用红黑树更好。Linux为了方便,两者都用,用红黑树快速确定含有指定地址的虚拟内存区域,单链表用来扫描整个虚拟内存区域集合,描述符中mm_rb指向红黑树的根,mmap指向单链表。

虚拟内存区域访问权限用vm_area_struct的vm_flags字段给出

分配、释放虚拟内存区域:do_mmap(file, addr, len, long prot, flag, offset),文件描述符指针file和文件偏移量offset

3.虚拟内存描述符

mm_struct是虚拟内存描述符,关系如下:

image-20210406003951566

4.创建进程的地址空间

创建一个新进程的时候,内核调用copy_mm()函数建立新进程的页表和内存描述符,以此来建立进程的地址空间。如果设置了CLONE_VM标识(clone函数创建轻量级进程的时候),copy_mm()函数就必须为新锦成创建一个新的地址空间,并把父进程描述符的mm字段复制过去。

然后调用dup_mmap()函数,复制进程的虚拟内存区域和页表。复制附近的指向的虚拟内存区域链表,进行扫描,复制每一个虚拟内存区域描述符,然后插入到新进程中相应位置,并把新内存描述符插入到整个虚拟内存描述符的双向链表中。

Exit_mm()函数释放进程的地址空间,即释放进程的内存描述符和所有相关的数据结构。

5.堆的管理

虚拟内存描述符中start_brk描述堆得起始地址,brk制定结束地址,利用堆,请求和释放动态内存的API如下:

Malloc:请求size个字节的动态内存,成功返回起始虚地址。

Calloc:请求一个元素大小为size,个数为n的数组,会清空。

Realloc:改变malloc和calloc所分配的内存区间大小

Free,释放malloc和calloc分配的起始地址为addr的内存区间

brk:用addr修改堆得大小,即修改堆得结束地址,成功时,返回堆得新的结束地址

8.2 物理内存管理

进程的虚拟地址里面去分配给用户动态内存,当进程允许产生缺页中断的时候,系统才通过缺页中断处理程序调用相应函数实现物理页框的分配。

物理内存布局

内核使用的内存,有的用来存放内核代码和内核静态数据结构,有的映射硬件设备I/O的共享内存,有的含有BIOS数据。内核将下列页框记为保留:可用物理地址范围外的页框、含有内核代码和已经初始化数据结构的页框、被保留页中的页框。这些页框不能被动态分配或交换到磁盘上。

内核用struct_page的页框描述符来记录页框当前信息,内核必须记录每个物理页框的当前状态:哪些页框属于进程,哪些页框是内核代码或内核数据页,哪些页框是空闲的。所有页框描述符存放在mem_map数组中。

页框描述符中:lru字段是一个页框双向链表,Linux内核根据页框的最近被访问情况,把页框按照LRU策略链入内存管理区描述符中的活动页框链表(active_list)或非活动页框链表(inactive_list)

非一致内存访问机制

即CPU对内存中不同的存储单元访问所需时间是不相同的。

Linux支持非一致内存访问模型,物理内存被划分为几个节点,对不同节点内的页面访问所需的时间可能不同。

Linux使用了节点管理内存,也就是说处理器在访问不同节点的内存的时候,花费的时间是不一样的。只有一个单独的节点,包含了系统中所有的物理内存。

Linux2.6把每个内存节点划分为3个管理区。以x86UMA体系结构为例,(1)ZONE_DMA:包含低于16MB的常规内存页框;(2)ZONE_NORMAL:包含16MB-896MB的常规内存页框;(3)ZONE_HIGHMEM:896MB开始的其它内存物理页框。

image-20210406004033334

分区页框分配器

负责处理对连续物理页框的分配请求

image-20210406004046431

管理区分配器负责接收动态内存的分配和释放请求

伙伴系统管理连续的页框,以解决外碎片问题(就是加载在已分配页框中间的哪些连续的小的空闲页框)伙伴算法把空闲页框组织成11个链表,分别连由大小为1,2,4,8……1024个连续页框的块链接而成。然后去分配页框。假设分配8个,先找8个的,然后找16个的,如果找打,把16个连续页框分成2分,一份满足请求,另一份插入到具有8个连续页框的链表中。

Free_area字段的结构:

image-20210406004055716

8.3 slab管理

针对内碎片去解决的

一般来说,内核对象的生命周期是这样的:分配内存-初始化-释放内存,内核中有大量的小对象,比如文件描述结构对象、任务描述结构对象,如果按照伙伴系统按页分配和释放内存,对小对象频繁的执行「分配内存-初始化-释放内存」会非常消耗性能。

伙伴系统分配出去的内存还是以页框为单位,而对于内核的很多场景都是分配小片内存,远用不到一页内存大小的空间。slab分配器,「通过将内存按使用对象不同再划分成不同大小的空间」,应用于内核对象的缓存。

伙伴系统和slab不是二选一的关系,slab 内存分配器是对伙伴分配算法的补充。

数据结构

image-20210406004109003

slab分配器

kmem_cache 是一个cache_chain 的链表组成节点,代表的是一个内核中的相同类型的「对象高速缓存」,每个kmem_cache 通常是一段连续的内存块,包含了三种类型的 slabs 链表:

  • slabs_full (完全分配的 slab 链表)
  • slabs_partial (部分分配的slab 链表)
  • slabs_empty ( 没有被分配对象的slab 链表)

同一硬件高速缓存行可以映射 RAM 中多个不同的块,相同大小的对象倾向于存 放在高速缓存内相同的偏移量处。在不同 slab 内具有相同偏移量的对象最终很可能映射到 同一高速缓存行中。而使用 slab 分配器的对象通常是频繁使用的小对象,高速 缓存的硬件可能因此而花费内存周期在同一高速缓存行与 RAM 内存单元之间来来往往的传送两个对象。

如下例:假设 cache 行为 32BytesCPU 包含 512cache 行(缓存大小 16K )。

假设对象 A,B 均为 32B ,且 A 的地址从 0 开始, B 的地址从 16K 开始,则根据组相联或直接相联映射方式 (全相联方式很少使用), A,B 对象很可能映射到 cache 的第 0 行 ,此时,如果 CPU 交替的访问 A,B50 次,每一次访问 cache0 行都失效,从而需要从内存传送数据。而 slab 着色就是为解决该问题产生的,不同的颜色 代表了不同的起始对象偏移量,对于 B 对象,如果将其位置偏移向右偏移 32B ,则其可能会被映射到 cache 的第 1 行上,这样交替的访问 A,B50 次,只需要 2 次内存访问即可。

这里的偏移量就代表了 slab 着色中的一种颜色,不同的颜色代表了不同 的偏移量,尽量使得不同的对象的对应到不同的硬件高速缓存行上,以最大限度的提高效率。实际的情况比上面的例子要复杂得多, slab 的着色还要考虑内存对齐等因素,以及 slab 内未用字节的大小,只有当未用字节数足够 大时,着色才起作用。

8.4 高端内存区管理

image-20210406004120298

在讲内核空间内存分配之前,先来回顾一下内核地址空间。kmallocvmalloc 分别用于分配不同映射区的虚拟内存,看这张上次画的图:

kmalloc

kmalloc() 分配的虚拟地址范围在内核空间的「直接内存映射区」。

按字节为单位虚拟内存,一般用于分配小块内存,释放内存对应于 kfree ,可以分配连续的物理内存。函数原型在 <linux/kmalloc.h> 中声明,一般情况下在驱动程序中都是调用 kmalloc() 来给数据结构分配内存 。

还记得前面说的 slab 吗?kmalloc 是基于slab 分配器的 ,同样可以用cat /proc/slabinfo 命令,查看 kmalloc 相关 slab 对象信息,下面的 kmalloc-8、kmalloc-16 等等就是基于slab分配的 kmalloc 高速缓存。

vmalloc

vmalloc 分配的虚拟地址区间,位于 vmalloc_startvmalloc_end 之间的「动态内存映射区」。

一般用分配大块内存,释放内存对应于 vfree,分配的虚拟内存地址连续,物理地址上不一定连续。函数原型在 <linux/vmalloc.h> 中声明。一般用在为活动的交换区分配数据结构,为某些 I/O 驱动程序分配缓冲区,或为内核模块分配空间。

image-20210406004130113

8.5 地址转换

image-20210406004138140

8.6 请求调页与缺页异常处理

页面交换策略是LFU:LRU和LFU是不同的!

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!

LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!

8.7 盘交换区空间管理

盘交换区用来存放从内存中暂时换出的页数据,每个盘交换区都由一组4KB的页槽组成,也就是由一组与页大小相等的块组成。盘交换区的第一个页槽用来存放该交换区的有关信息,其结构类型为swap_header联合体。

Linux文件系统

9.1 Ext2的磁盘涉及的数据结构

Linux系统的一个Ext2磁盘文件卷(文件系统,也叫分区)由若干个磁盘块组成,把他展开成带状如下:

image-20210406004224248

引导块:Ext2文件卷的第一个盘块不被文件系统使用,用作Linux系统的引导块或保留不用,引导块用以读入并启动操作系统,只有根文件系统的引导块才起作用。

块组:每个块组用块组描述符记录结构信息,每个块组包含了相邻磁道的磁盘块,且块组的大小相等并按顺序安排。

超级块:用于存放整个文件卷的资源管理信息

数据块位图:记录文件数据区各个盘块的使用情况

索引节点位图:记录索引节点区各个索引节点的使用情况

索引节点区:存放文件的索引节点。一个索引节点存放一个文件的管理和控制信息。

文件数据区:存放普通文件和目录文件等。

支持数形的目录结构:不仅支持树形的目录结构,而且他所支持的各种文件系统也是作为一个子树安装在ext2文件系统的某个目录下的。

文件控制块:为了提高文件的查找速度和更好地实现共享,Linux将普通文件目录项分为简单目录项和文件的索引节点。目录项包含文件名和文件分配的索引节点号等信息,索引节点包含文件的管理和控制信息。

Linux虚拟文件系统

所谓虚拟文件系统,是指它的所有数据结构在运行时才在内存建立,并在卸载的时候删除,在磁盘上没有存储这些数据结构,与之相对应的是上述的各个具体的文件系统的信息。

VFS作用:

  1. 对各种具体文件系统的数据结构进行抽象,统一管理
  2. 接收用户层的系统调用,如open, write, stat, link
  3. 支持多种具体文件系统之间的相互访问
  4. 接收内核其他子系统的操作请求,例如进程调度和内存管理

image-20210406004212863

10.1 虚拟文件系统涉及的数据结构

超级块对象:代表一个已经安装的文件系统。存放该文件系统的管理和控制信息。对应基于磁盘的文件系统,这类对象对应存放在磁盘上的文件系统控制块中,也就是说每个文件系统对应一个超级快对象。VFS超级块对象是各种具体的文件系统在安装时在内存中建立的。

所有被安装的文件系统的超级块对象以双向循环链以s_list结构链接在一起,链头指针保存在super_block中。

索引节点对象:对于具体文件系统,它代表一个文件,对应于存放在磁盘上的文件控制块FCB。每个文件都有一个索引节点对象,每个索引节点对象都有一个唯一的索引节点号,来表示文件系统中的一个特定文件。

也就是inode对象。一个文件的名字可以改变,但文件的索引节点是唯一的,包括文件占用的数据块情况、文件大小等。

目录项对象:他代表一个目录项,是一个文件路径的组成部分,存放目录项与对应文件进行连接的信息

VFS把每个目录看作是由若干个子目录和文件组成的一个普通文件。一旦目录项被读入主存,VFS就把他转换为虎基于dentry结构的一个目录项对象。

文件对象:它记录了由进程打开的文件与进程之间进行交互所必需的信息,是进程与文件系统的桥梁。

文件对象是为了描述进程与其打开的一个文件进行交互而引入的,文件对象在磁盘上没有对应的映像,文件对象是在文件被打开的时候创建的,由一个file数据结构描述。文件对象方法包括:llseek修改文件指针命令;read,从文件的offset位置开始读count字节的数据送入buf,读完,增加offset的值;write从buf中读count字节的值,然后将其写入文件的offset位置,写完增加offset的值。open:创建一个新的文件对象打开文件,并将它与相应的索引节点对象链接。

进程有自己的当前工作目录和根目录,进程描述符task_struct进程控制块的fs字段存放由类型为fs_struct结构的与安装的文件系统相关的信息。task_struct中的files字段存有结构类型为files_struct的进程当前打开文件的信息。

image-20210406004328548

10.2 文件系统的注册和安装

注册:第一:生成一个file_system_type类型的结构体并填写相关内容;第二:使用模块初始化代码,调用register_filesystem函数完成文件系统的注册。注册完成后形成的文件系统类型链表就有了新的文件系统

安装:Linux2.6每个进程都可以拥有自己的已安装文件系统树,叫做进程的名空间。mount命令会转换成对sys_mount命令的系统调用,它再调用do_mount,实现真正的安装操作。如将硬盘分区的NTFS文件系统安装在”/mnt/ntfs“目录下,可以用下面的命令来实现:mount -t ntfs /dev/hda2 /mnt/ntfs

10.3 VFS系统调用的实现

文件打开:进程与文件之间建立连接,打开文件描述符唯一的标识着这个连接。fd=open(要打开文件的路径名,打开文件的访问方式),open的系统调用服务例程为sys_open()

文件关闭:close

文件读写:

  1. 文件的地址变换函数bmap(ip,rwflg):ip是文件的索引节点对象指针,rwflg是文件读写标志,返回值为找到的物理块号。
  2. read, write:功能相似,参数是:已打开文件描述符fd、要传送数据的用户线性区地址buf和读写的字节数count。返回的是成功传送的字节数或错误时的一个错误码。

Linux I/O系统

11.1 设备驱动模型

11.2 设备文件

11.3 设备驱动程序

11.4 高速缓存

中断、异常、信号处理

12.1 中断和异常处理的硬件基础

12.2 中断和异常处理

12.3 信号处理机制

UNIX系统进程间通信

13.1 管道通信

13.2 UNIX系统V的交互进程通信

13.3 信号量机制

13.4 消息缓冲机制

13.5 共享内存区机制

This post is licensed under CC BY 4.0 by the author.

Trending Tags