前言：操作系统系列实验的blog比较抽象，如有需要可以直接去搬我上传的项目直接用
毕竟这几篇都是汇报检查是我打的草稿，内容很乱
链接如下：
可运行项目文件直达
注意：
这几个项目无需求直接 boch 运行即可，make编译报错解决方案如下
该项目是可以直接运行的，不用麦克编译，如果你编译报错并且弹出gcc和一个路径字样说明是gcc版本问题
如图：project3make报错解决
（系统里那个路径下自带的是4.4和4.4.3的gcc），而这个项目太老运行需要3.4.6的（更新降级又太麻烦），这里介绍一个简单的方法。
1 | sudo -i |
project3
（基于project2的）
概览
(1)实现src/geekos/syscall.c文件中的Sys_SetSchedulingPolicy系统调用，它的功能是设置系统采用的何种进程调度策略；
(2)实现geekos/syscall.c文件中的Sys_GetTimeOfDaysrc/系统调用，它的功能是获取全局变量g_numTicks的值；
(3)实现函数Change_Scheduling_Policy()，具体实现不同调度算法的转换。
(4)实现syscall.c中信号量有关的四个系统调用：sys_createsemaphore( )、sys_P( )、sys_V( )和sys_destroysemaphore( )。
前三个要求都是关于多级反馈调度策略的，第一个是设置，第三个是转换，第二个用来评估；第四个要求是有关信号量操作。
逐步实现
线程调度的优化
1. 实现Sys_SetSchedulingPolicy函数：
- 该函数的功能是设置系统采用的何种进程调度策略；2.
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/*
* Set the scheduling policy. // 设置调度策略
* Params:
* state->ebx - policy,// 调度策略
* state->ecx - number of ticks in quantum// 时间片长度
* Returns: 0 if successful, -1 otherwise// 成功返回0，否则返回-1
*/
static int Sys_SetSchedulingPolicy(struct Interrupt_State* state)
{
/* 如果输入的优先级调度方法参数无效(非 0 或 1)则返回错误 */
if (state->ebx != ROUND_ROBIN && state->ebx != MULTILEVEL_FEEDBACK)
{
Print("Error! Scheduling Policy should be RR or MLF\n");
return -1;
}
/* 如果输入的时间片参数不在[1, 100]之间则返回错误 */
if (state->ecx < 1 || state->ecx > 100)
{
Print("Error! Quantum should be in the range of [1, 100]\n");
return -1;
}
int res = Chang_Scheduling_Policy(state->ebx, state->ecx);
// 调用Chang_Scheduling_Policy函数，设置调度策略
return res;
}
/*
参数state是一个结构体，其中，state->ebx成员用于指定调度策略，值为0代表系统采用时间片轮转调度策略，值为1则代表系统采用四级反馈队列调度策略，若取其他值则出*错。state->ecx成员用于记录相应调度策略下的时间片长度。
*/Sys_GetTimeOfDay系统调用： - 该函数的功能是获取全局变量
g_numTicks的值； g_numTicks: 用于记录系统运行的时间，每次时钟中断处理函数Time_Interrupt_Handle被调用时，g_numTicks的值加1；1
2
3
4
5static int Sys_GetTimeOfDay(struct Interrupt_State* state)
{
/* 直接返回全局变量 g_numTicks 的值 */
return g_numTicks;
}
3.Change_Scheduling_Policy()函数：
- 该函数的功能是修改线程队列及系统相关变量，主要是
g_curSchedulingPolicy为当前调度策略，g_Quantum为时间片长度；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
37
38int Chang_Scheduling_Policy(int policy, int quantum)
{
/* 如果调度策略不同，则修改线程队列 */
if (policy != g_curSchedulingPolicy)
{
/* MLF -> RR */
if (policy == ROUND_ROBIN)
{
/* 从最后一个线程队列(此处为 Q3)开始将其中的所有线程依次移动到前一个队列，
直到所有线程都移动到 Q0 队列 */
int i;
for (i = MAX_QUEUE_LEVEL - 1; i > 0; i--)
Append_Thread_Queue(&s_runQueue[i - 1], &s_runQueue[i]);
}
/* RR -> MLF */
else{
/* 判断 Idle(空闲)线程是否在 Q0 队列 */
if (Is_Member_Of_Thread_Queue(&s_runQueue[0], IdleThread))
{
/* 将 Idle 线程从 Q0 队列移出 */
Remove_Thread(&s_runQueue[0], IdleThread);
/* 将 Idle 线程加入到最后一个队列(此处为 Q3) */
Enqueue_Thread(&s_runQueue[MAX_QUEUE_LEVEL - 1], IdleThread);
}
}
/* 保存原来的调度策略 */
g_preSchedulingPolicy = g_curSchedulingPolicy;
/* 将全局变量设置为对应的输入值 */
g_curSchedulingPolicy = policy;
Print("g_schedulingPolicy = %d\n", g_curSchedulingPolicy);
}
g_Quantum = quantum;// 设置时间片长度
Print("g_Quantum = %d\n", g_Quantum);
return 0;
}
信号量操作：
线程同步与互斥部分内容
Semaphore_Create( )
Semaphore_Acquire（P操作）
Semaphore_Release（V操作）
Semaphore_Destroy( )
皆在src/geekos/syscall.c中实现
Create_Semaphore（）函数首先检查请求创建的这个信号量的名字是否存在.
- 如果存在，那么就把这个线程加入到这个信号量所注册的线程链表上；
- 如果不存在，则分配内存给新的信号量，清空它的线程队列，把当前的这个线程加入到它的线程队列中，设置注册线程数量为1，初始化信号量的名字，值和信号量的ID，并把这个信号量添加到信号量链表上，最后返回信号量的ID。
P操作Semaphore_Acquire（）中，首先检查传入的信号量ID是否存在
- 如果存在，接着检查当前线程是否注册使用了这个信号量，
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，就把信号量的值减去1，
- 如果减去1后信号量的值小于0，那么就把当前线程放入这个信号量的等待队列上。
V操作Semaphore_Release（）中，首先也是检查传入的信号量ID是否存在，
- 如果存在，接着检查当前线程是否注册使用了这个信号量，
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，那就把信号量的值加上1，
- 如果加上1后信号量的值小于或等于0，则要把该信号量里等待队列上的一个线程唤醒。
Semaphore_Destroy（）中，首先也是检查传入的信号量ID是否存在，
- 如果存在，接着检查当前线程是否注册使用了这个信号量。
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，就把该线程从这个信号量的注册的线程数组中删除，并把注册的线程数量减去1。
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
30static int Sys_CreateSemaphore(struct Interrupt_State* state)
{
int res;
ulong_t userAddr = state->ebx; //信号量名字符串所在用户空间地址
ulong_t nameLen = state->ecx; //信号量名长度
ulong_t initCount = state->edx; //信号量初始值
/* 如果传入参数不正确则返回错误 */
if (nameLen <= 0 || initCount < 0 || nameLen > MAX_SEMAPHORE_NAME)
{
Print("Error! Semaphore Params incorrect\n");
return EINVALID;
}
char *semName = NULL;
/* 从用户空间拷贝信号量名字符串到内核空间 */
res = Copy_User_String(userAddr, nameLen, MAX_SEMAPHORE_NAME, &semName);
if (res != 0)
{
Print("Error! Cannot copy string from user spcce\n");
return res;
}
/* 判断信号量名的合法性(中间是否含有'\0'字符) */
if (strnlen(semName, MAX_SEMAPHORE_NAME) != nameLen)
{
Print("Error! Semaphore Name is Invalid\n");
return EINVALID;
}
/* 创建一个信号量 */
res = Create_Semaphore(semName, nameLen, initCount);
return res;
}1
2
3
4
5
6
7
8
9
10static int Sys_P(struct Interrupt_State* state)
{
int sid = state->ebx;// 信号量ID
if (sid <= 0)
{
Print("Error! Semaphore ID is Invalid\n");// 信号量ID无效
return EINVALID;// 信号量ID无效
}
return P(sid); // 申请信号量
}1
2
3
4
5
6
7
8
9
10static int Sys_V(struct Interrupt_State* state)
{
int sid = state->ebx;// 信号量ID
if (sid <= 0)
{
Print("Error! Semaphore ID is Invalid\n");
return EINVALID;// 信号量ID无效
}
return V(sid);// 释放信号量
}1
2
3
4
5
6
7
8
9
10static int Sys_DestroySemaphore(struct Interrupt_State* state)
{
int sid = state->ebx;// 信号量ID
if (sid <= 0)
{
Print("Error! Semaphore ID is Invalid\n");// 信号量ID无效
return EINVALID;
}
return Destroy_Semaphore(state->ebx); // 销毁信号量
}
以下几点前言，不用管（可以了解一下）
1、内核进程控制块
系统中每个内核进程有且只有一个进程控制块，进程控制块是用于记录进程状态及有关信息的数据结构。GeekOS操作系统中用数据结构Kernel_Thread作为内核进程控制块，对系统中的进程信息、执行情况、控制信息等加以维护，这个结构在include/kthread.h中定义。
2、GeekOS系统中最早的内核进程
GeekOS系统最早创建的内核进程有Idle、Peaper和Main3个进程。在系统初始化时，Main函数调用了一系列初始化函数，其中Init_Scheduler函数（\src\geekos\kthread.c）的作用：
初始化一个内核进程mainThread，并将该进程作为当前运行进程；
创建两个系统进程Idle和Reaper；
Idle进程类似于Windows中的系统闲置进程，什么也不做，创建后就一直存在于系统中，它存在的唯一目的是保证准备运行队列中有可调度的进程（占个位，有进程要用的时候就把资源让给他）。当系统没有可运行的进程时，CPU就运行Idle，一旦有其他准备运行的进程进入，Idle就会立即放弃CPU。
Reaper负责消亡进程的善后工作，如释放消亡进程占用的资源，内存、堆栈等。
3、内核进程对象
创建一个GeekOS内核进程需要调用Start_Kernel_Thread函数，而Start_Kernel_Thread内部调用Creat_Thread函数 ，该函数主要是创建内核进程对象，并调用Alloc_Page函数为进程对象、进程内核堆栈各分配一页内存（若失败，返回0，同时释放内核控制块空间）。
4、进程调度
GeekOS在一下几种情况会发生进程切换：
1）时间片用完；
2）执行内核进程Idle；
3）进程退出调用Exit函数；
4）进程进入等待调用Wait函数。
- 第一种情况下，当时间片用完，进程切换在中断处理函数Handle_Interrupt（在lowlevel.asm中定义）中完成。
- 后三种情况，函数内部都有调用Schedule()函数，其中又调用Switch_To_Thread函数（在lowlevel.asm中定义）
5、GeekOS进程调度策略
GeekOS的初始系统提供的进程调度是时间片轮转调度，所有准备运行进程（即Kernel_Thread）都放在一个FIFO队列里面，进程调度时找优先级最高的进程投入运行。
在GeekOS中，Get_Next_Runnable函数就是进程调度算法实现的地方，由\src\geekos\kthread.c文件中的Find_Best函数在准备运行进程的队列（s_runQueue指针指向）中查找，找优先级最高的。
6、GeekOS进程调度处理过程
进程调度是在时钟中断处理函数Time_Interrupt_Handle(/src/geekos/timer.c)内实现的。进程的Kernel_Thread结构中有一个numTicks变量，在进程对象初始化时被初始化为零，之后每次时钟中断处理，进程的该变量都会加1，然后系统会检查进程执行的时间是否超过了系统规定的时间片g_Quantum，如果超过，说明当前进程时间片已用完，系统应调度新的进程运行，于是将变量g_needReschedule置为true，用以标志需要重新调度新进程运行。
在时钟中断处理函数返回到Handle_Interrupt后检查g_needReschedule变量，如果为true，就调用Make_Runnable函数（kthread.c），将当前运行进程放入准备运行进程队列s_runQueue；之后再调用Get_Next_Runnable函数（kthread.c）找到优先级最高的进程；最后返回Handle_Interrupt将g_needReschedule返回为false，并切换到新进程运行。
workload 10<>
schedtest rr 1
semtest
在之前的项目中，GeekOS 使用的系统调度算法均为轮询调度算法，因此在此项目中，我们需要实现 MLF 调度算法的相关操作以及 RR 与 MLF 两种算法之间的队列转换 算法。
GeekOS 中，MLF 算法的规则描述为：
进程就绪队列共分为 4 级，按照优先级从高到低排列分别为 Q0、Q1、Q2 和 Q3 队列；
新创建的进程会被置入最高优先级的就绪队列（此处为 Q0）；每当一个进程运行完一个时间片长度之后，它就会被置入比之前低一级的就绪队列，直到到达优先级最低的队列（Q3）， 因此，CPU 密集型的进程最终会 被放到最低优先级的队列中；如果一个进程被阻塞（blocked），它的队列优先级就会提 升一个等级，直到被阻塞三次后达到最高优先级队列（Q0）。
在 MLF 策略与 RR 策略的进程队列转换时，GeekOS 给出的规则如下：
MLF->RR 时，将 Q1-Q3 队列中所有进程转移至 Q0 队列，然后按照优先级从高到低的顺序重新排序；
RR->MLF 时，只需将原本位于 Q0 队列中的 Idle（空闲）进程转移至 Q3 队列，其他进程无需再做修改。
- 在实际编写代码的时候，由于 GeekOS 提前实现了从队列中获取最高优先级进程的函数 Find_Best()，因此在 MLF->RR 时只需要将所有队列中进程移至 Q0 队列中即可。
- 为实现四级队列，设计中首先要修改s_runQueue（src/geekos/kthreas.c）的定义，从原来一个结构体改为一个4元素的结构体数组，每一个结构体元素用于存放一个优先级队列的队首指针。
- GeekOS系统将Idle进程始终放在优先级为3的进程队列末尾，且不允许移动到其它队列，以保证进程调度时一定能找到进程投入运行。
六、信号量和PV操作
信号量操作：
Semaphore_Create( )
Semaphore_Acquire（P操作）
Semaphore_Release（V操作）
Semaphore_Destroy( )
Create_Semaphore（）函数首先检查请求创建的这个信号量的名字是否存在.
- 如果存在，那么就把这个线程加入到这个信号量所注册的线程链表上；
- 如果不存在，则分配内存给新的信号量，清空它的线程队列，把当前的这个线程加入到它的线程队列中，设置注册线程数量为1，初始化信号量的名字，值和信号量的ID，并把这个信号量添加到信号量链表上，最后返回信号量的ID。
P操作Semaphore_Acquire（）中，首先检查传入的信号量ID是否存在
- 如果存在，接着检查当前线程是否注册使用了这个信号量，
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，就把信号量的值减去1，
- 如果减去1后信号量的值小于0，那么就把当前线程放入这个信号量的等待队列上。
V操作Semaphore_Release（）中，首先也是检查传入的信号量ID是否存在，
- 如果存在，接着检查当前线程是否注册使用了这个信号量，
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，那就把信号量的值加上1，
- 如果加上1后信号量的值小于或等于0，则要把该信号量里等待队列上的一个线程唤醒。
Semaphore_Destroy（）中，首先也是检查传入的信号量ID是否存在，
- 如果存在，接着检查当前线程是否注册使用了这个信号量。
- 如果这两项检查任意一项失败了，那么就返回-1。
- 如果成功了，就把该线程从这个信号量的注册的线程数组中删除，并把注册的线程数量减去1。
1 |
|
如果这个信号量的注册线程为0了，则把这个信号量从信号量链表中删除，并释放它的内存。
实现的信号量相关操作（创建、获取、释放和销毁） 都能够正确的在系统中执行，而且在 semtest2.exe 的测试中对于不正确的信号量操作（线 程对未授权信号量进行操作、无效信号量 ID 和销毁信号量后再对其进行获取操作）系统也能够进行相应的处理和反馈
系统调用的作用
系统调用是用户程序与操作系统内核之间的一个重要接口，主要用于以下目的：
- 资源请求：用户程序通过系统调用请求操作系统提供资源，如文件操作、内存管理、网络通信等。
- 权限提升：用户程序在用户态下运行，权限有限，通过系统调用可以临时提升权限，执行一些需要更高权限的操作。
- 硬件访问：用户程序不能直接访问硬件设备，必须通过系统调用请求操作系统代为执行。
- 状态查询：用户程序可以通过系统调用查询系统的当前状态，如时间、进程信息等。
系统调用的执行过程
系统调用的执行过程大致如下：
用户程序发起调用：
- 用户程序调用一个库函数，该库函数内部包含了一个系统调用指令。
- 例如，在GeekOS中，用户程序调用
Set_Scheduling_Policy(policy, quantum)来设置调度策略。
参数准备：
- 库函数将系统调用的参数（如
policy和quantum）准备好，并将它们放入特定的寄存器中。 - 例如，
policy放入寄存器EBX，quantum放入寄存器ECX。
- 库函数将系统调用的参数（如
中断指令：
- 库函数执行一条中断指令（如
int $0x90），触发一个中断。 - 中断指令将控制权从用户态转移到内核态，进入中断处理程序。
- 库函数执行一条中断指令（如
中断处理：
- 操作系统内核的中断处理程序捕获中断，保存当前的中断现场（包括寄存器状态）。
- 中断处理程序根据中断号（如
0x90）找到对应的系统调用处理函数。
系统调用处理：
- 系统调用处理函数（如
Sys_SetSchedulingPolicy）从保存的中断现场中提取参数（EBX和ECX）。 - 处理函数执行具体的系统调用逻辑，如更改调度策略、获取系统时间等。
- 系统调用处理函数（如
返回用户程序：
- 系统调用处理完成后，中断处理程序恢复中断现场，将控制权交还给用户程序。
- 用户程序继续执行，可以获取系统调用的返回值（如成功或失败的状态码）。
示例：GeekOS中的系统调用
在GeekOS中，系统调用的具体实现如下：
用户程序调用：
1
Set_Scheduling_Policy(policy, quantum);
库函数定义：
1
2
3
4
5
6
7
8
9
DEF_SYSCALL(Set_Scheduling_Policy, SYS_SETSCHEDULINGPOLICY, int, (int policy, int quantum), int arg0 = policy; int arg1 = quantum;, SYSCALL_REGS_2)系统调用处理函数：
1
2
3
4
5
6
7
8
9
10
11
12
13static int Sys_SetSchedulingPolicy(struct Interrupt_State* state) {
int n, quantum;
n = state->ebx;
quantum = state->ecx;
if (n == 0) {
Change_Scheduling_Policy(0, quantum);
} else if (n == 1) {
Change_Scheduling_Policy(1, quantum);
} else {
return -1;
}
return 0;
}
参数state是一个结构体，其中，state->ebx成员用于指定调度策略，值为0代表系统采用时间片轮转调度策略，值为1则代表系统采用四级反馈队列调度策略，若取其他值则出错。state->ecx成员用于记录相应调度策略下的时间片长度。
五、多级反馈策略测试运行流程
1 | if (argc == 3) { |
接着调用Sys_SetSchedulingPolicy（）（\src\geekos\syscall.c）设置调度策略：
1 |
到Chang_Scheduling_Policy（）（\src\geekos\kthread.c）修改线程队列及系统相关变量，主要是 g_curSchedulingPolicy 为当前调度策略， g_Quantum 为时间片长度：
1 | int Chang_Scheduling_Policy(int policy, int quantum) |