本次上机还算中规中矩，能够完全理解题意后，写起来还是很顺手的。（实际上，根本读题的信息都读不全）

Exam - 时间查询与计算

题目背景

在 Lab5 与 Lab2 中，我们分别实现了不同种类外设的读写操作，现在我们需要实现一个能够获取当前物理时间的函数，和一个要求进程必须等待指定时间后才能运行的函数。现在我们介绍如何获取实时间。

GXemul 中除了磁盘 disk 还存在另一类外设——实时时钟 rtc (Real-Time Clock)，其中记录了 Unix 时间戳，即从格林威治时间 1970 年 01 月 01 日 00 时 00 分 00 秒起至现在的总秒数。为了进一步精确 Unix 时间戳， rtc 中还记录了一个微秒字段。

当我们需要读取 rtc 中存放的时钟的值时，需要先触发时钟更新，才能获取到正确的数据，未更新时首次读取默认是 0（别问我怎么知道的）

在 GXemul 的手册中我们能查阅到 rtc 的起始地址为 0x15000000，且不同偏移量下的读写效果如下：

偏移 效果 数据位宽
0x0000 读/写：触发时钟更新 4 bytes
0x0010 读：从格林威治时间 1970 年 01 月 01 日 00 时 00 分 00 秒起至现在的总秒数 4 bytes
0x0020 读：为精确 Unix 时间戳而记录的微秒数，范围为 0 到 999999 微秒（1秒内） 4 bytes

题目要求

本题需要完成两个用户态中的函数，并要求在 user/include/lib.h 中声明，user/lib/ipc.c 中实现

  1. u_int get_time(u_int *us)

从 rtc 中读取总秒数和微秒数，总秒数作为该函数的返回值，微秒数通过指针参数 us 返回。

  1. void usleep(u_int us)

在任一用户态进程进入 usleep 函数后，必须停留 us 微秒后才能退出函数。这其中允许时间片的轮转，也就是说在等待调度的过程中仍然计时

  • 请避免单位换算时可能发生的整数溢出
  • u_int 为无符号整数，如果需要进行减法得到有符号整数，请在运算前使用 (int) 进行强制类型转换
  • 课程组给出的一种 usleep 的实现：
void usleep(u_int us) {
	// 读取进程进入 usleep 函数的时间
	while (1) {
		// 读取当前时间
		if (/* 当前时间 >= 进入时间 + us 微秒*/) {
			return;
		} else {
			// 进程切换
		}
	}
}

一种可行的做法

  • ipc.c
u_int get_time(u_int *us) { return syscall_get_time(us); }

void usleep(u_int us) {
  u_int inUs = 0;
  u_int nowUs = 0;
  u_int inTime = get_time(&inUs);

  while (1) {
    u_int nowTime = get_time(&nowUs);
    int del = (int)nowTime - (int)inTime;

    if (del * 1000000 + ((int)nowUs - (int)inUs) > us) {
      return;
    } else {
      syscall_yield();
    }
  }
}
  • syscall_all.c：增加了一个系统调用，用于直接访问用户态无权访问的 KSEG1 段内存
u_int sys_get_time(u_int *us) {
  u_int time = 0;
  memcpy(&time, (KSEG1 + 0x15000000), sizeof(u_int));  // flush rtc to get correct time
  memcpy(&time, (KSEG1 + 0x15000010), sizeof(u_int));  // store time in 'time'
  memcpy(us, (KSEG1 + 0x15000020), sizeof(u_int));     // store utime in 'us'

  return time;
}

以上。

思考

其实读取时间的那部分还蛮简单的，直接写系统调用进入内核态，再向 KSEG1 区用 memcpy 就能实现读外设。真正能卡人的部分在时间比较上。哦，还有人忘了更新时钟

关于时间比较上，群友们提供了以下几种可行的方法：

  1. u_int 溢出？我直接上 long long！

直接用 long long 类型存储时间，这样在 秒 → 微秒 的换算上就能避免溢出的问题，直接就能比较

  1. 我是守序善良者，我要选用合理的方法处理溢出

先获取微秒，再计算时间差就会溢出，那我先把大单位的秒相减，再移动不就溢出不了了？也就是先进行秒相减，随后再换算成微秒单位进行比较。在这个基础上还有混乱善良者，让（秒 - 秒）、（微秒 - 微秒），最后再换算相加作比较，实际上是一个意思

  1. 无所谓，我会 % 100

还有一些同学对大单位的秒进行了取模运算，实际上这并不安全，有可能两次比较的时间的后三位分别跨在 100 这个线两边，然后相减可能就出锅了。不过没关系，我们的测评很宽松，而且这种看脸的几率也很小，因为题目要求 us 大小上小于 5 秒

Extra - SSD 硬盘模拟

题目背景

在 MOS 的实现中，我们使用的是 GXemul 提供的 IDE 磁盘作为外挂的文件存储。现在我们使用固态硬盘 SSD 的概念对 IDE 磁盘进行模拟，即按照操作 SSD 的方法去操作我们的磁盘。

SSD 的特点是每个块存储数据后必须先擦除才能写入。同时闪存块是有擦写次数上限的，为了平衡各个块的擦写次数，SSD 引入了磨损平衡机制。我们在本次模拟过程中规定，模拟 SSD 的读、写、擦除均以块为单位，每块的大小都是 512 Bytes；且对于每个物理块，必须先擦除，才能写入数据。

我们定义如下几个概念：

逻辑块号：文件系统读写的逻辑硬盘块编号，在物理上不一定连续，每个块的大小为512Bytes

物理块号：SSD实际读写的闪存的物理编号，在物理上连续，每个块的大小都是512Bytes

闪存映射表：记录逻辑块号对应物理块号信息的表

物理块位图：记录各个物理块的状态信息

实际上，我们要先实现一个逻辑硬盘块到物理硬盘块的映射表，同时维护每个物理块的使用情况与擦除次数。并根据这些信息模拟正常的 SSD 工作流程。

首先说明，外界访问 SSD 时使用的是其逻辑块号，我们需要经闪存映射表获得其物理块号后，在 IDE 磁盘的对应扇区执行相关操作。

我们先规定 SSD 硬盘可能出现的四种操作：

  1. 初始化硬盘：清空闪存映射表，在物理块位图中将SSD的所有物理块初始化为可写状态，SSD各物理块的累计擦写次数清 0。（保证只在开始时调用一次）
  2. 读取逻辑块：查询闪存映射表，找到逻辑块号对应的表项。如果为空，则返回 -1 ；若不为空，就去读取对应的物理块，返回物理块内的数据，并返回 0。
  3. 写入逻辑块：查询闪存映射表，找到逻辑块号对应的表项。若为空（初次写），则分配一个可写的物理块，在闪存映射 表中填入此映射关系，将数据写入该物理块，并标记此物理块为不可写；若不为空（覆盖写），则擦除原来的物理块并清除该逻辑块号的映射，并按相同方法分配一 个物理块向其写入数据。
  4. 擦除逻辑块：查询闪存映射表，找到逻辑块号对应的表项。若为空，不做处理；若不为空，则将对应的物理块擦除（擦除表示将物理块数据全部清 0，下同）并清除此映射关系。

为了描述上面需要的状态，我们需要在代码中定义如下数据结构：

  • 闪存映射表：记录逻辑块号对应物理块号信息的表
  • 物理块位图：记录各个物理块是否可写。每次向可写的物理块中写入数据后，都需要标记物理块为不可写
  • 物理块累计擦除次数表：记录各个物理块的累计擦除次数

在完成上述基础机制后，我们还需要实现一个简单实现磨损平衡的分配函数，在这里就不展开逻辑了。

题目要求

在本题中，你需要使用IDE 0号硬盘（diskno = 0）的第0~31个扇区来模拟SSD的第0~31个物理块，之后根据 题目描述部分 的描述，在 fs/ide.c 中实现下列函数：

1. 初始化硬盘：

void ssd_init();
  • 功能：初始化闪存映射表、物理块位图、物理块累计擦除次数表。

2. 读取逻辑块：

int ssd_read(u_int logic_no, void *dst);
  • logic_no：逻辑块号
  • dst: 硬盘数据要加载到的内存地址
  • 功能：读取逻辑块 logic_no 的数据到 dst，成功返回 0，失败返回 -1

3. 写入逻辑块：

void ssd_write(u_int logic_no, void *src);
  • logic_no：逻辑块号
  • src: 要写入到硬盘中的数据的起始内存地址
  • 功能：向逻辑块号对应的硬盘块写入以 src 为起始地址的512字节数据

4. 擦除逻辑块

void ssd_erase(u_int logic_no);
  • logic_no：逻辑块号
  • 功能：擦除逻辑块 logic_no 上的数据，并取消 logic_no 到物理块号的映射关系

评测时将会调用上面的接口做一系列操作，验证操作执行结果是否正确，并会在操作的任何阶段读取硬盘数据以检查实现的正确与否。

为了实现上面的函数，你可能还需要自行实现以下两个函数，但我们不对函数的定义做具体要求：

  • 擦除物理块：将全 0 的数据写入到物理块中，物理块累计擦除次数加一，并置为可写状态
  • 分配新物理块：按“题目描述”部分的方法分配，需要用到物理块位图和物理块累计擦除次数两个信息

一种可行的做法

其实闪存映射表直接用一维的数组就足够了，下标代表逻辑号，内容代表物理号，无所谓，写完了才意识到。

首先按照合适的逻辑规定好数据结构：

u_int ssd_bitmap[32];    // 标记物理块是否可用，1 = free, 0 = using
u_int ssd_cleanmap[32];  // 标记物理第 i 块的擦除次数
u_int ssd_logic[32];     // 映射表中第 i 项映射的逻辑块号
u_int ssd_physics[32];   // 映射表中第 i 项映射的物理块号

然后顺手写好初始化函数：

ssd_init

初始化标记可用的位图，闪存映射表。

擦除次数默认为 0，又写成了全局变量，所以直接跳过初始化。注意不要让映射表不存在映射时保存 0，否则可能会识别为第 0 块存在的某个映射，这里按照课程组建议写了 0xffffffff

void ssd_init() {
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        ssd_bitmap[ssdno] = 1;
        ssd_physics[ssdno] = (u_int)0xffffffff;
        ssd_logic[ssdno]   = (u_int)0xffffffff;
    }
}

随后可以先实现比较简单的读函数，因为它不需要检查/改变硬盘块状态

ssd_read

为了给这个蹩脚的数据结构一些便利，我自己又写了个获取映射块的函数，多此一举。

注意下真正的读取函数还是 ide_read，要注意读取的扇区号和大小，其他的比较简单

int ssd_read(u_int logic_no, void *dst) {
    u_int physics_no = get_physics(logic_no);
    if (physics_no == (u_int)0xffffffff) { return -1; }

    ide_read(0, physics_no, dst, 1);

    return 0;
}

然后是两个比较复杂的操作，我的建议是先写擦除的函数，因为写之前免不了要进行擦除

ssd_erase

这里又写了一个专门擦除的 erase 函数，没什么实际意义，需要注意别忘了消除原有的映射。同时，当且仅当磁盘块在进行擦除时（erase 函数）会发生 cleanmap 数组值的变化，其他地方就不要写这个数组了。

void ssd_erase(u_int logic_no) {
    u_int physics_no = get_physics(logic_no);
    if (physics_no == (u_int)0xffffffff) { return; }

    // 查找映射，并使用 erase 函数擦除物理块，同时消除映射
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        if (ssd_logic[ssdno] == logic_no) {
            erase(ssd_physics[ssdno]);
            ssd_logic[ssdno] = (u_int)0xffffffff;
            ssd_physics[ssdno] = (u_int)0xffffffff;
        }
    }
    return;
}
void erase(u_int physics_no) {
    char buf[512];
    ssd_cleanmap[physics_no]++;  // 擦除次数 + 1
    ssd_bitmap[physics_no] = 1;  // 擦除后标记为可用块
    for (int i = 0; i < 512; i++) {
        buf[i] = 0;
    }
    ide_write(0, physics_no, buf, 1);  // 使用 ide_write 进行实际的 '擦除' 工作
}

最后是相对最复杂的写操作。因为这个函数中，不仅要完成写操作，主要是在写之前需要分配物理块，这其中的重点是实现磨损平衡的分配函数。

首先讲讲磨损平衡的实现方法：

  1. 在低负荷状态下，我们优先选取擦除次数最少的、当前状态为可用的（ssd_bitmap[i] = 1）磁盘块（若同次数选物理块号小的），并将其返回，直接结束
  2. 在高负荷状态下，即当前可用块最小擦除次数大于等于 5，此时就需要考虑非可用块了（避免长期驻留的数据影响块的擦除数）。首先按照和第一步相同的逻辑，选出非可用块中擦除次数最少的块。随后我们进行一个简单的内容替换：

将选出的非可用块包含的内容转存到选出的可用块中，这也包含将映射到该物理块的闪存表项同时更改；同时擦除非可用块，并进行分配。（有点像 Lab2 Extra 那味了）

总结一下，高负荷状态下需要：

  1. 将原可用块状态标记为不可写
  2. 更新替换块的原有映射
  3. 复制替换块的内容到原可用块中
  4. 对替换块执行一次擦除操作，标记为可用

alloc_physics

这个函数写的很臃肿，而且废话很多，怎么说呢，能跑就行（

u_int alloc_physics() {
    u_int target_no   = 1000;  // 低负荷下选出的可用块
    u_int erase_time  = 1000;  // 标记最少擦除次数
    u_int exchange_no = 1000;  // 高负荷下选出的替换块

    char buf[512];             // 用作转存时使用的中介

    /* Step 1: 根据选择逻辑获得擦除最少的可用物理块块号和擦除次数 */
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        if (ssd_cleanmap[ssdno] < erase_time && ssd_bitmap[ssdno] == 1) {
            target_no = ssdno;
            erase_time = ssd_cleanmap[ssdno];
        }
    }

    /* Step 2: 低负荷状态可以直接结束函数，同时恭喜你拿到了 80 分 */
    if (erase_time < 5) { return target_no; }

    /* Step 3: 高负荷状态下，按照选择逻辑再次获得替换块*/
    erase_time = 1000;
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        if (ssd_bitmap[ssdno] == 0 && ssd_cleanmap[ssdno] < erase_time) {
            exchange_no = ssdno;
            erase_time = ssd_cleanmap[ssdno];
        }
    }

    /* Step 4: 初始化转存的区域，不写也行 */
    for (int i = 0; i < 512; i++) { buf[i] = 0; }

    /* Step 5: 替换块擦除，做出提到的相应更新 */
    ssd_bitmap[target_no] = 0;                   // 1.
    for (int ssdno = 0; ssdno < 32; ssdno++) {   // 2.
        if (ssd_physics[ssdno] == exchange_no) {
            ssd_physics[ssdno] = target_no;
        }
    }
    ide_read(0, exchange_no, buf, 1);            // 3.
    ide_write(0, target_no, buf, 1);
    ssd_cleanmap[exchange_no]++;                 // 4.
   
    return exchange_no;
}
  • Step 5 里完全忘记用 erase 函数了，无所谓
  • 第一次写的时候，到后面逻辑就乱了，直接把 可用块 的内容复制给 替换块 了，导致最后一个高负荷的点跑不出来

ssd_write

实现分配逻辑函数后，写入就变得很简单了

void ssd_write(u_int logic_no, void *src) {
    u_int physics_no = (u_int)0xffffffff;
    
    /* Step 1: 先擦除原有物理块，销毁映射 */
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        if (ssd_logic[ssdno] == logic_no) {
            physics_no = ssd_physics[ssdno];
            if (physics_no != (u_int)0xffffffff) {
                ssd_erase(logic_no);
            }
        }
    }
    
    /* Step 2: 根据分配逻辑申请一个新物理块，同时新建映射，标记使用情况 */
    u_int save_no = alloc_physics();
    ssd_bitmap[save_no] = 0;
    // debugf("alloc physics %d\n", save_no);
    for (int ssdno = 0; ssdno < 32; ssdno++) {
        if (ssd_logic[ssdno] == (u_int)0xffffffff) {
            ssd_logic[ssdno] = logic_no;
            ssd_physics[ssdno] = save_no;
            break;
        }
    }
    
    /* Step 3: 最后进行写入的操作 */
    ide_write(0, save_no, src, 1);
}

思考

其实说到底，最后实现的核心就是模拟，说是模拟 SSD 硬盘，但实际上完成的内容又和之前的页表映射有点像。 Lab2 Extra 要求实现的换入换出，到这里就变成了写磁盘读磁盘。不过之前 Extra 并没有限制换页的分配函数，这次却着重写了这个分配的逻辑，只能说侧重点不同吧。

这次 Extra 里数据结构的选取也相对关键，比如标记使用情况的结构就选用了 bitmap（虽然当成 intmap 来用了，不过总归还是位图）；但标记映射实际上应该用个一维数组就够了，我仓皇之中选用的结构给之后写代码无形中增添了很多负担（主要是每次查都要遍历)。没关系，能跑就行下次一定

最后附一张课上的疯狂涂鸦，也许能提供一些结构上的思路，等告一段落之后再换成能看的图罢：

image-20230516004219883