计算机专业基础知识

计算机的字符与编码集

使用unicode

中文编码集，windows默认使用GBK

编程推荐使用UTF-8

文件的编码集 GB2312 支持中文

冯诺依曼机

输入设备

输出设备

存储器

运算器

控制器

计算机硬件：CPU 内存 硬盘 鼠标 键盘 显示器 网卡 电源 显卡 声卡 主板

CPU：存储器，运算器，控制器(里面有高速缓存)

计算机总线和IO设备

计算机的总线，计算机的输入/输出设备

总线的概述：USB(通用串行总线)

作用：提供了对外链接的接口，不同设备可以通过USB链接，促使外围设备接口的统一

PCI总线：显卡

没有总线需要各自设备之间的互相链接，有了总线就可以通过总线进行链接

总线的分类：片内总线，系统总线

片内总线：芯片内部的总线(高速缓存，控制器，中断系统，运算器)

总线可以简化 内部的电路结构

片内总线：高集成度芯片内部的信息传输线

系统总线：链接w外部设备的总线

系统总线：数据总线，地址总线 控制总线

数据总线：双向传输各个部件的数据信息

地址总线：传输数据的地址，寻址的作用，地址总线的位数与存储单元的位数有关

控制总线：监视不同组件的状态，是否准备就绪

总线的仲裁

主存和硬盘，IO设备交换数据 ，总线通过控制优先级来争夺资源，解决总线使用权的冲突问题

总线仲裁的方法：链式查询法 计时器定时查询法 独立请求法

链式查询：

问题：如果设备1,2同时发出仲裁请求，先到设备1，再到2

优点：电路复杂度低，仲裁方式简单

缺点：优先级低的设备难以获得总线的使用权

计时器定时查询

通过仲裁控制器发出1,2,3,4等信息，匹配到第几个第几个响应

独立请求法

每个设备均有总线独立链接仲裁器

设备科单独向冲裁器发送请求和接受请求

当同时收到多个请求信号，仲裁器有权限优先级分配使用权

优点：响应速度快，优先顺序可以改变

缺点：设备连线多，总线控制复杂

CPU与IO设备通信

输入输出接口的通用设计

CPU与IO设备的通信

程序程序中断

DMA(直接存储器访问)

CPU速度与IO设备速度不一致

程序中断：当外围s设备IO准备就绪时，向CPU发出中断信号

程序中断：提供了设备通知CPU的一种异步的方式，CPU可以高速运转的同时兼顾低俗设备响应

频繁打断CPU会降低效率

DMA(直接存储访问) DMA直接连接主存与I设备

DMA工作时不需要CPU的参与

有了DMA不需要打断CPU 工作，类似于脊髓

硬盘 显卡都有DMA的设备

计算机的存储器

计算机的存储器概览，计算机的高速存储器，计算机的主存储器与辅助存储器

存储器的分类：内存，U盘，固态硬盘，磁带，磁盘

存储介质分类

随机存储器(RAM)可读可写，与位置无关

串行存储器 与位置有关

只读存储器(ROM) 只读不写

计算机存储概览

1.缓存(容量最低，速度最快)

2.主存(内存)

3.辅存(硬盘)

计算机的CPU

计算机机的指令系统，计算机的运算器，计算机的控制器，指令的执行过程

由于CPU和存储器速度不一样所以引入cache

CPU—cache—主存—辅存

缓存—主存 将常用的软件进行内存置换(解决速度不匹配)

主存—辅存 解决主存容量不足的问题

主存储器(内存)----本质是RAM 随机存取存储器

为什么内存断电就会失去数据呢?

RAM是通过电容存储数据的，必须每隔一段时间刷新一次，刷新需要有电的存在，没有电，电子就会丢失

CPU里面的：

主存数据寄存器(MDR)----数据总线

主存地址寄存器(MAR)----地址总线

连接内存和CPU

32位最多只有4G的地址寻址空间 所以加再多的内存条没有用

64位操作系统地址范围有，支持2的34次方GB

电梯算法(磁盘的读取)

先来先服务算法

最短寻道时间算法

扫描算法(电梯算法)：每次只往一个方向移动，到达一个方向需要服务的劲头再反方向

循环扫描算法：只往一个方向读取到劲头置到最开始的地方

计算机的高速缓存

高速缓存的原理

字：放在存储单元中二进制代码的组合(计算机的最小的单位)

字块：可以理解为一组字(字块包含多个字)

主存：2的n次方个字，一个存储单元可以理解为一个字。一组字块就是字块。

寻址过程：所寻找的字属于哪个字块，字，字块的地址

字的地址：前m位指字块的地址

后b位指定字在字块中的地址

一个字块共B个字，主存共M个字块

字块数和地址之间的关系：2的对数之间的关系

字节：B(byte) 1kb = 1024byte 位：bit(0,1)

计算地址的时候需要log2操作

主存的容量大于缓存的容量，说明主存的字块数大于缓存的字块数

CPU所需要的数据在缓存中就从cache中拿，不在就在主存中拿

量化CPU从cache中的几率：缓存命中率(衡量缓存的性能指标)

从主存中替换到cache中的策略：

随机算法：随机选取一个位置来替换

先进先出算法(FIFO)：看做是一个先进先出的队列，cache满了之后淘汰1号位，进来9号位

最不经常使用算法(LFU)：使用额外的空间记录字块使用的频率，计数法

最近最少使用算法(LRU)：优先淘汰一段时间没有使用的字块，可以使用双向链表，将当前访问节点置于链表前面(保证头部节点是最近使用的)，满了之后就开始淘汰，每次最近使用就将其置到最前面

计算机的指令系统

操作码字段 ：操作码指明指令要完成的操作，操作码的位数反映了机器的操作种类

地址码字段：指定数据的地址

三地址指令，二地址指令，一地址指令

机器指令的操作类型：寄存器之间，寄存器与存储单元之间，存储单元之间

数据读写，jiaohua 地址数据，清零置一等操作

计算机寻址系统

机器指令的寻址方式：顺序寻址，跳跃寻址

数据寻址：立即寻址，直接寻址，间接寻址

计算机的控制器(CPU)

控制器是协调控制计算机的运行的

程序计数器用来存储下一条指令的地址，循环从程序计数器中拿出指令，当指令被拿出时指向下一条指令

时序发生器：发送时序脉冲，CPU根据不同的时序脉冲进行工作

指令译码器：是控制器主要部件之一，计算机指令由操作码和地址码组成，翻译操作码对应的操作以及控制传输地址码对应的数据

指令寄存器：从主存或高缓取计算机指令

主存地址寄存器：保存当前CPU正要访问的内存单元地址

主存数据寄存器：保存当前CPU正要读写的主存数据

通用寄存器：用于暂时存放或传送数据的

计数，发生，译码， 寄存，总线

计算机的运算器

数据缓冲器，ALU，通用寄存器，状态字寄存器，总线

数据缓冲器：分为输入缓冲和输出缓冲

输入缓冲暂时存放外设送来的数据

输出缓冲暂时存放送往外设的数据

ALU

算数逻辑单元，是运算器的重要组成

完成常见的位运算，算数运算(加减乘除)

计算机指令的执行过程

取指令-----分析指令-----执行指令

从指令缓存中取指令-----送到指令寄存器-----送到指令译码器进行译码-----发出控制信号-----程序计数器+1指向下一条指令-----装载数据到寄存器------ALU处理数据-----记录运算状态------送出运算结果

CPU的流水线设计(类似于工厂装配线)

流水线效率提升3倍

进制运算的基础知识：进制运算的基础

二进制数据的表示方法：有符号数与无符号数，二进制的补码表示法，二进制的反码表示法，小数的二进制补码表示

二进制数据的运算：定点数与浮点数，定点数的加减法运算，浮点数的减法运算，浮点数的乘除法运算

操作系统

操作系统的演进：无操系统

人工操作

用户独占

CPU等待人工操作

资源利用率很低

批处理系统

无需等待人工操作

批量处理任务

资源利用率提升

多道程序设计

分时系统：

人机交互

多用户共享

即时调试程序

资源利用率提升

多道程序设计：早期批处理系统一次只能处理一个任务

多道程序设计：计算机内存中可以存放多个程序，多道程序在计算机的管理程序下互相穿插运行

五大功能

进程管理(进程管理之进程实体，进程管理之五状态模型，进程管理之进程同步，Linux的进程管理)

存储管理(内存的分配与回收，段夜式存储管理，虚拟内存，Linux的存储管理)

作业管理(进程调度，死锁)

文件管理(操作系统的文件管理，Linux的文件系统，Linux的文件的基本操作)

设备管理

操作系统概览

what & why

操作系统是管理硬件和软件资源的计算机程序。

管理配置内存，决定供需顺序，控制输入输出设备。

操作系统提供让用户和系统交互的的操作界面。

在不同的设备上，操作系统可以向用户呈现不同的状态。

管理硬件，提供用户交互软件的系统

我们不能直接操作硬件

提供了统一的操作界面

操作系统也使更多人使用了计算机

操作系统的基本功能

处理器资源

存储器资源

IO设备资源

文件资源

用户无需面向硬件接口编程

IO设备管理软件，提供读写文件接口

文件管理软件，提供文件接口

操作系统实现了对计算机资源的抽象

操作系统提供了用户与计算机之间的接口

操作系统的基本功能

图像窗口形式

命令形式

系统调用形式

操作系统的相关概念

并发性

多道程序概念是并发的基础

共享性

多个程序可以同时使用主存资源

共享根据属性可分为两种方式：互斥共享形式，同时访问形式

当A占用资源，等释放了之后才能使用

同时是宏观的，看上去是同时访问

短时间看还是互斥的

虚拟性

虚拟性表现为把一个物理实体转变为若干个逻辑实体

物理实体是真实存在的，逻辑实体是虚拟的

虚拟的技术主要有时分复用技术，空分复用技术

时分复用技术：资源在时间上进行复用，不同程序并发使用

多道程序分时使用计算机资源

时分复用技术

空分复用技术

空分复用技术用来实现虚拟磁盘，虚拟内存等

提高资源利用率，提升编程效率

虚拟磁盘技术

物理磁盘虚拟为逻辑磁盘C,D,E等逻辑盘

使用起来更加方便

虚拟内存技术

在逻辑上扩大程序的存储容量

使用比实际内存更大的容量

大大提升编程效率

异步性

在多道程序下面允许多个程序并发执行

进程在使用资源时可能等待或放弃

进程执行不是一气呵成，是走走停停的

进程管理之进程实体

为什么需要进程

进程是系统进行资源分配和调度的基本单位

进程作为独立运行的载体保障程序的正常运行

进程的存在使操作系统资源利用率大大提升

进程实体

主存中的进程形态：标识符，状态，优先级，程序计数器，内存指针，上下文数据，IO状态信息，记账信息

标识符：标识唯一的进程(进程ID)

状态：标记进程的状态(运行态，阻塞态)

程序计数器：进程即将被执行的下一条指令的地址

内存指针：程序代码，进程数据相关的指针

上下文数据：进程执行时处理器存储的数据(寄存器，cache)

IO状态信息：被进程IO操作所占用的文件列表

记账信息：使用处理器时间，时钟总和等

总结起来：进程的标识符，处理机的状态，进程调度信息，进程控制信息

进程控制块

用于描述和控制进程运行的通用数据结构(每个进程都有PCB进程控制块)

记录进程当前状态和控制进程运行的全部信息

PCB的使得进程能够独立运行的基本单位

PCB是操作系统进行调度经常会被读取到的信息

PCB是常驻内存的，存放在系统专门开辟的PCB区域内

操作系统对进程的调度其实是对线程的调度

进程：资源分配的基本单位，独立调度的基本单位，进程系统开销大，进程IPC

线程：不拥有资源，独立调度的最小单位，线程系统开销小，读写同一进程数据通信

进程管理之无状态模型

创建 就绪 终止 阻塞 执行

当进程被分配到除CPU以外所必要的资源后

只要再获得CPU的使用权，就可以立即运行

其他资源都准备好，只差CPU资源的状态就为就绪状态

就绪进程就会排成就绪队列

进程获得CPU，其程序正在执行成为执行状态

在单核处理器时，在某个时刻只能有一个进程处于执行状态

进程的阻塞状态

进程因某种原因：其他设备为准备就绪而无法继续执行，从而CPU放弃的状态为阻塞状态

阻塞队列：存放阻塞的进程

创建状态：分配PCB，插入就绪队列

创建进程时拥有PCB但其他资源尚未就绪的状态为创建状态

操作系统提供fork函数接口创建进程

系统清理，PCB归还

进程结束由系统清理或者归还PCB的状态称为终止状态

进程管理之进程同步

进程间同步：

为什么需要进程间同步

进程间同步的原则

线程同步

生产者消费者问题

进程的同步：

空闲等待

忙则等待

有限等待

让权等待

进程间同步的方法：

消息队列

共享存储

信号量

进程间同步：

互斥量

读写锁

自旋锁

条件变量

Linux分为前台进程，后台进程，守护进程

占用终端：前台进程

没有占用终端，不和用户进行交互 & 符号结束就可以

可以将内容重定向到文件里面

linux中以d结尾的一般为守护进程(sshd，httpd，mysqld)

linux中进程的状态

R：运行状态

S：睡眠状态

D：IO等待状态

T：暂停状态

Z：退出状态(僵尸进程)

作业管理之进程调度

进程调度的概述

进程调度是值计算机通过决策决定哪个就绪程序可以获得CPU使用权(多道程序设计)

保存旧进程的运行信息，请出旧进程

选择新进程，准备运行换将并分配CPU

进程的调度

就绪队列的排队机制

为了提高进程调度的效率(排队)

选择运行进程的委派机制

调度进程按照一定的策略选择就绪进程，将CPU资源分配给它

新老进程的上下文切换机制

进程的调度

抢占式，非抢占式

抢占式切换频繁，开销大，相对公平

非抢占式切换次数少，开销小，不公平

进程调度的算法

先来先服务

短进程优先调度算法

高优先权优先调度算法(前台进程的优先级会高于后台进程)

时间片轮转算法

作业管理之死锁

死锁的产生：竞争资源，进程调度顺序不当

竞争资源不够共享资源的数量不满足各个进程的需求

会因为共享资源的竞争造成死锁

死锁的必要条件

互斥条件

请求保持条件(可以一次性申请所有需要的资源)

不可剥夺条件(当一个进程请求新的资源得不到满足，必须释放资源)

环路等待条件(按照线性排序，申请必须按照需要递增申请，按照顺序申请)

银行家算法

客户申请贷款有限，每次申请需要声明最大的资金量

银行家能在满足贷款时，都应该给用户贷款

客户在使用贷款后，能够及时归还

存储管理之内存分配与回收

单一连续分配的方法(只能在单用户，单进程的操作系统中使用)

固定分区分配方法

固定分区分配支持多道程序最简单的存储分配方式

内存空间被划分为若干固定大小的区域

每个分区只提供给一个程序使用，互不干扰

动态分区分配

内存分配的过程

首次适应算法(FF算法)(循环适应算法)

分配内存是从开始顺序查找适合内存区(链表)，遍历链表若没有合适的空闲区，则该次分配失败

最佳适应算法(BF算法)

按照内存大小进行排序(避免一些大材小用的情况)

快速适应算法(QF算法)

操作系统如何管理进程的空间

页式存储管理

段式存储管理

段页式存储管理

存储管理之虚拟内存

虚拟内存概述

有些进程实际需要内存很大，超过物理内存的容量

多道程序设计，使得每个程序可用的物理内存更加稀缺

不可能无线增加物理内存，物理内存总有不够的时候

把程序的内存划分，将暂时不使用的内存放在辅存中

程序的局部性原理

CPU访问存储器时，无论是存储指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续趋于中

程序运行时，无需全部转载至内存，装载部分即可

从用户层面来看，程序拥有很大的空间(虚拟内存

)

虚拟内存的置换算法

先入先出

最不经常使用算法

最近最少使用的算法

主存页面替换的时机：当主存缺页的时候就会进行替换

虚拟内存的置换算法

替换策略发生在cache-主存层次，主存-辅存层次

cache-主存层次的替换策略主要是为了解决速度问题

主存-辅存层次主要是为了解决容量问题

linux的存储管理

buddy内存管理算法

buddy算法是经典的内存管理算法

算法基于计算机处理二进制的优势具有极高的效率

算法主要为了解决内存碎片的问题

内存页内碎片，内存页外碎片

页内碎片：已经被分出去不能再利用了

页外碎片：没有被分出去也不能被利用了

向上取整2的幂大小

伙伴系统buddy

回收分配的内存，找伙伴内存。

buddy算法是经典的内存管理算法

算法基于计算机处理二进制的具有极高的效率

算法主要为了解决内存外碎片的问题

将内存外碎片问题转化为内存内碎片问题

linux交换空间

swap(交换空间)是磁盘的一个分区

linux物理内存满时，会把一些内存交换swap空间

linux中输入 top命令

是冷启动的依赖，启动需要大量的内存，将不怎么使用的内存交换到物理内存中

系统睡眠依赖

大进程空间依赖

swap空间 VS 虚拟内存

操作系统的文件管理

文件的逻辑结构

辅存的存储空间分配(磁盘)

目录管理

逻辑结构文件的类型

有结构文件(文本文件，文档，媒体文件)

无结构文件(二进制文件，链接库)

文件的逻辑结构

文件内容由定长记录和可变长记录组成

定长记录存储文件格式，文件描述等结构化数据项

可变长记录存储文件的具体内容

无结构文件

也成流式文件

文件内容长度以字节为单位

例：EXE文件 dll文件 so文件

顺序文件

顺序文件是按照顺序存放在介质中的文件

磁带的存储特性使得磁带文件只能顺序存储文件

顺序文件是所有逻辑文件中存储效率最高的

但是对顺序文件的增删改查效率比较低

为了解决此问题引出了索引文件

有一张索引表

辅存的存储空间分配

链接分配可以将文件存储在离散的盘块中

需要额外的存储空间存储文件盘块的链接顺序

FAT表：FAT文件系统 类似于路由表

读取文件需要将整个文件加载到内存然后进行检索

索引分配

把文件的所有盘块集中存储(索引)

读取某个文件时，将文件索引读取进内存即可

辅存的存储空间分配

主存和辅存都用了空闲表和空闲链表

将所有空闲的盘块存在一个链表

每个链表节点存储空闲盘块和空闲数目

重点：位示图

位示图的优点：

维护成本低

位示图可以非常容易找到空闲盘块

位置图使用0/1比特位，占用空间小

进阶补充

生产者，消费者模型/哲学家进餐问题

保护临界资源，进行通信

线程间同步：互斥量，读写锁，自旋锁，条件变量

进程间同步：共享内存，域套接字

用户态与内核态

上下文切换

协程

编写性能良好的程序指南

线程同步之互斥量

两个线程争抢共享资源，互斥使用。

原子性，一系列操作不可中断的特性

互斥量又称互斥锁(解锁和加锁)

互斥量是最简单的线程同步的方法

两个状态可以保证访问资源的串行

操作系统直接提供了互斥量的API

开发者可以直接使用API完成资源的加锁解锁的操作

自旋锁

自旋锁的模型和互斥锁模型一样

自旋锁也是一种多线程同步的变量

使用自旋锁的线程会反复检查锁变量是否可用

自旋锁不会让出CPU

自己死循环等待锁的释放

自旋锁避免了进程或线程的上下文(因为是自己死循环)的开销

操作系统内部很多地方使用自旋锁

自旋锁不适合在单核CPU使用(因为死循环)

读写锁

对互斥资源和自旋锁的改良

当临界资源(数据库)，是一种特殊的自旋锁

临界资源多读少写

不会改变临界资源

读和写互斥，读和读不互斥

线程同步之条件变量

缓冲区没有数据时，消费者不许消费，必须等待

缓冲区满了时，不允许生产者往缓冲区生产，生产者必须等待

可以更加严谨的约束

条件变量也提供了API

条件变量是一种相对复杂的线程同步方法

条件变量允许线程睡眠，直到满足某种条件

当满足条件时，生产者可以向该线程(消费者)发信号，通知唤醒

线程同步方法总结

互斥量 自旋锁 读写锁

先加锁，使用临界资源，后解锁

加锁后其他不能访问临界资源

解锁后，其他消费者才能访问临界资源

使用fork系统调用创建进程

c语言的系统调用

fork创建的进程初始化状态与父进程一样

父进程调用时子进程也会调用，fork函数会返回两次

用fork可以创建一个新的进程

所有语言底层创建进程都是fork系统调用的

进程同步之共享内存

多进程共享物理内存的

由于操作系统的进程管理，进程间的内存空间是相互独立的

进程空间通过页表映射到共享内存的一片分区中去

共享存储允许不相关的进程访问同一片物理内存(原理：将物理内存映射到进程的页表里面去，使得进程通过页表访问内存)

共享内存是两个进程之间共享和传递数据最快的方式

后台很多高性能服务都是通过共享内存实现

缺点：共享内存未提供同步机制，需要借助其他机制管理访问，以避免并发访问带来的问题

使用共享内存的四个步骤

向操作系统申请共享内存-----连接到进程空间------使用共享内存------脱离进程空间(删除)

client 共享内存 server

共享内存是传递数据最快的方式

Unix域套接字

客户端创建套接字，绑定套接字，监听套接字，接受处理信息

创建套接字，链接套接字，发送信息

进程同步之UNIX域套接字

提供了单机简单可靠的进程同步服务

只能在单机使用，不能跨机器使用

双向链表实现原理

往头部加入节点

往头部插入节点：将新的节点指向第一个节点，将第一个节点的上一个指向前一个节点，将头部指针指向新的节点

# 实现链表节点

class Node:

def __init__(self,key,value):

self.key = key

self.value = value

self.prev = None

self.next = None

def __str__(self):

val = {{}: {}}.format(self.key,self.value)

return val

def __repr__(self):

val = {{}: {}}.format(self.key,self.value)

return val

# 双向链表实现head指针 tail指针 链表的容量

class DoubleLinkList:

def __init__(self, cap = 0xffff):

self.cap = cap

self.head = None

self.tail = None

self.size = 0 # 当前链表存储了多少个节点

# 从头部添加

def __add_head(self,node):

if not self.head:

self.head = node

self.tail = node

self.head.next = None

self.tail.next = None

else:

node.next = self.head

self.head.prev = node

self.head = node

self.head.prev = None

self.size += 1

return node

# 从尾部添加

def __add_prev(self,node):

if not self.tail:

self.head = node

self.tail = node

self.head.next = None

self.tail.next = None

else:

self.prev.next = node

node.prev = self.tail

self.tail = node

self.tail.next = None

self.size += 1

return node

# 删除任意节点

def __del_node(self,node):

if not node:

node = self.tail

if node == self.tail:

pass

elif node == self.head:

pass

else:

node.prev.next = node.next

node.next.prev = node.prev

self.size -= 1

return node

# 弹出头部节点

def __del_head(self):

pass

# 弹出尾部节点

def __del_prev(self):

pass