Apr

OS:lab3实验报告 Thinking 3.1 请结合 MOS 中的页目录自映射应用解释代码中 e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_V 的含义。 UVPT是用户地址空间中页表项的起始地址 结合页目录自映射我们知道，只要给定了二级页表项的起始地址，我们就能通过自映射机制计算出页目录的起始虚拟地址 UVPT为二级页表基地址 则页目录基地址为$UVPT + (UVPT»12)*4 = UVPT+UVPT»10$ 映射到页目录的页表项的地址为$UVPT + ((UVPT+UVPT»10)»12)*4 = UVPT + UVPT»10 + UVPT»20$ 该项相对于页目录的index：或者说该项相对于页目录的地址偏移为$UVPT»20$，对应的偏移量为UVPT»22，即为PDX(UVPT) PDX(UVPT)可以得到二级页表起始虚拟地址UVPT的页目录号 e->env_pgdir[PDX(UVPT)]即为指向页目录中指向页目录自身的页目录项 PADDR(e->env_pgdir)得到页目录的物理地址并赋予有效位PTE_V Thinking 3.2 elf_load_seg 以函数指针的形式，接受外部自定义的回调函数 map_page。请你找到与之相关的 data 这一参数在此处的来源，并思考它的作用。没有这个参数可不可以？为什么？ data是传入的进程控制块指针 作用：在增加虚拟地址到物理地址的映射时提供当前进程地址空间的页目录基地址pg_dir和asid(load_icode_mapper)，所有这个参数是必要的 Thinking 3.3 结合 elf_load_seg 的参数和实现，考虑该函数需要处理哪些页面加载的情况 elf_load_seg函数的实现(elfloader.c) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 int elf_load_seg(Elf32_Phdr *ph, const void *bin, elf_mapper_t map_page, void *data) { u_long va = ph->p_vaddr; size_t bin_size = ph->p_filesz; size_t sgsize = ph->p_memsz; u_int perm = PTE_V; if (ph->p_flags & PF_W) { perm |= PTE_D; } int r; size_t i; u_long offset = va - ROUNDDOWN(va, PAGE_SIZE); if (offset != 0) { if ((r = map_page(data, va, offset, perm, bin, MIN(bin_size, PAGE_SIZE - offset))) != 0) { return r; } } /* Step 1: load all content of bin into memory. */ for (i = offset ? MIN(bin_size, PAGE_SIZE - offset) : 0; i < bin_size; i += PAGE_SIZE) { if ((r = map_page(data, va + i, 0, perm, bin + i, MIN(bin_size - i, PAGE_SIZE))) != 0) { return r; } } /* Step 2: alloc pages to reach `sgsize` when `bin_size` < `sgsize`. */ while (i < sgsize) { if ((r = map_page(data, va + i, 0, perm, NULL, MIN(sgsize - i, PAGE_SIZE))) != 0) { return r; } i += PAGE_SIZE; } return 0; } ...

OS理论期中考试复习 一.引论 1. 操作系统定义 操作系统是一组管理计算机硬件资源的软件集合，他向计算机程序提供共性的服务 2. 操作系统发展史 电子管时期：软件：手工修改硬件逻辑单元连接 解决人和CPU的矛盾：软件和硬件分离 2.1 批处理系统 加载在计算机上的一个系统软件，在他的控制下，计算机能够自动地、成批地处理一个或多个用户的作业 用户将一批作业提交给操作系统后就不再干预 2.1.1 联机批处理系统 在主机和输入机之间增加一个存储设备——磁带，在运行于主机的监督程序(OS)的自动控制下，计算机可自动完成：成批地把输入机上的用户作业读入磁带，依次把磁带上的用户作业读入主机内存并执行，然后把计算结果向输出机输出。完成了上一批作业后，监督程序又从输入机上输入另一批作业，保存在磁带上，重复处理 优点：监督程序不停地处理各个作业，实现了作业到作业的自动转接，减少了作业建立时间和手工操作时间，克服了人机矛盾。 缺点：CPU与慢速的外设之间的矛盾：在作业输入和结果输出时，主机的高速CPU需要等待慢速的输入输出设备完成工作，主机处于“忙等”状态 2.1.2 脱机批处理系统 增加一台不与初级直接相连而是与输入输出设备打交道的卫星机 优点：主机不直接与慢速的输入输出设备打交道，而是与速度相对较快的磁带机发生关系，主机与卫星机并行工作，发挥主机的高速计算能力 缺点：主机内存中仅存放一道作业，每当该作业运行期间发生输入输出请求后，高速的CPU便处于等待低速的IO完成状态，COU空闲 2.2 多道程序系统 多道程序设计技术，指允许多个程序同时进入内存并运行。即同时把多个程序放入内存中，并允许他们交替在CPU中运行，共享系统中的各种硬软件资源 当一道程序因为IO请求而暂停运行时，CPU便立即转去运行另一道程序，不同程序间的切换运行 使CPU得到充分利用,同时改善IO设备和内存的利用率，提高整个系统的资源利用率和系统吞吐量 宏观上并行：进入系统的几道程序都处于运行过程中，都开始了各自的运行，但都未运行完毕 微观上串行：各道程序轮流地使用CPU，并交替运行 2.3 单道程序系统 内存中只有一道程序，存在计算时IO设备空闲或进行IO操作时CPU空闲 2.4 多道批处理系统 多道：系统内可同时容纳多个作业 成批：在系统运行过程中，不允许用户与其作业发生交互 优点：系统吞吐量大，资源利用率高 缺点：平均周转时间长，单个用户不能交互，多用户使用和单独控制的矛盾 2.5 分时系统 分时技术：把处理机的运行时间分成很短的时间片，按时间片轮流把CPU分配给各联机作业/程序使用，给不同的用户提供程序的使用 一台计算机同时连接多个用户终端 特点 多路性：宏观上看多个用户并行工作，微观上看是各用户轮流使用计算机 交互性：用户可以根据系统对请求的响应结果，进一步向系统提出新的请求(交互式系统) 独立性：用户之间相互独立，互不干扰 及时性：系统对用户的输入及时作出响应 2.6 网络操作系统 传统单机OS上加单独软件层，提供联网功能和资源的远程访问，多机互联 2.7 分布式操作系统 多台机器统一管理形成单一系统 2.8 实时系统 在某个时间限制内及时完成某些及时任务不需要时间片排队 3. 操作系统的基本实现机制 用户态和内核态 用户态和内核态所在的内存空间不一样 CPU的运行状态不一样 指令的执行权限不一样 从用户态转入内核态 ...

OS第三次理论作业 一.第一题 (1) 答 32位虚拟地址空间，故整个的地址空间大小为4GB；页内偏移量为12位，故一页有4096字节 (2) 答 考察了二级页表的自映射机制，第一级页表所在的逻辑地址即为第一级页表中第一个页表项的逻辑地址，第一个页表项映射到第一个二级页表，第一个二级页表对应的虚拟页号为$0x80000000 » 12 = 0x00080000$，故该页表项为第$0x0008000$个页表项，相对于页表项起始地址的偏移量为$0x00080000 * 4$，故对应的逻辑地址为$PT_{base} + (PT_{base} «12) *4 = 0x80200000$ (3) 答 逻辑地址0x0：访问逻辑地址0x0时，对应的页目录偏移量为0，对应的有效位为0，引发了缺页中断，需要进行重填 逻辑地址0x00803004：访问逻辑地址0x00803004时，对应的页目录偏移量为2，有效位为1，对应的物理地址为0x5000，逻辑地址对应的二级页表偏移量为3，对应的页表项有效位为1，对应的物理地址为0x20000，页内偏移量为4字节， 若系统为小端存储(数据的低字节放在低地址空间，大小端的顺序是以字节为单位的，而不是bit)，则数据排布为0000_9000,0032_6001,则访问到的数据为0x1 若系统为大端存储(数据的高字节放在低地址空间)，则数据排布为0090_0000,0160_3200,则访问到的数据为0x0 逻辑地址0x00402001：访问逻辑地址0x00402001时，对应的页目录偏移量为1，有效位为1，对应的物理地址为0x1000，逻辑地址对应的二级页表偏移量为2，对应的页表项有效位为1，对应的物理地址为0x5000，页内偏移量为1字节，访问到的数据为0x0 (4) 答 ​ 要想访问物理地址0x326028，先看他的物理页号，物理页号为$0x326028 » 12 = 0x326000$则对应起始物理地址为0x20000页表中偏移量为1的项，对应页目录中偏移量为3的页表项的映射，页内偏移量为$0x28$，故逻辑地址为$0x00c01028$ 二.第二题 前提：LOAD STORE操作的均为虚拟地址 大尾端为将数据的高位存在低地址端 0000430: e684 6c4e 0100 1800 53ef 0100 0100 0000 0000440: b484 6c4e 004e ed00 0000 0000 0100 0000 在大端模式下，前32位应该这样读: e6 84 6c 4e 在小端模式下，前32位应该这样读: 4e 6c 84 e6 ...

OO第二单元第三次作业 [toc] 0.本次作业新增需求 新增一种RESET请求，可以将单部电梯重置为双轿电梯 [时间戳]RESET_ACCEPT-电梯ID-换乘楼层-每个轿厢的满载人数-每个轿厢移动一层的时间(单位s) 重置电梯两个轿厢的参数相同（满载人数、移动一层的时间） 重置完成后轿厢A默认在换乘楼层的下一层，轿厢B默认在换乘楼层的上一层 轿厢A只能在换乘楼层及以下运行，轿厢B只能在换乘楼层及以上运行 两个轿厢不能同时处于换乘楼层 特别地，双轿厢电梯可以不受RECEIVE约束地从换乘楼层移动一层以离开换乘楼层 保证双轿厢电梯不会接收到第一类重置请求和第二类重置请求。 换乘楼层在3层和9层之间 双轿厢电梯耗电量为$\frac 1 4$ 1.处理流程分析 ​ 本次作业中主要的任务即为处理新增的RESET请求，对于上次作业已有的调度策略没有进行改变，目标比较明确。下面是时序图 1.1 UML时序图 1.2 新增RESET请求的处理 1.2.1 Elevator ​ 本次作业中对于双轿厢RESET请求的类协作与第二次作业中普通重置请求相同。这里我对于RESET请求的处理方式是接收到双轿厢RESET请求时新建一个线程，将原来的线程作为A轿厢，新建的电梯线程作为B轿厢。这里首先给出电梯新增的几个属性 1 2 3 4 5 6 7 //Elevator private char elevatorType = 'C'; // 轿厢类型 A B private int transferFloor = -1; private int lowerLimit = 1; private int upperLimit = 11; private Flag busyFlag = null; // 一组电梯共享一个flag进行通信 private AtomicInteger personSatisfied; elevatorType：电梯的类型，初始时电梯的类型为C类型，双轿厢重置后修改为A/B类型 lowerlimit/upperlimit：电梯的运行楼层限制，用于Dispatcher中对于符合运行范围电梯的筛选 transferFloor：换乘楼层(似乎没用，不是lowerlimit就是upperlimit) busyFlag：用于控制双轿厢电梯在换乘楼层互斥的需求，这里借鉴了讨论区中实现线程安全类的思路 personSatisfied：计数器，所有电梯线程和输入线程的共享变量，当一个乘客需求被满足(送到指定楼层)，该原子类型+1 ​ 参考NormalReset在第二次作业中的实现方式，DoubleCarReset我选择相同的实现方法，当电梯拿到DoubleCarReset请求之后立即进行重置 ...

OO第二单元第二次作业 [toc] 0.题目新增需求 乘客不再固定电梯接送，设计电梯调度策略 增加RECEIVE输出，避免自由竞争策略 增加RESET请求，时长1.2s，在RESET期间电梯处于静默状态(不可以开关门、移动、RECEIVE等)，重置电梯 1.处理流程分析 1.1 电梯调度策略 ​ 在本次作业中，需要设计将乘客分配给合适的电梯的调度器(补第五次作业偷的懒)，我的设计中选择将调度器作为一个线程实现，输入线程与调度器线程交互，调度器线程与六个电梯线程交互。对于单个电梯运行的策略我保留了第五次作业的LOOK算法，对于多部电梯的分配策略，我选择了性价比较高的调参方法，性价比体现在代码量较少的同时能够拿到比较好的性能分数。UML时序图如下 1.1.1 UML时序图 1.1.2 调参算法 ​ 所谓调参算法其实就是选取几个有关电梯的指标，给这些指标赋予合适的参数，为每部电梯计算出得分，选择得分最高的电梯进行分配。我选取的指标有电梯接到该乘客需要走的距离，电梯中人数，电梯等待队列中人数，电梯容量，电梯速度。 距离：这里距离的计算是不准确的，没有找出电梯运行的上确界或下确界，即没有找出电梯运行到哪里就可以转向，而是同一按照1/11处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private int getDistance(int fromFloor,int toFloor,int curFloor,boolean direction) { int distance = 0; int flow = (direction) ? 1 : -1; if ((toFloor - fromFloor) * flow > 0) { // 乘客移动方向与电梯当前移动方向相同 if ((fromFloor - curFloor) * flow >= 0) { // 电梯沿当前方向能接到乘客 distance = abs(fromFloor - curFloor); } else { if (flow == 1) { distance = 20 - curFloor + fromFloor; } else { distance = 20 + curFloor - fromFloor; } } } else { if (flow == 1) { distance = 22 - curFloor - fromFloor; } else { distance = curFloor + fromFloor - 2; } } return distance; } 电梯状态：电梯状态这个参数实际上是电梯容量、电梯中人数、电梯等待队列中人数三个量经过调参得来的，可以适当增加电梯等待队列中人数的权重，避免给一部性能好的电梯分配太多乘客，这样的性能可能还不如大家都运行 ...

OS:lab3课下基础 1.进程 由于没有实现线程，本实验中进程既是基本的分配单元，也是基本的执行单元 1.1 进程控制块 ​ 进程控制块(Process Control Block)是用来管理进程的数据结构，可以记录进程的变化过程，记录进程的外部特征。PCB是系统感知进程存在的唯一标志，进程与PCB是一一对应的。在MOS中，PCB定义为一个Env结构体 1 2 3 4 5 6 7 8 9 10 11 struct Env { struct Trapframe env_tf; // saved context (registers) before switching LIST_ENTRY(Env) env_link; // intrusive entry in 'env_free_list' u_int env_id; // unique environment identifier u_int env_asid; // ASID of this env u_int env_parent_id; // env_id of this env's parent u_int env_status; // status of this env Pde *env_pgdir; // page directory TAILQ_ENTRY(Env) env_sched_link; // intrusive entry in 'env_sched_list' u_int env_pri; // schedule priority }; env_tf : 在发生进程调度，或当陷入内核时，会将当时的进程上下文环境保存在env_tf变量中 ...