今天来聊聊总结(三) 操作系统

模块一:硬件

1,存储分层

越上面速度越快。

L1,L2 Cache是CPU私有的。L3是多个CPU共用的。

CPU

CPU缓存一致性问题

要解决这个问题,需要保证两点

  • 写传播:每一条写进cache的,要传给所有CPU的cache。
  • 事务的串行化:某个CPU对数据操作,应该在其他CPU看来是有序的。

写传播的实现用的是总线嗅探。

事务的串行化实现用的是MESI,它是基于总线嗅探实现的。

模块二:内存管理

如果程序直接引用物理地址,可能导致内存只能使用一个程序。因为其他程序也运行的话,可能会直接占用前一个程序的物理地址。

这时候我们就需要一个虚拟内存的机制,再分配到物理地址里。

虚拟内存地址和物理内存地址

虚拟内存的实现主要有两种方式:内存分段和内存分页。

内存分段

通过段表和物理内存地址进行映射。

段表结构

该段的物理地址 = 短号对应的基地址+偏移量。如果偏移量超过段长,则越界中断。

问题

内存碎片问题和内存交换效率低的问题。

出现碎片问题

很多个程序同时运行,这时候中间一个小程序内存可能被释放,那么就会出现碎片问题。

碎片问题分两种

  • 内部碎片问题:一个程序内很多占用内存的部分不咋用,浪费。
  • 外部碎片问题:释放后出现多个不连续的物理小内存。

解决内部碎片问题

使用内存交换的方法。

将占用的内存读到磁盘去,再从磁盘读回来,但是位置和以前不同了,这样能解决碎片问题。

因为磁盘效率慢,如果读到磁盘的是很大的程序,就会效率非常差

内存分页

为了解决分段的两个缺点(碎片问题和内存交换效率低)。

实现:将虚拟内存和实际内存分割成一小片,这片称为页。Linux中页的大小是4k。

再把页表和物理内存映射起来。

页表存在内存里,MMU则进行虚拟地址和物理地址转换的操作。

缺页异常:当进程在页表查询虚拟内存,找不到的时候,就会发生缺页异常。然后就分重新分配页表,最后进程恢复运行。

如何解决碎片问题和内存交换效率低的问题?

碎片问题:

因为是通过映射页的方式,所以不会出现进程无法使用的内存块,每个释放的页都能被重新使用。

内存交换:

遇到不常使用的内存空间时,不需要像分段一样传递整个程序的占用内存,只需要传递几个页到磁盘,这样效率就很高。

页表如何实现

页表内有虚拟页号和物理页号(对应的块号)。

转换到物理地址的过程:

  • 将虚拟地址转换成页号和页内偏移量
  • 拿着页号去页表查询物理页号
  • 物理页号加偏移量就是物理地址

缺点

1,简单分页的情况下,因为操作系统运行的进程很大,那么就意味着页表占用内存也特别大,很浪费。

进步

因为简单页表出现的占用大问题,所以引入了多级页表

多级页表:

一级页表和简单页表一样,然后通过对页表的分页,建立出二级页表。

虽然这样比一级页表占用更多了,但是可以通过二级页表直接映射,也就是说,一级页表可以置换到磁盘里了。

再继续分页,就出现多级页表。

段页式内存管理

分段和分页不是分开的功能,我们可以把他们合并起来一起使用。

实现方式

  • 先把程序划分成有逻辑意义的段。
  • 再将每个段划分成页,也就是对分段划分出的连续空间,划分成固定大小的页。

通过这种方式,就可以将表划分为 段号,段内页号,页内位移。

每个程序拥有一个段表,然后每个段拥有一张页表。

这样提高了CPU利用率。

Linux内存管理

主要采用分页内存管理,但是也有用上分段机制。

模块三:进程与线程

进程

1,并行与并发

2,进程的基本状态

  • 运行状态
  • 阻塞状态
  • 就绪状态
  • 创建状态
  • 结束状态

3,进程的其他状态

因为有时候等太久,很浪费内存,得放入磁盘,调用时再掉到内存里,这种叫挂起

所以又有两个状态

就绪挂起状态和阻塞挂起状态

4,如何挂起?

  • CPU自行调度
  • sleep方法
  • Ctrl – Z (linux)

进程的控制结构 – PCB

1,操作系统靠控制PCB/进程控制块来控制进程。

2,PCB是进程存在的唯一标识,进程如果存在一定存在PCB,进程被释放PCB也被释放。

3,PCB包含信息

不太重要/记不住

4,PCB如何组织

  • 通过链表组织成队列。如阻塞队列,就绪队列。
  • 还有索引的方式组织。

一般选用链表,因为抢占式调度,链接比较容易插入和删除。

进程的控制

通过PCB进程控制。

1,创建进程:

  • 先分配一个进程标识号,再分配一个空白的PCB。
  • 给进程分配内存空间。
  • 初始化PCB
  • 插入队列中。

2,终止进程

  • 找到该进程的PCB。
  • 如果执行,终止执行。
  • 如果有子进程,终止子进程。
  • 释放资源。
  • 清楚PCB。

3,阻塞状态/唤醒状态

  • 找到PCB
  • 修改PCB中的状态
  • 插入队列。

进程的上下文切换

一个进程还没执行完,切换到下一个进程。

1,过程:

把交换的信息保存在进程的PCB中,然后切换到下一个进程,下次再通过PCB恢复。

进程的调度

1,先来先服务调度算法

2,时间片轮转调度算法

3,高响应比优先调度算法

4,最短作业优先调度算法

5,最高优先级调度算法

6,多级反馈队列调度算法

线程

1,为什么用线程?

  • 进程间通信开销大
  • 进程各种状态,上下文切换开销大

2,线程是进程的一条执行流程。

3,线程的优点

  • 共享资源和地址
  • 并发执行
  • 一个进程有多个线程

4,线程和进程的区别

  • 进程是资源分配的单位,线程是CPU调度的单位。(最大差别)
  • 进程有完整的资源平台,线程只占用必要的资源,如寄存器和栈。
  • 线程有三种基本状态,执行,阻塞,就绪。
  • 线程启动和终止时间和占用资源都比进程少。
  • 线程崩了,所在进程也会崩溃。但是进程间互不影响。
  • 同一进程的线程共享同样的资源,就不用经过内核,速度快还减小开销。
  • 线程的上下文切换速度比进程快。

5,线程的上下文切换

  • 同一进程的话,虚拟内存不变,只需要切换线程的私有数据,寄存器和栈啥的就行。
  • 不同进程的话,和进程上下文切换一样。

6,线程的实现

有三种线程和其对应的实现方式:

  • 用户线程:用户实现的线程
  • 内核线程:内核中实现的线程
  • 轻量级进程:

进程的通信

  • 管道

1,存在内核中的缓存,一端存进去,另外一端读出来缓存。

分为两种

匿名管道和命名管道。

匿名管道:只能在父子进程之间使用。

命名管道:可以在不同进程使用,匿名管道的功能同样可以。

缺点:管道不适合频繁交换信息的情况。

类似邮箱,通信时一方进程将信息交给消息队列,另外一方需要的时候取出来就好。

消息队列是保存在内核的链表。

缺点:通信不及时,信息大小限制。

  • 共享内存

拿出一块虚拟内存,映射到相同的物理地址。

缺点:并发问题。

  • 信号量

为了防止共享内存出现的竞争问题,推出机制信号量。

信号量用来表示资源的互斥与同步。

P操作和V操作

信号量=0同步,=1互斥。

  • 信号

上面都是常用情况下,这是对异常情况下。

比如人为强制。

  • Socket

上面都是同主机进程,socket可以跨主机跨网络通信。当然同主机也可以。

多线程同步

呃。

死锁

两个进程竞争资源,每个进程都拿了一部分又不释放,就会出现死锁问题。

死锁四个条件

  • 互斥条件:多个线程不能用同一份资源。
  • 持有并等待条件:持有了一份资源,等待另外一份资源
  • 不可剥夺条件:使用前不可以被剥夺。
  • 环路等待条件:获取资源的顺序行成环。比如说A获得了1资源,等待2资源,这时候2获得2资源,等待1资源。

破坏死锁

只要破坏其他一个条件就可以。

所以常用的方法:使用资源有序分配法,破坏环路等待。

乐观锁和悲观锁

  • 基础锁

互斥锁和自旋锁

区别:

互斥锁:没获取锁的时候,进程会释放CPU。但是会从用户态变成内核态(阻塞),也增大了内核开销。

自旋锁:没获取锁的时候,进程会忙等待(自旋),一直占用CPU。

所以如果能确定锁的时间很短,则应该使用互斥锁,不是自旋锁。

  • 读锁和写锁和其优先级

原理:当写锁没被持有的时候,则多个进程可以并发持有读锁。

当写锁被持有时,持有读锁的线程会被阻塞,获取读锁的操作也被阻塞。

所以读写锁,用于读多写少的环境下。

  • 读优先锁和写优先锁

根据情况的不同,可以分成这两种锁。

读优先锁:当读线程 A 先持有了读锁,写线程 B 在获取写锁的时候,会被阻塞,并且在阻塞过程中,后续来的读线程 C 仍然可以成功获取读锁,最后直到读线程 A 和 C 释放读锁后,写线程 B 才可以成功获取写锁。

写优先锁:当读线程 A 先持有了读锁,写线程 B 在获取写锁的时候,会被阻塞,并且在阻塞过程中,后续来的读线程 C 获取读锁时会失败,于是读线程 C 将被阻塞在获取读锁的操作,这样只要读线程 A 释放读锁后,写线程 B 就可以成功获取读锁。

不管是哪一种锁,都会出现线程饥饿问题。所以还有一种,公平读写锁。

谁先获得谁拿锁,另外一种阻塞。

乐观锁和悲观锁

思想。

悲观锁:互斥锁。

乐观锁:先修改共享数据,然后检查是否冲突,如果有线程修改了就放弃这次操作。

协程

轻量级线程。

由用户自由调度(yield)。线程是由CPU调度上下文切换,协程是全部由用户来操作。

线程同步的方式

模块四:调度算法

分为三大类:进程调度,页面调度,磁盘调度。

进程调度算法

正文完