操作系统进程线程复习
程序顺序执行特征
顺序性:按照程序结构所指定的次序执行
封闭性:独享计算机所有资源
可再现性:初始条件相同则结果相同
程序并发执行特征
间断性:并发程序具有“执行—-暂停——执行”这种间断性的活动规律。
非封闭性:多个程序共享资源
不可再现性:在初始条件相同的情况下,程序执行结果取决于执行次序
竞争定义多个程序在读写一个共享数据时结果依赖顺序。所以如果不依赖顺序,只是读写共享数据也不能说它是竞争。
判断——Bernstein条件定义
$$R(SI)$$
SI的读子集,代表着进程SI需要读的资源
$$W(SI)$$
SI的写子集,代表着进程SI需要写的资源
条件两个进程S1和S2可并发,当且仅当下列条件同时成立:
$$\eqalign{
& R(S1) \cap W(S2) = \emptyset \cr
& W(S1) \cap R(S2) = \emptyset \cr
& W(S1) \cap W(S2) = \emptyset \cr} $$
不然就会发生竞争,运行结果将不确定。
其他定义
临界资源:一次只能允许一个进程访问的资源叫临界资源
临界 ...
操作系统内存管理方式复习
前置知识大小尾端大尾端所谓的大端模式,就是高位字节排放在内存的低地址端,低位字节排放在内存的高地址端。所谓的小端模式,就是低位字节排放在内存的低地址端,高位字节排放在内存的高地址端。举个例子,比如对于0x12345678
大端模式:
$$\eqalign{
& address:00 \cdot 01 \cdot 02 \cdot 03 \cr
& thValue:12 \cdot 34 \cdot 56 \cdot 78 \cr} $$
小端模式:
$$\eqalign{
& address:00 \cdot 01 \cdot 02 \cdot 03 \cr
& thValue:78 \cdot 56 \cdot 34 \cdot 12 \cr} $$
记忆方式
记忆一:地址从低到高,符合一般认知的数字排列方式是大端。
记忆二:小段高位对高地址,低位对低地址。这个真的很重要!期末必考,我说的!
作业作业是用户需要计算机完成的某项任务,是要求计算机所做工作的集合。进程进程包括程序和程序处理对象(数据集),是一个程序对某个数据集的执行过程。程序程序是静止的, ...
操作系统内存管理复习
存储器(非重要)DRAM(动态存储器)和SRAM(静态存储器)的对比
分类
RAM: Random Access Memory
SRAM
DRAM
SDRAM,DDR SDRAM
ROM: Read Only Memory
PROM,EPROM,EEPROM
Flash memory(SSD)
Nor
NAND
Disk(磁盘)
Tape(磁带)
GCC包含的几个工具
CC1 : 预处理器和编译器
as : 汇编器
collect2 : 链接器
程序装入、执行的过程一般要经历预处理、编译、链接、重定位、装入。
链接
重定位重定位分为静态重定位和动态重定位。
装入流程
ELF头魔数检验
找到段表项
根据段表项解析出各个段应当被加载到的虚地址,在文件中的偏移。
正式加载每一段,分配物理页面,并按虚地址映射。
用0填充内存和文件大小不匹配的区域
改PC为入口地址
开始执行
段我们只需要了解bss段,data段和text段。bss:用来存放程序中未初始化的全局变量的一块内存区域。bss是英文Block Started by Symbol的简称。 ...
操作系统启动复习
MIPS全流程图(框选为流程中谁占有CPU)
文字注解GPT解释
BootLoader解释一BootLoader是Booter和Loader的合写:Booter要初始化系统硬件使之运行起来,至少是部分运行起来。Loader将操作系统映像加载到内存中,并跳转到操作系统的代码运行。
解释二BootLoader都分为stage1和stage2两大部分:
依赖于cpu体系结构的代码(如设备初始化代码等)通常都放在stage1且可以用汇编语言来实现;
stage2则通常用C语言来实现,这样可以实现复杂的功能,而且有更好的可读性和移植性;
将内核加载到内存也是在这一阶段完成的。我们见到的U-Boot就是BootLoader的具体一种。
引导操作系统(Linux)这一部分对应流程图中第二个方框,在BootLoader加载内核镜像到内存后,控制权交给操作系统,Bootloader结束工作,操作系统开始进行自初始化。
具体流程一阶段
二阶段
总结经历过流程图中的启动,在mips上的启动就已经完全完成了。
X86全流程图
文字注解GPT解释GPT这里有点问题,就是BootLoader的位置,详情看注 ...
操作系统引论复习
操作系统定义OS课程定义操作系统是一组管理计算机硬件资源的软件集合,它向计算机程序提供共性的服务。
王道定义操作系统是指控制和管理整个计算机系统的硬件与软件资源,合理的组织、调度计算机的工作与资源的分配,进而为用户和其他软件提供方便接口与环境的程序集合。
区别最大的区别在于OS课程没有强调操作系统同时管理软件资源,软硬件资源合称计算机资源软件资源指为方便使用计算机和提高使用效率而组织的程序以及用于开发、使用和维护的有关文档。软件系统可分为系统软件和应用软件两大类资源。
操作系统定位
操作系统是计算机系统中最基本的系统软件,也就是它的本质仍为软件。
操作系统管理硬件、为上层提供统一接口从而方便使用、并提供保护(内核态)。
操作系统特征并发,共享,虚拟,异步。并发指的是宏观上两个或多个事件在同一时间间隔内发生,实际上,对于单CPU环境,每一时刻只能有一个程序执行。但在宏观上好像在同时执行,称为并发。并行指的是在每一时刻都有两个或多个事件在同时发生,这是真正的同时进行。把在一段时间内只允许一个进程访问的资源称为临界资源。
操作系统功能计算机系统资源的管理者
处理机管理
存储器管理
设 ...
Manacher算法
这个算法应用在日常中还是比较常见使用的,但不知道为什么很少人讲这个算法,至少在我的身边是这样。
问题引入给定如下序列,求其最长回文子串的长度
$${\rm{a}}baccabd$$
没错,Manacher就是解决这种最长回文字串的问题,其时间复杂度为O(n)。暴力解法时间复杂度为O(n^2)。双指针解法时间复杂度为O(n^2)。动态规划解法时间复杂度为O(n^2)。现在知道选谁了吧(
算法学习处理输入解释说明先看两个回文串的例子:
$$aabbaa$$
这个回文串的中心位置在两个B的中间,我们叫它虚对称轴。
$$aabaa$$
这个回文串的中心位置在B,我们叫它实对称轴。在任何给定的回文串中,都可能会出现这两种情况,处理第二种情况显然是比较轻松的。第一种则比较复杂,那么为了处理方便,我们可以把任意给定的字符串的虚对称轴实化:
$$a*a*b*a*a$$
即用一个符号显式表示出虚对称轴,这样,我们就将第一种情况归一化到了第二种情况,处理时候只处理第二种情况即可。需要注意,我们在两个字符之间插入“*”会导致字符串整体扩大2倍,所以最后的答案要/2。
代码演示123456789publi ...
贝叶斯估计
这是北航由刘雪峰老师讲授的信号处理与信息推断课程,本人根据老师PPT在期末复习时总结如下,如有侵权,立刻删除。在这里也鼓励计算机学院的大家去选这门课,真的对人生很有帮助。
前置知识信息推断信息推断是指从观察到的现象、推测出现象背后隐藏的信息。即从表象推本质,这显然是很难做到准确的,因为内因与外在不是一一对应的,且千人千面。
错误的信息推断黑白思维定义一件事情发生的原因只有一个,而且是我认为的那个,在此期间我只会找能加强我认为的原因的证据来确信想法。
问题
事情发生的原因不止一个
证据是没有用的,你只找加强你自信心的证据
较好的信息推断概率思维定义找到一件事情背后尽可能的原因,搜集尽可能的数据,来给原因给予概率,找最大的原因作为最终的原因。
好处
不会遗漏原因
证据有用,用来调整概率
信息量大(搜集了全面的证据)
最大似然估计定义对于一件事情列举所有可能的原因,找到每一个原因产生该事实的概率,选择概率最大的原因作为结论,即最有可能产生该现象的原因。
地位这是概率思维的具体体现
特点
好处自然是概率思维的好处
缺陷:忽略了这个原因本身发生的可能性,可能会导致结论出错。
举例坐在飞 ...
CPU扩展设计——分支预测
写在开头本文为笔者学习《超标量处理器设计》的一些理解,请学习时结合本书食用~超标量处理器设计分享
概述考虑我们在计组设计中未曾考虑的问题:如果跳转指令成功跳转,选择默认不跳转的我们需要清空流水线前面的指令,这种清空被称为跳转惩罚。但由于我们的设计是五层流水线,跳转级在第二级,我们只需要引入延迟槽,便不需要清空流水线前面的指令,使得这个问题得到了解决。
但现代CPU设计具有以下的特点:
流水线的深度往往较深,可以达到十几级,一次清空就要被浪费掉许多条指令。
流水线的设计采用超标量设计,一次取指取到大于等于两条指令。
处理器高并行。
这样的特点导致了这种惩罚已经不是可以通过延迟槽避免的了,并且单次惩罚损失10+条指令。
并且在现代编程中,if,for,while这些语句的出现并不稀奇,所以这种频繁的惩罚是我们不能接受的,我们就需要对跳转进行尽力的预测,让CPU的实际运行尽力接近于我们的预测,这就引入了今天的设计——分支预测。
预测内容方向我们需要预测现在摆在我们面前的这条分支语句会不会发生跳转。
目标地址我们需要预测现在摆在我们面前的这条分支语句如果真跳了,会跳到哪里?这里可能有一个 ...
Unix 记忆留存 (三)
这是该系列第三篇,也是最后一篇
前言本篇博客是笔者在学习Unix课程时所积累的学习笔记。希望对后来学习Unix的友友复习准备Unix的期末考试有帮助。
系统调用文件I/O引言基本文件I/O函数:open、creat、read、write、lseek、close术语:不带缓冲的I/O(指每一个read、write都调用内核中的一个系统调用),低级例程。
文件描述符一个非负的整数,一个结构数组的下标,进程打开的文件表项的下标。open、creat函数会返回一个文件描述符文件描述符0、1、2默认打开,分别对应于标准输入(键盘)、标准输出(显示器)、标准错误输出(显示器)文件。在unistd.h中定义为STDIN_FILENO、STDOUT_FILENO、STDERR_FILENO
函数介绍open#include <fcntl.h>int open(const char *pathname, int oflag, [mode_t mode])返回值:若成功,返回非负整数,即文件描述符。一定是当前“进程文件描述符表”中最小未使用的描述符。出错返回-1。pathname:常量,文件 ...
Unix 记忆留存 (二)
这是该系列第二篇。
前言本篇博客是笔者在学习Unix课程时所积累的学习笔记。希望对后来学习Unix的友友复习准备Unix的期末考试有帮助。
UNIX体系结构
Shell编程意义1.将一些有用的命令组合变成实用工具。例如:12345ls -l | sed -n '/^d/p' //显示当前目录下的子目录$ vi lsdir //用vi打开lsdir$ sh lsdir //执行lsdir脚本$ chmod +x lsdir //为lsdir赋予执行权限$ PATH=$HOME/bin:$PATH //修改路径2.快速编写一些实用的软件例如写一个自己的cat命令:1234$ vi mycat //用vi打开mycat文件awk '{print NR, ": ",$0}' $1 //$1 为shell命令的第1个参数$ chmod +x mycat // ...