2018-05-23 17:36:13 u011955067 阅读数 279
  • 机器学习之概率与统计推断

    本课程讲解机器学习算法所需概率和统计推断知识。概率部分包括概率公理及推论、条件概率、贝叶斯公式、随机变量及其概率函数(CDF/pdf)、常用概率分布及其均值、方差;统计推断部分包括大数定律和中心极限定理、极大似然估计、贝叶斯估计,估计的评价、偏差-方差平衡。课程还会讲解假设检验的基本概念。

    20162 人正在学习 去看看 AI100讲师

现代操作系统(三)

三.内存管理

分层存储器体系:MB级别的快速、昂贵、易失的高速缓存(cache);GB级别的速度与价格适中、易失的内存;TB级别的低速、廉价、非易失的磁盘存储;USB等可移动存储设备
操作系统中管理分层存储器体系的部分称为存储管理器

无存储器抽象

直接访问物理内存,所以想在内存中同时运行两个程序是不可能的,因为新的程序会覆盖前一个程序在相同位置的所有内容

在不使用存储器抽象的情况下运行多个程序
操作系统只需要把当前内存中所有内容保存到磁盘中,然后把下一个程序读入到内存中再运行即可。只要在某一个时间内存中只有一个程序,那么就不会发生冲突
特殊硬件在没有交换功能情况下,也可以并发运行多个程序,只是需要静态重定位(将加载地址加到每一个程序地址上,会减慢加载速度)

一种存储器抽象:地址空间

1.地址空间的概念
地址空间是一个进程可用于寻址内存的一套地址集合,每个进程都有一个自己的地址空间,并且这个地址空间独立于其他进程的地址空间(除了共享空间)

基址寄存器和界限寄存器
动态重定位:简单地把每个进程的地址空间映射到物理内存的不同部分
每个CPU都配置基址寄存器和界限寄存器
当一个程序运行时,程序的起始物理地址装载到基址寄存器,程序的长度装载到界限寄存器
每次一个进程访问内存,CPU硬件会在把地址发送到内存总线前,自动把基址值加到进程发出的地址值上;同时,它检查程序提供的地址是否大于等于界限寄存器的值
缺点:每次访问内存都需要进行加法和比较运算

2.交换技术
把一个进程完整调入内存,使该进程运行一段时间,然后把它存回磁盘。空闲进程主要存储在磁盘上,所以当他们不运行时就不会占用内存
内存紧缩
交换在内存中产生了多个空闲区,通过把所有的进程尽可能向下移动,有可能将这些小的空闲区合成一大块。但是会耗费大量CPU时间
进程运行时增长
当换入或者移动进程时,为它分配额外的内存(换出到磁盘时,只交换进程实际使用的内存中的内容)
如果有两个可增长的段,一个自上向下增长,一个自下向上增长,在这两者之间可以供这两个段使用

3.空闲内存管理

1)使用位图的存储管理
每个分配单元对应于位图中的一位
分配单元的大小是一个重要的设计因素。分配单元越小,位图越大
缺点:在决定把一个占有K个分配单元的进程调入内存时,存储管理器必须搜索位图,在位图中找到有K个连续的0串,比较耗时

2)使用链表的存储管理
链表中每个结点都包含以下域:空闲区或者进程的指示标志、起始地址、长度和指向下一个结点的指针
首次适配算法:存储管理器沿着段链表进行搜索,直到找到一个足够大的空闲区,然后分成一部分供进程使用,另一部分形成新的空闲区。速度很快,尽可能减少搜索链表节点
下次适配算法:类似首次适配算法,不同点在于每次找到合适的空闲区时都记录当前的位置,以便下次寻找空闲区时从上次结束的地方开始搜索,而不用从头开始搜索。性能略低于首次适配算法
最佳适配算法:搜索整个链表,找出能够容纳进程的最小的空闲区。试图找出一个最接近实际需要的空闲区,以最好的匹配请求和可用空闲区。性能比首次适配算法要慢,而且会浪费更多的内存(因为会产生大量无用的小空闲区)。如果进程和空闲区使用不同的链表,则可以按照大小对空闲区链表排序,以便提高最佳适配算法的速度
快速适配算法:他为那些常用大小的空闲区维护单独的链表。寻找一个指定大小的空闲区十分快速,但是和所有按大小排序的方案一样,有一个共同缺点——在一个进程终止或者被换出时,寻找它相邻块并查看是否可合并的过程都是耗时的。如果不进行合并,内存将很快分裂出大量进程无法使用的小空闲区

虚拟内存

基本思想:每个程序拥有自己的地址空间,被分割成许多块,每一块称为一页或页面。每一页有连续的地址范围。这些页被映射到物理内存,但不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件执行必要的映射;当程序引用到一部分不在物理内存的地址空间时,由操作系统将缺失的部分装入物理内存并重新执行失败的指令

分页
由程序产生的地址称为虚拟地址,它们构成了一个虚拟地址空间。在没有虚拟内存的计算机上,系统直接将虚拟内存送到内存总线上,读写操作使用具有同样地址的物理内存字;在使用虚拟内存的情况下,虚拟地址不是被直接送到内存总线上,而是被送到内存管理单元(MMU),MMU把虚拟地址映射为物理内存地址

虚拟地址空间按照固定大小划分成为页面,物理内存中对应的单元称为页框
RAM和磁盘之间的交换总是以整个页面为单元进行的
在实际的硬件中,会有异味用来记录页面在内存中的实际存在情况
当加载未映射的页面:MMU注意到该页面并没有被映射,于是CPU陷入到操作系统,这个陷阱成为缺页中断或者缺页错误,操作系统找到一个很少使用的页框并把它的内容写入磁盘,随后把需要访问的页面读到刚才回收的页框中,修改映射关系,然后重新启动引起陷阱的指令

页表
虚拟地址被分为两部分:虚拟页号(高位)和偏移量(低位)
虚拟页号可用作页表的索引,用来找到该虚拟页面对应的页表项。由页表项可以找到页框号,然后把页框号拼接到偏移量的高位端,以替换掉虚拟页号,形成送往内存的物理地址
页表的目的是把虚拟页面映射成页框

页表项的结构

阴影 高速缓存禁止位 访问位 修改位 保护位 在/不在位 页框号

最重要的是页框号,映射的目的就是找到这个值
在/不在位:1表示有效可以使用;0表示不在内存,会引起缺页中断
保护:指出一个页允许什么类型的访问
修改:在写入一个页面时自动设置;如果一个页面被修改过,则必须写回磁盘
访问:帮助操作系统在缺页中断时选择要淘汰的页面
最后一位用于禁止高速缓存

加速分页过程
虚拟地址到物理地址的映射必须非常快
如果虚拟地址空间很大,页表也会很大

转换检测缓冲区
基于这样一种观察:大多数程序总是对少量的页面进行多次的访问
所以设计出一种小型的硬件设备,将虚拟地址直接映射到物理地址,而不必直接访问页表,称为转换检测缓冲区(TLB)或者是相联存储器、快表

软件TLB管理

针对大内存的页表
多级页表:通过分级的方式避免把全部的页表都保存在内存中
倒排页表:实际内存中的每个页框对应一个表项,而不是每个虚拟页面对应一个表项,缺点是从虚拟地址到物理地址的转换会变得很困难,同样使用TLB解决困难

页面置换算法

最优页面置换算法
在缺页中断发生时,有些页面在内存中,其中有一个页面(包含紧接着的下一条指令的那个页面)将很快被访问,其他页面也可能在10、100、1000条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。
最优页面置换算法规定应该置换标记最大的页面

最近未使用页面置换算法(Not Recently Used)
随机的从类编号最小的非空类中挑选一个页面淘汰。优点在于易于理解和能够有效被实现,虽然性能不是最好的。
使用R位和W位:当启动进程时,它的所有的页面的两个位都被设置为0,R位被定期的(比如每次时钟中断时)清零,以区分最近没有被访问的页面和被访问的页面

先进先出页面置换算法
由操作系统维护一个所有当前在内存中的页面的链表,最新进入的页面放在表尾,最早进入的页面放在表头。当发生缺页中断时,淘汰表头的页面并把新调入的页面放在表尾

第二次机会页面置换算法
对先进先出算法进行改进,检查最老页面的R位。如果R位是0,那么这个页面既老又没有被使用,可以立刻置换掉;如果是1,就将R位清0,并把该页面放在链表的尾端,修改它的装入时间就像刚装入的一样,然后继续搜索
第二次机会算法就是寻找一个最近的时钟间隔内没有被访问过的页面

时钟页面置换算法
一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中,一个表针指向最老的页面。当发生缺页中断时,算法首先检查表针指向的页面,如果它的R位是0就淘汰该页面,并把新的页面插入这个位置;如果R位是1就清除R位并把表针前移一个位置。如此重复。

最近最少使用页面置换算法(Least Recently Used)
在缺页中断发生时,置换未使用时间最长的页面

用软件模拟LRU
一种可能的方案是NFU(Not Frequently Used,最不常用)算法。该算法将每个页面与一个软件计数器相关联,计数器的初值为0。每次时钟中断时,由操作系统扫描内存中所有的页面,将每个页面的R位加到它的计数器上。这个计数器大体上跟踪了每个页面被访问的频繁程度。发生缺页中断时,则置换计数器值最小的页面。该算法的主要问题在于从来不忘记任何事情

优化:使用老化算法。首先在R位被加进之前先将计数器右移一位;其次。将R位加到计数器最左端的位而不是最右端的位。发生缺页中断时,将置换计数器值最小的页面。

工作集页面置换算法
请求调页策略:页面是在需要时被调入的,而不是预先装入
局部性原理:在进程运行的任何阶段,它都只访问较少的一部分页面
一个进程正在使用的页面的集合称为它的工作集。如果整个工作集都被装入到了内存中,那么进程在运行到下一阶段之前,不会产生很多缺页中断。
若每执行几条指令就发生了一次缺页中断,那么就称这个程序发生了颠簸。
跟踪进程的工作集,以确保在让进程运行以前,它的工作集就已经在内存中。该方法称为工作集模型,其目的在于大大减少缺页中断率。在进程运行前就预先装入其工作集页面也称为预先调页。工作集是随着时间变化的

工作集时钟页面置换算法

分页系统中的设计问题

局部分配策略和全局分配策略
局部算法可以有效地为每个进程分配固定大小的内存片段。全局算法在可运行进程之间动态的分配页框,因此分配给每个进程的页框数也是随时间变化的
负载控制
一些进程需要更多的内存,但是没有进程需要更少的内存。在这种情况下,没有方法能够在不影响其他进程的情况下满足那些需要更多内存进程的需要。唯一现实的解决方案就是暂时从内存中去掉一些进程
将一部分进程交换到磁盘,并释放他们所占有的所有页面
页面大小
内部碎片:分配的页面没有全部使用
分离的指令空间和数据空间
共享页面
只读的页面可以共享,但是数据页面不能共享
共享库
当一个共享库被装载和使用时,整个库并不是一次性的读入内存,而是根据需要,以页面为单位装载,因此没有被调用到的函数是不会被装载到内存中的
需要解决的小问题:使用相对定位
内存映射文件
进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。在多数实现中,在映射共享的页面时不会实际读入页面的内容,而是在访问页面时才会被每次一页的读入,磁盘文件则被当做后备存储
清除策略
保存一定数目的页框供给比使用所有内存并在需要时搜索一个页框有更好的性能。分页守护进程至少保证了所有的空闲页框是干净的,所有空闲页框在分配时不必急着写回磁盘
虚拟内存接口

有关实现的问题

与分页有关的工作
缺页中断处理
指令备份
锁定内存中的页面
后备存储
策略和机制的分离

分段

每个段由一个从0到最大的线性地址序列构成
因为每个段都构成了一个独立的地址空间,所以它们可以独立的增长或减小而不会影响到其他的段。段是一个逻辑实体

纯分段的实现
页面是定长的而段不是。在系统运行一段时间后内存被划分成许多块,一些块包含着段,一些则成为了空闲区,这种现象称为外部碎片

分段和分页的结合:MULTICS
一个地址由两部分构成:段和段内地址。段内地址又进一步分为页号和页内的字

  • 根据段号找到段描述符
  • 检查该段的页表是否在内存中
  • 检查所请求虚拟页面的页表项
  • 把偏移量加到页面的起始地址上
  • 最后进行读或写操作

分段和分页的结合:INTEL X86

2018-05-05 02:38:00 weixin_30348519 阅读数 23
  • 机器学习之概率与统计推断

    本课程讲解机器学习算法所需概率和统计推断知识。概率部分包括概率公理及推论、条件概率、贝叶斯公式、随机变量及其概率函数(CDF/pdf)、常用概率分布及其均值、方差;统计推断部分包括大数定律和中心极限定理、极大似然估计、贝叶斯估计,估计的评价、偏差-方差平衡。课程还会讲解假设检验的基本概念。

    20162 人正在学习 去看看 AI100讲师

看了B站上的孙老师视频,感觉太啰嗦了看完进程的看不下去了,这里给出个人总结。

1.1 推荐书籍 :
操作系统概念pdf
现代操作系统pdf
 
2.2操作系统有哪些
IOS
MacOS
Linux
Andriod
Unix
VxWorks --- 航天航空军事领域,嵌入式
FreeBSD --- 服务器,稳定
DOS --- 只能操作一个程序
 
操作系统特点:管理硬件资源
 
5.5
 

 

 
INT(汇编指令:中断):中断后进入中断服务程序(一定是操作系统编写的)
 
系统调用:应用程序执行INT指令,跳到中断服务程序(内核)
当应用程序调用open()时,转换为汇编就是INT,然后传入 系统调用编号(要调用哪个系统调用)
中断服务程序检查系统调用编号,找到程序的位置。
 
strace -- 跟踪一个程序调用了那些系统调用
 
printf()调用了write()
 
问题:C语言中函数参数传递过程
往栈中一个个压入参数,然后一个个取出
 
问题:系统调用参数传递过程
类似
 
用户态的数据只能写入用户态的内存,内核态可以直接访问用户态的内存
用户态不能直接访问内核态的内存。
 
6.6
系统程序:
磁盘分区,磁盘快照,任务管理器,资源管理器(操作文件)
 
7.7
DOS:应用程序可以不经DOS操作系统使用硬件
Solaris操作系统:
 
8.8进程管理
汇编指令:
in指令 --- 直接操作硬件端口输入
out --- 直接操作硬件端口读入
这两个指令在用户态不允许执行
 
计算机boot过程:
 

 

执行BIOS程序(ROM中)
选择存储设备(硬盘还是U盘等等)
MBR放在硬盘的第一个扇区(1到512个字节)
将MBR加载到0x7c00然后执行
 
 
进程:(内存地址:0-max)
PC和其他寄存器
代码段(指令)
数据段(编译阶段决定了的数据,比如helloworld的字符串)
 
max最大可达4G
 
进程切换 --- PCB(Precess Control Blocking)进程控制块
 
1.进程切换之前将状态(寄存器等)存入PCB中
2.操作系统内核选择下一个调度的进程
3.加载下一个进程的PCB
 
就绪PCB队列
阻塞PCB队列
 
 
 
问题1 由运行态到就绪态:进程切换之前由程序使用CPU,系统内核如何获得执行权
使用中断(时钟中断,每隔一段时间发出中断,中断服务程序 -- 操作系统)
 
问题2 由运行态到等待态 :
由程序主动进入等待态,程序调用系统调用
 
问题:需要降低进程切换的开销
硬件方面:CPU设计完成:
1.一个指令完成现场保存,比一个个PUSH快得多
2.直接换一批寄存器组
 
12 进程的创建
子进程由父进程创建
1.子进程和父进程资源完全共享 --- 嵌入式系统
2.子进程共享父进程资源的一部分 --- Unix系统
3.子进程和父进程之间没有任何关系  --- Windows
 
a 父进程子进程同时运行
b 父进程等待子进程工作完再运行
 
          1)子进程内存空间克隆父进程内存空间 --- Linux
          2)子进程从硬盘加载程序 --- Windows
 
 
 fork()  ---- 执行到fork()操作系统会在这里复制父进程,返回0给子进程返回大于0给父进程

转载于:https://www.cnblogs.com/coderlynn/p/8993467.html

2019-01-09 22:12:00 li_haoren 阅读数 114
  • 机器学习之概率与统计推断

    本课程讲解机器学习算法所需概率和统计推断知识。概率部分包括概率公理及推论、条件概率、贝叶斯公式、随机变量及其概率函数(CDF/pdf)、常用概率分布及其均值、方差;统计推断部分包括大数定律和中心极限定理、极大似然估计、贝叶斯估计,估计的评价、偏差-方差平衡。课程还会讲解假设检验的基本概念。

    20162 人正在学习 去看看 AI100讲师

进程与线程思维导图------现代操作系统(第四版)

 现代操作系统的进程与线程部分的思维导图,看不清的话,右键 在新页面中打开图片  就能放大了

 

 

 

 现代操作系统的进程与线程部分的思维导图,看不清的话,右键 在新页面中打开图片  就能放大了

posted @ 2019-01-09 22:12 ff_d 阅读(...) 评论(...) 编辑 收藏
2018-09-08 22:02:31 qq475703980 阅读数 4002
  • 机器学习之概率与统计推断

    本课程讲解机器学习算法所需概率和统计推断知识。概率部分包括概率公理及推论、条件概率、贝叶斯公式、随机变量及其概率函数(CDF/pdf)、常用概率分布及其均值、方差;统计推断部分包括大数定律和中心极限定理、极大似然估计、贝叶斯估计,估计的评价、偏差-方差平衡。课程还会讲解假设检验的基本概念。

    20162 人正在学习 去看看 AI100讲师

既然买了《现代操作系统》(《Modern Operating System》)这本书,那就好好学习一下吧,这是第一篇读书笔记。
##第一章 引论

计算机系统总的来说分为软件和硬件,如下图所示。多数计算机有两种运行模式:内核态和用户态软件中最基础的部分是操作系统, 它运行在内核态。操作系统具有对所有硬件的完全访问权限,可以执行机器能够运行的任何指令。 其他软件运行在用户态,只能使用部分机器指令。特别指出,哪些会影响极其的控制或可进行I/O操作的指令,在用户态中的程序是禁止的。 无法直接运行指令,则只能通过操作系统提供的接口来达到目的。

操作系统由硬件进行保护,防止用户试图对其进行修改。

大家都操作过Windows、Linux等操作系统,感觉这是不是就是操作系统? 这些与用户交互的程序,实际上并不是操作系统的一部分,经它们使用操作系统来完成工作,基于图标的称为图形用户界面(GUI, Graphical User Interface),我们所用的Windows就是这种,可以看到各种图标; 基于文本的则通常称为shell, 比如我们在Windows中使用cmd命令, 或者在Ubuntu中是Xshell等软件程序。

不过,在嵌入式系统(没有内核态)或解释系统(如基于Java的操作系统,它采用解释方式,而非硬件方式区分组件), 上述划分的边界是比较模糊的。

在这里插入图片描述

1.1 什么是操作系统

操作系统是一种运行在内核态的软件,但这个说法并不总符合事实, 不过操作系统概括起来主要有两个作用:

  • 1.为应用程序(程序员)提供资源集的清晰抽象
  • 2.管理硬件资源

第二点好理解, 第一点用大白话说就是给上层提供相应的接口或者方法, 让上层应用程序可以使用资源。

另外,对于操作系统的理解,从不同角度看的,有不同的定义,

自顶向下看:操作系统为应用程序提供基本抽象,从而使应用程序在此基础上可以组合功能。

自底向上看:操作系统用来管理复杂系统的各个部分,对资源的请求进行分配,调节不同程序见相互冲突的资源请求。其中, 资源的管理有两种不同方式实现多路复用(共享)资源:时间上复用和空间上复用

  • 时间上复用:当一种资源在时间上复用时,就是不同程序或者用户轮流使用它,大家排队使用。CPU就是这种操作, 一个位置,大家轮流坐
  • 空间上复用:每个程序都得到资源的一部分,就不用排队了,这就是多个位置,一人坐一个。内存就是这样分配。
  • 两种方式的公平和保护问题,由操作系统解决

1.2 操作系统的历史

第一代:真空管和穿孔卡片

第二代:晶体管和批处理系统

第三代:小规模集成电路和多到程序设计

第四代:个人计算机(大规模集成电路)

第五代:移动计算机(手机、平板等)

1.3 计算机硬件简介

####1.3.1处理器

先附图,所有设备都是通过总线连接的:

在这里插入图片描述

相当于计算机的大脑,从内存中取出指令并执行。每个CPU都一套可执行的专门指令集。所以x86不能执行ARM程序,ARM处理器也不能执行x86程序。

CPU内部有一些用来保存关键变量和了临时数据的通用寄存器、还有一些专用寄存器,如程序计数器(PC)、堆栈指针寄存器(指向当前内存中栈顶位置)、程序状态字寄存器(Program Status Word, PSW, 包含了条件码位、CPU优先级、内核态/用户态等控制位)。

CPU取出指令执行的机制,是通过内部的取指单元、解码单元、执行单元三部分完成。为了提高效率。现在CPU通常可以同时取出多条指令。当CPU执行指令n时,它可以正在对指令n+1解码,并读取指令n+2,这样,当执行完指令n后,无需等待,就可以直接执行n+1,然后n+2,这样的机制,称为流水线(pipeline)

在这里插入图片描述

intel和AMD的不同CPU设计:
在这里插入图片描述

1.3.2 存储器

典型的存储层次结构及其一个大概的访问时间如下:
在这里插入图片描述

存储系统的顶层是CPU中的寄存器,它用和CPU一样的材料制成,和CPU一样快,访问没有时延。其典型的存储容量:32位CPU为32x32位,在64位CPU中为64x64位

下一层次为高速缓存,CPU读取数据时,如果数据在高速缓存行中,则成为高速缓存命中。提升高速缓存命中有利于提升效率。

1.3.3磁盘

磁盘同RAM相比,每个二进制位的成本低两个数量级以上,所以容量大且便宜,但是读取速度低。

下图是常见的机械硬盘结构:

在这里插入图片描述
在这里插入图片描述
在一个磁盘中有一个或多个金属盘片,一个盘片的两面都可以记录数据,每个面都分为了很多同心圆,一个同心圆又被分为了很多少区,每个扇区的典型大小为512字节.然后如图所示,每个盘又分为了很多柱面(或称为扇面)。

每个盘面都有读写头用来读写数据。机械臂从一个柱面移动到相邻的柱面大约需要1ms,而随机移动到某一个柱面的典型时间为5-10ms。

1.3.4 I/O设备:

I/O设备就是输入输出设备,比如键盘、鼠标、打印机、硬盘灯。I/O设备一般包含两部分:设备控制器和i/o设备本身。控制器是插在电路板上的一块或一组芯片。

每一类设备控制器都是不同的,需要不同的软件进行控制,专门与控制器对话,发出命令并接收响应的软件,叫做设备驱动程序(device driver).

实现输入输出有三种方式。第一种,用户程序发出一个系统调用,然后就执行I/O过程,CPU一直等待I/O的数据,直到得到数据后处理,处理完以后返回结果,CPU才继续处理其他事情。这种方式称为忙等待。

第二种是通过中断机制,需要I/O时,先让I/O设备执行对应操作,这个时候CPU不需要等待,继续做其他事情,如果I/O执行完,拿到数据了,这个时候由中断控制器对CPU发起一个中断,处理这个I/O得到的数据。大白话就是先让CPU处理其他事情,当得到I/O数据后,告诉CPU,你先停一下现在手头上的事儿,你刚刚要的数据准备好了,现在给你,你处理下。

第三种,使用直接存储器访问芯片(DMA,Direct Memory Access),直接控制位流,DMA得到数据时,也会对CPU发起中断。

1.3.5 总线

总线就是CPU连接其他设备的线,各种设备间的数据传输通过总线完成。刚开始那张示例图已经展示了,现在再来张 总的示例图:

在这里插入图片描述

1.3.6 启动计算机(的过程)

通电后,系统首先启动BIOS里面的程序, BIOS全称基本输入输出系统(Basic Input Output System), 内部包含了一下基本的参数设置,以及接下来要启动的程序,从而把系统启动起来。

1.4 操作系统大观园(各种操作系统)

操作系统有很多,主要有:大型机操作系统、服务器操作系统、多处理器操作系统、个人计算机操作系统、掌上计算机操作系统、嵌入式操作系统、传感器节点操作系统、实时操作系统、智能卡操作系统。

1.5 操作系统概念

操作系统中有很多基本概念和抽象,它们是需要理解的核心内容,主要有:进程、地址空间、文件、I/O(输入输出)、保护、shell.

1.5.1 进程

进程:进程的本质是正在执行的一个程序。可以简单理解一个进程就是一个程序,但有时,一个程序包含多个进程。进程是对CPU处理器的一个抽象概念,可以把进程看做一个资源调度的集合,通常包含的资源有:寄存器(程序计数器和堆栈指针)、打开文件的清单、突出的警报、有关进程的清单以及程序需要的其他信息。

1.5.2 地址空间

计算机的主存用来保存正在执行的程序,为了找到程序在主存(也就是内存)的位置,物理内存设置了对应的地址编号,地址编号的一个集合就是地址空间。 物理地址空间是有限的,这是设备决定的,不过有虚拟地址空间技术。地址空间这个概念其实就是对内存的一个抽象,用来方便管理内存及进程。

1.5.3 文件

文件这个概念的抽象是为了描述数据的集合,这个比较好理解。在现实中的文件其实就是某些资料装订在了一起,这些资料通常保存的也是某些数据(文字、图表等)。

1.5.4 I/O(输入输出)

主要是指输入输出设备,通过这些设备来输入或输出数据, 比如键盘、打印机等。键盘输入字母,就可以在硬盘或者其他位置输出文字。

1.5.5 保护

计算机有大量信息,用户希望对其进行保护。对一个文件来说,通常有三种状态,可读(只能读取,不可修改),可写(只能写入,不可读出),可读可写。

1.6 系统调用

先简单了解下系统调用的流程,下图是调用一个read方法的过程:

在这里插入图片描述

然后是一些常用的调用函数:

在这里插入图片描述

1.7 操作系统结构

1.7.1 单体系统

整个操作系统以单一程序的方式运行,所有过程链接成一个大型可执行二进制程序

1.7.2 层次式系统

整个系统分了很多层,每一层都进行一些封装,再给上一层次调用,从而可以加入一些限制进行保护。

1.8 依靠C的世界

操作系统通常都是c语言(或者c++)写的。

2018-09-08 22:05:50 qq475703980 阅读数 1592
  • 机器学习之概率与统计推断

    本课程讲解机器学习算法所需概率和统计推断知识。概率部分包括概率公理及推论、条件概率、贝叶斯公式、随机变量及其概率函数(CDF/pdf)、常用概率分布及其均值、方差;统计推断部分包括大数定律和中心极限定理、极大似然估计、贝叶斯估计,估计的评价、偏差-方差平衡。课程还会讲解假设检验的基本概念。

    20162 人正在学习 去看看 AI100讲师

#第四章 文件系统

在多程序多用户的系统上,读取数据有以下问题:

  • 如何找到信息?
  • 如何防止一个用户读取另一个用户的数据
  • 如何知道哪些块是空闲的?

通过前面的学习, 我们知道 操作系统对处理器进行抽象 建立了进程这个概念; 通过对物理存储器的抽象建立了 虚拟地址空间的概念, 现在,为了解决问题, 就创建了 文件 这个抽象概念。

操作系统处理文件的部分 称为文件系统

4.1文件

文件命名:如homepage.html, 圆点前面是名字,圆点以后是文件扩展名,.html表示 这是一个html文件。在某些系统中,文件扩展名是一种约定,指定为某一类文件,但是操作系统并不强制采用这种形式,常见扩展名如下:

在这里插入图片描述

文件结构:常见三种方式:

  • 无结构字节序列:全都是字节,其内容含义只有在用户程序中解释,UNIX和Windows都采用这种方法
  • 记录序列:这种结构中,文件时有固定长度记录的序列,每个记录尤其内部结构
  • 树:文件由一颗记录树构成,每个记录长度不一,每个记录的固定位置有一个,通过键可以快速查找,一般在处理商业数据的大型计算机系统中使用。

在这里插入图片描述

文件类型

  • 目录(或者说文件夹):每个目录也是一种文件, 是管理文件系统结构的系统文件
  • 普通文件:一般分为ASCII文件和二进制文件。 ASCII文件的优势就是可以显示和打印, 也是普通用户常用的文件,如文本。二进制文件如视频图片等。
  • 字符特殊文件(character special file)
  • 块特殊文件(block special file)

下图是一个可执行二进制文件和一个存档普通文件的结构,可执行二进制文件的结构有:文件头、正文、数据、重定位位,符号表。

在这里插入图片描述

文件访问

  • 早期只有顺序访问
  • 随机访问:按照关键字位置来访问记录, 可以任意跳转。有两种方式指示从何处开始读取文件,一种是read操作时给出开始文件位置,另一种是通过seek操作设置访问的位置。、

文件属性:
在这里插入图片描述

文件操作: 常见操作有:create, delete,open,close,read,write,append,copy, seek,get attributes,set attributes, rename.其中seek用于随机访问文件,把当前位置指针指向文件中特定位置后,从该位置顺序读取数据。

4.2目录

文件系统通常提供目录或文件夹用于记录文件位置,通常,目录或者说文件夹本身也是文件

一级目录系统:在早期系统或者限制一些简单的嵌入式系统中,采用,目录只有一个层级,如下,方形表示目录文件,原型表示普通文件:
在这里插入图片描述

层次目录系统:多数计算机系统都采用多层次目录系统,如下:

在这里插入图片描述

路径名:在层次目录系统中,每个文件都有一个绝对路径名,它是从根目录到文件的路径,例如 /usr/ast/mailbox。不同系统的路径的分隔符不同,有 / 或者 \ 或者 > , 如下:
在这里插入图片描述

在操作系统的每个目录有两个特殊目录项: "."和“…”, 读作dot和dotdot, dot指当前目录, dotdot指父目录:

在这里插入图片描述

目录操作:常用目录操作有 create, delete, opendir, closedir, readdir, rename, link, unlink等。

4.3文件系统的实现

###4.2.1文件系统布局

文件系统放在磁盘上,多数磁盘划分为一个或多个分区,每个分区有一个独立的文件系统。磁盘的0号扇区称为主引导记录(Master Boot Record,MBR),用来引导计算机。MBR的结尾是分区表,该表给出了每个分区的其实和结束位置。表中的一个分区标记为活动分区,计算机启动时,BIOS读入并执行MBR,MBR第一件事就是确定活动分区,然后读入它的第一个块,称为引导块(boot block),然后执行它。引导块中的程序将装载该分区中的操作系统。为了统一,每个分区都从第一个引导块开始,即使它并不包含操作系统,不过也不排除它未来不会安装操作系统。

除了都是从引导块开始,不同文件系统的磁盘分区的布局是不同的,下图是一种文件系统的结构布局, 第一个是超级块(superblock),包含了文件系统的所有关键参数,在计算机启动或者该文件系统首次使用时,超级快会被读入内存,其中的典型信息有:文件系统类型使用的魔数,文件系统中块的数量以及其他重要管理信息,示例图如下:

在这里插入图片描述

4.2.2文件的实现

文件存储的关键问题是记录各个文件分别用到哪些磁盘块,主要有:连续分配、聊表分配、采用内存中的表进行链表分配,i节点。

**连续分配:**把文件作为一串连续数据块存储在磁盘上。简单且效率高,但是随着时间分配,磁盘变得零碎,如果某个连续空间比较小,而文件比较大,就不会放入这个空间,造成浪费。最终形成很多磁盘空洞,这时,如果重新挪动位置压缩磁盘空间,代价就太大了。因此,这个比较适合一次性写入的介质。

链表分配:磁盘每个块的第一个字作为指向下一个块的指针,块的其他部分存放数据。 链表不会浪费空间,但是随机访问很慢。而且由于每个块保存了指针,剩余部分存储的字节就不再是2的整数次幂,而许多程序都是以2的整数次幂读取磁盘块,这也会降低效率。

在这里插入图片描述

采用内存中的表进行链表分配:对链表分配的优化,就是把每个磁盘块的指针,存放在内存的一个表中,就可以解决链表分配的不足。当有连续块是,就可存放在连续块中,当连续块不够,就指向其余空闲的块中。内存中这样的表格称为 文件分配表(File Allocation Table, FAT)。 示例图如下:

不过这种方法的缺点就是必须把整个表存在内存中,如果磁盘很大,这个表就会特别大,因此FAT并不怎么适合大型磁盘中。

i节点:给每个文件赋予一个名字为 **i节点(index-node)**的数据结构,用来记录文件包含了哪些磁盘块。只要给定i节点,就能找到文件的所有块。这种方式的优势在于,只有文件被打开时,其i节点才在内存中,从而节省了内存。

如果每个i节点只能存储固定数量的磁盘地址,那么一个文件包含的磁盘块超过了固定数量怎么办呢? 其中一种解决办法就是最后一个地址指向一个包含额外地址的底盘块,升级版是最后两个或三个地址都可以指向其他存放地址的磁盘块,示例图:
在这里插入图片描述

4.2.3 目录的实现

要找到文件,就要根据路径名去找,路径就涉及到目录以及在何处去存放文件的属性。实现方式有两种:1.简单目录,即在目录文件中有一个固定大小的目录项列表,每个文件对应一项,,其中有(固定长度)的文件名、属性的结构体、磁盘块的位置的一个或多个地址。 2.对于采用了i节点的系统,可以把属性存放在i节点中,而不是目录项中,这样,目录项中就只需要存放文件名和i节点号了,这种方式更好。两种方式的目录项示例图如下:

在这里插入图片描述

还有另一个问题,就是文件名的长度以及文件名的保存。第一种简单的方式就是给予文件名一个固定的长度限制,同时给文件名分配固定大小的目录空间。但是如果文件名用不了这么多长度,就白白浪费了。第二种方式是 每个目录项前面部分是固定格式的数据,如目录项长度、文件属性,然后接上可变的任意长度的文件名,文件名以特殊字符(通常为0)结束。如下图图a, 这个方法的缺点就是每个文件项的大小不一,如果移走一个文件,再新来一个文件,新文件的文件项不一定刚好适合这个空隙。这和连续磁盘空隙类似。

** 第三种**方式就是目录项有一个固定长度,而将文件名放在目录后面的堆中,这样移走一个文件,下一个文件进来了,也刚好可以适合这个空隙。不过,就必须对堆进行管理。示例图如下:
在这里插入图片描述

4.3.4共享文件

![在这里插入图片描述](https://img-blog.csdnimg.cn/20190414221950615.png)

在上图中,目录C下有一个文件和目录B共享, 有两种方式,一种是链接(link),共享文件的所有者是C,但是这个文件在C的目录项的计数为2,当在C目录下去删除共享文件时, 如果共享文件发现计数为2,就不会去删除这个文件,而是把计数减1,直到计数为0,才会删除。这个或者叫硬链接。例图如下:
在这里插入图片描述

另一种方法为符号链接(symbolic linking),或者叫软连接,就是在B中新建一个文件,但这个文件只包含了链接的共享文件的路径名,可以指向共享文件。就类似于Windows的快捷方式, 指向了一个具体目录,删除快捷方式不会删除源文件。

4.3.5 日志结构文件系统

与现有文件系统不太匹配,暂未广泛 使用。

4.3.6日志文件系统

**日志文件系统:**保存一个用于记录系统下一步需要做什么的日志,这样,如果系统在即将完成任务时崩溃,重新启动后,可以通过查看日志,获取崩溃前计划完成的任务,并重新去完成它,完成后擦除日志项。

4.4 文件系统管理和优化

4.4.1 磁盘空间管理

1.块的大小, 这个通过研究曲线决定,目前最佳为64k, 如下图:
在这里插入图片描述

2.记录空闲块

一种是采用磁盘块链表,链表中每个块包含尽可能多的空闲磁盘块号。 另一种方式是采用位图,n个块的磁盘就用n位的位图,每一位表示一个块,1表示使用,0表示未使用,如下图:

在这里插入图片描述

3.磁盘配额

为防止人们贪心占用过多空间,由管理员为每位用户分配最大拥有文件和块的数量。

4.4.2 文件系统备份

为了防止文件系统被破坏,通常需要对文件进行备份。主要是为了解决两个问题:

  • 1.从以外的灾难中恢复
  • 2.从错误中恢复

同时备份文件不要防在同一个地方,应在不同的地方保存,不过又会增加安保的难度,不过这个不在讨论之列。

为文件做备份费时费空间,因此要选择有意义的目录,如临时文件目录就不用备份了。备份一些特定目录或者重要目录。

其次,对前一次备份没做更改而再去备份也是一种浪费,因此有了增量转储的思想。最简单的增量转储形式就是每周或每月做一次全面备份,而每天只需要对从上一次转储后改变的文件备份即可。不过这个回复起来比较复杂。所以通常用更复杂的增量转储方法。

第三、既然转储文件时海量的,那么需不需要压缩也应该考虑。

第四、记录文件系统的瞬时快照,赋值关键数据结构,其余留待空闲时在备份

第五、非技术性问题,注意备份文件的安保。

**物理转储:**从磁盘第0块开始,直到最后一块, 全部复制

**逻辑转储:**从一个或几个指定目录开始,递归的转储给定日期以后更改的文件及目录。

4.4.3 文件系统一致性

一种处理方法就是磁盘块计数表,使用的块和空闲的块, 加起来, 各个位都为1,否则就是一致性出错。
在这里插入图片描述

4.4.4 文件系统性能

1.高速缓存 : 块告诉缓存逻辑上属于磁盘,但实际上基于性能考虑保存在内存中。告诉缓存块的换入换出,可参考第二章的FIFO算法,LRU算法等页面置换算法。 为了防止计算机系统崩溃导致文件系统破坏,UNIX无限循环没30s调用一次sync,强制将修改过的块立即写到磁盘,这样,就算系统崩溃,丢失数据不会超过30s。

2.块提前读

提前将即将调用的块写入告诉缓存,明显可以提升执行效率。通常使用与顺序读文件。对于随机读文件,先按照顺序提前读入,即使一开始错了也没关系,然后真正通过读入的块的文件关联性,去提前加载下一个块, 从而提升命中率。

3。减少磁盘臂运动

不是有可能顺序访问的块放在一起,最好在一个柱面上,较少磁臂运动时间。

4.4.5磁盘碎片整理

定期整理磁盘,减少碎片。当然, SSD固态硬盘除外,那只会减少SSD寿命。

4.5 文件系统实例

UNIX V7 文件系统

对于大型文件,通常采用前面讲 i节点 时,图4-13使用的方法,就是最后几个地址存放的是另外的块, 快中存放的还是文件块的地址。如果文件很大,可以使用两次间接块甚至三次间接块,如下图:
在这里插入图片描述
在这里插入图片描述
例如查找目录 /usr/ast/mbox的过程,如下图,其中**.**表示当前目录的i节点号, **…**表示父目录i节点号:

在这里插入图片描述

没有更多推荐了,返回首页