操作系统

2017-08-08  本文已影响77人  klory

参考自 https://www.coursera.org/learn/os-pku/home/welcome

概述

作用

  1. 管理资源
  2. 提供简单方便的指令。用户通过终端命令和高级语言向系统提出服务请求。
  3. 抽象硬件（CPU抽象为进程；内存抽象为进程地址空间；磁盘抽象为文件）

特征

  1. 并发：宏观同时运行，微观顺序执行。
  2. 共享
  3. 虚拟
  4. 随机： 随时对不可预测的次序发生的时间进行响应并处理。所以，无法预知进程的运行快慢，很难重现某一时刻的状态。

架构

Windows

应用 - 操作系统 - 硬件

Unix

硬件 - 内核 - 系统调用接口 - Unix命令

Linux

硬件 - 内核态 - 用户态

Android

分类

按年代

按类型（TANENBAUM)

大型机、服务器、个人、掌上、嵌入式、智能卡等。

运行环境

处理器

构成

运算器、控制器、寄存器、高速缓存
【寄存器】控制和状态寄存器控制处理器的操作。

中断与异常机制

改变了CPU的执行流程。

中断（外中断）

相当于汽车发动机或飞机引擎。
os是由中断（事件）驱动的，外部设备引发的。异步的

异常（内中断）

正在执行的指令引发的。CPU执行指令是本身出现的问题。同步的。

中断/异常的工作原理

硬件工作：响应，把CPU控制权给中断程序。中断寄存器，每个指令执行周期的最后时刻扫描中断寄存器，如果有中断，保存现象（PC+PSW），查中断向量表（存放了中断程序的地址），推入寄存器，执行程序。
软件工作：处理。
系统提前定义好中断程序，硬件去执行。

x86对中断的支持

实模式

保护模式

IDTR-IDT（中断描述符，偏移）- GDTR（端描述符，段基地址）
中断程序地址 = 偏移 + 段基地址

系统调用机制（SYStem call）

用户在编程时可以调用的操作系统功能。
用户态 --> 内核态。
接口类型：进程控制、进程通信、文件使用、目录操作、设备管理、信息维护。

进程和线程

进程

多道：单个PC（物理程序计数器）虚拟成多个PC。
并发：多个程序同时处于开始但尚未结束的状态，而且次序不定。

进程=任务

进程控制块PCB

记录一个进程的各种属性和变化过程。
进程表：所有PCB的集合，固定大小，所以有最大进程数。
PCB中包括：描述（ID、名字、用户、组），控制（状态、优先级等），使用资源（打开的文件等），CPU现场(寄存器值、PC、PSW)。
Linux中叫做：task_struct
Windows: Eprocess+...

进程状态

运行、就绪（由于时间片导致的，是正常进程轮换）、等待（或者叫阻塞、封锁、睡眠。由于同步导致的）。动态产生、动态消亡。

此外，创建、终止、挂起（就绪挂起、阻塞挂起）
不同状态不同进程队列（元素是PCB）。

进程控制

原语：完成某种特定功能的一段程序，不可中断（通过屏蔽中断）。

Unix的几个基本操作（均为系统调用）

fork

Unix一次一页的复制父进程地址空间，共享资源，设置为就绪，插入就绪队，子进程返回0，父进程返回子进程pid，从而实现父进程一分为二。

Linux的fork实现，采用了Copy-On-Write技术。

进程相关概念

分类

系统进程、用户进程。
前台进程、后台进程。
CPU密集进程、I/O密集型进程。

进程层次

Unix: init为根，根结束后，其他子进程必须结束。
Windows：也通过复制生成新进程，但是没有相互关系。

进程vs.程序

进程并发。进程动态。进程短暂的生命周期。一个程序多个进程。进程具有创建其他进程的能力。
例子：学生=CPU，课表=程序，每门课=进程。

进程地址空间

进程中的数据的地址是在当前进程的地址空间的位置，而不是物理内存的位置。

进程映像

对进程执行活动全过程的静态描述。用户栈+程序代买+进程控制块

上下文切换

CPU硬件状态从一个进程换到另一个进程。即PCB和CPU寄存器的切换（PC，PSW，通用寄存器等）

线程

共享进程的地址空间。字处理程序、web服务器程序、
并发：线程并发性更高
开销：线程创建简单、线程通信不需要内核介入，效率高。
性能：

和进程（资源拥有+CPU调度单位）相比，线程只是CPU的调度单位，是轻量级的进程。

线程属性

id，状态，保存寄存器，自己的栈指针
共享所在进程的地址空间和资源。

线程实现

用户级（UNIX)

核心级（Windows）

混合型（Solaris）

处理器调度

相关概念

调度算法

调度时机：运行->终止，阻塞->就绪，运行->阻塞，运行->就绪。即内核返回用户态的时候。

调度过程：切换进程（全局页、内核栈和上下文）

例子，A下B上：

  1. 保存A
  2. 更新A的PCB
  3. A移动到适当队列
  4. B设置为运行态
  5. B的PCB恢复上下文

上下文切换开销

直接+间接（缓存）

算法设计

用户：响应快
系统：公平

衡量指标

吞吐量、周转时间、响应时间，开销

设计需要考虑的问题

方法：抢占式、不可抢占式

批处理系统的调度算法

FCFS，SJF；SRTN，HRRN

交互系统的调度算法

时间片轮转（Round Robin）、虚拟轮转算法（VIRTUAL RR)、最高优先级算法

优先级反转问题：低优先级进程占用了高优先级进程的资源。

临界区：无法共享的资源，只能单独占用。

解决方案：

多级反馈队列调度算法(multilevel feedback)

设计原则

Windows线程调度算法

解决“饥饿”现象：使用平衡级管理器。

同步机制

进程互斥

临界资源
临界区：对某个临界资源使用的代码段

进程互斥的软件方案

进程互斥的硬件方案

小结

忙等待：进程在得到临界区访问权之前，持续测试而不做其他事情。

自旋锁（多处理器）。切换处理器的开销大于忙等待开销。
优先级反转是由于临界区保护产生的。

进程同步

多个进程中的事件存在某种时序关系。A进程的运行依赖于B进程的信息，否则进入阻塞态，直到有了信息后进入就绪态。

生产者/消费者问题

或者叫有界缓冲区问题。生产者和消费者都读写buffer。
睡眠sleep()和唤醒wakeup(someone)操作。
SPOOLing中的生产者和消费者。

信号量和PV操作

1965，Dijkstra提出。

PV操作

信号量结构体：count和queue
semaphore s;
操作：init, P(test/up), V(increment/down)
P and V are called by process.
P和 V是原语操作（封中断执行）。
二元信号量到一般信号量。解决同步和互斥问题。

PV解决互斥问题

互斥量mutex（mutual exclusive）
解决同步：两个进程一个P一个V
解决互斥：在一个进程内执行P和V

porducer() {
  P(empty)
  P(mutex)
  insert_item()
  V(mutex)
  V(full)
}

读者和写者问题

读者优先；
写者和其他读者写者互斥；
Linux中的读写锁

管程

信号量有缺点（编写难、易出错）。
1973年提出。
在程序语言中引入高级同步机制。
管程：由关于共享资源的数据结构和在其上的操作的一组过程组成。
进程只能通过调用管程中的过程来间接访问管程中的数据结构，把同步和互斥的实现封装在相应的过程中，这样进程只需要调用过程即可，方便很多。

解决两个问题：

hoare管程

后面进程唤醒前面的进程，前面的执行，后面的等待，把后面的进入管程内的紧急等待队列（比管程外的优先级高）。

wait(c), 紧急队列非空，唤醒等待者；否则释放管程互斥权，同时自己进入c链末尾。

signal(c), c链为空，则相当于空操作；否者唤醒第一个等待着，同时自己进入紧急等待队列。

管程的应用

实现：直接构造（高效）或者间接构造（使用已有机制PV等）。

解决生产者消费者问题

C/C++没有管程，JAVA中有实现。

MESA管程

1980年提出。

notify:当一个正在管程中的进程执行notify(c)时，它使得c条件队列得到通知，发信号的进程继续执行。

结果：使得位于条件队列头的 进程在将来合适的时候执行。由于不是立刻执行，所以不能保证条件满足。所以将来唤醒前，需要重新检查（用while循环代替if语句）。

MESA一般认为优于Hoare。
PThread 是一个MESA过程。

进程间通信IPC

【目的】解决PV和管程不能传递大量信息的问题 。
管程不能适用于多处理器。

消息缓冲区

陷入内核 ，复制消息（到缓冲区），消息入队，复制消息（到接收）

共享内存

管道通信方式

存储管理

地址重定位

代码段、数据段、堆-（共享库、内存映射文件等）-栈

所以进程中的地址不是最重的物理地址，进程运行之前无法计算出物理地址。
需要地址重定位的支持。

静态重定位：（软件实现）

动态重定位：执行过程中逐条指令执行时完成转换（硬件）

MMU：内存地址单元（将虚拟的内存地址翻译成实际的物理地址）

空闲内存管理

内存分配算法

然后：把该分配区分成两部分：一部分给程序；剩下的重新分配。

回收内存算法

主要考虑合并：上相邻、下相邻、上下都相邻、都不相邻

伙伴系统（Linux底层管理内存的方案）

最佳适配。
分配时检查大小，小于一半则分成伙伴；
合并时检查伙伴是否空闲，空闲则合并。

内存管理方案

进程是基本加载单位。

单一连续区

【特点】一段时间内只有一个进程在内存。简单，但是内存利用率低。

固定分区

分区大小不同。不同大小的进程进入不同的区的链表。（最早的手机）

可变分区

根据内存需要，分给进程，剩余的成为新的空闲区（洞）。
【问题】外碎片，导致内存利用率下降。
【解决方案】紧缩（压缩、搬家、紧致）技术：在内存中移动进程。

以上三种传统的方案一个进程占据内存中的一块连续区域，以下三种则进入内存中若干不连续区域。

页式

用户进程地址分块，称为页/页面
内存空间按同样大小分块，称为叶框。
分配时，逻辑相邻，但是物理不一定相邻。
典型页面大小：4K/4M
逻辑地址：页号+页内偏移。（自动划分）

段式

用户地址空间，按照程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名。
内存空间，被分成长度不等的区域，称为物理段。

逻辑地址：段号+段内偏移。（手动划分）

段页式存储

交换技术

内存不足怎么办？大地址空间装入小内存。

覆盖技术

把不会同时执行的程序段共享同一块内存（程序员自己声明，即所谓的对用户不透明），用于早期系统。

交换技术

交换到外存。

进程增长问题：预留空间

虚拟存储技术

页表和页表项的设计

MMU

地址转换

快表

页故障

缺页异常

软件策略

置换算法

其他相关技术

内存映射文件

由于虚存包括内存+磁盘，所以实际在操作文件时，可以把文件的一部分映射到虚存中。然后对文件的操作就相当于对内存的操作。

写时复制技术

文件

概述

进程是对CPU的抽象，地址空间是对内存的抽象，文件是对磁盘的抽象。
名字空间映射到磁盘空间

把各种设备抽象为文件有利于提供一个统一的I/O接口，如字符设备文件或者块设备文件。

存储介质

磁盘物理地址的形式：磁头号（盘面号）、磁道号（柱面号），扇区（512bytes）号
扇区：标题（10bytes)、数据（512）、ECC纠错信息（12-16)
访盘过程：寻道（沿半径移动找到磁道）、旋转（磁盘旋转找到扇区）、传输
SSD只有传输过程。

磁盘空间管理

系统启动后，专用块在内存中。

文件控制块和文件目录

文件目录有目录项（FCB）组成。

文件的物理结构

文件系统的实现

磁盘上内容

UNIX文件系统

文件系统 II

FAT16

FAT32

文件操作

文件系统的可靠性

文件的保护机制

UNIX中的文件访问控制

文件系统的性能

磁盘访问是瓶颈。

I/O系统

概述

特点

设备分类

目标

组成

I/O控制方式

I/O软件

I/O缓冲技术

凡是数据到达和离去速度不匹配的地方都采取缓冲技术
提高并行化能力

I/O设备管理的数据结构

死锁

基本概念

进程进入了等待状态

活锁

如果是轮询类的算法，进程有机会上CPU（不阻塞），但是没有进展。（如peterson算法）

饥饿

资源费配策略导致的。

死锁发生的必要条件

资源分配图（RAG）

使用有向图描述系统资源和进程状态
节点是进程或者资源
边：分配边或者申请边

死锁定理

资源分配图中没有环路，就没有死锁
有环路，可能存在死锁。
但是，如果只有一个资源实例，则变为充分必要条件。

解决死锁

不理

死锁预防（静态）

破坏四个必要条件之一

避免（动态）

对资源申请进行动态检查。分成几个区域。（系统）安全状态和（进程）安全序列。
安全状态没有死锁。
不安全状态一定会导致死锁发生。

银行家算法（Dijkstra提出）

检测和解除

允许死锁发生， 但是系统不断监视死锁发生了没有。一旦发生，解除死锁。

哲学家就餐问题

5个哲学家，5支筷子。
回忆对比读者/写者问题和生产者/消费者问题。

解决

上一篇 下一篇

猜你喜欢

热点阅读