poetry

烟花巷陌,依约丹青屏障。
幸有意中人,堪寻访。
且恁偎红倚翠,风流事,平生畅。
青春都一饷。忍把浮名,换了浅斟低唱。

简介

Operation System 是系统资源的管理者,在有限的资源内,通过算法,完成相对合理的分配。在复杂的硬件环境中,通过封装,完成动作指令的抽象化。这一切的基石,则是密集的数据结构和算法。

相对合理体现在:

  • 调度算法实现的低用户响应时间和紧急事件处理
  • 虚拟技术实现多用户登录
  • IO设备控制器尽可能减少CPU调度
  • 文件目录系统屏蔽了数据写入物理块的底层细节
  • 命令接口、图形接口的封装

相关概念

  • 并发:在多台处理器上同时处理多个任务
  • 并行:在一台处理器上宏观上同时处理多个任务,微观上一个时间段只处理一个任务
  • 并发进程的制约关系:同步和互斥
  • 同步:同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
  • 互斥:互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待, 当占用临界资源的进程退出临界区后,另一进程才允许去访问此临界资源。
  • 异步:异步是进程之间彼此独立,在等待其他进程的运行时,本进程继续做自己的事,不需要等待其他进程完成后再工作。
  • 临界资源:一次仅允许一个进程使用的资源
  • 管程:管程在功能上和信号量及PV操作类似,属于一种进程同步互斥工具
  • 符号链接:是文件共享的一种方式,允许一个文件或子目录有多个父目录,但其中仅有一个座位主父目录,但其他几个父目录都是通过符号链接方式与之相连。
  • 索引结点实现文件共享:在文件目录中只设置文件名以及指向相应索引结点的指针,源文件删除后,会出现悬空指针。
  • 工作集:是指在某段时间间隔 ∆ 里,进程实际要访问的页面的集合。
  • 抖动:如果多道程度过高,页面在内存与外存之间频繁调度,以至于调度页面所需时间比进程实际运行的时间还多,此时系统效率急剧下降,甚至导致系统崩溃。这种现象称为颠簸或抖动(thrashing)

相关技术

  • 虚拟技术
  • 复用技术
  • 中断技术
  • 封装技术

相关算法

  • 双标志后检查法
  • 记录型信号量机制
  • 先来先服务算法(First Come First Serve)
  • 短作业优先(Shortest Job First)
  • 高响应比优先(Highest Response Ratio Next)
  • 时间片轮转调度(Round Robin)
  • 优先级调度算法
  • 多级反馈调度算法



一个进程从被创建到终止,其中不得不说的故事

   当我们打开一个程序。这个程序就会被执行。因为CPU速度非常快,普通硬盘的读写速度跟不上CPU的速度,所以我们会把程序调入内存中执行,这样就产生了进程。

   如果我们同时打开多个应用,就会产生多个进程,在宏观上每一个进程在CPU内同时执行(并发),微观上每个进程在CPU内交替执行,同一个处理机同一时间内只能执行一个进程(并行)。

   由于人们的需求不一样,希望有些应用执行的更快一点,就此产生了进程的优先级。但在处理机调度算法中,优先级只是决定一个进程能够被分到多少运行时间的指标之一,还有其他的指标,诸如:CPU利用率(CPU忙碌的时间 / 作业被处理所需要的总时间),系统吞吐量(单位时间内完成作业的数量),周转时间(作业从被提交给系统到最后完成所用时间),响应时间(用户提出请求到首次响应所用的时间,简而言之,就是你点击一个应用,系统过了多个才给你打开),这些也是衡量一个处理机调度算法优劣的指标。

   截止到现在,你还是只点了一下应用,电脑界面还什么都没有发生。当你点下鼠标的那一刻,该应用(下文全部用作业来代替)会被装入到内存,但是并不是全部被装入内存,比如打开英雄联盟,它只会将加载页面放入内存,而不会把对战地图放入内存,这样有一个好处就是,原本8G的League of Legends,现在只需要不到4G就可以带动了。

  当一个作业被装入内存,会有模块链接的相关步骤,但现代操作系统一般采用运行时动态链接,即程序执行过程中需要改模块时,才对它进行链接。而在以前,则采用静态链接,即在程序运行之前,先将各个目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块),之后不再拆开。所以这一步不再是程序执行的第一步了,写到这,程序执行的第一步即将开始,那就是动态重定位装入。

  装入就是将作业装入内存,其中涉及到很多东西,比如内存如何分配给作业、作业执行完之后如何回收内存、当作业太大时内存如何扩展等。先看最开始的——如何分配内存给作业。

  现在操作系统一般采用离散分配的方式,就是将作业拆成很多块,同时将内存拆成很多块,按照非连续的方式,将作业放入内存。这样可以产生较少的空间碎片。一般的分配机制采取分页存储管理、分段存储管理或者段页存储管理。这时候,我们的LOL的一部分(可能是登录界面),已经被拆成很多块,塞到内存页中了。下一步就是交给CPU执行了,但其实还缺少了一步——进程创建。我们一直在将它如何进入内存,却忘了给它创建进程,但现在也为时不晚。

  进程创建首先要向操作系统申请空白的PCB(Process Control Block),获得唯一标识符UID,然后是分配资源,毕竟进程是系统资源调度的最小单位,而线程则是处理机调度的最小单位。接着初始化PCB信息初始化处理机状态信息 :使程序计时器指向程序的入口地址,使指针指向栈项,初始化处理机控制信息 :设置进程状态为就绪或者静止就绪,优先级默认为最低。最后终于可以将进程插入就绪队列,只等处理机调度了。虽然程序已经做了这么多事,但现在用户还是什么也看不到,当用户第一次看到反应的时候,就是用户响应时间(前面提到过的处理机调度算法的指标)

  这个时候可以谈一谈处理机如何调度进程的,这个就是进程切换。得益于优秀的数据结构,处理机实现进程切换只需要把PCB(进程控制模块)中的相关数据进行修改。比如一个进程从运行态切换为阻塞态,处理机会根据进程标识符UID,读取进程状态,将进程PCB中的状态信息修改从运行修改为阻塞,同时将运行环境信息存入该进程的PCB中,再把该进程移到阻塞队列队尾,选择下一个就绪队列的进程,读取其PCB中CPU的运行环境,然后恢复运行环境,开始执行这个进程,类似同时和多个人聊微信时的状态。这里会产生一个问题,进程并不是平等的,操作系统会希望一些进程执行的更快,一些则无所谓。这就像同时和多个人聊微信,对女朋友所化的时间总是会比其他人多,因为有一些人、或是进程的优先级总是高于其他。这就涉及到了处理机调度算法,这里只介绍两种算法。

  处理机调度算法是为了更高的I/O,更快的响应时间,以及更多的CPU利用率等等。

  • 时间片轮转调度算法(Round Robin)

  这种算法把时间切片,比如在一分钟内有三个进程运行。处理机划分时间片为100ms,每隔100ms切换一次进程。

000~100ms:执行进程A1
100~200ms:执行进程A2
200~300ms:执行进程A3
300~400ms:执行进程A1
400~500ms:执行进程A2
500~600ms:执行进程A3
........
  • 多级反馈调度算法

  (说实话,写到这里我已经不想写了,为什么我们的程序还没执行)

多级反馈调度算法

  该算法划分了多个优先级就绪队列以及多种时间片大小,优先级越高,时间片越小。当一个进程产生时,先到优先级最高的就绪队列执行一个时间片,如果作业没有执行完,那么就进入下一个优先级次一级的队列,这时候进来的进程仍然送往第一优先级队列,执行一个时间片,然后送往第二优先级队列。如果此时没有进程,则执行第二优先级队列。如果作业还没有执行完,则放入第三优先级队列。

总结:

1、设置多级就绪队列,各级队列优先级从高到低、时间片从小到大
2、新进程到达时,先进入一级队列,运行结束后进入下一级队列队尾,到了最下一级,就重新放回该队列队尾
3、只有第k级为空,才会为k+1级队列分配时间片

优点:

1、对各类进程相对公平(FCFS的优点)
2、每个进程到达都可以很快的得到响应(RR优点)
3、短进程只用较少的时间就可以完成(SPF优点)
4、不必实现估计进程的运行时间(避免用户作假)
5、灵活的调整对各类进程的偏好程度,I/O密集型进程(将因I/O阻塞的进程重新放回队列)

  我们的游戏此时还在就绪队列,可能就在多级反馈调度算法的第一个队列中。之后,该进程就会被安排上处理机执行。在执行的过程中还会发生一件事,比如你进入了游戏,需要加载地图界面,这时候,操作系统就会发生缺页中断,缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。缺页中断、请求调页和页面置换是实现分页请求功能的三个步骤。

    请求分页也称为页式虚拟存储管理,是建立在基本分页基础上,为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能其基本思想是:在进程开始运行之前,不是装入全部页面,而是装入部分页面,之后根据进程运行的需要,动态装入其他页面,当内存空间已满,又需要装入新的页面时,根据某种算法淘汰某个页面,以便装进新的页面。

  实现请求分页,就需要解决两个问题——调出和调入。调出调哪里的页面?

调出

现代操作系统一般采用可变分配全局置换,进程缺页时,只允许该进程在内存的页面中选择一页换出,这样就不会影响其他进程运行,如果该进程在运行过程中频繁的中断,系统再为该进程分配若干物理块。

调入

将请求分页系统的外存分为两步分,用于存放文件区和用于存放对换页面的对换区。通常,对换区采取连续分配的方式。如果系统有足够的空间,可以全部从对换区调入所需页面。如果系统缺少足够的对换区空间,这时,凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于未被修改,所以不必再将他们换出。对于那些会被修改的文件,则将他们调出时,便调到对换区,需要时,再从对换区调入。

页面调入的过程

--程序所要访问的页面不在内存
--CPU发出缺页中断
--中断处理程序保留CPU环境,分析中断原因,转入中断处理
--查号页表,得到该页的外存地址
判断
IF {内存能容纳新页}:
    启动I/O,将所缺页调入,并修改页表
ELSE {内存满了}:
    按照某种置换算法,从内存中选取一页准备换出
判断    
    IF {准备换出的这一页没有被修改过}:
        不必写入磁盘
    ELSE {修改过}:
        则必须写入磁盘
--然后把所缺页调入内存,并修改页表中相应的值。

  以上实现了操作系统的虚拟化存储,以便于去执行那些内存大的程序。当操作系统产生了一个作业的执行结果,它会将执行的结果通过I/O设备传输给用户,简而言之就是屏幕。那么操作系统是如何通过屏幕让用户看到的呢?而且我们玩的过程中所敲的QWERDF是如何被操作系统识别的呢?这个就设计到了操作系统的IO管理。I/O管理系统可以让我们不用关心一个当我们敲下一个字符的时候,计算机是怎么接受、怎么处理以及怎么显示在我们希望它显示的位置,但学习计算机一定会了解I/O管理系统。

  一般I/O设备是不会直接和CPU进行通信的,因为这样会大量占用CPU的资源,总不可能你在键盘上输入一个字符,就直接通过I/O设备进入到CPU中。为了提高CPU的利用率,I/O系统在I/O设备和CPU通信之间设置了中间件,这就是设备控制器

Device_Control.webp

  键盘鼠标等输入输出设备现将内容传输给设备控制器的缓冲区,缓冲区积累一定的量之后,由设备控制器向CPU发送一个中断指令,CPU保存其运行环境,然后和设备控制器进行通信。至此,你所敲下的信息被操作系统所认知。接下来就是CPU将接受到的信息进行处理,将最终结果返还给用户,下面是处理过程。

  操作系统是一个庞大的进程合集,一个进程需要将自己的数据传输给其他进程,比如说当你在网页上复制一段下载链接时,后台的迅雷就会自动跳出来。这就是进程间通信,通俗一点就是进程间信息的传递。进程通信存在同步(同步和互斥)和异步两种方式。而进程间通信的具体实现主要是以下三种方式:

1、共享存储

设置一个共享空间
互斥的访问共享空间
两种方式:基于数据结构、基于存储区的共享

2、管道通信

设置一个特殊的共享文件(管道),其实就是一个缓冲区
一个管道只能实现半双工通信
实现双向同时通信要建立两个管道
各进程要互斥的访问管道
写满时,不能再写,读空时,不能再读
没写满,不能读,没读空,不能写

3、消息传递

传递结构化的消息(消息头/消息体)
系统提供“发送/接受原语”
两种方式
    直接通信方式:消息直接挂到接收方的消息队列里
    间接(信箱)通信方式:消息先发到中间体(信箱)

  通过进程间通信,就可以将消息传递给其他程序,其他程序再讲消息传递给设备控制器,设备控制器将数据输出到屏幕,至此一个基本的操作系统成型。

  最后一点是关于文件系统的,文件系统规定了文件存储的格式,其同样封装了文件存储在磁盘上的细节,只留给用户图形接口来对文件进行wrx等操作,其内部实现了对文件的共享和保护,常见的文件系统有ext3、NFS、exfat等。

文件系统的框架.webp

  文件目录是一种数据结构,用于表示系统中的文件以及其物理地址,供检索时使用。文件目录实现了“按名存取”,“提高了对文件的检索速度”,“实现了文件共享”,“允许文件重名”,这一切主要通过定义它的数据结构FCB来控制。

FCB主要信息:

基本信息:文件名、物理地址
存取控制类:存取权限
使用信息:建立时间、修改时间、打开文件的进程数

  文件描述信息单独形成一个称为索引结点的数据结构,在文件目录中,每个目录项仅由文件名和指向该文件名所对应的结点指针所构成,文件索引表:

文件名 指针
Name1 Point1
Name2 Point2
Name3 Point3

  这些索引表最终构成了简单的文件目录,单级文件目录、两级文件目录、树形目录结构。我们的文件、程序、应用等一系列的数据就存放在由格式化的文件系统构成的目录下,当程序执行时,磁盘通过算法读取到相应的信息,然后是内存调入(地址映射,重定向,分页管理,页面置换),接着被处理机(CPU)执行,其间会产生很多中断,当执行完成之后,操作系统通过IO管理系统将结果发送到屏幕。

  然而,一切到这里才刚刚开始,这个操作系统的网络部分还没有浮出水面…..


文件管理系统应该实现按名存取

  1. 文件存储空间的管理 – 分配和回收
  2. 实现文件名到物理地址的映射
  3. 实现对文件的操作–建立、删除、读写、目录
  4. 实现文件共享和文件保护
  5. 提供操作文件的接口、包括命令、程序、菜单

Operation System安全机制

  1. 标识与鉴别
  2. 访问控制
  3. 最小权限管理
  4. 可信通路
  5. 安全审计

Questions!

进程?

什么是进程?
进程的特性?
如何控制和产生一个进程?
如何控制和调度多个进程?
进程死锁怎么办,怎么避免?
进程状态转换的本质是什么,进程转换过程中做了哪些操作?
进程有哪些状态?
进程为什么会状态转换?
怎样避免多个进程运行的时候不产生混乱?
什么是临界资源?进程如何访问临界资源?
进程互斥算法?
两个或者多个进程间如何通信?
为什么要产生线程?
线程和进程的区别?
线程有哪些好处?
什么是管程?
为什么要引入管程,管程有哪些好处?

CPU?

什么是CPU?CPU能干什么?
什么是调度?调度有哪几种?
什么时候进行调度?
怎么调度?
怎么评价一个调度算法的好坏?
早起调度算法与交互式系统调度算法有什么区别?
列举几种常见的CPU调度算法,并描述其实现机制?

内存?

什么是内存?内存有什么用?
一台电脑内存4G是什么意思?
内存管理是如何完成地址映射的?
程序是如何进入内存的?
内存是如何分配和回收空间的?
内存分配回收空间有哪几种算法,各个的优缺点是什么?
内存的连续分配和非连续分配是什么?
分页存储的基本原理?
分页存储和分段存储有什么不同?
用什么样的数据结构记录系统已经分配的内存、以及系统剩余的内存?
内存空间的扩展是如何实现的?
内存保护是什么?有什么作用?怎么实现的?怎么产生的?

虚拟存储机制?

什么是虚拟存储?为什么会有虚拟存储?
怎样实现虚拟存储?
缺页中断是什么?
页面是什么时候调入?
页面是从哪里调入?
如何评价一个页面置换算法的好坏?
页面置换是如何置换的?
页面置换的算法?
什么是抖动和工作集?

I/O系统?

为什么要有输入输出系统?
输入输出系统是怎么产生的?
I/O系统的层次结构模型是什么样的?
设备控制器是什么?
设备控制器有什么用?
中断机构和中断处理程序?
设备驱动程序是什么?
缓冲区的引入有什么好处?
有哪几种缓冲区?
磁盘存储是什么?
磁盘存放数据按照什么格式?机械硬盘是什么格式?固态硬盘是什么格式?
U盘存储原理?
怎样衡量一个磁盘调度算法?
有哪些是磁盘调度算法?如何实现?

文件管理系统?

为什么会产生文件系统?
文件有什么数据结构?
这些数据结构能支持文件完成哪些动作?
什么是目录?
为什么会产生目录?
目录有什么样的数据结构?
目录存放在磁盘的什么地方?
文件和目录是怎么建立联系的?
文件共享是如何实现的?
文件保护是如何实现的?



其他

任何程序都必须满足结构性,以便于外部或内部对其rwx