操作系统大题强化

PV操作大题总结

PV操作常见的考法

• 生产者消费者问题
  • 一类进程负责生产资源，另一类进程负责消费资源
• 理发师问题：
  • 一类进程负责生产服务，另一类资源负责消费服务
• 读者写者问题：
  • 同类不互斥，异类互斥
• 哲学家进餐问题：
  • 只有一类进程，每个进程需要同时拥有多种资源才能运行
  • 核心问题是解决思索，如何让每个进程持有多种资源去运行，同时还不造成这种循环等待的死锁
• 单纯的同步问题：
  • 前驱后继图

生产者—消费者问题

• 进程→动作→PV同步→PV互斥缓冲区→信号量→死锁
• 1、分析有几类进程
  • 每类进程对应一个函数
  • 具体有几类进程得看这些进程需要做的动作完全一致，就属于同一进程，如果要做的动作不完全一致，那就属于不同类的进程
• 2、在每个函数内部分析，用中文描述各类进程的动作是什么
  • 动作有两种：
    • 只做一次？
      • 不加while
    • 不断重复？
      • 加while（1）
• 3、依次分析每一类动作之前，是否需要P什么？
  • 先确定P操作，在哪些地方需要P一个资源
    • 这些动作需不需要等待某一事情的发生才能进行，那么在这种动作之前，需要P一种资源（有没有可能因为什么资源不到位而导致这个动作被阻塞）
      • 不需要等待某件事情的发生就能够进行，那么在该动作之前不需要P操作
  • 再想办法去思考这个V操作，只要有P必有V，每写一个P，就要安排V，这个V操作应该安排在什么位置
    • 也就是前面P操作申请的某种资源在哪里会得到释放，在对应的动作后面加入V操作
  • 注意隐含的互斥（eg：缓冲区访问需要加P（mutex））
    • 缓冲区需要互斥访问，p1写的时候p2不能读
    • 访问前p（mutex）访问后v（mutex），保证对缓冲区的互斥访问
    • 如果需要把产品放到某个地方或者说某个缓冲区（所有用于存放零件存放产品的这些东西，都把他视为所谓的缓冲区），那么就需要加P（mutex）和V（mutex）
      • 互斥信号量的初始值=1
• 4、所有PV写完后，再去定义信号量，定义完再思考每个信号量的初值是多少？
• 5、检查多个P连续出现的地方，是否可能产生死锁？
  • 可以尝试调整P顺序，若某信号量P、V操作总时连续出现，中间没有夹其他P，则不可能因此产生死锁
  • 同步问题和互斥问题同时出现的时候，要确保互斥锁P的操作在同步的P操作的后面，同步操作把互斥操作包含在内
  • 死锁产生的条件：请求和保持
    • 手里面持有资源的同时在等待新的资源
    • 一般来说缓冲区的互斥访问PV里面没有夹杂其他PV操作，所以一般来说互斥访问缓冲区的PV操作不会产生死锁
• 6、读题检查，是否满足题目要求

习题带练

1

2

• 第一种思路

• 第二种思路

环形缓冲区：按照环形有序的序列去放产品

实现方式：利用循环队列，队头队尾取数存数
in：队尾指针，进队前移
out：队头指针，出队前移

在环形缓冲区的条件下，生产者进程所访问的位置一定是in指针所指的位置，消费者进程所访问的位置一定是out指针所指的位置，因此生产者进程和消费者进程就不可能同时访问同一个缓冲区，这就打破了经典的生产者消费者问题里面的限制，即生产者和消费者对于缓冲区的互斥访问，生产者进程和消费者进程可以同时访问缓冲区

互斥关系变成了生产者之间，消费者之间，各自的互斥访问，而生产者和消费者之间不再互斥。程序的并发度提高。

因为in和out指针指向的是缓冲区的位置，我们改变的in和out指针其实就相当于改变缓冲区，因此对in和out指针改变的操作应该用互斥信号量进行控制

并不是代表缓冲区有10个产品才可以开始取，就算缓冲区只有一个产品，此时消费者进程也可以开始取产品，只不过取完一个产品之后，需要等生产者进程继续往里面放产品，然后消费者进程才可以接着取

3

哲学家问题

• 1、限制申请资源的顺序（解法一不通用，不建议使用）
  • 如：规定单号哲学家先取左筷子，双号先取右筷子
    • 破坏了请求和保持这个条件
• 2、限制并发进程数量（解法二通用，但并发度不高，不建议使用）
  • 如：规定同一时间只能有一个哲学家就餐（禁止并行）
• 3、让进程一口气取得所有资源，再开始运行（通用，且并发度高，建议使用）
  • 如：哲学家只有能够取得两个筷子时才会就餐
• 第二种和第三种解决方法的区别：
  • 第二种可能出现尚未就餐的哲学家部分占有资源而等待用餐哲学家释放所需资源的情况，而第三种则不可能出现部分占有，要么全拿要么一个都没有
• 一类进程需要同时持有多种资源才能正常往下运行
• 哲学家问题大概率出现防止死锁的题眼

哲学家问题模板

• 用int型变量定义各类资源，在每一个进程开始做事之前，一口气把所有的资源都拿到手，然后再开始做他该做的事情，做完这些事情之后，再一口气归还所有的资源。
  • 这样可以确保死锁不发生，也可以确保进程和进程之间的并发度

• 表示资源的常用方法：

  • 模板1：用int变量表示资源（并发度高）

    • ①定义大锁

      • semephore lock=1
        • 互斥信号量
        • 所有哲学家进程在获取资源之前都需要先获取这个大锁
        • 保证获取这些资源是互斥进行的

    • ②定义资源数int

      • 如：有a、b、c三类资源，分别有9个、8个、5个，定义3个int变量
        • int a=9;
          • 表示a的剩余数量
        • int b=8;
          • 表示b的剩余数量
        • int c=5;
          • 表示c的剩余数量

    • ③写代码模板：

      • 一口气拿所有资源

      Process(){
      while(1){//不断轮询去检查资源够不够
      	p(lock);//上锁，同一时刻只有一个哲学家进程去检查这些资源够不够，也就是确保每个哲学家对于各种资源的访问是互斥的，不会同时去访问这些变量
          if(所有资源都够){//ifa>=3 &&b>=2(假如需要3个a，2个b)
          	所有资源int值减少;//题目会告诉你每类资源要几个，需要多少减多少
              取xxx资源;//一口气拿走所有资源
              V(lock);//拿完资源，解锁
              break;//跳出while循环，到第4个步骤
          }
          v(lock);//资源不够，解锁，再循环尝试一次，直到if的条件成立，才进入if内最后到break跳出循环
      
      }//while结束
      }
      C++

    • ④做进程该做的事（如：哲学家干饭）

      • 用中文说明即可
      • 到这一步进程所需要的所有资源都已经够了

    • ⑤一口气归还所有资源

      P(Lock);
      归还所有资源，所有资源int值增加;
      V(Lock);
      C++

    • 并发度问题：

      • 这种情况下进程的并发度一定是很高的，比如有p1p2p3p4进程，都在轮询检查资源够不够
        • p1检查了一段时间后时间片用完，处理机调度（CPU调度）切换成另一个进程上CPU运行，也会while循环检查
        • 此时如果另一个进程p5释放了资源，那p2就能一口气获得所需要的资源
        • 因此这种while循环不会让一个进程无限制地占用处理机，因为操作系统有CPU调度这个功能
        • 所以一个进程运行了若干个时间片之后，会下处理及运行，虽然这个进程没有被阻塞，但是会下处理机，然后调度另一个进程继续执行，所有进程等待资源的时候都在轮询检查，直到能够一口气获取所有资源，这样进程的并发度就能够得到保证

  • 模板2：每一类资源对应一种信号量

    • 为了确保可以一口气拿走所有资源，可以用一个mutex，先p（mutex）然后p所有资源，再v（mutex）
    • 并发度不高，剩余资源足够的可能因为mutex取不到导致并发度不高

习题带练

1

单纯的同步问题

• 前V后P，每一对前驱后继关系中间定义一个信号量（暴力）

习题带练

1

2

理发师问题

理发师问题和生产者消费者问题的区别

• 生产者消费者问题

  • A进程生产数据，数据会放到缓冲区里
  • B进程会从缓冲区里取走数据
  • 二者一个生产资源一个消费资源

• 理发师问题

  • 没有明显的生产资源消费资源的关系
  • 服务和被服务的关系

• 思路

  • 顾客（被服务）
    • 如何用代码表示”取号“动作？
    • 是否有”等位区座位上限“？

  //顾客
  int waiting=0;//当前有多少个顾客正在等待被服务（已取号但未被服务的顾客）
  semaphore mutex=1;//用互斥变量保证对waiting变量的互斥访问
  semaphore service=0;//服务信号量，特殊的生产者消费者关系
  customer_i(){//因为被服务一次即完成，所以不用循环
      p(mutex);//互斥访问waiting，上锁
      取号;
      waiting ++;
      v(mutex);//解锁
      等待被叫号;
      p(service);//因为需要申请一个服务才能够被服务，所以需要p一种资源
      被服务;
      
  }
  C++

  • 服务人员（提供服务）
    • 如何用代码表示”叫号“？
    • 没有顾客时，应该”忙等“or”睡觉“？
      • 睡觉：p操作阻塞
      • 忙等：while循环

  //服务人员
  int waiting=0;//当前有多少个顾客正在等待被服务
  semaphore mutex=1;//用互斥变量保证对waiting变量的互斥访问
  semaphore service=0;//服务信号量，特殊的生产者消费者关系
  server_j(){
      while(1){//不停服务，所以要循环
         p(mutex);//互斥访问waiting,上锁
      if(waiting>0){//有顾客在等待
          
          叫号;
          waiting --;
          v(mutex);//解锁
          v(service);//提供一个服务
          提供服务;
      }
      else{
          v(mutex);//在无顾客的时候也要解锁
          
      	}//else end
  	}//while end
  }
  C++

  • 总结

    顾客无等位区需求，服务人员忙等的情况

  int waiting=0;//当前有多少个顾客正在等待被服务（已取号但未被服务的顾客）
  semaphore mutex=1;//用互斥变量保证对waiting变量的互斥访问
  semaphore service=0;//服务信号量，特殊的生产者消费者关系
  //顾客
  customer_i(){//因为被服务一次即完成，所以不用循环
      p(mutex);//互斥访问waiting，上锁
      取号;
      waiting ++;
      v(mutex);//解锁
      等待被叫号;
      p(service);//因为需要申请一个服务才能够被服务，所以需要p一种资源
      被服务;
      
  }
  //服务人员
  server_j(){
      while(1){//不停服务，所以要循环
         p(mutex);//互斥访问waiting,上锁
      if(waiting>0){//有顾客在等待
          
          叫号;
          waiting --;
          v(mutex);//解锁
          v(service);//提供一个服务
          提供服务;
      }
      else{
          v(mutex);//在无顾客的时候也要解锁
          
      	}//else end
  	}//while end
  }
  C++

  顾客有等位区需求，服务人员忙等的情况

  int waiting=0;//当前有多少个顾客正在等待被服务（已取号但未被服务的顾客）
  semaphore mutex=1;//用互斥变量保证对waiting变量的互斥访问
  semaphore service=0;//服务信号量，特殊的生产者消费者关系
  //顾客
  customer_i(){//因为被服务一次即完成，所以不用循环
      p(mutex);//互斥访问waiting，上锁
      if(waiting>=max){
          v(mutex);//释放互斥信号量
          return;//离开
      }
      取号;
      waiting ++;
      v(mutex);//解锁
      等待被叫号;
      p(service);//因为需要申请一个服务才能够被服务，所以需要p一种资源
      被服务;
      
  }
  //服务人员
  server_j(){
      while(1){//不停服务，所以要循环
         p(mutex);//互斥访问waiting,上锁
      if(waiting>0){//有顾客在等待
          
          叫号;
          waiting --;
          v(mutex);//解锁
          v(service);//提供一个服务
          提供服务;
      }
      else{
          v(mutex);//在无顾客的时候也要解锁
          
      	}//else end
  	}//while end
  }
  C++

  顾客有等位区需求，服务人员闲时阻塞的情况

  int waiting=0;//当前有多少个顾客正在等待被服务（已取号但未被服务的顾客）
  semaphore customer= 0;
  semaphore mutex=1;//用互斥变量保证对waiting变量的互斥访问
  semaphore service=0;//服务信号量，特殊的生产者消费者关系
  //顾客
  customer_i(){//因为被服务一次即完成，所以不用循环
      p(mutex);//互斥访问waiting，上锁
      if(waiting>=max){
          v(mutex);//释放互斥信号量
          return;//离开
      }
      取号;
      waiting ++;
      v(mutex);//解锁
      v(customer);
      等待被叫号;
      p(service);//因为需要申请一个服务才能够被服务，所以需要p一种资源
      被服务;
      
  }
  //服务人员
  server_j(){
      while(1){//不停服务，所以要循环
         p(mutex);//互斥访问waiting,上锁
      if(waiting>0){//有顾客在等待
          
          叫号;
          waiting --;
          v(mutex);//解锁
          v(service);//提供一个服务
          提供服务;
      }
      else{
          v(mutex);//在无顾客的时候也要解锁
          p(customer);//有顾客才被唤醒，此处需要p操作p一种资源才能进行
      	}//else end
  	}//while end
  }
  C++

  

习题带练

1

• 睡觉：阻塞等待

2

• 循环忙等

3

4

5

6

读者写者问题

不同进程伪代码访问全局变量

• 思路

  • ①分析每行代码分别read和write哪些全局变量

  • ②分析互斥关系

    • 两两互斥的情况下，相当于对某一个缓冲区都需要互斥访问（类似于独立）

    

    • 互斥关系分析除了看访问的情况还要看本质和实际情况

经典的读者写者问题

读者优先

• 如何看图说话？

  • 写者先进入rw关卡，p（rw），得到锁之后直接写文件，writing

    • 写完之后直接V操作，不用判断，v（rw）

  • 读者进来，看到rw关卡前面有个分支，说明要进行分支判断

    • 此时判断是不是第一个人，如果是第一个人，p（rw），读文件，如果不是，直接进入，读文件

    p(mutex);
    	count++;
    		if(count==1)
    			p(rw);
    v(mutex)
    C++

    • 出来之后，面临分支，如果里面还有读者，不用进行v操作，如果没有读者，进行一个v操作

    p(mutex);
    	count--;
    		if(count==0);
    			v(rw);
    v(mutex);
    C++

• 总体代码

semaphore rw=1;//用于保证读者和写者互斥地访问文件
semaphore mutex=1;//用于保护更新count变量时的互斥
int count=0;//用于记录当前的读者数量
//写者进程
writer(){
    while(1){
        p(rw);//互斥访问共享文件
        	读文件;
        v(rw);//释放共享文件
    }
}
//读者进程
reader(){
    while(1){
        p(mutex);//互斥访问count变量
        	if(count==0)//当第一个读进程读共享文件时
                	p(rw);//阻止写进程写
        count++;//读者计数器+1
        v(mutex);//释放互斥变量
        读文件；
        p(mutex);//互斥访问count变量
        	count--;//读者计数器-1
        	if(count==0)//当最后一个读进程读完共享文件
                v(rw);//允许写进程写
        v(mutex);//释放互斥变量count
    }
}
C++

读写公平

• 如何看图说话？
  • 写者：
    • 进来之后先p(w)，然后来到rw关卡，然后p(rw)，然后v(w)，读文件，读完V(rw)
  • 读者：
    • 进来之后先p(w)，然后捧到分支，判断是否有其他读者进程，有的话读文件，没有的话要p(rw)，然后V(w)
    • 读完以后遇到分支，判断里面是否还有读者，如果有读者直接出去，没有读者V(rw)
• 总体代码

semaphore mutex=1;//用于保护更新count变量时的互斥
semaphore w=1;//用于实现读写公平
semaphore rw=1;//用于保证读者和写者互斥地访问文件
int count =0;//用于记录当前读者的数量

//写者进程
writer(){
    while(1){
        p(w);//在无写进程请求时进入
        	p(rw);//互斥访问共享文件
        		v(w);//恢复对共享文件的访问
        写文件；
            v(rw);//释放共享文件
    }
}

//读者进程
reader(){
    while(1){
        p(w);//在无写进程请求时进入
        	p(mutex);//互斥访问count变量
        		if(count==0)//当第一个读进程读共享文件时
                    p(rw);//阻止写进程写
        		count++;//读者计数器+1
        	v(mutex);//释放互斥变量count
        	v(w);//恢复对共享文件的访问
        读文件;
        p(mutex);//互斥访问count变量
        	count--;//读者计数器-1
        	if(count==0);//当最后一个读进程读完共享文件
        		v(rw);//允许写进程写
        v(mutex);//释放互斥变量count              
    }
}
C++

写者优先

• 因为写者之间是互斥的，因此不能采用读者优先的方法在rw那里开小路，而是在最开始W处开小路，让写者不用排W，而是直接去rw处排队
• 写者优先的实现：
  • 读者和写者同时在w处排队，如果文件里面还有写者，那么写者不用排w，直接进去排rw，但是读者还是得排w，因为写者还锁着w，因此写者就比读者快一步进入rw排队逻辑
• 总体逻辑

semaphore read =1;//互斥信号量，用于给读者“上锁”
semaphore write =1;//互斥信号量，用于给写者“上锁”
semaphore rmutex =1;//互斥信号量，实现对readCount的互斥访问
semaphore wmutex =1;//互斥信号量，实现对writeCount的互斥访问
int readCount =0,wirteCount =0;//读者、写者的数量

//读者进程（在这个题例就是可以多人一起共用更衣室的队员们）
Reader(){
    while(true){
        P(read);//每个读者到达时先对read上锁
        P(rmutex);
        	readCount++;
        if(readCount==1) P(write);//第一个开始读的读者对写者上锁
        V(rmutex);
        V(read);//每个读者正式开始读之前对read解锁
        读者读...;
        P(rmutex);
        	readCount--;
        if(readCount==0) V(write);//最后一个读完的读者对写者解锁
        V(rmutex);
    }
}

//写者进程（在这个题目里，对应必须独享更衣室的教练们）
Writer(){
    while(true){
        P(wmutex);
        	writeCount++;
        if(writeCount==1)P(read);//第一个到达的写者对读者上锁，这一步是实现“写优先”的关键
        V(wmutex);
        P(write);//每个写者开始写之前都要P(write)，保证写者之间互斥，同时也能保证若当前有读者正在读，那么写者等待
        写者写..；
        V(write);
        P(wmutex);
        	writeCount--;
        if(writeCount==0)V(read);//最后一个写者写完之后，对读者解锁
        V(mutex);
    }
}
C++

例

semaphore read =1;//互斥信号量，用于给读者“上锁”
semaphore write =1;//互斥信号量，用于给写者“上锁”
semaphore rmutex =1;//互斥信号量，实现对readCount的互斥访问
semaphore wmutex =1;//互斥信号量，实现对writeCount的互斥访问
int readCount =0,wirteCount =0;//读者、写者的数量

//读者进程（在这个题例就是可以多人一起共用更衣室的队员们）
Reader(){
    while(true){
        P(read);//每个读者到达时先对read上锁
        P(rmutex);
        	readCount++;
        if(readCount==1) P(write);//第一个开始读的读者对写者上锁
        V(rmutex);
        V(read);//每个读者正式开始读之前对read解锁
        读者读...;
        P(rmutex);
        	readCount--;
        if(readCount==0) V(write);//最后一个读完的读者对写者解锁
        V(rmutex);
    }
}

//写者进程（在这个题目里，对应必须独享更衣室的教练们）
Writer(){
    while(true){
        P(wmutex);
        	writeCount++;
        if(writeCount==1)P(read);//第一个到达的写者对读者上锁，这一步是实现“写优先”的关键
        V(wmutex);
        P(write);//每个写者开始写之前都要P(write)，保证写者之间互斥，同时也能保证若当前有读者正在读，那么写者等待
        写者写..；
        V(write);
        P(wmutex);
        	writeCount--;
        if(writeCount==0)V(read);//最后一个写者写完之后，对读者解锁
        V(mutex);
    }
}
C++

PV操作带练

同步问题

• 同一个进程本身的动作不需要我们去同步

• 没有缓冲区，不存在互斥问题，非消费者生产者问题
  • 并没有说把这个东西生产完之后放在哪里，只是不停地生产它，因此没有互斥关系只有同步关系

• 刚开始生产的，因为第一次可以直接进行，因此信号量为1，一开始需要条件的，信号量设为0

互斥问题

• 只有全局变量才可能成为临界资源，局部变量只能在单一线程内访问，被单一线程看到
• 不是说几个临界资源，几个全局变量就设置几组互斥关系的
• 也不是说几个进程就设置几组互斥关系的

• 并不是信号量设置的越少并发度越高，也不是信号量越多并发度越高，只有正确地设置信号量才能保证并发度

互斥问题——读者写者

• 遇见分支了，我们就要引入辅助变量count来帮助我们解决问题

有读者和写者两个并发进程

有读者和写者两组并发进程

• 如果这样写，会导致实际上读者和读者之间也是互斥访问的

• 蓝色是P操作，红色是V操作，读者有两条路，因此出现了分支，必引出辅助变量，需要额外设置信号量

//写者
writer(){
    p(ww);//实现写者之间的互斥
        p(rw);
    		写文件
        v(rw);
    v(ww);
}
//读者
reader(){
    
    if(count==0){
        p(rw);
        
    }
    else{
        read;
    }
}
C++

• 读者优先

• 读写公平

• 因为W关卡的本质是设置一个公平排队逻辑，让每次只有一个读者或者一个写者进入排队队列，因此当这个读者或者写者排完队进入这个文件以后，就要对排队逻辑进行一个V操作

互斥问题——哲学家吃饭

同步互斥综合问题

• 环形缓冲区：有序缓冲区，能够通过合理的设置，可以在不使用信号量的情况下，天然地保证生产者和消费者不会访问到同一个缓冲区
• 普通缓冲区：无序缓冲区，因为无论是生产者还是消费者都需要互斥访问这个缓冲区

内存管理

• 一般考请求分页，请求分页可能结合一级页表也可能结合二级页表
• 如果考基本分页则一般考二级页表
• 核心是地址转换
• 页表：把虚拟地址（逻辑地址）映射为物理地址
  • 无论是指令还是数据都是存储在内存里面的，无论是数据还是指令，在进程内部都是用虚拟地址来表示

进程的内存示意图

• 用户程序不可以访问PCB
• 编译、汇编的时候生成机器指令
  • 编译：将高级语言源程序一次性翻译成目标程序
  • 解释：将源程序的一条语句翻译成对应的机器目标代码，并立即执行，然后翻译下一条源程序语句并执行，直至所有原程序语句全部被翻译并执行完，并不会生成目标程序
  • 汇编：把汇编语言翻译为机器语言程序
• 库函数本质上也是指令序列，会被这个系统当中的所有程序所共享，会被映射到共享库的存储映射区
  • 这些函数对应的指令序列在物理上只有一份，只是多个进程都会把这一份物理指令序列映射到自己的虚拟地址空间当中，相当于页面共享
• 操作系统内核区也是被所有进程所共享的
  • 操作系统内核区的数据物理上也只有一份，为所有的进程所共享
  • 实现方法：把这些进程更高地址的1GB映射到同样的一片物理页框中即可

存储系统图

• 左边是虚拟地址空间，中间是物理地址空间，右边是磁盘
• 由于7号页在磁盘不在内存，因此访问7号页面会缺页，需要把7号页调入主存

• 假设现在CPU要写的某一个变量的虚拟地址是0003 996H，现在要去查一级页表，一级页表存储在虚拟地址空间的操作系统内核区（属于内核数据结构）

• CPU是怎么去找到当前执行的进程页表存储在什么位置？

  • PCB进程控制块记载了当前进程的页表始址

• 操作系统怎么找到当前进程的PCB

  • 通过进程号PID，数据结构PCB，PID是数组下标，假设操作系统最多可以支持100个进程并发运行，可以定义一个struct pcb a[100]，每个进程的PID就可以作为这个数组的数组下标，因此，根据进程的PID，我去查找这个PCB数组的某一个元素，比如PID=3，那么我们去找a[3]

• 定义一个指针指向当前页表的页表始址，在内核区的某个虚拟地址

• 每一个进程在被调度上处理机的时候，操作系统会根据被调度的进程的PID，去找它的PCB，然后从PCB里面得知页表始址（虚拟地址），然后转化为物理地址，然后把该始址存储到CPU的寄存器里面（页表始址寄存器）

  • 如何把页表始址的虚拟地址转化为物理地址？
    • 所有的进程都是共享操作系统内核区的，所以所有的进程操作系统内核区的映射关系都是一样的。
    • 因为任意一个进程的页表都是存储在操作系统内核区的，而操作系统内核区是被所有进程共享的。
    • 因此，只要我知道了这个进程的页表起始地址，那么操作系统不管是任何一个进程，都可以根据每个进程的页表起始地址去转换成映射到我操作系统内核区的物理地址。

• 查页表的过程：

  • 根据页表始址寄存器所指明的地址去内存中，在某一个页框中找到页表
    • 页表是由页表项组成的，页表项有很多个，页表项在页表当中连续存储，本质是struct结构体，页表项存储有效位，页面在外存中的地址，脏位，页框号（VA→PA页框），页表本质是页表项的数组
    • eg：游戏存档：本质上就是把内存里面脏位=1的那些数据，当存储这些数据的页面被淘汰，被置换到外存，或者主动手动点存档的时候，脏了的页面需要协会到外存

• 二级页表的情况下，PCB会保存顶级页表的起始地址，放到顶级页表（页目录表）始址寄存器当中

• 注意虚拟页号划分，有几级页表虚拟页号就分成几段，然后最高地址是一级页表，依次升级

• 如果查到某一个页表项的有效位为0，说明没有调入主存，出发缺页异常（内中断，指令触发），接下来操作系统会进入到内核态，然后执行缺页异常的处理程序，然后会根据该页表项所写的数据在外存中的存储位置，从磁盘块中调进来。

  • 调进来之后，修改有效位，对应内存页框号更新

  • 异常处理程序执行结束之后会再次执行指令，就不会发生缺页，正常进行虚拟地址转化为物理地址

    • 缺页异常（内中断，指令触发），比如说我执行int a=3，可能涉及到一个mov [虚拟内存地址]，3的指令，然后在转换的过程中，发现有效位为0，也就是这条指令引发了缺页异常

    • 引发之后会转为处理异常的处理程序，操作系统陷入内核态，转入缺页异常的处理程序，然后执行一系列上面的事情

      • 由于虚拟地址空间通常比物理内存大，因此无法一次性将所有虚拟地址空间中的页面都加载到物理内存中。操作系统会根据需求动态地将需要的页面加载到内存，而其他不常用的页面会被暂时置换到磁盘。这个过程叫做缺页处理

        • 而页表里面的页表项存储的是虚拟地址空间里面的页表的信息， 所以页表里面不可能每一个页表项的有效位都为1（因为物理内存容纳不下所有的页都调入）

          • 由于物理内存有限，虚拟地址空间可能会比物理内存大，所以会有一些数据暂时存放在磁盘（外存）中，只有当数据被访问时，操作系统会通过缺页中断将需要的数据从磁盘调入内存。
          • 而且这还是一个进程的情况，多个进程的情况下每个进程实际上物理空间的冲突和缺页会更加频繁

        • 虚拟地址空间是为每个进程提供的独立的地址空间，它在物理内存中并不直接对应具体的内存位置，而是通过操作系统的内存管理单元（MMU）进行映射，也就是操作系统负责形成虚拟地址和物理地址的映射关系并且形成页表

          • 操作系统根据一定逻辑形成虚拟地址和物理地址的映射关系并且形成页表，至于这里面的映射逻辑已经超出了408考试的范围，我们不用在意，只知道有一个东西即操作系统形成这个映射关系，导致物理内存容纳不下虚拟内存的所有东西，但是虚拟内存的东西在页表中有记录，哪些要放入虚拟内存，虚拟内存有那些东西都是操作系统负责，在磁盘中又能找到就行了

          • 所以，你只需要知道：

            1. 操作系统会管理虚拟内存和物理内存的映射，并且通过页表来记录哪些虚拟地址对应物理地址。
            2. 如果物理内存不足，操作系统会将不常用的数据交换到磁盘，并且需要时从磁盘读取数据回到内存。

            不需要过多关注具体的映射逻辑细节，考试中大多会让你理解虚拟内存的概念和内存管理的基本原理即可。

• 快表没有命中但是慢表命中以后，会把命中的慢表中的一些信息复制到TLB当中进行更新
  • 也就是说访问一个页面第一次没有命中，但是第二次访问同一个页面的时候快表肯定能命中
    • 命中：有效位为1且有匹配的页号
  • 当查TLB没有命中，查慢表发现缺页异常的时候，缺页处理程序把一个页面从外存中调入内存的时候，除了修改内存中的慢表之外，还会修改快表，因此当缺页处理之后，再次执行指令的时候TLB命中（除非题目说不修改TLB）
• 缺页处理还可能涉及页面置换（页框不够），被换出的页面需要检查脏位，如果脏位为1，则操作系统会把对应页框的数据写回磁盘对应的区域（写磁盘）。然后空出来的原页框，就会被新调入的覆盖（读磁盘）
  • 因为原页面被置换出去，原页表的页表项有效位要改为0，后面可以不改
  • 换入的页的页表项有效位变成1，脏位变为0，页框号更新，对应置换算法的标记更新
  • 页面置换算法属于缺页异常处理程序的子功能
  • TLB那边也得相应发生改变

• 上图为两个进程共享某些页面

• 每个进程的虚拟地址空间都是不一样的，但是有一些数据（比如操作系统内核区和共享库的存储映射区）是共享的

  • 操作系统内核区的数据是独一份，只有操作系统内核代码可以去访问
    • 用户态下想访问会被阻止

• 如何实现共享？

  • 页表映射到同一个页框号，比如说进程A的页表中，页目录FFH存储的是操作系统内核的数据，进程B的页表中，页目录FFH存储的也是操作系统内核的数据，然后对应的二级页表中的页表项也相等，这样当他们访问相同虚拟地址的时候，访问的都是同一段数据
  • 当所有进程都共享独一份的操作系统内核区数据（只要让所有进程的某一块页表项都映射到物理地址空间的同一块地方就可以了）
  • 当然，因为二者的数据完全一致，所以完全可以让二者共享同一份二级页表（原来是两个页表但是映射到同一块区域，现在是另一个进程直接指向另一个进程的页表某块）
  • 但是共享库的内存映射区不能这么干，因为二者数据不完全一致，引用的库函数不完全相同，所以有两份页表

• p1和p2进程实现进程间通信的方式

  • 共享内存

    • 要进行系统调用，告诉操作系统哪个页面作为共享内存来交换数据，比如p1说4号页面，p2说六号页面，然后操作系统就会把p1的四号页所指向的页框和p2的六号页所指向的页框映射到同一个位置（比如都是FEEH物理地址）
      • 此时当p1进程往四号页面读写的时候实际上是在读写FEEH，当p2进程往六号页面读写的时候，实际上是在读写FEEH
      • p1写p2读，这样实际上就实现了进程之间的通信

  • 信箱通信

    

    

    • p1进程通过系统调用，先给操作系统写一段数据，然后操作系统再把这一段数据交给p2进程
      • P1进程对操作系统发出系统调用，表示要用信箱通信，跟p2进程完成进程间通信。并且指明要写的数据是什么位置
      • 操作系统收到系统调用之后，从用户态变为内核态
      • 之后操作系统根据系统调用号（异常号）找到中断向量表，找到该系统调用所对应的函数入口（指令的起始位置），PC指向该系统调用指令第一条指令的起始位置，然后就可以开始执行系统调用的这个处理程序
        • 因为此时CPU已经变成内核态了，所以PC要去访问这条指令或者说要去访问操作系统内核区的时候，是可以被允许的
      • 操作系统的系统调用处理程序会根据传递过来的参数去访问用户区，找到p1进程准备好的数据，然后先复制到操作系统内核区某一个位置，当p2进程通过系统调用，对操作系统发出要从信箱中取多少数据的指令，接下来操作系统会把那段数据从操作系统的内核区复制给p2进程指定的其用户区的位置
        • 因为所有进程共享独一无二的一片内核区，因此p2进程也能找到p1进程准备好的放在内核区的数据

• 进程的驻留集大小就是给某一进程分配了几个页框，比如说某个进程的页表有三个页表项也就是3个页，但是实际上物理空间只分配了2个页框，那么其页表中有效位最多有2个为1的。

• 局部淘汰：只从给进程本身分配的页框当中选择一个淘汰出去

  • 全局淘汰：可能从其他进程的页框当中选择一个淘汰出去

• 页表始址寄存器里面保存的是物理地址

• 进程切换开销：从一个进程切换到另一个进程的时候，意味着TLB里面的所有数据，所有缓存的数据都得作废，Cache里面的数据也要作废

  • 同一进程不同线程的切换，TLB和Cache数据副本不会作废，所以切换代价比进程切换小

• 数组在虚拟地址空间中的地址连续，在物理地址空间里面不一定连续

时间计算

• 注意区分地址转换和访存时间计算的区别
  • 地址转换只要得到页框号就停止
  • 访存时间=地址转换时间+内存访问的时间

• 以上为不发生缺页时候的情况
• 如果发生缺页，则
  • 地址转换时间=查到最后一级页表的时间+缺页处理时间+TLB查询时间
  • 内存访问时间=查到最后一级页表的时间+缺页处理时间+TLB查询时间+访存时间
    • 因为TLB未命中的时候，查页表的同时会更新TLB
    • 缺页的时候，调入页面的同时会更新页表和TLB

• 二级页表的情况下，一级页表是可能缺页的，因为一级页表的页目录项中，有效位是否为1取决于对应的二级页表有没有调入内存，此时需要先把二级页表调入内存，然后再查二级页表，如果二级页表缺页，再把对应的页调入内存
  • 一级页表里面存储的是二级页表的页框号

总结

• 操作系统创建一个新进程的时候，就会给这个进程分配虚拟地址空间，而每一个进程的这个虚拟地址空间，里面包含各个页面，这些页面会被映射到物理内存的各个位置
• 有一些页面是在外存当中还没有调入内存，所以我们需要有一个页表，用页表去表示出这个虚拟页面和物理页框之间的映射关系
• 如果访问到一个暂时没有调入内存的页面，那么这样的页面，在页表项中，有效位是0，操作系统会通过缺页异常的处理，去外存当中把这个页面的数据调入内存，并且更新页表项。如果有TLB，更新慢表项数据的同时，也会把这个新调入的页面所对应的页表项的副本数据复制一份到TLB当中，这样的话，再次访问同一个页面，就可以直接TLB命中。
• 操作系统给一个进程分配的页框是有限的，那么当页框不够用的时候，就要通过页面置换算法把页框置换出去
• 两个进程共享操作系统的内核区，只要把两个进程虚拟地址的高地址部分映射到同一片物理页框里面即可
• 共享内存，本质是就是操作系统修改两个进程的页表，让两个进程的页面（虚拟地址空间）映射到同一个页框（物理地址空间），让两个进程在同一个页框当中进行数据的读写

文件管理

• pdf保存：
  • https://www.notion.so/PDF-219b5125721b8099b94af0afb47e035c?source=copy_link

文件结构

• 文件物理结构
  • 连续分配
  • 隐式链接分配
  • 显式链接
    • FAT文件分配表
      • 如果文件存储介质容量较小，则在文件操作是，可把整个FAT装入内存，从而可显著地提高检索的速度；而在整个文件卷中在设置一个备份FAT，则可较好地增加文件系统的可靠性。
      • 但采用显示连接分配时，对较大文件的随机存取，需先在FAT中顺序查找许多盘块好号，故它不能支持高效的随机存取；如果文件存储介质容量较大，则FAT也需占用较大的存储空间，此时将整个FAT装入内存显然是不现实的，这会进一步影响到文件随机存取的效率
      • 先改FAT表再删改数据
  • 索引分配
• 文件逻辑结构
  • 文件逻辑结构的第x个字节指明的是文件的逻辑地址
• 文件系统会根据文件的物理结构，把文件的逻辑地址映射为这个文件实际存储的物理地址，这个映射过程跟文件系统文件的物理结构有关
  • 然后文件系统把这个文件的数据从外存读入内存
• 簇就是块，磁盘块是linux的说法
• 每个磁盘分区里面，当对某一个分区进行格式化的时候，这个分区的文件系统就被建立了
  • 文件系统的格式有很多种
  • 一旦文件系统建立完之后，其实就确定了这个盘里面存储文件到底是使用什么样的物理结构
    • UNIX的UFS文件系统，文件的物理结构就是索引分配，而且是混合索引分配
    • FAT文件系统是微软在早期DOS系统里面配的，物理结构采用显示链接分配
    • 因此理论上可以让每个盘在格式化的时候，建立不同的文件系统，比如C盘用ufs，D盘用FAT
      • fat只能传4GB，一个4gb的u盘可以 格式化成fat
• 文件系统确定，文件物理结构确定
  • 文件系统建立，根目录的信息也会被建立
    • 如果是ufs文件系统，此时索引节点会被放在外存的几个连续的磁盘块中
  • 文件系统建立，inode结点集中存储的位置和根目录的存储位置也会被确定
  • 文件系统建立，硬盘/文件系统的空闲分区管理的数据结构也会在磁盘内部建立
    • eg：位示图

操作系统引导（开机过程）



• 主存分为两个部分：BIOS系统集成在主板上，在ROM芯片里面，ROM上面就是RAM，内存的物理地址PA指向了ROM+RAM两个部分

• ①开机的时候CPU首先会去执行ROM芯片当中的自举程序

• ②自举程序会把主引导记录（MBR）读入RAM， 执行磁盘引导程序，扫描分区表，检查电脑中有几个分区，找出系统盘。

  • 物理磁盘的第一个扇区就是MBR分区
  • MBR包含磁盘引导程序和分区表

• ③找到系统盘之后，自举程序会把**系统盘中的第一个磁盘块（存储操作系统初始化引导程序）（PBR）**读入内存

  • 每一个逻辑分区（如C、D、E、F）都有一个PBR（分区引导记录扇区），也就是每个分区的第一个扇区，里面存放了该分区的引导程序
  • 如果分区中有操作系统，PBR会包含操作系统的引导加载程序，所以在图4.20一个可能的文件系统布局中，磁盘分区第一个块明明应该是PBR但是却称为引导块

• ④读入内存后，执行该磁盘块中的操作系统初始化引导程序

• ⑤操作系统初始化引导程序的执行，会引导CPU去把根目录的信息（inode结点）读入内存

• ⑥有了根目录的信息（inode结点）就知道系统盘里面的内容，存储了哪些东西

• ⑦接着操作系统的初始化程序就可以从根目录出发，去找到系统盘里面，操作系统开机所需要的文件，并逐一加载进内存

• MBR和PBR的关系：

  • MBR是磁盘的第一个扇区，通常包含启动计算机所需要的引导程序。

    • MBR 是硬盘的第一个扇区，其大小为 512 字节，通常位于硬盘的最前面。它独立于于任何分区，它是硬盘的“引导区域”，用于存储启动引导信息和硬盘的分区表。

    PBR是每个分区的第一个扇区，它包含启动该分区操作系统所需的引导信息。

  • MBR负责引导计算机启动，而PBR负责启动具体的分区操作系统。

  • MBR包含的是计算机启动代码，而PBR是负责分区操作系统的引导。不同分区的PBR可以有所不同，尤其在多操作系统的情况下，每个操作系统的PBR都是独立的

  • MBR 中的机器码只负责引导加载分区并将控制权转移到活动分区的第一个扇区（PBR）。它并不直接启动操作系统，只是启动引导过程的第一步。

    PBR 是活动分区的引导记录，它的主要任务是启动操作系统的引导程序，如 GRUB 或 Windows 启动管理器，并将操作系统加载到内存中，最终启动操作系统。

  • MBR的机器码：计算机开机后，CPU 会首先读取硬盘的 MBR。MBR 中的机器码检查分区表，识别活动分区，假设活动分区是分区 1。

    PBR的机器码：MBR 将控制权交给分区 1 的第一个扇区（即 PBR）。PBR 中的引导程序负责加载操作系统的引导程序（例如，GRUB 或 Windows 启动管理器）。

    操作系统引导程序：PBR 会启动操作系统引导程序，操作系统的内核就会被加载到内存中，并完成操作系统的初始化。

  • MBR根据分区表找到活动分区，把控制权交给活动分区并指示继续读取该活动分区的第一个扇区即PBR

    而PBR不需要再去查找其他扇区，它已经包含了操作系统的引导程序，PBR 的引导程序会加载操作系统的主引导程序，例如 GRUB（Linux 系统的引导管理器）或 Windows 启动程序。

    引导程序接下来会加载操作系统的内核，并启动操作系统。

  • 

• PBR和操作系统引导程序的关系：

  • PBR 通常包含以下几部分内容：

    • 引导程序（Boot Loader）：
      • 这是 PBR 中的主要内容，包含了用于引导操作系统的机器码。通常这个引导程序会非常小，负责将操作系统的更大部分（如启动管理器或操作系统内核）加载到内存中。
      • 引导程序也会通过加载操作系统的启动管理器（如 GRUB 或 Windows 引导程序），进一步引导系统进入操作系统内核的启动过程。
    • 文件系统信息：
      • PBR 中也可能包含一些与分区文件系统相关的信息，比如分区的类型（如 FAT32、NTFS、EXT4 等）和一些文件系统的启动信息，这样操作系统的引导程序才能理解如何访问分区内的数据。
    • 操作系统引导程序的地址：
      • 在 PBR 中，引导程序会知道如何找到并加载操作系统的主引导程序。通常这包括操作系统内核或者启动管理器的文件路径和位置。这个过程对于多操作系统的启动至关重要。
    • 引导记录签名：
      • PBR 的最后 2 字节通常是 0x55AA，这个签名用于验证该扇区是否有效。如果 PBR 中的签名正确，表示该分区有一个有效的引导记录，可以继续加载操作系统。否则，启动过程会失败。

  • PBR 读取并执行内嵌的引导程序，该程序负责将操作系统的启动程序加载到内存中。

    启动程序（如 GRUB 或 Windows 引导程序）加载操作系统的内核到内存并启动操作系统。

  • PBR 是活动分区的第一个扇区，包含了启动操作系统所需的引导程序。

    PBR 中的引导程序会加载操作系统的主引导程序（如 GRUB 或 Windows 启动管理器），进而启动操作系统。

    引导操作系统的程序通常是非常小的，它的主要任务是将操作系统的核心部分加载到内存中，并确保操作系统能够正确启动。

UFS文件系统

• 文件物理结构：混合索引

  • 目录文件由目录项（FCB文件控制块）组成，一个目录下面有几个文件就有几个目录项

    • eg：上图root根目录里面应该包含3个目录项

  • 索引分配会把文件的存储信息用索引表来表示，索引信息放到Inode当中

    • 每一个目录项由文件名以及指向索引节点的指针构成
    • ufs在磁盘当中专门用几个连续的磁盘块去存储这些Inode结点
      • Inode结点实际上就是一个struct结构体，struct inode{};inode a[N]连续存放到外存某一个固定的磁盘块，那些索引节点的编号本质上就是数组下标
        • 无论索引节点有没有被使用，当ufs文件系统被格式化的时候，就会在某一个磁盘块把所有的索引节点集中存储在其中
        • 每一个索引节点的大小都是一致的
        • inode结点里面包含索引信息、所有者、创建者、总块数、共享计数等信息
          • 共享计数在硬链接中使用，说明几个FCB指向这个inode，比如当两个FCB指向同一个inode，那么该inode的共享计数为2

  • inode和索引表的关系：

    

    • 索引表是inode的一部分内容，inode除了储存索引表以外，还会存储一些其他信息比如所有者、创建时间、总块数、共享计数等

  • 目录文件、目录项、索引表、索引结点之间的关系梳理

    • 目录文件由目录项组成
    • 目录项记载了文件名和指向inode结点的指针
    • inode结点包含索引表和一些说明信息

  • 根目录存储在固定的位置，这样可以保证开机时，能够找到根目录，再从根目录出发找到其他信息

    

    • 开机的时候需要去系统盘里面去找操作系统的引导程序

      • 为了找到系统盘里面存储的东西，需要保证这个系统盘根目录的存储信息存储在一个固定的位置
      • 比如名单表放在一个盒子里面，为了找到这个名单表，我得把盒子放在一个固定的位置
      • 这样开机启动读取固定的块，就可以找到系统盘存储的信息

    • 开机时，根目录的内容通常会被加载到内存，并一直常驻内存

    • 这个根目录有ABC三个目录下，当我想要访问A文件的时候，要去1号inode里面去找，把A文件的inode信息从磁盘读到内存里面，这样就可以在内存里面查看里面有什么数据

      • 比如我想访问A文件的第5000个字节，因为一个磁盘块的大小是4KB，因此第5000个字节一定是在这个文件的第二个逻辑块上，而第二个逻辑块存储在第七个磁盘块这个位置。

        

        • 因此当我想要访问第5000个字节的时候，应该把七号磁盘块读入内存

  • 文件数量的上限受到inode节点数量的影响

    

    • inode区的大小不能更改，在给磁盘格式化的时候就已经确定，不可动态增加，除非清空磁盘再次格式化

  • inode区也是存储在固定位置

    • 好处是想要去访问某一个文件的inode，就可以方便找到inode

  • 位示图

    

  • 引导块

    

    • 开机的时候一定要从这段程序开始运行

  • 如果我的操作系统安排在C盘，那么我的电脑如何找到这个开机需要运行的程序？

    

    • 首先，电脑通电之后会去找ROM芯片里面的自举程序，然后运行。自举程序的执行效果就是会把安装了操作系统的这个盘（分区）的第一个磁盘块读到RAM（内存）里面。第一个磁盘块里面保存的就是操作系统的初始化程序

      

    • 之后，执行操作系统的这段初始化程序。这段程序和文件格式是相匹配的，如果我是ufs文件系统，那么这个引导程序就会初始化为以ufs文件系统去开机的一段逻辑，而如果我是fat文件系统，那么这个引导程序，就基于fat文件系统去写开机需要做什么事情。

    • 开机时引导操作系统初始化程序的初始化，是在格式化文件系统的时候确定的，而由于确定了文件系统，文件系统根目录在磁盘中的位置也就确定了，因此可以在操作系统初始化程序中去指明这个文件系统的根目录信息位置。然后将根目录的inode结点（固定位置）从外存读到内存。

      

    • 而C盘里面包含了操作系统初始化的更多信息，只要找到根目录，就可以从根目录出发完成开机的一系列事情。之后根据根目录inode内容，将**根目录的具体内容数据（索引表记载的盘块号，对应盘块号里面的内容）**加载到内存

      

      • 接下来想要访问任何一个文件，只要告诉这个文件的存储路径，就可以从这个根目录出发，逐级往下找

  • 超级块：用于快速找到空闲区

    • 功能和位示图有一定重合性，但也是用于管理磁盘，当我们想要哦那个磁盘里面分配一些空闲块的时候，找到很多个空闲磁盘块，从超级块出发去找会比较方便

    

读某个文件的过程

• open的作用：把文件的inode结点读入内存

  read的作用：指明接下来访问的是文件的哪些字节，然后让操作系统从外存读入内存，操作系统是根据inode结点的信息去判断，要访问的这些字节到底存储在磁盘的哪个磁盘块中

  write的作用：指明要写的是哪个文件（文件描述符），指明准备好的数据在哪个位置，写多少个字节，操作系统根据inode结点信息去判断要写的这些字节存储在磁盘的哪个磁盘块中

  write(fd,第二块,a[4096])
  C++

• 首先要找到文件（open）

  • 在根目录常驻主存的前提下，从根目录出发找到A中的Dm文件
    • 从根目录下面找到名为A的目录项，然后将A对应的inode结点读入内存
    • 根据inode信息找到A的目录文件，并读入内存
      • 一个一个磁盘读入，读一个搜一个
    • 发现Dm文件对应的目录项，得到dm文件对应的inode结点
    • 把该inode结点从外存读入内存，之后想要访问这个文件的某个字节，存储在磁盘当中的哪个位置，就可以根据这个inode结点里面的索引表去找

• 打开之后，操作系统会给我返回这个文件的文件描述符fd，接下来就可以根据fd去读fd指向的文件（read）

  • 操作系统收到read调用以后，会把对应磁盘块从外存读入内存，然后操作系统会把这个磁盘块中的第0~1023个字符，从内核区复制到进程的用户区定义的buffer数组

  *fd=open("/A/Dm")
  read(fd,0~1023,buffer);//char buffer[1024];
  //文件描述符，读哪几个字符，存储到什么位置
  C++

• 把主要信息都进来之后，在操作系统的内部有两个数据结构，一个叫系统打开文件表，还有一个叫做用户打开文件表

  • 文件描述符指向用户打开表的某一个表项
    • 该表项指向系统打开表对应的文件的inode结点的内存指针
      • 如果有两个进程打开同一个文件，那就两个用户打开表中有两个指向同一个系统打开表表项
    • inode结点的内存指针指向内存中的inode结点

  

  

  • 用户打开文件表是每一个进程都有一个，包含在进程的PCB当中
  • 系统打开表则是整个系统独一份

文件的逻辑结构和物理结构的映射关系

• 假设这个文件B叫柯南.mp4，逻辑上看这个文件刚好占三个磁盘块大小，12kb，假设这个视频一共有3段，三段大小相等存储在3个块中，如果我要看这个视频，肯定要把b的这个文件的数据读入内存
  • B在根目录下面，因为根目录常驻内存，就可以直接从根目录找到b这个文件
  • b这个文件对应的inode是2号inode
  • 在看这个视频之前我得open，所以看这个视频本质上就是read，我要把这个MP4文件read到内存里面，然后我的视频播放器这个进程，就会从内存里面获取这个视频的完整的数据，把文件转化为视频信息，然后通过I/O系统从扬声器和显示器播放，然后开始读第一个逻辑块，当想要播放中间，就要读入第二块
    • 假设我只读入了一好快，此时我在视频播放器上点了快进到最后的一分钟，那么对于我的这个视频播放器用户进程而言，快进到最后一分钟，本质上就是我告诉操作系统，我想要去访问这个视频文件的第三个逻辑块
      • 这个快进背后对应的就是read系统调用，会触发一个read系统调用告诉操作系统，把最后一分钟对应的数据读入内存
        • 最后一分钟的数据，操作系统可以在内存当中已经读入的inode里面找到，然后读进内存
      • 先open再read
  • 要openb，先得找到b对应的inode，找到b对应的inode是二号，接下来把二号inode从外存读到内存
  • 有了inode信息以后，就可以read它的任何一块的数据





• 应用程序或者说用户进程会根据文件的逻辑格式，去告诉操作系统想要访问的是这个文件的逻辑上的第几个块/第几个字节。
  • 操作系统会把逻辑地址转化为物理地址，然后从外存当中把想要访问的数据读入内存

如何读z文件

• open"/C/F/Z"

  • open的最终目标是找到目标文件的inode结点，并且把它的inode结点读入内存

  • ①从常驻内存的根目录出发，找到要读的c对应的目录项，找到C是对应inode7

    

  • ②把inode7读入内存，然后根据7号inode结点的信息知道C的目录文件存储在9号块处

    

  • ③读入九号块，查看C的具体内容，找到F

    

    

  • F对应4号inode，将4号inode读入内存

    

  • 从目录文件F对应的inode结点得知F的目录文件存储在14号块，读入14号块，读入14号块的本质是想看F下面存储了什么东西

    

    

  • 发现Z对应的inode是13号，把13号inode读入内存

    

    

    • 直接索引会指向前10个块，一级间接指向索引块，查一级索引表也要把对应的索引块读入内存，读入之后就能知道逻辑地址块对应的物理地址

      

      • 也就是说指向1024个数据



• 间址指向的是索引块而不是inode

• 假设我找到z后要读取z的第6154个字，那么我得去二级间址找

  

  • 该索引块包含1024个索引项

    

    • 经过计算可知6154应该在下表为4的索引项对应的索引块那

      

      

• 计算

  

  

  

关于inode的调入

对于 第一次打开文件，操作系统必须去硬盘读取对应的 inode，而不依赖于内存中的 inode 缓存。即使是其他 inode 已经被调入内存，只要是 第一次打开文件，操作系统都需要去硬盘读取该文件的 inode。下面我进一步澄清这个过程：

1. 第一次打开文件时必须去硬盘读取 inode：

• 当进程请求打开一个文件时，文件系统必须找到该文件的 inode，而 inode 存储着文件的元数据。
• 即使其他 inode 已经被加载到内存中（比如在之前访问其他文件时已经调入），操作系统也不能直接假设该文件的 inode 已经在内存中。这是因为 inode 的存储是**按块（block）**来组织的，多个 inode 可能会被存储在同一个块中。操作系统在读取一个 inode 时，实际上是将该块从硬盘加载到内存中，而不是只读取一个单独的 inode。

2. inode 缓存的作用：

• 操作系统会将访问过的 inode 缓存到内存中的 inode 缓存，以提高后续访问同一文件时的效率。如果 inode 已经在内存中，操作系统可以直接从内存中获取。
• 然而，第一次打开文件时，因为该文件的 inode 还没有被缓存到内存中，操作系统就必须去硬盘上查找和加载该 inode。

3. 不存在“先查看内存”的步骤：

• 虽然操作系统会维护一个 inode 缓存，但它并不在第一次打开文件时先检查内存。操作系统在打开文件时会直接通过文件的路径来定位 inode（通常是通过目录项与 inode 的映射关系）。如果这个 inode 不在内存中，操作系统会去硬盘读取。
• 只有当文件的 inode 被加载到内存中后，才会通过 inode 缓存来提高后续对同一文件的访问效率。

4. 总结：

• 第一次打开文件时，操作系统必须去硬盘读取 inode，并将其加载到内存中。
• 即使其他 inode 已经在内存中，也不能影响第一次打开文件的过程，因为每个 inode 都是单独按块存储的，而且操作系统无法预先知道该 inode 是否已经在内存中。
• inode 缓存只在后续访问同一文件时提供帮助，减少了磁盘 I/O 操作。

举个简单例子：

1. 第一次打开文件时，操作系统必须去磁盘读取该文件的 inode。它会读取硬盘的目录结构，找到 inode 所在的块，将该块读取到内存中。
2. 以后如果再次访问相同的文件，操作系统就可以直接从内存中的 inode 缓存中获取 inode，避免了磁盘读取。

FAT文件系统

• 刚开始的几个块和UFS系统有区别

  • FAT文件系统在最开始固定了几个连续的块去存储FAT文件分配表

    • FAT本质上是静态链表
    • 开机的时候除了读入根目录，也要把整个FAT表读入并常驻内存

    

  • 根目录也要存储在固定的位置

    • 因为开机的时候得去固定的位置找根目录，然后把根目录的信息读入内存
      • 如果根目录不止占一块，那么得去FAT表里面找读入的第一个根目录磁盘块的下一个块块号

    

FAT如何访问一个文件


• FAT表的块号是隐含的，真正占据存储空间的是下一块块号，FAT表能指的范围，就是FAT表最多能容纳多少个表项

• FAT表中-2表示空闲

• 如何扩充一个文件：找到空闲盘块号，再找到该文件的最后一个盘块的指针，指向分配的空闲盘块

  

访问B

• ①读或写一个文件之前一定要open该文件

  • 本质上是找齐控制信息然后存放到内存里面
  • 由于b这个文件的文件目录项就是完整的控制信息，b对应的目录项里面包含了这个文件完整的控制信息

  

  

• ②找到b文件的目录项，然后去将访问的块读入内存，比如要访问第三块，就去将第三块读入内存

• ③从FAT表里面找到第三块的物理地址

  • 从目录项里面得知起始块号是10，去FAT表里面找10，然后找到下一块块号12，然后继续找12，找到12的下一块块号8，则第三块是八号块

• ④根据物理地址将对应磁盘块读入内存

• 为什么显式链接能够实现随机访问？

  • 因为给出一个逻辑地址，操作系统总能根据FAT表推算出逻辑地址在外存中对应的磁盘块号

读写/A/Dm文件

• ①根据文件路径，先取根目录找A
• ②通过FAT文件表判断出A的块都在什么位置
• ③A的各个块依次读入，看能不能找到，一个块不能找到就读下一个，直到找到完整的控制信息为止
• ④根据控制信息找到Dm对应的块，去FAT表里面看Dm有几个块，将它们读入主存即可

读写/C/F/Z文件

• open z
• read z
• 都是先读入再检索，循环往复直到找到所需要的控制信息，得到起始地址，然后根据控制信息去FAT找物理地址
• 因此FAT文件存大文件效率低，但是读大文件的话inode读磁盘的次数比fat读磁盘的次数多
  • fat反复查FAT表（内存当中），就能找到物理地址，然后根据物理地址直接从磁盘中取出，只用读一次磁盘
  • 而inode要不断索引跳转

习题带练

梳理/补充

• 索引方式下，读一个文件，首先去读该文件的索引节点所在的磁盘块，再读该文件内容（数据）所在的磁盘块（由索引节点得知）
• 索引节点相同，说明指向同一个文件，并且是硬链接
• 将某个文件读入内存的过程就是找到该文件的FCB/inode，然后再读数据的过程，分为两个部分进行计算得到最终需要存取几次磁盘
• 减少读磁盘的次数会有两种解决思路
  • fcb分解法
    • 把文件名和文件信息分别存储，建立inode节点，目录项只保存文件名，及inode节点的指针信息，这样目录项的大小被缩短，找到目录项之后，再根据inode节点指针找到inode节点，而inode节点里就会包含文件的各种详细信息
  • 设置当前目录
    • 设置当前目录说明目录文件已经被放到内存里面了，意味着可以直接找到fcb，不用一级一级往下找

磁盘计算

相关物理量

• t：每个柱面上的磁道数
  • 相当于一个柱面共有几个磁头，即多少个盘面
• s：每个磁道上的扇区数
  • 每个磁道的扇区数量都是一样的
• i：柱面号
  • 因为所有编号从0开始，所以i相当于实际经过的完整竹面数量，后续计算也是直接用i，如果编号从1开始，那么只算i-1个柱面数，后序物理量同理
• j：当前所在柱面的磁头号
  • 一个柱面有多个磁头，因为编号从0开始，实际上已经填满了该柱面前面的j个磁道
• k：扇区号

磁盘结构说明

• 如图所示，假设一个磁道有100个扇区，由图可知，所有的磁道扇区数量是一样的，只不过内磁道的扇区弧段更短，外磁道的扇区弧段更长

• 因此磁盘的地址结构：柱面号，盘面号，扇区号是按照填入顺序形成的
  • 先填满一个磁道的所有扇区，然后继续填满下一个同柱面的磁道，最后再移到另一个磁道

计算式解析

• 如果要求柱面号i=2，磁头号j=4，扇区号k=10所对应的块号b
  • 由图可知t=6，s=100（假设已知）
• 系统存放信息时，并不是按照磁盘面上的磁道顺序存满一个磁盘后再存放下一个盘面，而是按照柱面顺序存放，当同一柱面上的磁道存满后，再存放到下一个柱面上
• 所以当i=2，说明0号和1号磁道已经填满了，这两个柱面一共有i*t个磁道数加上自己当前的磁头号j（这里磁头号=磁道号）
  • 总磁道数=j+i*t
  • 经过的扇区数=s* (j+i*t)
  • 总扇区数=经过的扇区数+自己当前的扇区号 k=k+s* （j+i *t）
• 反过来求柱面号i，磁道号j和扇区号k
  • 令d=s*t（s是每个磁道上的扇区数，t是每个柱面上的磁道数）
  • i=b/d
  • j=b%d/s
  • k=b%d%s