Fork me on GitHub

现代操作系统知识点

现代操作系统知识点

现代操作系统有一些知识点需要归纳一下。先记录一部分,后续再慢慢补充。

线程和进程

线程和进程的区别

进程是一个程序在一个数据集上运行的实例,进程是系统进行资源分配和调度的独立单位。线程是CPU调度的基本单位线程本身不拥有系统资源,线程之间共享进程的资源,线程可以撤销另一个进程,进程之间可以并发运行。进程只能由另一个进程fork出来。

创建进程的方法

进程的创建有以下几种方法

  1. 系统初始化 
    系统初始化会在前台和后台创建一些必要的进程。
  2. 执行了一个从事创建进程的API,
    这个API被正在运行的进程调用
  3. 用户请求创建新进程。
  4. 一个批作业的初始化
    批作业是指运行多个程序,如果cpu有资源,就创建进程运行其他的程序
    所有的进程只能由一个已经运行的进程创建,子进程是父进程的一个副本。但是地址空间不同,线程无法创建进程。

    进程的状态

    进程主要分为三种状态:
  5. 运行态(该时刻进程占用CPU)
  6. 就绪态(可运行,但是还没轮到他运行)
  7. 阻塞态(除非某种外部事件发生唤醒他,不然不能运行)
    68296874-1866-4115-85DB-7EC1887B9195

使用线程的原因

在传统的操作系统中,进程拥有独立的内存地址空间和一个用于控制的线程。但是,现在的情况更多的情况下要求在同一地址空间下拥有多个线程并发执行(阻塞)。因此线程被引入操作系统。

  • 多线程之间共享同一个地址空间和所有可用数据的能力。多进程模型(多个进程之间不共享地址空间)不能表达出来的。
  • 线程比进程更加轻量级,所以线程比进程更快创建和取消。 线程的创建时间比进程快10倍到100倍。
  • 性能方面。如果多线程都是从事cpu密集工作,那么不会提升性能。 但是存在I/O阻塞,使用多线程会提升速度。
    不同的进程分配在堆上的内存不能互相访问,因为进程之间的内存空间是互相独立的。

    操作系统实现线程的几种方式

    内核线程

    操作系统知道线程的存在,线程表存放在操作系统内核
    所有阻塞线程的调用都是以系统调用(system call)的方式实现。当一个线程阻塞时,系统可以选择将CPU交给同一个进程中的其他线程或者其他进程中的线程。在内核中实现线程的成本较高,可以采用线程回收技术。当一个线程被销毁时,修改标志位而不是销毁线程本身。当注册一个新的线程时,同样修改标志位,类似于线程池。
    15203852-5544-4DBE-AD18-C51C276E9E74

    用户线程

    将线程包都放在用户空间,内核对线程包不知道。内核按照单线程进程管理。进程中要用专门的线程表来跟踪线程的运行。
    用户级线程的优点
  1. 在用户空间下进行线程切换的速度要远快于在操作系统内核中实现
  2. 在用户空间下实现线程使得程序员可以实现自己的线程调度算法。比如进程可以实现垃圾回收器来回收线程。还有,当线程数量过多时,由于在用户空间维护线程表,不会占用大量的操作系统空间。

用户级线程的缺点:

  1. 如何实现系统阻塞调用 因为内核当线程阻塞时,会按照单线程进程处理,阻塞整个进程,即使这个进程中的其他线程还在工作。CPU只能调度内核线程,即轻量级进程。
  2. 如果线程长时间不释放CPU,因为用户空间没有时钟中断,导致进程中的其他线程得不到CPU而持续等待。(CPU只能切换内核线程,不能切换线程)

AF381807-06AE-4B3B-BB84-D9A7892495D9

混合模式

还有一种实现方式是将上面两种模式进行混合,用户空间中进程管理自己的线程,操作系统内核中有一部分内核级别的线程。
在这种模式下,操作系统只能看到内核线程。用户空间线程基于操作系统线程运行。因此,程序员可以决定使用多少用户空间线程以及操作系统线程,这无疑具有更大的灵活性。而用户空间线程的调度和前面所说的在用户空间下执行实现线程是一样的,同样可以自定义实现。如果线程阻塞,那么内核就调用内核线程去调度其他的线程。内核级线程中有一个可以轮流使用的用户线程合集。
A4DDD2A7-B5CB-4F6A-B478-3AE77CEDE182

进程间通信

进程间通信只要包括3个方面

  1. 进程A如何把消息传递给进程B
  2. 进程之间的同步问题。比如共同抢占资源和进程之间的先后顺序

进程间的通信的方式有
管道,信号量,消息队列,共享内存和套接字

  1. 管道:半双工的通信方式,数据只能单向流动,而且只能在有亲缘关系的进程使用。进程的亲缘关系指父子进程关系
  2. 有名管道:半双工方式,允许没有亲缘关系的进程通信
  3. 信号量:信号量是限制访问资源的数目 和semophere类似
  4. 消息队列:消息队列是消息的链表,存放在内存中,消息队列克服信号传递信息少,管道只能承载无格式字节符和缓冲区受限制。
  5. 信号:通知进程某个事件完成。 wait nofity
  6. 共享内存,共享的内存 堆
  7. 套接字:其他可能需要用同一个系统内核做中介,套接字是基于网络传输来实现。 socket

进程调度的方式

当计算机系统是多道程序设计系统,则多个进程会竞争CPU,这样就需要一个调配程序告诉CPU在哪个时间点执行哪个进程,这就是调度。

  1. 轮转调度:每个进程平均分时间段去使用CPU,这样导致管理时间很久,浪费和大
  2. 优先级调度:每个进程都有一个优先级别,级别高的有权先调度,级别低的用后面再调度。
  3. 最短进程优先:最短进程优先就会有最短响应时间。
  4. 保证调度:向用户做出明确的调度保证,然后去实现它。
  5. 彩票调度:改进版的彩票调度,向每个进程提供的各种系统资源的彩票,一旦要做出决策时,就随机抽取一张彩票,拥有该彩票的进程获得该资源,得到CPU的应用时间。
  6. 公平分享调度:这个是为了改善不同用户间的进程而设置的。

用户空间和内核空间 进程上下文和中断上下文

我们知道现在操作系统都是采用虚拟存储器,那么对32位操作系统而言,它的寻址空间(虚拟存储空间)为4G(2的32次方)。
操心系统的核心是内核,独立于普通的应用程序,可以访问受保护的内存空间,也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核,保证内核的安全,操心系统将虚拟空间划分为两部分,一部分为内核空间,一部分为用户空间
针对linux操作系统而言,将最高的1G字节(从虚拟地址0xC0000000到0xFFFFFFFF),供内核使用,称为内核空间,而将较低的3G字节(从虚拟地址0x00000000到0xBFFFFFFF),供各个进程使用,称为用户空间。
每个进程可以通过系统调用进入内核,因此,Linux内核由系统内的所有进程共享。于是,从具体进程的角度来看,每个进程可以拥有4G字节的虚拟空间。
需要注意的细节问题:

  1. 内核空间中存放的是内核代码和数据,而进程的用户空间中存放的是用户程序的代码和数据。不管是内核空间还是用户空间,它们都处于虚拟空间中。
  2. 内核态与用户态:
    当一个任务(进程)执行系统调用而陷入内核代码中执行时,称进程处于内核运行态(内核态)。此时处理器处于特权级最高的(0级)内核代码中执行。当进程处于内核态时,执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。
    当进程在执行用户自己的代码时,则称其处于用户运行态(用户态)。此时处理器在特权级最低的(3级)用户代码中运行。当正在执行用户程序而突然被中断程序中断时,此时用户程序也可以象征性地称为处于进程的内核态。因为中断处理程序将使用当前进程的内核栈。

调度程序激活

当内核了解到一个线程阻塞后,内核就通知这个该进程的运行时系统,并且在堆栈中传递有问题的线程的编号和问题描述。然后运行时系统就将该线程标记为阻塞并从就绪表中取出另一个线程,设置寄存器,启动这个线程。当内核知道了之前的线程可运行了,就在再次调用进程的运行时系统,通知这个事件,这时候运行时系统可以根据自己的判断立即启动这个线程或者放在就绪表中稍后运行。

存储管理

存储管理主要讲了操作系统的分页,分段和页面置换算法和寻址的细节实现。

存储器抽象

无储存器抽象,程序都是访问物理地址。则在电脑上无法运行两个程序。
暴露物理地址的问题是

  1. 如果程序可以寻址内存的多个地址,那么容易破坏操作系统
  2. 这种模型无法运行多个程序

解决多个程序之间在内存中互不影响的问题:  
在没有内存抽象的系统中实现并行使用多线程编程。 因为多线程是进程中的所有线程对同一个内存映像可见。 但是人们希望在同一时间运行没有关联的程序,这是线程抽象不能提供。
总结 暴露地址空间带来的问题

  1. 用户程序可以寻址内存的每个字节,可以破坏操作系统。
  2. 无法在一个系统中运行多个程序。当一个程序在2000的位置写入新的值,会将原来的程序在2000的值擦除。

地址空间

地址空间是一个进程用于寻址内存的一套地址集合。每个进程都有自己的地址空间,并且和其他的进程不同。

基址寄存器和界限寄存器

程序的起始物理地址装载到基址寄存器中,程序的长度装到界限寄存器中。但是他们的缺点是每次访问内存都需要进行加法和比较运算,效率相对低。程序过大,无法将多个程序都放在内存中运行。解决办法有交换策略和虚拟内存。
EE2745DC-0F42-47FF-9C05-DB2B706FE191

交换内存

把一个进程完整的调入内存,运行一段时间后保存回磁盘。交换策略会在内存中产生空闲区,通过把所有进程尽可能向下移动,有可能将小的空闲区合成一块,该技术称为内存紧缩。
如果程序的数据段会增长,如java允许程序在堆上动态分配内存。则分配内存时候分配空闲区。
空闲内存管理可以使用位图或者是链表进行存储管理。分配内存有多重算法,对应的是NP问题,现在常用的算法有:首次适配算法,最佳适配算法,下次适配算法等等。

虚拟内存

比如内存1g,但是程序需要2g的内存。那么使用交换内存技术就无法实现。又或者内存1g,程序1g。如果sata磁盘的速率为100m/s,那么每次交换需要10s时间。效率很低。
虚拟内存将整块的程序分成小片,那么交换的时候不需要全部交换,可以省去很多时间。
定义:每个程序都拥有自己的地址空间,这个空间被划分成多个块,称为虚拟页面。将这个页面向实际的地址空间映射。但是不是所有的页都要在地址空间中。如果不存在,称为页面缺陷。由操作系统从磁盘中找到这部分的程序写入地址中。
24EA775D-CF64-4436-ADE6-1D8032E44615
如图所示。cpu向MMU发送页面8的地址发现没有对内存的实际映射,引发缺页中断,那么MMU将把内存中不常使用的页框中的内容写到磁盘,比如页框1,然后把页面1的对应关系设置为未映射,将页面8的内容读到页框1中。

分页技术

现在大部分虚拟内存系统都使用分页技术。虚拟地址通过送到MMU转换成物理地址。
虚拟地址空间按照固定大小划分成页面的若干单元,在物理内存中对应的单元称为页框。
现有系统的页大小一般是512字节到64kb。

  1. 虚拟地址寻址
    MMU的内部结构如下所示。这个页表是MMU的内部一个表格,使用页号作为页表的索引。
    当输入的虚拟地址为8196(十六进制2004),那么高4位作为页号,低12位作为偏移量。则输入的实际地址为24580。达到寻址目的。
    D53FAD7E-A7AA-4599-8944-099B93E6C782
  2. 加速分页过程
    当有32位地址时,如果使用4kb的页面大小,那么会有2^20个的页面索引号。页表查询会非常慢。
    解决办法:
  • 可以使用转换检测缓冲区(TLB)来加速转换。
    TLB中保存了最近使用的虚拟地址。每次MMU都会先去TLB中寻找页框的对应号,如果没有才会进行正常的页表查询。
  • 多级页表
    对于32位地址总线可以使用 32位的地址总线,划分成10位的PT1区,10位的PT2区,12位的偏移。那么PT1将地址划分成4M,PT2将地址划分成4K。每一个表项为1024个表索引。那么PT1将地址分成了4M一份。存储页表项大概需要16M。因为2^22个表项,一个表项为4个字节。
  • 倒排页表
    对于64位的地址总线,虚拟地址的大小为2^64。 对于64位虚拟地址,4kb的页,1g的ram。如果是使用4kb大小的页面大小,那么久需要2^50 个页表项,一个页表的指针大小为8个字节,那么整个页表要超过3000万GB。不现实。
    使用倒排页表将使用虚拟页表到物理地址的映射。则只需要2^18 个页表项,即262144个页表项。1g为2的30次方,4kb为2的12次方。
    问题:从虚拟地址到物理地址的映射无法直接得到。要先去查找物理地址。那么每次都要查找2^18 项的表,运行会很慢。
    解决办法:使用散列表,用虚拟地址散列,每一项为物理地址对应虚拟地址。
    用虚拟地址为key,则将64位的hash散列到2^18 -1槽的物理地址map中,这时候肯定会存在hash冲突。其中每一项记录的是虚拟页面和物理地址的key_value。然后在这个继续根据hash来查找真实的物理页面号。
  1. 页面置换算法:
    当发生缺页中断时,操作系统要在内存中找到一个页面置换出去,将即将调入的页面
    问题:如果使用经常使用的页面置换,那么将会发生频繁的磁盘写入写出过程降低效率。那么要选择最优的页面来置换。
  • 最优页面置换算法:
    此算法是理想状态,不可能实现。它希望把最后才使用的页面置换出去,不过由于不可知每个页面的下一次使用时间,所以是做不到的。
  • 最近未使用页面置换算法(NRU not recently used):
    系统为每个页面设置两个状态位。当页面被访问的时候设置R位,当页面被修改的时候设置M位
    置换算法为:当启动一个进程时,该进程的所有的页面两个位都设置为0,R位定期的被清零(20ms),以区别最近页面有没有访问。如果R还是1,那么说明这个页面在20ms内使用了,是频繁使用的。NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰。
  • 先进先出页面算法(FIFO)
    该算法淘汰存在时间最长的页面,可能会淘汰重要的不实用的页面。
  • 第二次机会页面置换算法:
    检查页面的R位,如果R位为0,则被置换出去,如果R位是1,则将R位清零,并将页面放在链表的尾部,并修改它的装入时间,就想好刚刚装入一样。
    第二次会算法就是寻找一个最近的时钟间隔以来没有被访问过的页面,如果所有的页面都被访问过,该算法就简化为纯粹的FIFO算法。
  • 最近最少使用页面置换算法(LRU Least Recently Used):
    当出现缺页中断时,置换最长时间未使用的页面
  • 老化算法
    只需要8位的时间寄存器,寄存器的值不断右移,最后判断最小的值。如果时钟的间隔是20ms,8位一共是160ms,在160ms时间内使用最少的次数的页面。
  • 工作集算法:
    跟踪程序的主要的页面,然后将该页面预先放入内存,减少缺页中断。
    页面算法总结:
    LRU算法是非常优秀的算法,但是只能通过特定的硬件来实现。NFU是一种近似于LRU的算法。它的性能不是非常好,但是可以很有效的实现,因此是一个很好的选择。
    总之,最好的两种算法是老化算法和工作集时钟算法。他们分别基于LRU和工作集。
    缺页中断处理
  1. 硬件陷入内核,在内核堆栈中保存程序计数器。
  2. 系统发现缺页中断后,找到该虚拟页面,检查地址是否有效或者写保护,无效杀死进程等。
  3. 地址有效,则检查是否有空闲页框,没有就用页面置换算法找到一个合适的页面替换。
  4. 如果页面脏了,就重写回磁盘,IO阻塞,内核运行其他进程。
  5. 页框干净后,磁盘查找所需所需页面在磁盘的位置,通过磁盘将页面写入内存。
  6. 等页面完全写入内存后,将恢复程序计数器,重新运行该进程。

死锁的概念

可抢占资源和不可抢占资源的概念

  • 可抢占资源指可以从占有的进程中将资源抢占而不出错,存储器等
  • 不可抢占资源指在使用过程中无法抢占。如打开的文件,刻录机等

    死锁发生的条件

  • 互斥
  • 占有和等待条件 获取了一个资源的进程可以获取新的资源
  • 不可抢占条件 已经分配给一个进程的资源不能被强制剥夺,只能等进程释放
  • 环路等待条件 多个进程在请求资源时形成了环路

    IO阻塞的过程

    当进程请求的资源不存在时候发生IO阻塞时候,就进入休眠,进入队列,等待满足的条件发生由CPU唤醒
0%