按字编址与按字节编址
如今计算机分为32位和64位，其实就是代表总线进行数据传输时一块数据的内存大小，即字的大小
32位计算机：32位(bit)=4字节(byte)=1字(word)
64位计算机：64位(bit)=8字节(byte)=1字(word)
很显然一字等于几个字节不是固定的，只和计算机硬件有关
作为一些基础的编程语言数据类型单位，设定如下(b->bit,B->byte)
byte：1字节
short：2字节
int：4字节
long：8字节
float：4字节
double：8字节
char：2字节
boolean：1字节
ASCII：英文字符（1字节）、中文汉字（2字节）
UTF-8：英文字符（1字节）、中文汉字（3字节）
Unicode：英文字符（2字节）、中文汉字（2字节）
1byte=8bit,1024byte=1KB,1024KB=1MB,1024MB=1GB,1024GB=1TB
1KB=2的10次方B，1MB=2的20次方B
存放一个机器字的存储单元，通常称为字存储单元，相应的单元地址叫字地址。 存放一个字节的存储单元，称为字节存储单元，相应的地址称为字节地址。 如果计算机中可编程的最小单位是字存储单元，则该计算机称为按字寻址的计算机。 如果计算机中可编程的最小单位是字节，则该计算机称为按字节寻址的计算机。 一个机器字可以包含数个字节，所以一个存储单元也可以包含数个能够单独编制的字节地址。
不过题目中一般都是按字节编址，只有按字节编址才利用相应考察
例题.某存储器按字节编址，容量为1MB，cache为256B，块大小为4个字，一个字为4个字节。
（1）cache地址为几位？有多少块？
（2）主存地址为几位？有多少块？
答案
1MB=2的20次方B，256B=2的8次方B，一个块=16个字节=2的4次方个字节 按字节编址，则cache地址位数为8，主存地址位数为20 2的八次方/2的四次方=16个块 同理主存有2的16次方个块在写多点就到计组了，让我们回到操作系统内存
三种程序地址装入方式
- 绝对装入：编译时直接转换（前提是提前知道程序装入模块中的地址）
- 静态重定位：编译、链接时地址都是从0开始，装入过程中完成地址转换， 必需分配其要求的全部内存空间，在运行时不能移动
- 动态重定位：动态运行时装入，地址转换推迟到程序真正要执行时才进行
回顾程序从编译到运行的阶段
预处理->编译->汇编->链接
具体详情见“从0开始的C++”栏目//目前还没有！//
总之，装入发生在链接之后，毕竟生成的可执行文件装入到内存中开始运行
同时，链接也有三种方式
- 静态链接：程序运行之前将所有所需库函数链接成完成可执行文件（装入）
- 装入时动态链接：边装入边链接
- 运行时动态链接：执行时需要目标模块时才进行链接
内存管理
F&Q：操作系统作为系统资源的管理者，需要对内存进行管理，要管理什么呢？
- 负责内存空间的分配与回收
- 需要提供某种技术从逻辑上对内存空间进行扩充
- 需要提供地址转化功能，负责程序的逻辑地址与物理地址的转化
三种方式的后两种
- 提供内存保护功能
设置上下限寄存器和利用重定位寄存器、界地址寄存器进行判断
覆盖与交换
覆盖：将程序分为多个段，常用的常驻内存，不常用的需要时调入，分为“固定区”与“覆盖区”
缺点：程序员必须声明覆盖结构，对用户不透明，增加编程负担，且是一直用调用时间交换空间的方式
交换：把不需要的整个进程换出外存，把已具备运行条件的进程换入内存
中级调度就是这个意义，另外，暂时换出外存等待的进程的状态叫挂起状态
Q&A：1、外存什么位置保存被换出的进程？2、什么时候交换？3、换出什么进程？
- 换入磁盘中的对换区，所以说对换区采用连续分配方式，输入输出速度比文件区快很多
- 在进程运行很多且内存吃紧是进行，例如频繁缺页时
- 优先换出阻塞进程，优先级低的进程，驻留时间等。。。（PCB常驻内存）
连续分配管理方式
这种方式的前提是分配的内存空间必须是连续的
内存分区历史：
- 单一连续分配：优点：实现简单，无外部碎片；缺点：只能单任务，空间利用率低，有内部碎片（未利用的内存区）
- 固定分区分配：分为相同分区大小与不同分区大小（需要分区说明表）；优点：实现简单，无外部碎片；缺点：会产生内部碎片，内存利用率低
- 动态分区分配：不会预先划分内存分区，根据进程大小动态建立分区
很显然动态分区分配为现代常用的最优分配方式
所以接下来会以动态分区分配为核心探讨研究
Q&A：1、每个分配的分区用什么方式来储存？2、多个分区都满足需求时，选哪个？3、如何分配/回收分区？
- 空闲分区表/空闲分区链
- 见“空闲分区算法”
- 对于空闲分区表/链，一般情况下修改数据/删除结点（表）就可，不一定会按照地址递增顺序来排列，同时需要将处理过后相邻的空闲分区合并
内部碎片：分配给进程的内存区域没用上的部分
外部碎片：内存中某些空闲分区太小哦啊难以利用(解决方式：“紧凑”技术)
对于动态分区分配，无内部碎片，有外部碎片
动态分区分配算法
#include <iostream>
#include <fstream>
#include<string>
#include<vector>
#include<functional>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
typedef struct//分区
{
static int PartitionNum;//分区数量
int m_PartitionId;//分区首地容量址
int m_PartitionSize;//分区
int m_BlockId;//空白分区首地址
}Partition;
typedef struct//进程控制块
{
static int PCBNum;//进程数量
string m_PidName;//进程名称
int m_PidSize;//进程大小
}PCB;
void ReadData();//读入数据
void Display1();
void Display_Partition();
void Display();//输出分区完后各个分区的状态
void Display_PCB();//显示进程的状态
void FirstFit();//首次适应算法
void NextFit();//循环首次适应算法
void BestFit();//最佳适应算法
void WorstFit();//最坏适应算法
int main()
{
int choose;
while (1)
{
cout << "请选择实现的算法：" << endl;
cout << "***** 1 - 首次适应算法 " << endl;
cout << " 2 - 循环首次适应算法 " << endl;
cout << " 3 - 最佳适应算法 " << endl;
cout << " 4 - 最坏适应算法 " << endl;
cout << " 0 - 结束 *****" << endl;
cout << "输入你的选择 ： ";
cin >> choose;
switch (choose)
{
case 0:exit(0); break;
case 1:FirstFit(); break;
case 2:NextFit(); break;
case 3:BestFit(); break;
case 4:WorstFit(); break;
default:cout << "请输入正确的序号：" << endl;
}
}
system("pause");
return 0;
}
首次适应算法（First Fit）
每次从低地址开始查找，找到第一个能满足大小的空闲分区
void FirstFit()//首次适应算法
{
bool flag = false;
int i, j;
string choose;
ReadData();
//cout << "输入MIN:";
//cin >> MIN;
//Display_PCB();
do
{
Display_Partition();
pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
cout << "输入进程名称：";
cin >> pcb[PCB::PCBNum - 1].m_PidName;
cout << "输入进程大小:";
cin >> pcb[PCB::PCBNum - 1].m_PidSize;
i = PCB::PCBNum - 1;
for (j = 0; j < Partition::PartitionNum; j++)
{
if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)
{
partition[j].m_PartitionSize -= pcb[i].m_PidSize;
partition[j].m_BlockId += partition[j].m_PartitionSize;
if (partition[j].m_PartitionSize <= MIN)
{
partition[j].m_PartitionSize = 0;
}
flag = true;
break;
}
}
if (flag)
{
flag = false;
cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;
}
else
{
cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
}
Display1();
cout << "继续分配按Y" << endl;
cin >> choose;
} while (choose == "Y");
}
最佳适应算法（Bext Fit）
空闲分区链中分区大小递增排列，每次从链首开始查找，这样就能找到最合适的来分配内存
缺点：每次都会留下很多越来越小的外部碎片
void BestFit()//最佳适应算法
{
int pos = 0;
bool flag = false;
int i, j;
multimap<int, Partition*> m;
multimap<int, Partition*>::iterator ip;
string choose;
ReadData();
//Display_PCB();
/*cout << "输入MIN:";
cin >> MIN;*/
do
{
Display_Partition();
pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
cout << "输入进程名称：";
cin >> pcb[PCB::PCBNum - 1].m_PidName;
cout << "输入进程大小:";
cin >> pcb[PCB::PCBNum - 1].m_PidSize;
i = PCB::PCBNum - 1;
m.clear();
for (j = 0; j < Partition::PartitionNum; j++)//按从小带大排序
{
m.insert(make_pair(partition[j].m_PartitionSize, partition + j));
}
for (ip = m.begin(); ip != m.end();)
{
if (pcb[i].m_PidSize <= ip->first)
{
ip->second->m_PartitionSize -= pcb[i].m_PidSize;
ip->second->m_BlockId += ip->second->m_PartitionSize;
/*if (ip->second->m_PartitionSize <= MIN)
{
ip->second->m_PartitionSize = 0;
}*/
flag = true;
break;
}
else
{
ip++;
}
}
if (flag)
{
flag = false;
cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;
}
else
{
cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
}
Display();
cout << "继续分配按Y" << endl;
cin >> choose;
} while (choose == "Y");
}
最坏适应算法
和最佳想法优先使用最大的空闲区，每次排序时按大小递减，所以链首肯定符合
缺点：大空闲区消耗更快，导致将来的大进程可能难以使用
void WorstFit()//最坏适应算法
{
int pos = 0;
bool flag = false;
int i, j;
multimap<int, Partition*, greater<int>> m;
multimap<int, Partition*>::iterator ip = m.begin();
string choose;
ReadData();
//Display_PCB();
/*cout << "输入MIN:";
cin >> MIN;*/
do
{
Display_Partition();
pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
cout << "输入进程名称：";
cin >> pcb[PCB::PCBNum - 1].m_PidName;
cout << "输入进程大小:";
cin >> pcb[PCB::PCBNum - 1].m_PidSize;
i = PCB::PCBNum - 1;
m.clear();
for (j = 0; j < Partition::PartitionNum; j++)//按从大到小排序
{
m.insert(make_pair(partition[j].m_PartitionSize, partition + j));
}
for (ip = m.begin(); ip != m.end();)
{
if (pcb[i].m_PidSize <= ip->first)
{
ip->second->m_PartitionSize -= pcb[i].m_PidSize;
ip->second->m_BlockId += ip->second->m_PartitionSize;
/*if (ip->second->m_PartitionSize <= MIN)
{
ip->second->m_PartitionSize = 0;
}*/
flag = true;
break;
}
else
{
ip++;
}
}
if (flag)
{
flag = false;
cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;
}
else
{
cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
}
Display();
cout << "继续分配按Y" << endl;
cin >> choose;
} while (choose == "Y");
}
邻近适应算法
从上次查找结束的位置开始检查，可以减小查找的开销，而且可以防止小空闲分区聚合在链头。另外，空闲分区只需要按地址递增的顺序排列了（可以考虑用循环链表）
这个方法会将前言所有优点甚至缺点都聚合。。。属于是摆烂算法
void NextFit()//循环首次适应算法
{
int pos = 0;
bool flag = false;
int i, j;
string choose;
ReadData();
//Display_PCB();
/*cout << "输入MIN:";
cin >> MIN;*/
do
{
Display_Partition();
pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum+1));
cout << "输入进程名称：";
cin >> pcb[PCB::PCBNum - 1].m_PidName;
cout << "输入进程大小:";
cin >> pcb[PCB::PCBNum - 1].m_PidSize;
i = PCB::PCBNum - 1;
for (j = pos;; j++)
{
if (pos >= PCB::PCBNum)
{
pos = 0;
}
if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)
{
partition[j].m_PartitionSize -= pcb[i].m_PidSize;
partition[j].m_BlockId += partition[j].m_PartitionSize;
if (partition[j].m_PartitionSize <= MIN)
{
partition[j].m_PartitionSize = 0;
}
flag = true;
pos = j + 1;
if (pos == PCB::PCBNum)
{
pos = 0;
}
break;
}
}
if (flag)
{
flag = false;
cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;
}
else
{
cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
}
Display1();
cout << "继续分配按Y" << endl;
cin >> choose;
} while (choose == "Y");
}
分页存储管理
内存空间被分为一个个大小相等的分区，每个分区就是一个“页框“，编号为”页框号“，从0开始。
页框=页帧=内存块=物理块=物理页面
页框号=页帧号=内存块号=物理块号=物理页号
进程的逻辑地址空间也被分为与页框大小相等的”页“或”页面“,“页号”从0开始.
这样就有了一一对应关系
各个页面不必连续存放，也不必放到相邻页框中
页表
存放在PCB中,本质是数组
由页号和块号组成，代表了每个页与每个块的一一对应关系
对于页号，不占用储存空间，因为页号按照数字顺序排列，在数据结构中相当于隐藏数据了
对于块号，哪怕在题目中，通过内存块的数量推算出页表项中块号所占字节也是一个很重要的考点
块号不是地址，x号块起始地址为“x*内存块大小”
例题：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少为多少个字节？
答案
内存块大小=页面大小=4KB=2的12次方B 4GB会被分为2的20次方个内存块 用二进制表示地址，那么要用20bit来表示内存块号 按字节编址，则要至少用3B来表示块号 每个页表占3B，则储存整个页表至少需要3*（n+1）B地址转换
进程各个页面是离散存放的，但页面内部是连续存放的
先说结论：
逻辑地址A对应的物理地址=P号页面在内存中的起始地址+业内偏移量W
例题：页面大小50B。某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号、页内偏移量是多少？
答案
首先易得有四个页 页号=110/50=2……10 则页号为2 偏移量为10由于计算机地址是用二进制表示的，也就是说其实一般情况下题目的计算在计算机中很少发生，而若把页面大小设置为2的整数幂，则可以快速将逻辑地址拆分为页号和页内偏移量
例如页面大小为4KB，即2的12次方幂B，末尾12位则为页内偏移量
0号页的逻辑地址范围用二进制表示为：
00000000000000000000000000000000~00000000000000000000111111111111
1号页表示范围为：
00000000000000000001000000000000~00000000000000000001111111111111
红色即为页号，黑色即为页内偏移量
此外，最终的物理地址也可以直接通过将物理块号拼接上页内偏移量就能得到物理地址
如：页表中，1号页面存放的内存块号为9（1001）
则起始地址为：00000000000000001001000000000000=9*4096=x乘以内存块大小
总结：对于二进制逻辑地址结构
有K位表示“页内偏移量”，说明一个页面大小是2的k次方个内存单元
有M位表示“页号”，说明一个进程最多允许有2的m次方个页面
基本地址变换机构
该机构的具体作用就是在计计算机层面上借助页表将逻辑地址转换为物理地址
主要核心工具：页表寄存器，存放页表在内存中的起始地址F和页表长度M
进程未执行时这些东西都是放在PCB中的
PCB:进程控制块
进程被调度时，内核会把他们放到页表寄存器中，计算过程如下：
- 根据逻辑地址计算出页号、页内偏移量
- 根据页表长度判断页号是否越界
- 查询页表，找到页号对应的页表项，确定页面存放的内存块号
- 用内存块号和页内偏移量得到物理地址
- 访问目标内存单元
越界中断：包括对数组的大小进行越界。在这里，判断条件为“P>=M”，则越界，P为页表中的逻辑编号，由于P初始值为0，所以当两者相等时也算越界
总结公式：页表项地址=页表起始地址F+页号P*页表项长度
即：E=b*L+W
一些名词区分：
页表长度：页表中总共有几个页表项
页表项长度：页表项占的存储空间
页面大小：一个页面占多大的存储空间
页表是TMD表，页面是进行具体工作的页面
例题：页面大小1K，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E
答案
一个页面大小1K=2的10次方字节 先看是否越界：2500/2的10次方=2余452（偏移量） 不满足“P>=M”，不越界 再由公式E=b*L+W=8*2的10次方+452=8644为物理地址页式管理中地址是一维的
其实在真正的计算机中，每个页面大小和逻辑地址结构其实是物理已知量，不可能有变动的，所以对于系统来说，只要给出逻辑地址，就能自动算出物理地址
快表（TLB）
又称“联想寄存器”，实质是高速缓存而不是内存，用来存放最近访问的页表项的副本
相应的，内存中页表叫“慢表”
TLB速度很快，但不适合存页表，因为价格太贵，相当于用名牌书包取书本很快，但用一个书包存一整个图书馆的书是很不理智的
快表的大致内容和慢表是一致的，都有页号和内存块号，而快表的具体作用中“存放最近访问的页表项的副本”以为着存储最近访问的页号和对应内存块号，所以在多次查询相同页号的内容时，只要先查询快表是否命中，若命中则直接使用相应内存块号与内存偏移量相计算，就能快速得出结果。
所以说，若快表命中，则只需进行一次访存
若未命中，则需两次访存，当然，查询完慢表后须将内容复制到快表中
（这里一般会出现一个有关访问逻辑地址平均耗时的问题，注意有时候会出现“系统支持同时查找的情况”）
为什么快表存放很少的内容会使得速度大幅度提升，这里还是和著名的局部性原理 有关
TLB与Cache：TLB只存有页表项的副本，Cache中可能有其他数据的副本
两级页表
还是局部性原理
单级页表的问题：
1、页表必须连续存放，当页表很大时，需要占用多个连续页框
2、页表没必要常驻内存，进程在一段时间内可能只需要访问某几个特点页面
解决方法1：将页表进行分组，离散地分入一个个内存块中，为这些分组再建立页表”页目录表"
解决方法2：需要访问页面时再调入内存（虚拟内存技术）
一些小细节：
- 多级页表中，各级页表的大小不能超过一个页面,超过的话建立多一级页表
- 两级页表的访存次数分析（默认没有快表机制）N+1
分段存储管理方式
和分页比，离散分配时地址空间的基本单位不同
分段
按照程序自身逻辑来分为若干个段，每段都有段名，从0开始编址
分配规则：每个段在内存中占据连续空间，但各段之间可以不相邻
由于是按逻辑功能划分，所以用户编程更方便，程序可读性更高
段表
哎，这不是和分页差不了太多吗，头晕了摸了不想看了，有神能评论区指点两下就更好了
*
*
*
*
*
*
*
*
*
*
*
*
*
总结了两天10个小时给累昏了，打游戏都没这么累
———————————————— 字与字节原文链接：https://blog.csdn.net/qq_43627631/article/details/106456371
算法代码原文链接：https://blog.csdn.net/weixin_43886592/article/details/107581653