操作系统个人复习用笔记

复习

个人复习用，范围确定型复习笔记，配套计算机操作系统

Almost Complete.....

---

选择题类

1. 操作系统的地位

• 操作系统是软件，而且是系统软件。它在计算机系统中的作用，大致可以从两方面体会：
• 对内，操作系统管理计算机系统的各种资源，扩充硬件的功能
• 对外，操作系统提供良好的人机界面，方便用户使用计算机。它在整个计算机系统中具有承上启下的地位。

2. 分时系统与实时系统

• 分时操作系统将系统处理机时间与内存空间按一定的时间间隔，轮流地切换给各终端用户的程序使用。
• 实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。

3. 操作系统的特性

1. 并发(Concurrence)
2. 共享(Sharing)
3. 虚拟(Virtual)
4. 异步性(Asynchronism)

4. 信号量机制

• 整型信号量：PV操作，原子操作，未遵循“让权等待”规则
• 记录信号量：增加进程链表
• “AND” 型信号量：多资源
• “信号量集”机制：试用需求值和下限值
• 使用信号量实现前趋关系

• PV操作
  

  信号量S的物理意义是：当S≥0时，表示某资源的可用数，当S<0时，其绝对值表示阻塞队列中等待该资源的进程数。

5. 进程与线程的区别

1. 线程只和其他线程一起共享进程资源
2. 调度：以线程为单位进行进行处理机切换和调度时，处理机切换时间较短，效率较高
3. 并发性：进程中多线程可以并发
4. 资源：一般，线程不拥有系统资源，但可以访问进程资源
5. 系统开销：线程的代价低

进程相反

6. 调度的层次

1. 高级调度：
   调度对象：作业
   外存→内存
2. 低级调度：
   调度对象：进程
   内存→内存
   进程调度分抢占式调度与非抢占式调度
3. 中级调度：
   调度对象：进程
   暂不运行进程：内存→外存（挂起）
   重又具备运行条件且内存空闲：外存→内存（就绪态）

分区分配算法

1. 首次适应算法
2. 循环首次适应算法
3. 最佳适应算法
4. 最坏适应算法
5. 快速适应算法

7. 页面调入策略

1. 预调页策略
   
   • 一次调入若干个相邻的页
2. 请求页策略
   
   • 根据需要一个个调入

8. I/O控制方式

1. 程序I/O
   
   • 由程序直接控制CPU与I/O设备进行数据传输的方式，又称为“忙等”方式
2. 中断驱动I/O
   
   • CPU与设备并行工作，但每传送一个字节，需产生一次中断
3. DMA I/O
   
   • 仅在传送一个或多个数据块的开始和结束时，才需CPU干预
4. 通道控制
   
   • 对一组数据块操作

9. DMA

• DMA传送方式是让存储器与外设、或外设与外设之间直接交换数据，不需经过CPU的累加器中转，减少了这个中间环
• 通过DMA每传送一个数据块仅需要一次中断处理

10. 中断与陷入的区别

陷阱的中断源头来自CPU的内部，而中断的中断源头来自CPU外部

11. 设备独立性

• 设备独立性，即应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统在实际执行时， 还必须使用物理设备名称。

• 好处：

  1. 设备分配时的灵活性
  2. 易于实现I/O重定向

12. 独占设备

• 从资源分配的角度可将设备分为独占设备、共享设备和虚拟设备。
• 如其名。

13. RAID

1. RAID 0(0级盘阵列)：仅提供并行交叉存取。
2. RAID 1(1级盘阵列)：具有磁盘镜像功能。提高可靠性。

4块硬盘
- RAID 0＋1 不可以两边RAID0中各坏一块硬盘，但可以在单边同时坏掉单边的两块硬盘。
- RAID 1＋0 可以两边RAID1中各坏一块硬盘，但不能同时坏掉单边的两个硬盘。
http://wangxb.blog.51cto.com/89889/16560/

14. 目录管理

• 文件目录、目录文件
  
  • 目录文件：由文件目录组成，用来管理和实现文件系统功能的系统文件，通过目录文件可以对其他文件的信息进行检索。
• 目录结构形式
  基本功能：按名存取
  
  1. 单级目录结构
     
     • 整个文件系统只建立一张目录表，每个文件一个表项。
     • 优点：简单，缺点：查找速度慢、不允许重名、不便于实现文件共享。
  2. 两级目录结构
     
     • 为每个用户建立一个单独的用户文件目录UFD。系统中有个主文件目录MFD。
     • 优点：提高检索速度，不同用户可以有同样文件名，不同用户可以用不同文件名访问一个共享文件。
  3. 多级目录结构
     
     • 多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点
     • 理解绝对路径与相对路径。

15. 界面分类

• 窗口图形界面
• 命令行界面
• 程序界面

16. Linux知识

• 发明者 - Linus Torvalds
• 来自于 - 教学UNIX系统MINIX
• 权限
  
  • 读r、写w、执行x
  • 

---

名词解释

1. 临界区

• 每个进程中访问临界资源的那段代码称为临界区（Critical Section）（临界资源是一次仅允许一个进程使用的共享资源）。
• 每次只准许一个进程进入临界区，进入后不允许其他进程进入。

2. 线程

线程是进程中的一个实体，是被系统独立调度和分配的基本单位，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。

3. 虚拟内存

是指具有请求调入功能和置换功能，能从逻辑上对内存进行扩充的一种存储器系统。
利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，从而增强系统的处理能力。
特性：①多次性②交换性③离散性

4. SPOOLing

• （假脱机操作）它使用直接存取的大容量磁盘作为缓冲，将一个可共享的磁盘空间改造成若干个输入设备和输出设备，并使得I/O设备和CPU并行操作。
• 组成
  
  1. 输入井和输出井：在磁盘上开辟的2个大存储空间，模拟输入和输出设备。
  2. 输入缓冲区和输出缓冲区（内存中）
  3. 输入Spi和输出SPo进程：脱机输入\出控制器
• 特点:
  
  1. 提高I/O速度： 对低速设备操作—>变为对输入/出井操作。
  2. 将独占设备改造为共享设备 分配设备的实质是分配输入/出井
  3. 实现了虚拟设备功能

---

简答题

1. 进程的状态与常用状态

2. 利用信号量实现前趋关系

• 实现：
  

  var a,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0;
  begin
      parbegin
          begin S1;   signal(a);  signal(b);  end;
          begin wait(a);  S2; signal(c);  signal(d);  end;
          begin wait(b);  S3; signal(e);  end;
          begin wait(c);  S4; signal(f);  end;
          begin wait(d);  S5; signal(g);  end;
          begin wait(e);  wait(f);    wait(g);    S6; end;
      parend end
  end

3. 哲学家进餐问题

1. 使用记录型信号量

var chopstick:array[0...4] of semaphore = {1,1,1,1,1};
begin
    repeat
        wait(chopstick[i])
        wait(chopstick[(i+1) mod 5])
        ;
        eat;
        ;
        signal(chopstick[i])
        signal(chopstick[(i+1) mod 5])
        ;
        think;
    until false;
end

2. 使用AND信号量

var chopstick:array of semaphore := (1,1,1,1,1);
begin
    repeat
        think;
        Sswait(chopstick[(i+1) mod 5], chopstick[i]);
        eat;
        Ssignal(chopstick[(i+1) mod 5], chopstick[i]);
    until false;
end

4. 进程调度算法算法

周转时间

1. 先来先服务调度算法（FCFS）

   • 特点：简单，有利于长作业（进程）
   • CPU繁忙性作业,不利于短作业（进程）

2. 短作业（进程）优先调度算法：SJ(P)F

   • 降低了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）
   • 对长作业不利，有可能得不到服务
   • 不能保证紧迫性作业（进程）会被及时处理。

3. 高响应比优先调度算法

   • 优先权=（等待时间+要求服务时间）/要求服务时间

4. 基于时间片的轮转调度算法

   • 时间片太大：退化为FCFS； 太小：系统开销过大

5. 多级反馈队列调度：由系统设置多个就绪队列，每个就绪队列中的进程按时间片轮转法占用处理器。

响应时间：从提交第一个请求到产生第一个响应所用时间。
周转时间：从作业提交到作业完成的时间间隔。
周转时间计算：http://psupsuoooo.blog.163.com/blog/static/318414820071059262885/

5. 实时调度算法

1. 最早截止时间优先算法（EDF）
   
   • 最早截止时间
2. 最低松弛度优先算法（LLF)
   
   • 松弛度=必须完成时-执行时间

5. 产生死锁的条件

1. 互斥条件。
2. 请求和保持条件
3. 不剥夺条件
4. 环路等待条件。

6. 分页与分段

详见书本！

1. 分页
   
   • 将一个进程的地址空间划分成若干大小相等的区域，称为页。相应地，将主存空间划分成与页相同大小的若干物理块，称为块或页框架。
2. 分段
   
   • 把用户程序的地址空间分成若干个大小不等的段，实现了离散分配
3. 段页
   
   • 页和分段的结合，集中了它们的优点。即提高了内存的利用率，又能满足用户的要求。

---

计算题

1. 银行家算法

详见书本！

2. 页面置换算法

详见书本！

1. 最佳置换算法OPT
2. 先进先出算法FIFO
3. 最近最久未使用置换算法LRU
4. 最近未用置换算法NUR

3. 电梯算法

详见书本！

• SCAN 扫描算法（电梯算法）
  
  • SSTF存在进程“饥饿现象”
• 循环扫描CSCAN（单向电梯算法）

4. 文件存储：位示图法、成组链接法

1. 位示图法
   
   • 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。
   • 磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。
2. 成组链接法
   
   • 分配：到s.free(0)时，由于该块内容为下一组的盘号，将内容加入空闲盘块号栈中，再分配。
   • 回收：到s.free(100)时，将空闲盘块栈中内容放入新到的回收块中，将该回收块作为栈底。
   • 请自行脑补。

---

其他题

1. 举出10个操作系统

1. 目前微机上常见的操作系统有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netwar
   等
2. 麒麟操作系统(Kylin),由国防科技大学、中软公司、联想公司、浪潮公司和民族恒星公司五家单位合作研制的服务器操作系统
3. COS（China Operating System）操作系统是由上海联彤与中科院研究所联合开发，是一款具有自主知识产权的不开源的操作系统。
4. 2009年12月25日消息，雨林木风官方团队昨晚宣布正式发布自主品牌的操作系统，向微软发起叫板。2012年8月8日，ylmf os正式更名为StartOS。

2. 你觉得未来的操作系统是怎么样的，操作系统的发展方向？

鸡肉味

---