计算模型

计算模型是一种表达计算方式的模型，是我们日常见到的物理计算机的计算方式的抽象。有穷自动机和图灵机是计算模型。

有穷自动机

可以从我们常见的状态机来理解，比如tcp网络状态机，缓存一致性状态机，编译原理中的DFA,业务中的订单流转状态机都属于状态机。自动机是一种模型机，它根据系统当前状态和一个给定的输入来确定系统下一步将进入哪个状态或者下一步执行哪个动作。但它只会从一个状态进入另一个状态，并不会有其他额外的数据存储。于是，我们根据自动机的特点，构建出一种模型,这种模型可以用来识别和判断字符串是否符合正则表达式，状态转换是否合法等等.
用一个寄存器来存储当前状态，预先给这个模型设定好状态转化图。让模型一开始处于Start状态,然后不断读取输入字符串/状态转换路线，因为是有限的状态机，最终会终止.如果终止状态可以被Accept，则是合法.
注意 有穷自动机的计算能力是很有限的，只能根据给定的状态机来判断输入是否合法

图灵机

仔细思考我们可以发现，上面的计算模型：

1. 只能保存一个状态，而且不可保存数据，只能读取外部输入.于是我们可以增加另外一块存储区域,用来支持写数据。
2. 在读取输入字符串只能不断向前移动，不能向后移动.
   于是，设计这样一种模型.这时输入字符串(不再是固定的状态转换路线)就可以是下面几种操作:

• 读存储区的数据
• 向存储区写数据
• 数据运算
• 读指针向后跳转
  这就是经常说的图灵机纸带，读写头可以向前移动(不断读取新指令),向后移动(重新执行先前执行过的指令),移动到空白纸带(读写存储区)
  注意 图灵机已经拥有很强大的计算能力

通用图灵机

仔细思考我们可以发现，图灵机的模型，给定一个问题的算法后，便可以解决这一类问题。但是对于输入字符串该如何编写，如何用指令来描述解决问题的算法？所以需要对图灵机支持的指令进行规定。于是，我们又有一个新的模型，把指令集也作为一种输入给图灵机，这样图灵机就可以根据指令集和预先给定的算法来自动的处理和解决问题。这种将算法和指令集作为输入的模型称为通用图灵机(和图灵机的计算模型和计算能力并无不同)，这样，我们就可以不需要让模型依赖于解决问题的算法.

冯诺依曼机

下面，我们将图灵机做进一步的组件拆分，把读写输入指令的叫做控制器，支持存储的区域叫做存储器，把运算指令单独作为一个部件，再加上输入和输出设备，这样图灵机就可以根据预先给定的指令，来处理输入数据，并将结果传输到输出设备中。

注意 冯诺依曼机拥有和图灵机一样的计算能力，此外还具备和输入输出能力。这也是现代计算机的组成模型

计算机软硬协同

代入上面的理论，可以发现，具体的一个物理计算机实际上是通用图灵机的实现，物理计算机所支持的指令集就是通用图灵机的输入，相当于预先给定了一个输入，算法的输入就交给程序员。计算机系统分为硬件和软件，那么软件如何驱动硬件呢，就要根据机器支持的指令集,访问内存模型，访问输入输出设备模型来编写指令，硬件就只管读取输入的指令串，就实现了软件编程。一般的指令集有intel和AMD的x86，AArch64,mips等
注意 x86分为32位和64位,一般叫做x86_32和x86_64(简称为x64)。AArch32和AArch64是arm架构下的32位和64位指令集。IA64是intel不兼容的x86_32的64位指令集，安装在安腾处理器上，主流市场不常见.

计算机算术

整数表示:补码表示(原理是溢出截断情况下运算的等价性)参考
浮点表示: 科学计数法的表示，尾数和指数参考

计算机体系结构

cpu

cpu包含了冯诺依曼机中的运算器和控制器(CS,IP).CPU不断执行取出指令，解码指令，执行指令。cpu让IP寄存器始终指向指令区域的下一条，每执行一条指令，ip就指向下一条指令，直到碰到异常或者程序退出。CPU会支持中断，当外部设备或者使用中断指令中断cpu时(外中断)，cpu会跳转到中断处理函数处。cpu内部在遇到运算异常，访问内存权限异常也会发生中断(内中断),并转到中断处理函数处。CPU和其他部件通过总线来相连，总线包括地址总线(用来对内存单元寻址)，数据总线(传输数据)，控制总线(发送控制信号)

内存

内存以字节为基本单位划分为内存单元，cpu通过地址总线来确定访问哪个内存单元。内存地址范围是从0-最大值

输入输出设备

比如磁盘，GPIO，flash等，cpu通过读写寄存器并按照固定的协议和外部设备交互。

x86-16汇编

x86-16寄存器

分为通用寄存器，段寄存器,标志寄存器等。
通用寄存器包括：ax,bx,cx,dx
段寄存器包括:ds,cs,ss,es
标志寄存器： eflags(用来存储执行指令过程中溢出，是否为0等标志)

x86实模式访存模型

cpu一加电就进入实模式，实模式的内存模型是下面这样的

物理地址=段地址16+偏移地址
cpu访问内存按照实际地址来访问，比如访问0x01就是访问从ds16+0x01位置开始向递增方向一个字节的内容。偏移地址最多使用4个部分来指定(应对不同的数据结构)

1

target address = BaseReg + IndexReg + Disp

可以按照实际中常用的访问类型来理解：

1. 最简单的就是只有一个Disp,实际上就是绝对地址访问，比如 Disp = 0x01
2. 要用到BaseReg一般是访问某个内存块内部的单元
3. 要用到IndexReg部分的一般是数组访问,比如BaseReg指向数组首地址，IndexReg指向数组第几个元素，当数组存的是结构体时，Disp可以表示结构体内的成员

注意 x86实模式下如果不加段前缀，则默认使用的数据段前缀DS.保护模式下分段策略由GDT,LDT和段选择子决定

传送指令(前面是目的操作数，后面是源操作数)

向寄存器传输立即数 mov ax,01H
把内存单元传输到寄存器 mov ax,[01]
把寄存器传输到内存单元 mov [01],ax
寄存器之间传参 mov ax,bx,把bx传输给ax
注意 段寄存器只能从通用寄存器传送

运算指令

add和sub，sub ax,bx是 ax= ax - bx，这两个是无进位/借位的加减

adc和sbb , 这两个是无进位/借位的加减
mul和div 这两个是无符号乘法除法,并且是单操作数
被乘数放在AL/AX中，这是x86的默认寄存器规则，有些指令会默认使用特定的寄存器

1
2

MUL reg/mem8
MUL reg/meml6

如果乘积的高半部分不为零，则 MUL 会把进位标志位和溢出标志位置1。例如，当AX乘以一个 16 位操作数时，乘积存放在 DX和AX(从高到低)寄存器对中。其中，乘积的高16位存放在DX，低16位存放在AX。如果DX不等于零，则进位标志位置1，这就意味着隐含的目的操作数的低半部分容纳不了整个乘积。
被除数都是放在DX:AX中

1
2

DIV reg/mem8
DIV reg/meml6

问题 x86乘除法支持多操作数码？

控制跳转指令

跳转分为近转移(只修改ip，段内跳转)和远转移(同时改变cs和ip,段间跳转)，

• 标号跳转:
  jmp short 标号(jmp near pt 标号) 近转移
  jmp far ptr 标号 远转移
• 绝对地址跳转,跳转地址由寄存器或者内存单元给出
  jmp reg
jmp word ptr [内存单元]
jmp dword ptr [内存单元], 从内存单元开始处存放着2个字(x86字是16位),高位是目的段地址，低位目的偏移地址
• 有条件跳转
  jcxz 如果cx==0就跳转
  跳转可以用来实现分支和循环

入栈和出栈指令

push ax
push 01h
pop ax

调用子过程指令

call 和ret/retf
call 标号 相当于

1
2

push ip 
jmp near ptr 标号

ret相当于

1

pop ip

因此也对应近跳转和远跳转，标号跳转和绝对地址跳转。绝对地址跳转和上面类似，同时支持寄存器和内存单元

中断指令

int n,向cpu发起中断.cpu便会查找中断表中的中断号n所在的位置，跳转到中断号n对应的处理函数去处理
int n 相当于

1
2
3
4
5

pushf 
push cs
push ip
# 查中断表得到中断处理函数
call cs:ip

iret从中断处返回,相当于

1
2
3

pop ip
pop cs
popf

汇编语法

• intel语法

1. 寄存器前无前缀
2. 源操作数在后，目的操作数在前
3. 内存单元用方括号表示,并且地址是[INDEX * WIDTH + BASE + OFFSET]
4. 立即数无前缀，十六进制以h结尾

• AT&T 语法

1. 寄存器前有百分号
2. 源操作数在前，目的操作数在后
3. 内存单元用圆括号表示,并且地址是offset(base, index, width)的格式
4. 立即数前被冠以“$”,十六进制数前被冠以“0x”

汇编器

gnu汇编

主要是as汇编器，gcc将c语言编译后也是调用的as汇编器

nasm汇编

另外一种汇编器,同时支持intel和AT&T语法

伪指令

伪指令是汇编器支持的指令，比如有IF,DD等。这些不会翻译成机器指令，和编译器的宏和include有点类似

使用qemu学习汇编

安装qemu(我是ubuntu系统)

1

sudo apt install qemu

如果机器上出现了qemu-system-x86_64 qemu-system-i386就表示安装成功了

1
2
3
4
5

org 0x7c00 ;告诉汇编器程序的入口地址
mov ax,1
mov bx,2
add ax,bx				  
db 0x55,0xaa  ;结束表示，整个段程序的大小正好为510字节，占满一个扇区。

编译汇编代码并制作启动盘

这里原理就是机器加电bios自检通过后，bios会加载磁盘上第一个扇区(MBR扇区),并执行其中的代码。第一个扇区是用来引导操作系统。把咱们写的汇编程序放入这个扇区，bios会加载并执行这段代码

编译boot代码

要加-f bin
nasm fat.s -f bin -o ../out/boot.bin

制作软盘(用linux的loop设备将文件模拟成设备)

dd if=/dev/zero of=../out/floopy bs=512 count=2880
sudo losetup /dev/loop11 ../out/floopy
sudo mkfs.fat /dev/loop11 这步会留出主分区
sudo losetup -d /dev/loop11 卸载设备

将上面编译得到的bin写入mbr,写入上面软盘的第一个扇区
dd if=../out/boot.bin ibs=512 of=../out/floopy obs=512 count=1 seek=0 conv=notrunc

使用qemu启动，并使用gdb debug

-ex 表示启动时执行的命令, -fda指定启动的软盘
qemu-system-i386 -fda ../out/floopy -s -S
gdb -ex ‘set architecture i8086’ -ex ‘target remote :1234’ -ex ‘b *0x7c00’ -ex ‘layout asm’
这里加的断点0x7c00是x86架构加电后ip指向的位置，咱们编写汇编程序也是放在0x7c00.
注意 如果你是使用qemu-system-x86_64平台启动的,需要把架构设置成i386:x86-64即 set architecture i386:x86-64,具体看gdb报错信息

后续

你就可以写更多的汇编，并用qemu，gdb调试了,此时汇编是跑在裸机上.后面你会发现，这步实际上就是操作系统boot.但这对于底层的学习才是万里长征第一步，后面还有x86-32,x86-64,x86-64的AVX，保护模式和长模式

汇编的用处

在操作系统内核中，经常要用到，比如机器加电引导操作系统(裸机上)，并设置保护模式，在网卡接收数据触发中断，陷入内核时，做的上下文切换(这种一般是被c调用)。

引用

1. 从图灵机到冯诺依曼机
2. 计算复杂性-现代方法
3. 汇编语言-王爽
4. x86汇编语言从实模式到保护模式
5. x86指令手册

linux 源码目录结构

linux 入口

file_operation

系统编程

多路复用

管道

tcp server