1、程序运行分析
(1)通常我们在Linux端编译程序时输入的gcc会将我们所写的.c程序翻译成一个可执行目标文件,这个翻译的阶段可以分为4个阶段,执行这4个阶段的程序(预处理器、编译器、汇编器和链接器)一起构成了编译系统。
我们以hello.c程序为例来进行分析:
预处理阶段:
1.展开所有的宏定义,消除#define
2.处理所有的条件编译指令
3.处理以字符“#include”开头,将相应的头文件.h的内容直接插入到程序文本中
4.删除所有的注释
5.添加行号和文件名标识
6.保留所有的#pragma编译器指令
之后得到了一个以.i作为文件扩展名的另一个c程序。
编译阶段:编译器对上一步得到的.i文件进行一系列的词法分析,语法分析,语义分析以及优化后得到汇编语言程序.s。
汇编阶段:汇编器将上一步得到的.s转换成机器语言指令,并将这些指令打包成一种叫做可重定位目标程序的.o文件。
链接阶段:由上图知,hello.c程序调用了printf函数,而printf函数存在于一个名为printf.o的单独编译好了的 目标文件中。所以链接器负责将printf.o文件以某种方式合并到hello.o程序中,最终得到一个可执行目标文件.exe,它可以被加载到内存中,由系统执行。
(2)运行hello程序时发生了什么?
如上图所示,它是一个典型系统的硬件组成,这里解释四个概念:
加载:把一个字节或者一个字从主存复制到寄存器,以覆盖寄存器原来的内容。
存储:把一个字节或者一个字从寄存器复制到主存的某个位置,以覆盖这个位置上原来的内容。
操作:把两个寄存器的内容复制到ALU(算术/逻辑单元),ALU对其做算术操作,并将结果存放到一个寄存器中,以覆盖该寄存器中原来的内容。
跳转:从指令本身中抽取一个字,并将这个字复制到程序计数器PC中,以覆盖PC中原来的值。
当我们输入./hello后,shell将字符逐一读入寄存器,再把它放到存储器中。当我们敲下回车键之后,shell将hello目标文件中的代码及数据从磁盘复制到主存,然后处理器开始执行hello程序的main程序中的机器语言指令,这些指令将“hello world\n”字符串中的字节从主存复制到寄存器,再从寄存器复制到显示设备,最终显示在屏幕上。
(3)怎样做提高运行效率?
根据上述分析,可以知道运行一个程序,系统花费了大量的时间在将信息从一个地方挪到另一个地方,所以我们使用高速缓存来存放处理器近期可能会需要的信息,从而使得处理器访问速度加快。
2、操作系统提供了以下抽象:
(1)进程
进程:操作系统对一个正在运行的程序的一种抽象,作为拥有资源的基本单位。
内核将进程存放在双向循环链表中,链表中的每一项都是类型为task_struct(进程描述符)的结构。进程控制块记录当前进程状态的信息,系统管理调度进程就依靠PCB(进程控制块)中记录的信息。
进程终止:
——————正常终止:从main返回、调用exit、调用_exit或_Exit、最后一个线程从其启动例程返回、最后一个线程调用pthread_exit
——————异常终止:调用abort、接收到了一个信号并终止、最后一个线程对取消请求作出响应
进程的状态:
关于fork复制进程的典型例子:
int main()
{
fork();
printf("hello\n");
exit(0);
}
//result:打印两个hello
int main()
{
fork();
fork();
printf("hello\n");
exit(0);
}
//result:打印4个hello
int main()
{
fork();
fork();
fork();
printf("hello\n");
exit(0);
}
//result:打印8个hello
fork() || fork();//产生3个进程
for(int i = 0;i < 2;++i)//产生6个hello
{
fork();
printf("hello\n");
}
for(int i = 0;i < 2;++i)//产生8个hello
{
fork();
printf("hello");
}
僵尸进程:子进程先于父进程结束,则子进程变为僵尸进程,若不及时解决僵尸进程,则会导致占用内核空间,无法正常工作。解决僵尸进程有以下3中方法---->
a、捕获信号SIGCHLD(子进程状态改变产生此信号),在处理函数中调用wait,回收子进程的ID、终止状态以及资源利用信息(cpu时间、内存等)
//解决僵尸进程
signal(SIGCHLD,sig_child);
void sig_child(int signo)
{
pid_t pid;
int stat;
pid = wait(&stat);
return;
}
b、父进程将SIGCHLD(一个子进程停止或终止)的处理函数设SIG_IGN
signal(SIGCHLD,SIG_IGN);//忽略信号
c、fork两次,父进程fork产生一个子进程,然后子进程继续fork产生一个子进程(称孙进程),这时子进程退出,那么孙进程被init进程接管,孙进程结束,init回收。
进程上下文:
进程调度:
a、先来先服务调度算法(FCFS)
b、时间片轮转:周期性的进行进程切换
c、短任务优先(STCF):抢占式短任务优先------>每次进来一个新进程,需要对所有的进程进行比较,谁的时间短,谁就先运行; 非抢占式短任务优先------->让已经在cpu上运行的程序执行到结束,然后在所有候选的程序中选择时间最短的来执行
d、优先级调度:解决短任务优先造成的长进程饥饿
(2)线程
线程:是进程里面的执行上下文,或者是进程中完成一个任务的完整执行序列。它作为调度和分配的基本单位。为了记录线程的属性信息,也需要一个数据结构来表示,称为线程控制块。
线程独享的资源:程序计数器、寄存器、栈、状态字
线程通信:
a、管道:把一个进程的输出通过管道连接到另一个进程的输入,
分为------->>>>>无名官道(父子进程,即有亲缘关系的进程间才可以使用)
int pipe(int pipefd[2])l;//创建一个管道
//pipefd[0]代表读端,pipefd[1]代表写端,一般是父进程写,子进程读
-------->>>>>有名管道(任意的进程间使用)
mkfifo filename//创建的管道大小为0,内容写在内存中
b、套接字
c、信号量:
ipcs -s//显示信号量
ipcrm -s +semid//删除信号量
d、共享内存:最快的通信机制,信号量实现共享内存的同步
ipcs -m//显示共享内存
e、消息队列:与命名管道相比,其优势在于独立于发送和接收进程而存在
ipcs -q//显示消息队列
ipcs -q <id>//删除一个消息队列
f、信号
线程同步---->
content introduction:
***** 临界资源:同一时刻只允许一个线程访问的资源
***** 临界区:访问临界资源的代码段
***** 竞争:两个或多个线程争相访问同一个资源的现象
methods:
a、互斥锁:可以和初始值为1的信号量进行互换,lock相当于p,unlock相当于v
b、信号量:一个特殊变量,只取正数值0和1,只允许原子操作,可以被增加(sem_post)或减少(sem_wait),v代表释放资源(增加),p代表获取资源(减少)
c、管程:使用了互斥锁和条件变量(当某个共享数据到达某个值时,唤醒等待这个共享数据的线程)
d、消息传递:通过send和receive来实现网络环境下的同步
e、自旋锁:用于对称多处理器
线程安全:如果一个函数可以被多个线程同时调用且不发生竞态条件,则称它们是线程安全的。
a、线程同步
b、可重入函数
(3)虚拟存储器
地址空间:非负整数地址的有序集合{0,1,2……},若地址空间中的整数是连续的,那么我们说它是一个线性地址空间。主存中的每一个字节都有一个选自虚拟地址空间的虚拟地址和选自物理地址空间的物理地址。
物理地址:出现在CPU外部地址总线上的寻址物理内存的地址信号,是地址变换的最终结果。计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每一个字节都有一个唯一的物理地址。如下是早期的物理寻址-->
逻辑地址: 程序代码经过编译后在汇编程序中使用的地址。
虚拟地址:现代处理器使用的是虚拟寻址,cpu生成一个虚拟地址,通过MMU(存储器管理单元),利用存放在主存中的查询表来动态翻译虚拟地址,如下--->
虚拟存储器作为缓存(VM):它被组织成为一个存放在磁盘上的N个连续的字节大小单元组成的数组,数组的内容被缓存到主存中。VM系统通过将虚拟存储器分割为称为虚拟页的大小的块来处理这个问题;同样,物理存储器也被分为物理页的大小。
虚拟页面的集合分为三个不相交的子集,未分配的(VM系统还未创建的页,不占用任何磁盘空间)、缓存的(当前缓存在物理存储器中的已分配页)、未缓存的(没有缓存在物理存储器中的已分配页)。
页表:将虚拟页映射到物理页
有时我们发出的虚拟地址对应的物理地址是缓存的,则直接页命中。
有时我们发出的虚拟地址对应的物理地址是未缓存的的,则产生缺页。如下图vp3不存在于物理存储器中。
此时,我们需要使用页面调度算法来调度,本例调度了vp4作为牺牲页,并从磁盘上用vp3的拷贝取代它。
(4)死锁
死锁产生的4个必要条件:资源有限、持有等待、不能抢占、循环等待
死锁应对的方法:1、不予理睬(除过高可靠系统和实时控制系统)2、死锁检测与修复3、死锁的动态避免4、死锁的静态防止(即消除死锁发生的必要条件)
经典问题:哲学家就餐
解决哲学家就餐方法------>(用到上述第四种方法和第三种)1、杜绝循环等待条件,对筷子编号,拿筷子的人必须按照顺序拿;2、杜绝保持并等待:要求同时拿起两根筷子,要么一根也不拿;3、动态避免:在哲学家拿起这个筷子时,判断他是否可以拿这根筷子,判断的方式是如果有哲学家在吃饭或者发放筷子后还有多余的筷子,则允许拿起,否则拒绝;
3、并发和并行
并发:一个同时具有多个活动的系统
并行:用并发使一个系统运行地更快,利用每一个处理机来执行一个并发程序
4、页式内存管理
内部碎片:已经被分配出去,能明确指出是属于哪一个进程,却不能被利用的内存空间。
外部碎片:还没有被分配出去,但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
页:将虚拟内存与物理内存都分成大小一样的部分,称之为页,按页进行内存分配,就会克服外部碎片的问题。
1)内存管理单元完成将cpu发出的虚拟地址转变为物理地址:
MMU是通过查页表完成地址翻译过程,页表的内容也很丰富,如下图:
而MMU最主要的工作时完成地址翻译过程,详细如下图:
2)多级页表:若使用两层页表,则有如下:
它占用的内存空间少,因为大部分次级页表会放在磁盘上;但是多级页表有缺点,它降低了系统的速度,因为每次访问都变成了多次内存访问。
3)缺页中断:若cpu发出的虚拟地址对应的页面不在物理内存,就产生一个缺页中断。
处理:缺页中断服务程序将负责将需要的虚拟页面找到并加载到内存中。根据产生缺页中断的虚拟地址计算出该地址在缺页中断服务程序所对应的源程序中的位移量,然后要求文件系统在这个位移量的地方进行文件读操作,读够一个页面的数据并将其加载到物理内存。
4)内存抖动:在更换页面时,若更换的页面是一个很快会被再次访问的页面,则在此缺页中断后,很快又会产生新的缺页中断。由于磁盘访问速度大大低于内存访问速度,因此这种现象会造成整个系统的效率急剧下降,我们称此种现象为内存抖动。
5)页面更换算法:
a、随机更换算法:产生一个随机页面号,与该页面对应的物理页面将被替换。
b、先进先出算法:更换最早进入内存的页面,实现机制是使用链表将所有在内存的页面按照进入时间的早晚链接起来,每次置换链表头上的页面
c、第二次机会算法:
d、时钟算法
e、LRU算法(最近最少使用的):不仅仅看页面最近是否使用过,还要看最近使用的频率。
5、段--页 式内存管理
(1)段式内存管理:它可以解决分页系统的共享困难,段管理下物理地址生成示意图:
(2)段页式内存管理: