作业题汇总:第7章之后
第7章 Linux进程管理
1.进程控制块,其中与进程管理、存储器管理和文件管理有关的一些字段,线程组标识符。
进程管理相关字段:
- 进程标识符:唯一标识一个进程的数值;
- 进程状态:描述进程当前状态;
- 程序计数器:指示进程下一条指令的地址;
- CPU寄存器:保存进程在切换时的寄存器内容;
- 调度信息:包含优先级、调度队列指针以及其他调度算法使用的;
- 进程优先级:指示进程的优先级,影响调度决策。
存储器管理相关字段: - 基址寄存器和界限寄存器:用于进程地址空间的界定,保护内存;
- 页表指针:指向进程的页表,用于虚拟内存管理;
- 段表指针:指向进程的段表,用于段式内存管理;
- 内存限制:描述进程可以使用的内存范围。
文件管理相关字段: - 文件描述符表:存储进程打开的文件的列表及其状态;
- 根目录和当前工作目录:进程的根目录和当前工作目录信息;
- 权限信息:描述进程对文件系统中资源的访问权限。
线程组标识符: - 用于标识一个线程组,所有属于同一线程组的线程共享同一个TFID;
- 在一些系统中,TGID可以与进程标识符相同,以便于管理。
2.与进程创建有关的函数:fork( )、vfork( )、clone( )。
fork():
- 创建子进程函数;
- 创建成功后,子进程采用写时复制技术读共享父进程的全部地址空间,仅当父或子要写一个页时,才为其复制一个私有的页的副本。
vfork(): - 阻塞父进程直到子进程退出或执行了一个新程序为止。
clone(): - 创建轻量级进程函数;
- 实现对多线程应用程序的支持。共享进程在内核的很多数据结构,如页表、打开文件表等。
3.理解进程切换的过程。涉及到页目录表、核心栈、硬件上下文。
- 第⼀步,切换*⻚⽬录表以安装⼀个新的地址空间;
- 第二步,切换*核⼼栈 和 *硬件上下⽂(即必须装⼊CPU寄存器的⼀组数据)。
4.进程调度方式。进程调度时机。
- 系统采⽤*可抢先式的动态优先级调度⽅式。⽆论进程处于⽤户态还是核⼼态运⾏,都可能被抢占CPU。
5.Linux有很多内核线程,了解0号进程和1号进程的作用。
- 0号进程就是⼀个内核线程,0号进程是所有进程的祖先进程,⼜叫idle进程或叫做swapper进程。每个CPU都有⼀个0号进程。
- 1号进程是由0号进程创建的内核线程init,负责完成内核的初始化⼯作。在系统关闭之前,init进程⼀直存在,它负责创建和监控在操作系统外层执⾏的所有⽤户态进程。
第8章 Linux存储器管理
1.进程地址空间的划分?管理进程私有地址空间的数据结构?链接虚拟内存区域的单链表和红黑树。指向映射文件对象的指针字段?指向进程页目录表的指针字段?
进程地址空间的划分:
- 32位机,每个进程的地址空间为4GB
- 进程的私有地址空间是前3G,进程的公有地址空间是后1G的内核虚空间
- 内核1GB虚空间
- 前896MB⽤来映射物理内存的前896MB,因此前896MB的内存物理地址等于内核虚地址减0xc0000000
- 后128MB的虚空间实现对超过896MB的物理内存的映射
管理进程私有地址空间的数据结构:
- 页表、段表、虚拟内存区域、内存描述符
链接虚拟内存区域的单链表、红黑树: - 单链表:需⽤⼀组虚拟内存区域描述符vm_area_struct来描述进程地址空间的使用情况;
- 红黑树:排好序的平衡二叉树
- 四条规则:树中的每个节点或为红或为⿊;树的根节点必须为⿊;红节点的孩⼦必须为⿊;从⼀个节点到后代诸叶⼦节点的每条路经,都包含相同数量的⿊节点,在统计⿊节点个数时,空指针也算作⿊节点。
- 四条规则保证:具有n个节点的红⿊树,其⾼度⾄多为2*log(n+1);红⿊树保证最⻓路径不超过最短路径的⼆倍,因⽽近似平衡。
指向映射文件对象的指针字段:struct file * vm_file; 映射⽂件时指向⽂件对象。
指向进程页目录表的指针字段:mm_struct的指针。
2.Linux堆的管理:malloc( ),free( )。
- malloc():用于在堆上分配一块指定大小的内存。
- free():用于释放由malloc()、calloc()或realloc()分配的内存块。
3.管理物理内存页框的数据结构?内存管理区zone结构,伙伴系统?了解分区页框分配器分配页框的过程。
管理物理内存页框的数据结构:
- struct page结构体
内存管理区zone结构: - ZONE_DMA:包含低于16MB的常规内存⻚框。⽤于对⽼式的基于ISA设备的DMA⽀持;
- ZONE_NORMAL:包含⾼于16MB且低于896MB的常规内存⻚框;
- ZONE_HIGHMEM:包含从896MB开始的⾼端物理⻚框。内核不能直接访问这部分⻚框。在64位体系结构上,该区总是空的。
伙伴系统: - 假设要请求⼀个具有8个连续⻚框的块;
- 该算法先在8个连续⻚框块的链表中检查是否有:
- 如果有,则分配;
- 如果没有:
- 就在16个连续⻚框块的链表中找;
- 如果找到,就把这16个连续⻚框分成两等份,⼀份⽤来满⾜请求,另⼀份插⼊到具有8个连续⻚框块的链表中;
- 如果在16个连续⻚框块的链表中没有找到,就在更⼤的块链表中查找。
- 直到找到为⽌。
分区页框分配器分配页框的过程: - 确定目标zone;
- 查找适当的free_area;
- 分配内存块;
- 更新元数据。
4.理解slab分配器的原理。slab分配器的作用?
slab分配器的原理:为只有⼏⼗或⼏百个字节的⼩内存区分配内存。
slabe分配器的作用:
- 从⻚框分配器获得⼏组连续空闲⻚框;
- slab分配器为不同类型的对象⽣成不同的⾼速缓存,每个⾼速缓存存储相同类型的对象。⾼速缓存由⼀连串的slab构成,每个slab包含了若⼲个同类型的对象。
5.进程页表建立的时机?了解页目录表项或页表项所包含的字段。逻辑地址的划分,利用两级页表实现地址转换的过程。
进程页表建立的时机:进程创建时初始化,在访问新内存区域或发生缺页异常时更新。
页表项所包含的字段:
- Present标志:为1,表示页(页表)在内存;为0,不在内存。
- 页框物理地址(20位):页框大小为4096,占去12位。
- Accessed标志:页框访问标志,为1表示访问过。
- Dirty标志:每当对一个页框进行写操作时就设置这个标志。
逻辑地址的划分:页目录索引(前10位)、页表索引(中10位)、页内偏移(后12位)。
利用两级页表数实现地址转换的过程: - 获取页目录项;
- 获取页表项;
- 获取物理页框地址,偏移,得到最终的物理地址。
6.请求调页。所缺的页可能存放的地方。
请求调页:
- 增加了系统中的空闲⻚框数;
- ⻚⾯置换策略是LFU。
所缺的页可能存放的地方: - 该⻚从未被进程访问过,且没有相应的内存映射;
- 该⻚已被进程访问过,但其内容被临时保存到磁盘交换区上;
- 该⻚在⾮活动⻚框链表中;
- 该⻚正在由其它进程进⾏I/O传输过程中。
7.了解盘交换区空间的管理方法。
- 每个盘交换区都由⼀组4KB的⻚槽组成
- 盘交换区的第⼀个⻚槽⽤来存放该交换区的有关信息,有相应的描述符。
- 存放在磁盘分区中的交换区只有⼀个⼦区,存放在普通⽂件中的交换区可能有多个⼦区,原因是磁盘上的⽂件不要求连续存放。
- 内核尽⼒把换出的⻚存放在相邻的⻚槽中,减少访问交换区时磁盘的寻道时间。
第9-10章 Linux文件系统
1.Ext2文件卷的布局?各部分的作用是什么?
Ext2文件卷的布局:
- 把磁盘块分为组,每组包含存放在相邻磁道的数据块和索引节点,块组的⼤⼩相等并顺序安排;
- ⽤“块组描述符”来描述这些块组本⾝的结构信息,同时将超级块和所有块组描述符重复存储于每个块组中;
- 通过“位图”来管理每个块组中的磁盘块和索引节点。盘块位图,索引节点位图。
各部分的作用: - 超级块存放整个⽂件卷的资源管理信息;
- 索引节点存放⽂件的管理控制信息;
- 只有块组0中所包含的超级块和块组描述符才由内核使⽤,⽽其余的超级块和块组描述符保持不变,事实上,内核甚⾄不考虑它们;
- 盘块位图必须存放在⼀个单独的块中;
- 索引节点位图也必须存放在⼀个单独块中。
2.Linux系统把一般的文件目录项分成哪两部分?这样做的好处是什么?
文件目录项分为的两部分:简单目录项和索引节点。
好处:
- 简单⽬录项包含了⽂件名和索引节点号等,可以提⾼⽂件⽬录的检索速度;
- 系统只保留⼀个索引节点,就可实现多条路径共享⽂件,减少信息冗余。
3.Linux文件系统的索引节点中,索引表划分成几级?文件的索引表是如何增长的?要求能够利用索引表实现将文件中的字节地址转换成文件的物理块的操作。
索引表划分等级:3级:直接索引项、一次间接索引块、二次间接索引块、三次间接索引块;
文件索引表的增长方式:文件大小增长时,索引表逐级增长,从直接索引到一次、二次和三次间接索引块;
字节地址到物理块的转换:通过查找索引节点中的直接索引或通过间接索引表进行查找,将文件的逻辑地址(字节地址)映射到物理块的地址。
4.硬链接和符号链接的区别?
- 硬链接是通过索引节点(inodeindex)来进行链接的,多个文件名指向同一索引点。保存在磁盘分区中的文件不管是什么类型都有一个编号,称为索引节点号(inodeindex)。硬链接的作用是允许一个文件拥有多个有效路径名。
- 硬链接文件有两个限制:
- 不允许给目录创建硬链接;
- 只允许在同一文件系统中的文件之间才能创建链接。
- 对于硬练级文件进行读写和删除操作的时候,结果和符号链接相同。但是如果我们删除硬链接文件的源文件,硬链接文件仍存在,而且保留了原有的内容。
- 符号链接在建立的时候建立了一个新的inode,并记录了指向源文件inode的路径。所以符号的inode number跟原始档案的inode number是不一样的。
- 符号链接文件包含了另一个文件的路径名。可以是任意文件或目录,也可以链接不同文件系统的文件。在对符号链接进行读写操作的时候,系统会自动把该操作转换为对源文件的操作。但是删除链接文件时,系统仅仅删除符号链接文件,而不删除源文件本身。
5.Linux文件系统如何管理空闲存储空间?
空闲存储空间管理:
- 磁盘块和索引节点的分配和回收
- ⽂件的数据块和其索引节点尽量在同⼀个块组中;
- ⽂件和它的⽬录项尽量在同⼀个块组中;
- ⽗⽬录和⼦⽬录尽量在同⼀个块组中;
- 每个⽂件的数据块尽量连续存放。
6.VFS通用文件模型中的四个主要对象?
- 超级块对象:Linux为每个安装好的⽂件系统都建⽴⼀个超级块对象;
- 索引节点对象:打开的⽂件对应的…
- ⽬录项对象
- ⽂件对象:记录了进程与打开的⽂件之间的交互信息。
7.Linux系统中,进程打开一个磁盘文件要涉及哪些数据结构?了解:它们各有哪些关键字段?他们的作用是什么?参考图
图 进程打开文件的过程 提取码7568
- task_struct
- files:指向 files_struct 的指针。
- 作用:task_struct 是每个进程在内核中的表示,其中包含了进程的所有信息,包括打开的文件等。files 字段指向该进程所有打开文件的描述信息。
- files_struct
- fd_array[]:文件描述符数组,每个条目指向一个 file 结构。
- 作用:files_struct 维护了一个进程的所有打开文件的列表。每个已打开的文件都会在 fd_array[] 中有一个条目,条目内容为指向对应 file 结构体的指针。
- file
- f_list:链表,连接在同一文件结构中的所有文件对象。
- f_dentry:指向 dentry 结构的指针。
- f_op:指向文件操作的函数指针(file_operations)。
- f_pos:当前文件的位置偏移量。
- f_count:引用计数器。
- 作用:file 结构表示一个已打开的文件。它包含了文件的状态信息,包括当前文件位置、引用计数和文件操作函数。在访问文件内容时,通过 f_dentry 字段,file 结构指向文件的 dentry 结构(目录项)。
- dentry
- d_inode:指向 inode 结构的指针。
- d_op:指向目录项操作(dentry_operations)。
- 作用:dentry 结构用于目录项管理。它包含了文件名到 inode 的映射,用于加速文件路径的查找。访问文件时,通过 d_inode 字段,dentry 结构指向文件的 inode 结构。
- inode
- i_ino:文件的 inode 编号。
- i_op:指向 inode 操作的函数指针(inode_operations)。
- i_nlink:文件的硬链接计数。
- i_data[]:文件数据块指针。
- 作用:inode 结构包含了文件的元数据,包括权限、所有者、大小等。在访问文件数据时,inode 中的 i_data 字段指向数据块的地址,i_op 字段指向一组函数,这些函数定义了操作 inode 的方法。
- ext2_inode_info
- i_data[15]:指向文件数据块的指针数组。
- 作用:ext2_inode_info 是 inode 结构的一个具体实现,用于特定的文件系统类型(如 ext2/ext3/ext4 等)。i_data[15] 包含了文件数据块的指针(直接、间接、双重间接,三重间接指针)。
8.一个文件在使用与不用时各占用系统哪些资源?
文件未被使用时:
- 磁盘空间:inode、数据块、目录项。
文件被使用时: - 内存:文件描述符表、文件表项、目录项缓存、inode缓存;
- 内核数据结构;
- 缓存:页面缓存、缓冲区缓存;
9.安装表的作用是什么?
内核将安装点与被安装的⽂件系统信息保存在vfsmount结构中,形成⼀个链式安装表。
作用:
- 记录已挂载的文件系统;
- 路径名解析;
- 挂载和卸载操作;
- 文件系统操作的统一接口;
- 系统维护和状态监控。
第14章 Windows操作系统模型
1.Windows 采用什么样的体系结构?
分为用户态、核心态两部分。
- 用户态:系统与服务进程、应用程序(子系统DLL)、Windows子系统进程、Ntdll.dll;
- 核心态:执行体P267、内核、硬件抽象层、设备驱动程序、win32k.sys、NTFS.sys。
2.硬件抽象层HAL的作用是什么?
作用:直接操纵硬件。
3.Windows系统组件的基本机制包括:陷阱调度、执行体对象管理器、同步(自旋锁、内核调度程序对象)、本地过程调用LPC等。
Windouws的系统机制:
- 陷阱调度
- 属于内核的功能;
- 包括中断、DPC、APC、异常调度、系统服务调度。
- 执⾏体对象管理器
- 同步
- ⾃旋锁、内核调度程序对象。
- 本地过程调⽤LPC
- 在同⼀台计算机上实现客户进程和服务器进程之间的消息传递。
- 服务器创建⼀个LPC连接端⼝对象,然后在该端⼝上监听客户连接请求
- 类似socket编程
4.理解:延迟过程调用DPC,异步过程调用APC。
延迟过程调用DPC:
DPC被内核⽤来执⾏⼀些相对于当前⾼优先级的任务来说不那么紧急的任务;有时内核在进⾏系统嵌套调⽤时,检测到应该进⾏线程调度,为了保证调度的正确性,内核⽤DPC来延迟调度的产⽣。
异步过程调用APC:
- 每个线程都有⾃⼰的APC队列。 当⼀个线程被调度时,它的APC过程会⽴刻被执⾏。
- 两种APC:
- 核心态APC:可以中断线程,在线程被调度时⽴即执⾏,不需要得到线程的“允许”
- ⽤户态APC:需要得到线程的“允许”才能执⾏。如异步I/O,异步读取完成后调⽤回调函数(完成例程)是通过APC实现的。
5.Windows中有哪些对象,都有什么作用?
- 两种类型对象:执行体对象和内核对象。
- 执行体组件:进程和线程管理器、内存管理器、I/O管理器、对象管理器等。– 内核对象是由内核实现的一个初级对象集,对用户态代码不可见,仅供执行体使用。一个执行体对象可以包含一个或多个內核对象。
6.在多处理机系统中,提供了哪些同步和互斥机制?
- 内核引入自旋锁实现多处理机互斥机制。
- 内核以内核对象的形式给执行体提供其他的同步机构—“调度程序对象”,包括:进程对象、线程对象、事件对象、信号量对象、互斥体对象、可等待的定时器对象及文件对象等。
- 每个同步对象都有“有信号”或“无信号”两种状态。
7.如何实现等待一个同步对象的操作?
- 创建并初始化同步对象
- 等待同步对象
- 执行共享资源的操作
- 释放同步对象
- 销毁同步对象
第15章 Windows 进程和线程管理
1.管理进程和线程的数据结构:执行体进程块EPROCESS、执行体线程块ETHREAD、内核进程块KPROCESS、内核线程块KTHREAD。
执行体进程块EPROCESS:
- 内核进程块
- 进程的句柄表
- 页目录页面的页表项32位
- 进程的可执行映像文件名
- 指向可执行映像文件的区域对象
- 该区域的基地址
- 物理VAD树的根
- 进程工作集页面
- 位于进程私有地址空间的环境块
- 指向由Windows子系统管理的进程区域,
- 此值不为空,说明是GUI进程。
- 进程的优先级
- 线程链表
- 所有活动进程连接在一起
执行体线程块ETHREAD
- 线程的起始地址 等
内核进程块KPROCESS:
- 调度程序对象
- 页目录表的物理地址
- 基本优先级
执行体线程块KTHREAD
- 核心栈的栈指针
- 与调度和同步有关的信息(优先级、时间片、当前的状态、等待块列表等)
- 与本线程有关的APC列表
2.创建进程:CreateProcess();创建线程:CreateThread()
创建进程:
- 打开可执行文件(.exe),创建一个区域对象,建立可执行文件与虚拟内存之间的映射关系。
- 创建执行体进程对象EPROCESS。
- 创建一个主线程。
- 通知Win32子系统。对新进程和线程进行一系列初始化。
- 完成地址空间的初始化,开始执行程序。
创建线程:CreateThread() - 线程对象的服务
3.线程的7种状态,及其解释。
- 就绪状态
- 备用状态(standby)。已选好处理机,正等待描述表切换,以便进入运行状态
- 运行状态(Running)
- 等待状态(waiting)
- 传输状态(transition)。核心栈被调到外存的就绪态。
- 终止状态(terminated)
- 初始化状态(Initialized)。正在创建过程中。
4.线程调度:基于优先级的抢先式的多处理机调度系统。线程调度程序的数据结构:32个就绪线程队列、32位线程就绪队列位图、32位处理机空闲位图。
线程调度:基于优先级的抢先式的多处理器调度系统,优先级相同时按时间片轮转。、
线程调度程序的数据结构:
- 32个就绪队列:每个优先级对应一个。
- 32位掩码的就绪位图:一位指示一个优先级就绪队列中是否有线程等待运行。
- 32位掩码的空闲位图:每一位指示一个处理机是否处于空闲状态。
5.线程优先级的提升时机。
系统会提升线程的优先级,以改善性能
- I/O操作完成后的线程
- 信号量或事件等待结束的线程
- 前台进程中的线程完成一个等待操作
- 由于窗口活动而唤醒GUI线程
- 线程处于就绪状态超过一定时间,仍未能进入运行状态(处理器饥饿)
第16章 Windows 存储器管理
1.两种数据结构:虚拟地址描述符VAD、区域对象,这两种结构各有什么作用?
虚拟地址描述符VAD:
- 当线程要求分配一块连续虚存时,存储器管理器不立即为其构建页表
- 而是为它建立一个VAD结构
- 被分配的地址域起始、结束地址
- 该域是共享的还是私有的
- 该域的存取保护
- 该域是否可继承
- …
- 进程的VAD结构被构造成自平衡二叉树
区域对象: - 称为文件映射对象,是一个可被多个进程共享的存储区
- 一个区域对象可被多个进程打开
- 利用区域对象映射磁盘上的文件(包括页文件,可执行文件)
- 然后访问这个文件就象访问内存中的一个大数组,而不需要读/写操作
- 执行体、高速缓冲管理器、进程均可使用
2.虚拟内存区域:空闲的、保留的、提交的
进程私有2G地址空间的地址域可能是空闲的,被保留reserved,被提交committed。
- 空闲的:还没有被使用过
- 被保留:已预留虚存,还没分配物理主存
- 被提交:已分配物理主存或交换区
3.32位逻辑地址,二级页表。页目录表项和页表项具有相同的数据结构,该数据结构包含哪些数据项?进程页表建立的时机。进程的地址转换过程。
x86采用二级页表结构:页目录表、页表;
n页表和页目录表的结构相同;
数据项:大页位、修改位、访问位、页的写保护位、有效位等。
进程页表的构建:一直推迟到访问页时才建立。(“懒惰”方式)
进程的地址转换过程:
- 结构:页目录索引、页表索引、页内字节索引
- 利用页目录索引访问页目录表获取页表基地址。
- 利用页表索引访问页表获取物理帧地址。
- 物理帧地址 + 页内偏移 = 物理地址
4.管理物理内存的数据结构:页框数据库。页框的8种状态:活动、转换、备用、更改、更改不写入、空闲、零初始化、坏,页框的状态转换图16.9。
管理物理内存的数据结构:页框数据库是一个数组,其索引号从0到主存的页框总数-1。
页框的8种状态:
- 活动(有效):是进程工作集的一部分
- 转移 Transition:说明一个页框正处于I/O操作进行中
- 备用Standby:已不属于工作集,页表项仍然指向该页,但被标记为正在转移的无效PTE
- 更改Modified:已不属于工作集,修改未写磁盘,页表项仍指向该页,被标记为正在转移的无效PTE
- 更改不写入Modified no-write:更改但不写入磁盘
- 空闲 Free:不属于任何一个工作集
- 零初始化 Zeroed:清零的空闲页框
- 坏页框Bad:奇偶校验或其他硬件错误,不能再使用
状态转换图 提取码7568
5.原型页表,区域对象的页表。虚拟页式中,采用原型页表实现多进程共享页。
- 当一个页框被两个或多个进程共享时,存储器管理器依靠一个称为“原型页表”(Prototype PTE)的页表来记录这些被共享的页框;
- 区域对象有原型页表;
- 当进程访问区域对象中的页时,利用原型页表填写进程页表。
6.Windows采用的页替换策略是什么?
置换策略:
- 在多处理器系统中,采用了局部先进先出置换策略
- 在单处理器系统中,更接近于最近最久未使用策略(LRU,也称为“时钟页面置换算法”)
第17章 Windows 文件系统
1.Windows所支持的文件系统类型有哪些?
- FAT(FileAllocationTable)
- uNTFS(NewTechnologyFileSystem)
- uexFAT(ExtendedFileAllocationTableFileSystem)
2.虚拟簇号和逻辑簇号的概念。
虚拟簇号:通过VCN引用文件中的数据
逻辑簇号:
- 文件卷分成若干簇,并从卷头到卷尾进行编号
- 通过LCN引用文件在磁盘上的物理位置
3.NTFS卷的结构,主控文件表MFT的作用。
NTFS卷结构由三部分组成:
- 分区引导扇区PartitionBootSector:最多占16个扇区。包含卷的布局、文件系统结构以及引导代码等信息
- 主控文件表区MasterFileTable,MFT:是NTFS卷的管理控制中心,包含了卷上所有的文件、目录及空闲未用盘簇的管理信息
- 文件数据区:依次存放所有系统文件、MFT的镜像、根目录、普通文件和子目录及空闲簇
MFT的作用: - MFT是NTFS卷的管理控制核心
- MFT由若干个记录构成,记录的大小固定为1KB
- MFT仅供系统本身组织、架构文件系统使用,称为元数据(metadata)
- 每个记录描述一个文件或目录
- 记录:一个记录头+若干(属性,属性值)对
- 记录头包含用于有效性检查的魔数、文件生成时的顺序号、引用计数、记录中实际使用的字节数
- (属性,属性值)对如($FILE_NAME,A.C),($DATA,文件的具体内容)
- MFT中的前16个记录是为NTFS元数据文件保留的。
4.NTFS文件的物理结构:索引顺序结构。
5.对于大目录,采用B+树,使得查找一个特定文件的访盘次数减到最少。
大目录文件的索引根属性包含B+树的第一级并指向包含下一级的索引缓冲区。