|
Linux/Unix操作系统如何读写文件数据？
Linux/Unix系统下读写文件一般有两种方式：传统输入输出（Input and Output,IO）和内存映射(Memory Map,MMAP)。
一、传统IO读写文件
传统IO的底层实现是通过调用read()和write()方法来实现的，实现的过程可以概括为图1所示的5个步骤：
图1. 传统IO读写文件流程框图
传统IO有何弊端？
从传统IO读取文件的过程中可以看出，用户进程读取磁盘中的数据页需要经历两次拷贝：磁盘->页缓存->用户缓存区，有没有一种方式能够在用户空间直接操作页缓存中的数据，避免页缓存->用户缓存区的拷贝呢？图1中值得注意的是，当存在多个进程同时读取同一个磁盘数据页时，传统IO会在每个进程的用户缓存区中都拷贝一份数据页副本，这将造成数据页的冗余和物理内存的浪费。二、内存映射mmap读写文件
通过内存映射的方式来读写文件可以看成是mmap和内存管理单元(Memory Management Unit, MMU)打的一套组合拳。首先由mmap完成磁盘文件到虚拟内存地址的映射，再通过MMU进行地址转换，将虚拟内存地址转化为物理地址对数据进行操作，同时，每个进程都会在用户空间中维护一张页表，判断一个虚拟页是否已经在物理内存中存在。这种读写文件的方式无需经历”页缓存->用户缓存区“的拷贝，且由于虚拟内存的存在，每个进程无需拷贝相同的数据页副本，有效改善了传统IO读写的两个弊端，使得用户进程访问文件就像在访问内存一样，如图2所示。
图2. 内存映射读写文件流程图
图中涉及到一些未接触过的概念，可能会带来理解上的困难，下面对这些概念做了一下总结：
数据访问流程
mmap()的调用回返回一个指针ptr，指向虚拟内存地址，但是需要注意的是，虚拟内存中并不会真的拷贝文件数据，所以接下来必须由MMU将虚拟内存地址转换为物理地址，在物理地址上进行数据拷贝，展开相关操作。通过构建的内存映射就可以像操作内存一样对磁盘文件数据进行处理，进程无需调用read()和write()方法。
缺页现象&缓存页面置换
仔细的读者通过观察图2能够发现：按照上述数据读取流程，当进程通过mmap()拿到的ptr指针指向虚拟页VP4/VP5的时候，由MMU完成地址转换，发现物理内存不够，并且找不到与ptr相对应的物理地址时，应该怎么办呢？这种现象称为缺页。为了把VP4从磁盘中拷贝到物理内存，需要从物理内存中调度一个牺牲页，将其从物理内存拷贝到磁盘中，以保持物理内存原有大小，这个过程称之为缓存页面置换。如何进行牺牲页的选取，使得页面调度次数尽可能的少是衡量一个页面置换算法性能的重要指标。理想情况下，每次调换出的页面应是所有内存页面中最迟将被使用的，这可以最大限度的减少页面调度。基于这个思想，衍生出了很多页面置换算法向该理想情况靠拢，典型的页面置换算法有：OPT、FIFO、LRU等。
LRU页面置换算法
LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当物理内存空间已存满数据时，应当把最久没有被访问到的数据淘汰，其算法工作流程如图3所示。
图3. LRU工作流程图
为了能够从LRU的工作流程抽象出其算法设计unix系统文件，将自己带入图3的流程来总结一下LRU到底做了什么：
*写入页面9、0、8、1时，都使用的是相同的逻辑：
1.先判断栈中是否已经存在需要写入的数据页，发现并不存在。
2.判断栈是否已满，发现未满，将数据页写入栈底。
*写入页面7时：
1.先判断栈中是否已经存在需要写入的数据页，发现并不存在。
2.判断栈是否已满，发现已满。
3.调出栈底数据页0，在栈顶添加数据页7。
*引用页面0时：
将页面0从原位置调出，并重新放置到栈顶。
不难发现，在模拟LRU的工作流程时，可以从两个方面进行代码抽象：数据写入和数据引用，抽象出的LRU逻辑伪代码如下：
写入数据():
if 数据页未存在于栈中:
if 栈未满:
添加数据页到栈顶;
else:
调出栈底数据页，添加数据页到栈底；
else://数据页已存在于栈
从栈中调出已存在数据页，更新数据并重新写入栈顶;
引用数据():
从栈中调出引用数据页，重新写入栈顶;
LRU算法实现（C++、Java代码）
根据上节中抽象出的LRU伪代码，通过哈希表+双向链表来进行代码实现。哈希表用来存储。双向链表用来模拟图3的栈结构，记录节点顺序，head最近访问的节点，tail为最久访问的节点，如图4所示：
图4. LRU数据结构
至此伪代码可具像化为：
put(key, value){
if(key in map){//key已经存在于双向链表中
removeNode(key_ptr);//调出节点
addNode(key_ptr);//添加节点至头部
}else{
Node* newNode= new Node;
if(链表长度>链表容量){//超出缓存范围需要删除尾部结点
//调出尾部结点
removeNode(Tail);//从双向链表中删除
map.erase(Tail_key);//从map中删除
delete Tail_ptr;//从缓存中删除开辟过的空间
}
//添加新节点
addNode(newNode);//在链表中添加新节点
map[key] = newNode;//在哈希表中添加新节点
}
};
get(key){
if(key in map){//key已经存在
removeNode(key_ptr);
addNode(key_ptr);
}else{
"返回未找到数据";
}
};
到此，LRU的代码框架已经初步成型，接下来将removeNode()、addNode等函数逐一实现后，得到完成的LRU代码：
//双向链表
struct DLinkedNode{
int key;
int value;
DLinkedNode* pre;
DLinkedNode* next;
DLinkedNode(int k, int v){
this->key = k;
this->value = v;
this->pre = NULL;
this->next = NULL;
}
};
class cache{
private:
int count;
int capacity;
DLinkedNode* Phead;//头指针
DLinkedNode* Ptail;//尾指针
map<int,DLinkedNode*> mp;
public:
//构造函数
cache(int capacity){
this->capacity = capacity;//链表容量
this->count = 0;//当前链表长度
this->Phead = NULL;
this->Ptail = NULL;
};
//稀构函数
~cache(){
map<int, DLinkedNode*>::iterator it = mp.begin();
for(;it!=mp.end();){
delete it->second;
it->second = NULL;
mp.erase(it++);
this->count--;
}
delete Phead;
Phead = NULL;
delete Ptail;
Ptail = NULL;
};
//调出节点
void removeNode(DLinkedNode* p){
if(p->pre==NULL){//头节点
Phead = p->next;
Phead->pre = NULL;
}else if(p->next==NULL){//尾节点
Ptail = p->pre;
Ptail->next = NULL;
}else{//中间结点
p->next->pre = p->pre;
p->pre->next = p->next;
}
};
//添加节点
void addNode(DLinkedNode* p){
p->next = Phead;
p->pre = NULL;
if(Phead==NULL){
Phead = p;
}else{
Phead->pre = p;
Phead = p;
}
if(Ptail==NULL){
Ptail = Phead;
}
};
int getCount(){
return this->count;
};
//调出节点并重新添加至头部
void moveToHead(DLinkedNode* p){
removeNode(p);
addNode(p);
};
int get(int k){
map<int, DLinkedNode*>:: iterator it = mp.find(k);
if(it!=mp.end()){//key已经存在
DLinkedNode* node = it->second;
removeNode(node);
addNode(node);
return node->value;
}else{//没找到
return -1;
}
};
void put(int k, int v){
map<int, DLinkedNode*>:: iterator it = mp.find(k);
if(it!=mp.end()){//key存在
DLinkedNode* node = it->second;
removeNode(node);
node->value = v;
addNode(node);
}else{//key不存在
this->count++;
DLinkedNode* newNode = new DLinkedNode(k,v);//new一个内存，记得要delete掉！！！
if(this->count>this->capacity){//超出缓存范围需要删除尾部结点
//在map中找到取出尾部key值，并删除
map<int,DLinkedNode*>::iterator it = mp.find(Ptail->key);//先取出尾部结点的迭代器
removeNode(this->Ptail);
mp.erase(it);//从map中删除
delete it->second;//从缓存中删除开辟过的空间
this->count--;
}
addNode(newNode);
mp[k] = newNode;
}
};
};
（编辑：92站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
