操作系统磁盘复习
主引导扇区定义硬盘的0柱面、0磁头、1扇区称为主引导扇区。主引导扇区是在硬盘分区时由分区软件写入的(FDISK),因而不属于任何操作系统,所以分区时不进行操作系统引导扇区的写入。
组成前446字节为启动代码(BootLoader)后面64字节是分区表(DPT),一共可以记录4个分区。最后有2个字节是幻数,标识这是一个被分区的硬盘硬盘分区有三种,主磁盘分区、扩展磁盘分区、逻辑分区。主分区只能有一个是激活(活动)的,其余是未激活。分出主分区后,其余的部分可以分成扩展分区,一般是剩下的部分全部分成扩展分区,也可以不全分,剩下的部分就浪费了。扩展分区不能直接使用,必须分成若干逻辑分区。所有的逻辑分区都是扩展分区的一部分。
DPT表项
磁盘分类固定头磁盘磁头相对于盘片径向方向固定的,称为固定头磁盘,每个磁道一个磁头。
活动头磁盘磁头可移动的、可以来回伸缩定位磁道的,称为活动头磁盘
固定盘磁盘磁盘永久固定在磁盘驱动器内,称为固定盘磁盘。
可换盘磁盘磁盘可移动和替换的,称为可换盘磁盘。
磁盘地址与块号的转换先记忆一个知识,一个逻辑块号的大小为一个扇区的大小。一般情况下、先填满扇区、再填满磁道、再 ...
操作系统外设管理复习
外设管理目的
提高效率:通过缓存等机制,匹配CPU的速度
方便用户:统一了繁多的外设,提供了统一的访问方法
方便控制:方便OS对外设的控制
功能
提供接口
设备的分配、释放
设备的访问、控制
I/O缓存和调度设备的分配和释放是逻辑I/O,实际上与设备无关设备的访问和控制通过设备驱动程序完成,是真正的I/O
控制方式对外设的控制是通过外设提供的控制器进行的,包括控制寄存器、状态寄存器、以及一些数据的寄存器。通过读写这些寄存器我们就实现了对外设的控制
I/O分类数据组织
块设备:以数据块为单位存储、传输信息。传输速率高,可随机读写
字符设备:以字符为单位存储、传输信息。传输速率低,不可随机读写
用途
存储设备
传输设备
人机交互设备
资源分配
独占设备:同时只能由一个设备访问
共享设备:同时允许多个设备访问
虚设备:在一类设备上模拟另一类设备
设备控制器图示
功能
接受和识别CPU指令
数据交换:CPU与控制器、控制器与设备
设备状态的了解和报告
设备地址识别
缓冲区
对设备传来的数据进行差错检测
I/O硬件组成
控制器与CPU接口:数据寄存器、控制寄存器、状态寄存器
控制 ...
操作系统调度复习
调度类型图示
具体
高级调度:作业之间的调度,调度执行哪个作业,不执行哪个作业
中级调度:调度页面的换入换出
低级调度:调度进程概念积累周转时间作业从提交到完成(得到结果)所经历的时间放进去就开始计时,什么时候吐出来什么时候停止计时,至于它在里面是在被执行还是被阻塞,不管。
带权周转时间周转时间/执行时间平均周转时间作业周转总时间/作业数平均带权周转时间带权周转总时间/作业数响应时间发出请求到系统首次给出响应的时间。吞吐量单位时间内所完成的作业数这里注意吞吐量不是平均周转时间的倒数,这是由于并发执行的作业在时间上可以重叠。
进程占用CPU的方式不可抢占式一旦处理器分配给一个进程,它就一直占用处理器,直到该进程自己因调用原语操作或等待I/O等原因而进入阻塞状态,或时间片用完时才让出处理器,重新进行。注意描述,不可抢占并不代表它会从头执行到尾,只是说不会被其他进程抢占,自己作那没办法。
抢占式就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时,便立即进行进程调度,把处理器转给优先级高的进程。
批处理系统调度算法先来先服务调度对象作业、进程
定义顾名思义,谁先来拷打谁,按照来的 ...
操作系统进程线程复习
程序顺序执行特征
顺序性:按照程序结构所指定的次序执行
封闭性:独享计算机所有资源
可再现性:初始条件相同则结果相同
程序并发执行特征
间断性:并发程序具有“执行—-暂停——执行”这种间断性的活动规律。
非封闭性:多个程序共享资源
不可再现性:在初始条件相同的情况下,程序执行结果取决于执行次序
竞争定义多个程序在读写一个共享数据时结果依赖顺序。所以如果不依赖顺序,只是读写共享数据也不能说它是竞争。
判断——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在期末复习时总结如下,如有侵权,立刻删除。在这里也鼓励计算机学院的大家去选这门课,真的对人生很有帮助。
前置知识信息推断信息推断是指从观察到的现象、推测出现象背后隐藏的信息。即从表象推本质,这显然是很难做到准确的,因为内因与外在不是一一对应的,且千人千面。
错误的信息推断黑白思维定义一件事情发生的原因只有一个,而且是我认为的那个,在此期间我只会找能加强我认为的原因的证据来确信想法。
问题
事情发生的原因不止一个
证据是没有用的,你只找加强你自信心的证据
较好的信息推断概率思维定义找到一件事情背后尽可能的原因,搜集尽可能的数据,来给原因给予概率,找最大的原因作为最终的原因。
好处
不会遗漏原因
证据有用,用来调整概率
信息量大(搜集了全面的证据)
最大似然估计定义对于一件事情列举所有可能的原因,找到每一个原因产生该事实的概率,选择概率最大的原因作为结论,即最有可能产生该现象的原因。
地位这是概率思维的具体体现
特点
好处自然是概率思维的好处
缺陷:忽略了这个原因本身发生的可能性,可能会导致结论出错。
举例坐在飞 ...