23-处理器调度 (xv6 上下文切换；处理器调度：机制和策略)

Created2025-09-10Updated2025-11-26

23-处理器调度 (xv6 上下文切换；处理器调度：机制和策略)

由用户态，执行syscall

跳转到内核态代码，寄存器保存，切换页表和栈

调度策略

1
taskset -c 3 nice -n 19 yes > /dev/null & taskset -c 3 nice -n 9 yes > /dev/null

nice值相差10，占用cpu时间相差1倍

上下文切换是机制，策略是选择哪个进程执行

动态优先级，CPU密集型的优先级逐渐降低，交互型的优先级逐渐增加

动态优先级实现的虚拟时间是什么原理，为什么“好人”和“坏人”会相差几倍

进程的nice值越小（优先级越高），权重越大，在实际运行时间相同的情况下，虚拟运行时间越短，进程累计的虚拟运行时间增加得越慢，在红黑树中向右移动的速度越慢，被调度器选中的机会越大，被分配的运行时间相对越多。随着优先级高进程的虚拟运行时间增长，低优先级的进程也会有机会被调度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

Linux CFS调度器 vruntime 的计算_linux vruntime-CSDN博客

CFS，完全公平调度，记录每个进程运行时间，每次都切换到运行时间最少的进程。

红黑树

=运算符重载

Created2025-09-10Updated2025-09-11
1
2
3
4
5
6
7
8
9
10
Polynomial& Polynomial::operator=(const Polynomial& p){
		if(this == &p) return *this;
		delete[] coefficients;
		size = p.size;
		coefficients = new double[size];
		for(int i = 0; i < size; i++){
			coefficients[i] = p.coefficients[i];
		}
		return *this;
}

多项式类的赋值

要考虑 a = b = c 这种情况，所以返回reference类型

6.s081debug kernel

Created2025-09-10Updated2025-11-26

6.s081debug kernel

在vscode配置好后无法debug用户程序，不能打断点

在debug console执行-exec file user/_ls

qemu-gdb debug指南之can not access memory解决！ - 知乎 (zhihu.com)

当你的xv6 kernel已经运行起来的时候， 你想往一个用户程序打断点，你只能先加载他的符号表，然后将断点打在main函数的入口，然后在xv6 调用该程序，触发main函数断点，然后才可以在任意一行打断点。记住顺序不能乱。

解决方案，先暂停程序，然后在debug console中输入

1
-exec file user/_

加载该程序文件，然后打断点，运行程序debug

C++部分知识点

Created2025-09-10Updated2025-11-26

关于inline函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person
{
public:
	Person(const string &name)
	{
		Name = name;
	}
    void printName();
	//在类里面没有显式声明
private:
	string Name;
};
void Person::printName()//不是内联函数
{//在类外面也没有显式定义
	cout << Name << endl;
}

C++类里面的哪些成员函数是内联函数？_操作符函数是内联的吗-CSDN博客

关于友元类和友元函数

  • 友元关系是单向的，不具有交换性。

  • 友元关系不能传递

  • 友元关系不能被继承，但对已有的方法来说访问权限不改变。

  • 类A把类B声明为友元类，在前面要有前置声明

  • 类A把类B中的函数声明为友元函数，在类A之前必须有类B的完整定义

    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
    class Date; // 前置声明
    class Time
    {
        friend class Date; 
        // 声明日期类为时间类的友元类，则在日期类中就直接访问Time类中的私有成员变量
    public:
        Time(int hour, int minute, int second): _hour(hour), _minute(minute), _second(second)
        {}
     
    private:
        int _hour;
        int _minute;
        int _second;
    };
     
    class Date
    {
    public:
        Date(int year = 1900, int month = 1, int day = 1): _year(year),                                     
        _month(month),_day(day)
        {}
        void SetTimeOfDate(int hour, int minute, int second)
        {
            // 直接访问时间类私有的成员变量
            _t._hour = hour;
            _t._minute = minute;
            _t.second = second;
        }
    private:
        int _year;
        int _month;
        int _day;
        Time _t;
    };

    重载输出运算符设置为全局函数

为什么输出运算符重载不能是一个成员函数?而非得声明为友元？
原因如下：

1
返回值 operator运算符(参数列表){}

重载运算符时，函数声明在类内和类外是有区别的，比方说 + - * / 等需要2个操作数的运算符，当声明在类的外部时，则参数列表为2个参数，第一个参数为运算符左边的操作数，而第二个参数为操作符右边的操作数：如下

1
classType operator+(classType& left, classType& right);

而当函数声明在类的内部时，即为类的成员函数时，

1
classType operator+(classType& right );

而第一个操作数就是调用该操作符的对象的引用，第二个操作数是传进来的参数，所以，如果要重载<<运算符，一般写法是这样的

1
ostream& operator<<(ostream& os, const classType& obj);

则第一个参数是该运算符的第一个操作数，然而，却不是类对象，
所以当该类运算符重载时写在类的内部时，又为了访问类内除public外的其它变量或函数

C++中友元函数和成员函数的区别-CSDN博客

关于protected和private

在C++中，private和protected是两种不同的访问修饰符，它们控制类成员的访问权限。

  • private：私有成员只能被该类的成员函数和友元函数访问，不能被该类的对象或者任何其他类访问。
  • protected：受保护成员可以被该类的成员函数、该类派生出的子类的成员函数以及友元函数访问，但不能被该类的对象访问。

在你的代码中，object类的成员a是私有的，所以它只能被object类的成员函数和友元函数访问。如果你想让a能被object类派生出的子类访问，你应该将a声明为受保护的，例如：

1
2
3
4
5
6
7
8
class object {
public:
    object() {
        a = 0;
    }
protected:
    int a;
};

在这个例子中，a是受保护的，所以它可以被object类的成员函数、object类派生出的子类的成员函数以及友元函数访问。

虚函数和static互斥,static函数也不能加const

虚函数

  • 与对象关联：虚函数是与具体的对象实例关联的，它们通过对象的虚函数表（vtbl）实现动态绑定。
  • 需要对象上下文：调用虚函数时，需要知道具体对象的类型，以便调用正确的函数实现。这需要通过this指针来访问对象的状态和虚函数表。

静态成员函数

  • 与类关联：静态成员函数是与类本身关联的，而不是与具体的对象实例关联的。
  • 没有对象上下文：静态成员函数没有this指针，不能访问对象的非静态成员或虚函数表，因为它们在类层次上调用，而不是通过对象。

简单总结

  • 虚函数：需要对象实例来确定调用哪个函数实现。
  • 静态成员函数：不依赖任何对象实例，只能访问类的静态成员。

由于虚函数依赖于对象的上下文，而静态成员函数没有对象上下文，因此它们不能结合在一起使用。虚函数需要对象实例和虚函数表，而静态成员函数不具备这些特性，因此它们是互斥的。

为何static成员函数不能为const函数

当声明一个非静态成员函数为const时，对this指针会有影响。对于一个Test类中的const修饰的成员函数，this指针相当于Test const *, 而对于非const成员函数，this指针相当于Test *. 而static成员函数没有this指针，所以使用const来修饰static成员函数没有任何意义。 volatile的道理也是如此。

关于new运算符

new运算符做的三件事：获得一块内存空间、调用构造函数、返回正确的指针

New运算符的使用方法：

1、new() ：分配这种类型的一个大小的内存空间,并以括号中的值来初始化这个变量;

2、 new[] ：分配这种类型的n个大小的内存空间,并用默认构造函数来初始化这些变量;

char* p=new char[6]; strcpy(p,”Hello”);

3、当使用new运算符定义一个多维数组变量或数组对象时，它产生一个指向数组第一个元素的指针，返回的类型保持了除最左边维数外的所有维数。例如： 

1
2
3
4
5
6
7
8
9
10
11
int *p1 = new int[10];

返回的是一个指向int的指针int*  

int (*p2)[10] = new int[2][10];

new了一个二维数组, 去掉最左边那一维[2], 剩下int[10], 所以返回的是一个指向int[10]这种一维数组的指针int (*)[10].  

int (*p3)[2][10] = new int[5][2][10];

 new了一个三维数组, 去掉最左边那一维[5], 还有int[2][10], 所以返回的是一个指向二维数组int[2][10]这种类型的指针int (*)[2][10].

4、创建类对象

1）new创建对象，pTest用来接收对象指针。new申请的对象，则只有调用到delete时才会执行析构函数，如果程序退出而没有执行delete则会造成内存泄漏：

CTest* pTest = new CTest(); delete pTest;

2）不用new，直接使用类定义申明，使用完后不需要手动释放，该类析构函数会自动执行：

CTest mTest;

3）使用普通方式创建的类对象，在创建之初就已经分配了内存空间。而类指针，如果未经过对象初始化，则不需要delete释放：

CTest* pTest = NULL;

作用域运算符::

::是运算符中等级最高的，它分为三种：全局作用域符，类作用域符，命名空间作用域符

全局作用

全局作用域符号：当全局变量在局部函数中与其中某个变量重名，那么就可以用::来区分如： 

1
2
3
4
5
6
7
char zhou; //全局变量 
　　void sleep（） 
　　{ 
　　char zhou; //局部变量 
　　zhou(局部变量) = zhou(局部变量) *zhou(局部变量) ; 
　　::zhou(全局变量) =::zhou(全局变量) *zhou(局部变量); 
}

类作用

作用域符号::的前面一般是类名称，后面一般是该类的成员名称，C++为了避免不同的类有名称相同的成员而采用作用域的方式进行区分
　　如：A,B表示两个类，在A,B中都有成员member。那么
　　A::member就表示类A中的成员member
　　B::member就表示类B中的成员member

命名空间

“::”是作用域限定符或者称作用域运算符或者作用域操作符（scope operator）.例如命名空间

“::”作用：

1
namespace::name

:: 的另一种用法

直接用在全局函数前，表示是全局函数。

关于缺省值函数

在C++中，函数形参的缺省值（默认值）有以下规则：

缺省值必须从右向左连续设定。也就是说，如果一个参数有缺省值，那么它右边的所有参数都必须有缺省值。例如，以下函数声明是合法的：

1
void fun(int x, int y = 1, int z = 2);

但是，以下函数声明是非法的，因为y有缺省值，但是它右边的参数z没有缺省值：

1
void fun(int x, int y = 1, int z); // 非法

缺省值只能在函数声明时设定，不能在函数定义时设定。例如，以下代码是合法的：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 在函数声明时设定缺省值
void fun(int x = 0);
// 函数定义
void fun(int x) {
  // ...
}
但是，以下代码是非法的，因为缺省值在函数定义时设定：
// 函数声明
void fun(int x);
// 在函数定义时设定缺省值
void fun(int x = 0) { // 非法
  // ...
}

如果函数在同一作用域内多次声明，那么它的每个参数的缺省值最多只能设定一次。但是，如果函数在不同的作用域内声明，那么在不同的作用域内可以给同一个参数设定不同的缺省值。

关于try和catch

多态

动态多态

运行时的多态存在于继承类中，通过虚函数现动态选择调用。

静态多态

静态多态是发生在编译时期的，通过模板和函数重载实现，相比动态多态不需派生关系。

C++文件操作

C++文件操作（2023最新详解）-CSDN博客

1、要打开一个输入文件流，需要定义一个 ifstream类型的对象。->Input-stream
2、要打开一个输出文件流，需要定义一个 ofstream类型的对象。->Output-stream
3、如果要打开输入输出文件流，则要定义一个 fstream类型的对象。->File-stream

**这3种类型都定义在头文件 **fstream里

1
2
ofstream ofs;   		  //2、打开一个相应的文件流
ofs.open("mytest.txt");	  //3、流与文件关联上

因为ifstream、ofstream和fstream这3个类都具有自动打开文件的构造函数，而这个构造函数就具有 open() 的功能。

因此，我们可以在创建流对象的时候就可以关联文件：ofstream myStream("myText.txt");

open函数的原型如下：

1
void open(char const *,int filemode,int =filebuf::openprot);
ios::in 打开文件进行读操作，这种方式可避免删除现存文件的内容
ios::out 打开文件进行写操作，这是默认模式
ios::ate 打开一个已有的输入或输出文件并查找到文件尾开始
ios::app 在文件尾追加方式写文件
ios::binary 指定文件以二进制方式打开，默认为文本方式
ios::trunc 如文件存在，将其长度截断为零并清除原有内容，如果文件存在先删除，再创建

三种继承

1.公有继承–public:（原样复制）

公有继承时，对基类的公有成员和保护成员的访问属性不变，派生类的新增成员只能访问基类的公有成员和保护成员（都一样）。派生类的对象只能访问派生类的公有成员（包括继承的公有成员），访问不了保护成员和私有成员**（公有继承的对象多了个访问继承的公有成员）**。

2.保护继承–protected

保护继承中，基类的公有成员和保护成员被派生类继承后变成保护成员，派生类的新增成员只能访问基类的公有成员和保护成员（都一样），派生类的对象只能访问派生类的公有成员。

3.私有继承–private

私有继承时，基类的公有成员和保护成员都被派生类继承下来之后变成私有成员，派生类的新增成员只能访问基类的公有成员和保护成员（都一样）。派生类的对象只能访问派生类的公有成员(这里和protected继承一样)。

关于多继承

C++多继承中的二义性问题_c++多重继承引起的二义性问题-CSDN博客

同名二义性

一个子类继承两个有同名数据成员的父类

路径二义性

一个子类继承两个父类，这两个父类又继承自同一个祖父类

class7自旋锁

Created2025-09-10Updated2025-11-26

在class7的自旋锁多核启动失败，只能单cpu

解决方法

修改/home/cgz/work/nju-os-workbench/abstract-machine/scripts/platform/qemu.mk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.PHONY: build-arg

smp        ?= 4//改这个
LDFLAGS    += -N -Ttext-segment=0x00100000
QEMU_FLAGS += -serial mon:stdio \
              -machine accel=tcg \
              -smp "$(smp),cores=1,sockets=$(smp)" \//改这里的sockets和cores
              -drive format=raw,file=$(IMAGE)

build-arg: image
	@( echo -n $(mainargs); ) | dd if=/dev/stdin of=$(IMAGE) bs=512 count=2 seek=1 conv=notrunc status=none

BOOT_HOME := $(AM_HOME)/am/src/x86/qemu/boot

image: $(IMAGE).elf
	@$(MAKE) -s -C $(BOOT_HOME)
	@echo + CREATE "->" $(IMAGE_REL)
	@( cat $(BOOT_HOME)/bootblock.o; head -c 1024 /dev/zero; cat $(IMAGE).elf ) > $(IMAGE)

collect采用gpt生成，适用于mosaic结果的分析

Created2025-09-10Updated2025-11-26

collect采用gpt生成，适用于mosaic结果的分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/bin/bash

# 从管道读取 JSON 格式输入
input=$(cat)

# 检查 JSON 数据中是否包含 "vertices" 和 "edges"
if ! echo "$input" | jq -e '.vertices and .edges' > /dev/null; then
    echo "Error: JSON input must contain 'vertices' and 'edges' arrays."
    exit 1
fi

# 提取路径中的节点信息
path=$(echo "$input" | jq -r '.vertices[-1].stdout')
# 计算顶点 |V| 和边 |E| 数量
num_vertices=$(echo "$input" | jq '.vertices | length')
num_edges=$(echo "$input" | jq '.edges | length')

# 生成唯一的输出计数
unique_outputs=1

# 输出格式
echo "$path"
echo "|V| = $num_vertices, |E| = $num_edges."
echo "There are $unique_outputs distinct outputs."

gdbinit

Created2025-09-10Updated2025-11-26

让gdb启动时就打开tui

编写gdbinit文件

img

所以先在home目录下设置gdbinit

然后执行

1
source ~/.gdbinit

hanoi

Created2025-09-10Updated2025-11-26

hanoi

每个Frame（栈帧）都有自己的变量，pc是相互独立的，指示自身栈帧下一步要执行什么

每次call，入栈，把pc置为0，在while(1)开头再指向top

每次执行完case语句，都把pc加1，不一定是栈顶的

把递归的分解为6步，逐步执行，case3移动一个不需要保存，在case6加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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int hanoi(int n, char from, char to, char via) {
    Frame stk[64];
    Frame *top = stk - 1;

    // Function call: push a new frame (PC=0) onto the stack
    #define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
    
    // Function return: pop the top-most frame
    #define ret(val) ({ top--; retval = (val); })


    // The last function-return's value. It is not obvious
    // that we only need one retval.
    int retval = 0;

    // The initial call to the recursive function
    call(n, from, to, via);

    while (1) {
        // Fetch the top-most frame.
        Frame *f = top;
        printf("pc=%d\n",  f->pc);
       
       
        if (top < stk) {
           // No top-most frame any more; we're done.
            break;
        }

        // Jumps may change this default next pc.
        int next_pc = f->pc + 1;
        
        // Single step execution.

        // Extract the parameters from the current frame. (It's
        // generally a bad idea to reuse variable names in
        // practice; but we did it here for readability.)
        int n = f->n, from = f->from, to = f->to, via = f->via;
        
        switch (f->pc) {
            case 0:
                if (n == 1) {
                    printf("%c -> %c\n", from, to);
                    ret(1);
                }
                break;
            case 1: call(n - 1, from, via, to); break;
            case 2: f->c1 = retval; break;
            case 3: call(1, from, to, via); break;
            case 4: call(n - 1, via, to, from); break;
            case 5: f->c2 = retval; break;
            case 6: ret(f->c1 + f->c2 + 1); break;
            default: assert(0);
        }

        f->pc = next_pc;
    }

    return retval;
}

ostep28.14使用pack和unpack

Created2025-09-10Updated2025-11-26

ostep28.14使用pack和unpack

存在自旋，但是自旋仅在guard保护修改flag和队列中，比用户的临界区短

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
1  typedef struct __lock_t {
2      int flag;
3      int guard;
4      queue_t *q;
5  } lock_t;

6  void lock_init(lock_t *m) {
7      m->flag = 0;
8      m->guard = 0;
9      queue_init(m->q);
10 }

11 void lock(lock_t *m) {
12     while (TestAndSet(&m->guard, 1) == 1) // acquire guard lock by spinning
13         ; // 自旋直到获取到guard锁
14     if (m->flag == 0) { // 如果flag为0，表示锁未被占用
15         m->flag = 1; // 获取锁
16         m->guard = 0; // 释放guard锁
17     } else { // 锁已被占用
18         queue_add(m->q, gettid()); // 将当前线程加入等待队列
19         m->guard = 0; // 释放guard锁
20         park(); // 将线程挂起，进入睡眠状态
21     }
22 }

23 void unlock(lock_t *m) {
24     while (TestAndSet(&m->guard, 1) == 1) // acquire guard lock by spinning
25         ; // 自旋直到获取到guard锁
26     if (queue_empty(m->q)) { // 如果队列为空，表示没有等待线程
27         m->flag = 0; // 释放锁
28     } else {
29         unpark(queue_remove(m->q)); // 唤醒等待队列中的下一个线程
30     }
31     m->guard = 0; // 释放guard锁
32 }

guard的作用是保护flag和队列的修改，flag保护临界区

在unlock中，唤醒等待线程后，不需要设置flag=1,这样直接将锁从解锁的线程传给了被唤醒的线程。

是的，在原文的代码实现中，线程被唤醒后就直接进入临界区

存在的问题就是唤醒的丢失，因为A线程加入队列后如果切换到释放锁的线程B，线程B唤醒A后，A继续执行然后睡眠，但是此时等待队列已经没有A了，所以会造成死锁

使用setpark,如果setpark后切换到另一个线程，调用unpark释放后，返回lock函数，pack会直接返回而不再睡眠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ;  // 自旋等待获取guard锁
    
    if (m->flag == 0) {  // 如果锁未被占用
        m->flag = 1;     // 获取锁
        m->guard = 0;    // 释放guard锁
    } else {             // 如果锁被占用
        queue_add(m->q, gettid());  // 将当前线程加入等待队列
        setpark();                  // 设置park状态，防止丢失唤醒
        m->guard = 0;               // 释放guard锁
        park();                     // 挂起线程，等待被唤醒
        // 唤醒后继续执行
    }
}