yhzhuang
0%

发表于 更新于

实验课程: 操作系统

实验名称: Lab9 malloc-free

  • 学生姓名: 庄云皓
  • 学生学号: 22336327

1. 实验要求

实现系统调用malloc和free。malloc用于分配任意字节的内存，free用于释放任意字节的内存。

按照教程中给的代码复现实验，并对加入同步互斥代码以保证保证动态内存分配时的线程安全。

2. 实验过程

基本思路

分配𝑠𝑖𝑧𝑒个字节的内存时的时候，我们需要找到一个𝑁，满足2^(𝑁−1)<𝑠𝑖𝑧𝑒≤2^𝑁

也就是从小到大搜索，找到第一个恰好不小于𝑠𝑖𝑧𝑒的arena。找到这样一个arena后，我们便返回arena的起始地址作为分配的结果。特别地，当没有arena能够包含𝑠𝑖𝑧𝑒个字节时，我们就分配连续的𝑀个页，使得(𝑀−1)×4096<𝑠𝑖𝑧𝑒≤𝑀×4096

返回这𝑀个页的起始地址作为分配的结果。

过程

先在setup函数中设置两个系统调用：

1
2
3
4
//设置4号系统调用
systemService.setSystemCall(4, (int)syscall_malloc);
//设置5号系统调用
systemService.setSystemCall(5, (int)syscall_free);

在system_call.cpp中加入

1
2
3
4
5
6
void* malloc(int size){
    return (void*)asm_system_call(4,size);
}
void free(void* address){
    asm_system_call(5,(int)address);
}

接着我们需要完善这两个系统调用函数：

void* syscall_malloc(intsize)和 void syscall_free(void*address)

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
void *syscall_malloc(int size)
{
    PCB *pcb = programManager.running;
    if (pcb->pageDirectoryAddress)
    {
        // 每一个进程有自己的ByteMemoryManager
        return pcb->byteMemoryManager.allocate(size);
    }
    else
    {
        // 所有内核线程共享一个ByteMemoryManager
        return kernelByteMemoryManager.allocate(size);
    }
}

void syscall_free(void *address)
{
    PCB *pcb = programManager.running;
    if (pcb->pageDirectoryAddress)
    {
        pcb->byteMemoryManager.release(address);
    }
    else
    {
        kernelByteMemoryManager.release(address);
    }
}

在memory.h中定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// MemoryManager是在内核态调用的内存管理对象
class ByteMemoryManager
{

private:
    // 16, 32, 64, 128, 256, 512, 1024
    static const int MEM_BLOCK_TYPES = 7;       // 内存块的类型数目
    static const int minSize = 16;              // 内存块的最小大小
    int arenaSize[MEM_BLOCK_TYPES];             // 每种类型对应的内存块大小
    MemoryBlockListItem *arenas[MEM_BLOCK_TYPES]; // 每种类型的arena内存块的指针

public:
    ByteMemoryManager();
    void initialize();
    void *allocate(int size);  // 分配一块地址
    void release(void *address); // 释放一块地址

private:
    bool getNewArena(AddressPoolType type, int index);
};

ByteMemoryManager初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ByteMemoryManager::ByteMemoryManager()
{
    initialize();
}

void ByteMemoryManager::initialize()
{
    int size = minSize;
    for (int i = 0; i < MEM_BLOCK_TYPES; ++i)
    {
        arenas[i] = nullptr;
        arenaSize[i] = size;
        size = size << 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
void *ByteMemoryManager::allocate(int size)
{
    int index = 0;
    while (index < MEM_BLOCK_TYPES && arenaSize[index] < size)
        ++index;

    PCB *pcb = programManager.running;
    AddressPoolType poolType = (pcb->pageDirectoryAddress) ? AddressPoolType::USER : AddressPoolType::KERNEL;
    void *ans = nullptr;

    if (index == MEM_BLOCK_TYPES)
    {
        // 上取整
        int pageAmount = (size + sizeof(Arena) + PAGE_SIZE - 1) / PAGE_SIZE;

        ans = memoryManager.allocatePages(poolType, pageAmount);

        if (ans)
        {
            Arena *arena = (Arena *)ans;
            arena->type = ArenaType::ARENA_MORE;
            arena->counter = pageAmount;
        }
    }
    else
    {
        //printf("---ByteMemoryManager::allocate----\n");
        if (arenas[index] == nullptr)
        {
            if (!getNewArena(poolType, index))
                return nullptr;
        }

        // 每次取出内存块链表中的第一个内存块
        ans = arenas[index];
        arenas[index] = ((MemoryBlockListItem *)ans)->next;

        if (arenas[index])
        {
            (arenas[index])->previous = nullptr;
        }

        Arena *arena = (Arena *)((int)ans & 0xfffff000);
        --(arena->counter);
        //printf("---ByteMemoryManager::allocate----\n");
    }

    return ans;
}

如果空闲arena链表为空，则需要从内核中分配一个页，写入元信息，然后将该页划分成一个个arena。

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
bool ByteMemoryManager::getNewArena(AddressPoolType type, int index)
{
    void *ptr = memoryManager.allocatePages(type, 1);

    if (ptr == nullptr)
        return false;

    // 内存块的数量
    int times = (PAGE_SIZE - sizeof(Arena)) / arenaSize[index];
    // 内存块的起始地址
    int address = (int)ptr + sizeof(Arena);

    // 记录下内存块的数据
    Arena *arena = (Arena *)ptr;
    arena->type = (ArenaType)index;
    arena->counter = times;
    // printf("---ByteMemoryManager::getNewArena: type: %d, arena->counter: %d\n", index, arena->counter);

    MemoryBlockListItem *prevPtr = (MemoryBlockListItem *)address;
    MemoryBlockListItem *curPtr = nullptr;
    arenas[index] = prevPtr;
    prevPtr->previous = nullptr;
    prevPtr->next = nullptr;
    --times;

    while (times)
    {
        address += arenaSize[index];
        curPtr = (MemoryBlockListItem *)address;
        prevPtr->next = curPtr;
        curPtr->previous = prevPtr;
        curPtr->next = nullptr;
        prevPtr = curPtr;
        --times;
    }

    return true;
}

接下来我们来实现内存释放。

内存释放非常简单，当我们释放一个动态分配的内存地址时，我们可以找到这个地址所在的页。然后通过这个页开头保存的元信息就能够找到这个地址对应的arena类型。最后将这个arena放到对应的空闲arena链表即可。

特别地，当一个页内的所有arena都被释放时，我们需要释放这个页。

教程中的代码有一些拼写问题和release没有指定内存池是kernel还是user的问题，进行了修改。

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
61
62
63
64
65
66
void ByteMemoryManager::release(void *address)
{
    // 由于Arena是按页分配的，所以其首地址的低12位必定0，
    // 其中划分的内存块的高20位也必定与其所在的Arena首地址相同
    Arena *arena = (Arena *)((int)address & 0xfffff000);

    if (arena->type == ARENA_MORE)
    {
        int address = (int)arena;

        memeoryManager.releasePage(address, arena->counter);
    }
    else
    {
        MemoryBlockListItem *itemPtr = (MemoryBlockListItem *)address;
        itemPtr->next = arenas[arena->type];
        itemPtr->previous = nullptr;

        if (itemPtr->next)
        {
            itemPtr->next->previous = itemPtr;
        }

        arenas[arena->type] = itemPtr;
        ++(arena->counter);

        // 若整个Arena被归还，则清空分配给Arena的页
        int amount = (PAGE_SIZE - sizeof(Arena)) / arenaSize[arena->type];
        // printf("---ByteMemoryManager::release---: arena->counter: %d, amount: %d\n", arena->counter, amount);

        if (arena->counter == amount)
        {
            // 将属于Arena的内存块从链上删除
            while (itemPtr)
            {
                if ((int)arena != ((int)itemPtr & 0xfffff000))
                {
                    itemPtr = itemPtr->next;
                    continue;
                }

                if (itemPtr->previous == nullptr) // 链表中的第一个节点
                {
                    arenas[arena->type] = itemPtr->next;
                    if (itemPtr->next)
                    {
                        itemPtr->next->previous = nullptr;
                    }
                }
                else
                {
                    itemPtr->previous->next = itemPtr->next;
                }

                if (itemPtr->next)
                {
                    itemPtr->next->previous = itemPtr->previous;
                }

                itemPtr = itemPtr->next;
            }

            memeoryManager.releasePage((int)address, 1);
        }
    }
}

由于进程有自己的内存空间，我们修改PCB，在PCB中加入 ByteMemeoryManager。

1
2
3
4
5
6
struct PCB
{
	...
    ByteMemoryManager byteMemoryManager; // 进程内存管理者
    ...
};

在pcb初始化函数中加上

1
thread->byteMemoryManager.initialize();

setup函数中

1
2
3
4
5
6
7
8
ByteMemoryManager kernelByteMemoryManager;
extern "C" void setup_kernel()
{

    ...
    kernelByteMemoryManager.initialize();
    ...
}

3. 关键代码

见上一部分

4. 实验结果

我们在这里加上延迟来展示没有实现互斥时发生的错误，同时把时间片轮转的ticks调低来增加并发度

1
2
3
4
5
6
7
8
9
10
void *ByteMemoryManager::allocate(int size)
{
	...
	ans = arenas[index];
        //设置延迟

        int delay = 0xfffffff;
        while(delay--);
	...
}

来看这个样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void second_thread(void *arg) {
    void* addr = malloc(50);
    printf("first_thread get addr0(50) %x\n", addr);
    void* addr1 = malloc(30);
    printf("first_thread get addr1(30) %x\n", addr1);
    free(addr);
  
    free(addr1);

}
void third_thread(void *arg) {
    void* addr2 = malloc(50);
    printf("second_thread get addr2(50) %x\n",addr2);
    free(addr2);
}

thread1和 tread2都malloc了50B,在tread1获取了ans之后延迟，并没有设置 arenas[index] = ((MemoryBlockListItem *)ans)->next;此时tread2被调度上处理机，获取了一样的地址。

分配了同样的地址会导致release的时候也无法回收，所以我们只看到了两个release.

无锁:

1720841743990

有锁：

在这里加上锁保证对arena数组的互斥访问

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
void *ByteMemoryManager::allocate(int size){
    ...
    else
    {
        bt_sem.P();
        printf("---ByteMemoryManager::allocate----\n");
        if (arenas[index] == nullptr)
        {

            if (!getNewArena(poolType, index))
                return nullptr;
            printf("getNewArena\n");
        }

        // 每次取出内存块链表中的第一个内存块
        ans = arenas[index];
        //设置延迟

        int delay = 0xfffffff;
        while(delay--);

  
        arenas[index] = ((MemoryBlockListItem *)ans)->next;

        if (arenas[index])
        {
            (arenas[index])->previous = nullptr;
        }

        Arena *arena = (Arena *)((int)ans & 0xfffff000);
        --(arena->counter);
        //printf("---ByteMemoryManager::allocate----\n");
        bt_sem.V();
    }
}

加锁之后在 thread1和 tread2都malloc了50B时分配的地址是不同的。可见实现了分配时的互斥。thread1在exit的时候回收了资源，所以 thread2malloc分配到的地址和thread1是一样的。

1720841689908

在其他需要互斥的地方加上信号量：

这里加上是为了保证在为进程分配内存的时候实现的互斥以及malloc分配空间>1024Byte时的分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Semaphore semaphore;
void MemoryManager::initialize()
{
    semaphore.initialize(1);
    ...
}
int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    semaphore.P();
    // 第一步：从虚拟地址池中分配若干虚拟页
    int virtualAddress = allocateVirtualPages(type, count);
    ...
    semaphore.V();
    return virtualAddress;
}

对于进程来说，也能通过系统调用实现正常分配内存：

1
2
3
4
5
6
7
8
9
10
void first_process()
{
    void* addr = malloc(50);

    printf("first_process get addr0(50) %x\n", addr);
    void* addr1 = malloc(30);
    printf("first_process get addr1(30) %x\n", addr1);
    free(addr);
    free(addr1);
}

1720857389774

5. 总结

这次实验可以说比较综合，涉及到内存管理、系统调用、线程互斥等多方面的内容，虽然说整体难度不大只需要在教程给出的代码上进行修改但是还是要完全理解还是有些难度。实验中遇到了没有在setup.cpp函数中BytememoryManagemebt.initalize()，导致调用默认构造函数size都被初始化为0的问题。后来发现并解决了。实验教程中采用了不同大小的块进行动态内存分配，减少了碎片，可以说是很精巧的。

发表于 更新于

实验课程: 操作系统

实验名称: Lab7 内存管理

  • 姓名: 庄云皓
  • 学号: 22336327

1. 实验要求

Assignment 1

复现参考代码，实现二级分页机制，并能够在虚拟机地址空间中进行内存管理，包括内存的申请和释放等，截图并给出过程解释。

Assignment 2

参照理论课上的学习的物理内存分配算法如first-fit, best-fit等实现动态分区算法等，或者自行提出自己的算法。

Assignment 3

复现“虚拟页内存管理”一节的代码，完成如下要求。

  • 结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放。
  • 构造测试例子来分析虚拟页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测例简要分析虚拟页内存管理的实现的正确性。
  • （不做要求，对评分没有影响）如果你有想法，可以在自己的理解的基础上，参考ucore，《操作系统真象还原》，《一个操作系统的实现》等资料来实现自己的虚拟页内存管理。在完成之后，你需要指明相比较于本教程，你的实现的虚拟页内存管理的特点所在。

Assignment 4

参照理论课上虚拟内存管理的页面置换算法如FIFO、LRU等，实现页面置换，也可以提出自己的算法。

2. 实验过程

Assignment1

BitMap

setup.cpp中

char*pages_0= (char*)memoryManager.allocatePhysicalPages(AddressPoolType::KERNEL, 128);

调用了 MemoryManager的成员函数allocatePhisicalPages

1717171735091

接着我们进入 allocatePhysicalPages,这里的resources是一个Bitmap变量，allocate在给的代码中默认采用的是first_fit的算法，Bitmap::allocate的功能是按照分配方式找到位图对应的位置，都置为1。位图位与内核空间中。

第一次调用 Bitmap::allocate的返回值为0，分配完128pages，后第二次调用 Bitmap::allocate返回值为128（返回值为分配时bitmap数组的起始位置）

则 AddressPool::allocate的返回值为PAGE_SIZE*start+startAddress 即从哪个地址开始分配 ,这里的startAddress可认为是起始地址的基址，是2097152，即0x200000。

1717172406777

release的过程类似:(address - startAddress/PAGE_SIZE)算出bitmap对应的位置index,然后从该位置开始把后面count个元素置零。

Assignment2

  • first_fit：从低地址开始搜索,找到第一个可以容纳请求块的空闲分区
  • best_fit：从所有可用分区中找到最小的能够满足请求的分区
  • worst_fit：从所有可用分区中找到最大的能够满足请求的分区
    具体实现见关键代码处

Assignment3

虚拟页内存分配的三步：

  • 从虚拟地址池中分配连续的多个虚拟页 。1717297841023
    我们建立了用户虚拟地址池,首先定义虚拟地址起始地址的宏，使得分配的页空间虚拟地址仅在3-4GB之
    间
1
#define KERNEL_VIRTUAL_START 0xc0100000

从地址池中分配count个连续页的过程在assignment1中已经提到，不再赘述。
这是 kernel/memory.cpp中的 MemoryManager::allocatePages函数：

1
int MemoryManager::allocatePages(enum AddressPoolType type, const int count);
1
2
3
4
5
6
// 第一步：从虚拟地址池中分配若干虚拟页
int virtualAddress = allocateVirtualPages(type, count);
if (!virtualAddress)
{
    return 0;
}

接下来，我们要开始为每一个虚拟页指定物理页，这件事分为两步，先分配虚拟页，再建立虚拟页和物理页的联系。分配过程和之前一样

  • 从物理地址池中为每一个虚拟页分配相应大小的物理页 。
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
bool flag;
int physicalPageAddress;
int vaddress = virtualAddress;

// 依次为每一个虚拟页指定物理页
for (int i = 0; i < count; ++i, vaddress += PAGE_SIZE)
{
    flag = false;
    // 第二步：从物理地址池中分配一个物理页
    physicalPageAddress = allocatePhysicalPages(type, 1);
    if (physicalPageAddress)
    {
        //printf("allocate physical page 0x%x\n", physicalPageAddress);

        // 第三步：为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。
        flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
    }
    else
    {
        flag = false;
    }

    // 分配失败，释放前面已经分配的虚拟页和物理页表
    if (!flag)
    {
        // 前i个页表已经指定了物理页
        releasePages(type, virtualAddress, i);
        // 剩余的页表未指定物理页
        releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
        return 0;
    }
}

return virtualAddress;

  • 在页目录表和页表中建立虚拟页和物理页之间的对应关系 。此时，由于分页机制的存在，物理页的地址可以不连续。CPU的MMU会在程序执行过程中将虚拟地址翻译成物理地址。

我们具体来看这个函数：connectPhysicalVirtualPage(vaddress, physicalPageAddress);

1717315484763

  • 首先得到虚拟地址对应的页目录项pde和页表项pte
  • 如果页目录项无页表则1.分配物理页给页表 2.使页目录项指向页表 3.进行空间的分配
  • 有的话直接将页表项指向物理页

一些关键代码的解释:
*pde & 0x00000001表示获取存在位（P位），若为0则取分配物理页

1717316547661

将页表项指向物理页，*physicalPageAddress | 0x7中的按位或运算是为了设置页目录项的标志位

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
bool MemoryManager::connectPhysicalVirtualPage(const int virtualAddress, const int physicalPageAddress)
{
    // 计算虚拟地址对应的页目录项和页表项
    int *pde = (int *)toPDE(virtualAddress);
    int *pte = (int *)toPTE(virtualAddress);

    // 页目录项无对应的页表，先分配一个页表
    if(!(*pde & 0x00000001)) 
    {
        // 从内核物理地址空间中分配一个页表
        int page = allocatePhysicalPages(AddressPoolType::KERNEL, 1);
        if (!page)
            return false;

        // 使页目录项指向页表
        *pde = page | 0x7;
        // 初始化页表
        char *pagePtr = (char *)(((int)pte) & 0xfffff000);
        memset(pagePtr, 0, PAGE_SIZE);
    }

    // 使页表项指向物理页
    *pte = physicalPageAddress | 0x7;

    return true;
}

释放内存过程：分为两步,首先释放物理页再释放虚拟页。

要注意把页表项pte置空，防止再次被访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void MemoryManager::releasePages(enum AddressPoolType type, const int virtualAddress, const int count)
{
    int vaddr = virtualAddress;
    int *pte;
    for (int i = 0; i < count; ++i, vaddr += PAGE_SIZE)
    {
        // 第一步，对每一个虚拟页，释放为其分配的物理页
        releasePhysicalPages(type, vaddr2paddr(vaddr), 1);

        // 设置页表项为不存在，防止释放后被再次使用
        pte = (int *)toPTE(vaddr);
        *pte = 0;
    }

    // 第二步，释放虚拟页
    releaseVirtualPages(type, virtualAddress, count);
}

通过打印测试用例发现，确实达到了虚拟内存连续分配，物理内存分配不连续的效果

测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
    char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);

    printf("%x %x %x\n", p1, p2, p3);

    memoryManager.releasePages(AddressPoolType::KERNEL, (int)p2, 10);
    p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);

    printf("%x\n", p2);

    p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
  
    printf("%x\n", p2);

虚拟内存分配结果:p2释放后重新分配100页的空间时，从0xc01d2000,而分配10页空间时从原来释放内存的0x164000开始

1717372803677

物理内存则在分配100页时从原来释放的地址的开始，如果孔空间不够继续找到下一个空的空间。

一些bug:

没有使用互斥机制导致不同线程可能都进入临界区，分配到相同的物理地址。我们延长了等待时间使得这个错误发生。具体错误见实验结果处。

解决方案：使用信号量解决.

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
Semaphore semaphore;
void MemoryManager::initialize()
{
    semaphore.initialize(1);
...
}

int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    semaphore.P();
  
    // 第一步：从虚拟地址池中分配若干虚拟页
    int virtualAddress = allocateVirtualPages(type, count);
  
    if (!virtualAddress)
    {
        return 0;
    }

    bool flag;
    int physicalPageAddress;
    int vaddress = virtualAddress;
  
    // 依次为每一个虚拟页指定物理页
    for (int i = 0; i < count; ++i, vaddress += PAGE_SIZE)
    {
        flag = false;
        // 第二步：从物理地址池中分配一个物理页
        physicalPageAddress = allocatePhysicalPages(type, 1);

        if (physicalPageAddress)
        {

            //printf("allocate physical page 0x%x\n", physicalPageAddress);

            // 第三步：为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。
            flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
        }
        else
        {
            flag = false;
        }
    semaphore.V();
        // 分配失败，释放前面已经分配的虚拟页和物理页表
        if (!flag)
        {
            // 前i个页表已经指定了物理页
            releasePages(type, virtualAddress, i);
            // 剩余的页表未指定物理页
            releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
            return 0;
        }
    }

    return virtualAddress;
}

还有可能在其他地方也会出现没有互斥访问导致的问题没有解决。

Assignment 4

本实验中我在win环境中模拟LRU

LRU页面置换

核心原理是基于“最近使用的数据将来被使用的概率更高”这一假设，即如果一个数据最近被访问过，那么它在不久的将来很可能再次被访问；相反，如果一个数据很长时间没有被访问，那么它在将来被访问的概率较低。我们使用一个times变量来记录多少次没有被访问过，取最大的淘汰。

实现代码见关键代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>

using namespace std;
struct memory{
	int id;
	int times;
};
class LRUCache {
private:
    int num; // 元素数量
    int capacity; // 缓存空间
    memory mem[3];

public:
    LRUCache(int capacity){
        this->capacity = capacity;
        num = 0;
        for(int i = 0;i<capacity;i++){
        	mem[i].id = -1;
        	mem[i].times = 0;
		}
    }
	void tihuan(int k){
		int max = -1;
		int max_id = -1;
		for(int i = 0;i<num;i++){
			if(mem[i].times>max){
				max = mem[i].times;
				max_id = i;
			}
		}
		printf("%d被替换为%d\n",mem[max_id].id,k);
		mem[max_id].id= k;
		mem[max_id].times = 0;

	}
	bool find(int n){
		int flag = 0;
		for(int i = 0;i<num;i++){
			if(mem[i].id== n){
				flag = 1;
				mem[i].times = 0;
				break;
			}
		}
		return flag;

	}
    void put(int k){
    	for(int i = 0;i<num;i++){
    		mem[i].times++;
		}
    	if(!find(k)){
    		if(num<capacity){
    			mem[num].id=k;
    			mem[num].times=0;
    			num++;
			}else{
				tihuan(k);
			}
    	
		}else{
			printf("id %d hit\n",k);
		}

		printf("page id now:\n");
		for(int i = 0;i<num;i++){
			printf("%d ",mem[i].id);

		}
		printf("\n");

	}
};
int main() {
	int seq[10]= {7,0,1,2,0,3,0,4,2,3};
    LRUCache cache1(3); // 设置缓存容量为3
	for(int i=0; i<10;i++){
		cache1.put(seq[i]);
	}

    return 0;
}

3. 关键代码

Assignment1中分配内存用的是和Assignment2一样的测试代码

Assignment2中first_fit:

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
int BitMap::allocate(const int count)
{
    if (count == 0)
        return -1;

    int index, empty, start;

    index = 0;
    while (index < length)
    {
        // 越过已经分配的资源
        while (index < length && get(index))
            ++index;

        // 不存在连续的count个资源
        if (index == length)
            return -1;

        // 找到1个未分配的资源
        // 检查是否存在从index开始的连续count个资源
        empty = 0;
        start = index;
        while ((index < length) && (!get(index)) && (empty < count))
        {
            ++empty;
            ++index;
        }

        // 存在连续的count个资源
        if (empty == count)
        {
            for (int i = 0; i < count; ++i)
            {
                set(start + i, true);
            }

            return start;
        }
    }

    return -1;
}

best_fit:使用min_space和min_start记录当前最小且大于count的最小空间，和其对应的起始地址。

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
int BitMap::best_fit(const int count){
	if (count == 0)
        return -1;

    int index, empty, start;
    int min_space = 0xffffff;
    int min_start = 0;
    index = 0;
    while (index < length)
    {
        // 越过已经分配的资源
        while (index < length && get(index)){
            ++index;
        }
        
        // 不存在连续的count个资源
        if (index == length)
            break;

        // 找到1个未分配的资源
        // 检查是否存在从index开始的连续count个资源
        empty = 0;
        start = index;
        while ((index < length) && (!get(index)))
        {
            ++empty;
            ++index;
        }

        if(empty>=count && empty<min_space){
            min_space = empty;
            min_start = start;
        }
    
        // 存在连续的count个资源

    }
    if(min_space == 0xffffff){
        return -1;

    }
    start = min_start;
    for (int i = 0; i < count; ++i)
            {
                set(start + i, true);
            }

            return start;

}

worst_fit:则与best_fit相反

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
int BitMap::worst_fit(const int count){
    if (count == 0)
        return -1;

    int index, empty, start;
    int max_space = -1;
    int max_start = 0;
    index = 0;
    while (index < length)
    {
        // 越过已经分配的资源
        while (index < length && get(index)){
            ++index;
        }
  
        // 不存在连续的count个资源
        if (index == length)
            break;

        // 找到1个未分配的资源
        // 检查是否存在从index开始的连续count个资源
        empty = 0;
        start = index;
        while ((index < length) && (!get(index)))
        {
            ++empty;
            ++index;
        }

        if(empty>=count && empty>max_space){
            max_space = empty;
            max_start = start;
        }
  
        // 存在连续的count个资源

    }
    if(max_space == -1){
        return -1;

    }
    start = max_start;
    for (int i = 0; i < count; ++i)
            {
                set(start + i, true);
            }

            return start;
}

Assignment4

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>

using namespace std;
struct memory{
	int id;
	int times;
};
class LRUCache {
private:
    int num; // 元素数量
    int capacity; // 缓存空间
    memory mem[3];

public:
    LRUCache(int capacity){
        this->capacity = capacity;
        num = 0;
        for(int i = 0;i<capacity;i++){
        	mem[i].id = -1;
        	mem[i].times = 0;
		}
    }
	void tihuan(int k){
		int max = -1;
		int max_id = -1;
		for(int i = 0;i<num;i++){
			if(mem[i].times>max){
				max = mem[i].times;
				max_id = i;
			}
		}
		printf("%d被替换为%d\n",mem[max_id].id,k);
		mem[max_id].id= k;
		mem[max_id].times = 0;

	}
	bool find(int n){
		int flag = 0;
		for(int i = 0;i<num;i++){
			if(mem[i].id== n){
				flag = 1;
				mem[i].times = 0;
				break;
			}
		}
		return flag;

	}
    void put(int k){
    	for(int i = 0;i<num;i++){
    		mem[i].times++;
		}
    	if(!find(k)){
    		if(num<capacity){
    			mem[num].id=k;
    			mem[num].times=0;
    			num++;
			}else{
				tihuan(k);
			}
  
		}else{
			printf("id %d hit\n",k);
		}

		printf("page id now:\n");
		for(int i = 0;i<num;i++){
			printf("%d ",mem[i].id);

		}
		printf("\n");

	}
};
int main() {
	int seq[10]= {7,0,1,2,0,3,0,4,2,3};
    LRUCache cache1(3); // 设置缓存容量为3
	for(int i=0; i<10;i++){
		cache1.put(seq[i]);
	}

    return 0;
}

4. 实验结果

Assignment 2

分配四次，释放两次内存后的内存空间如左图所示，右侧是采用不同方法继续分配两次空间后的结果

1717131430906

1717116874977

best_fit:

可以看到，

1717086633066

worst_fit

1717130935790

Assignment 3

没有实现互斥机制时的错误：分配到了同样的虚拟地址

测试用例：

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
memoryManager memoryManager;
void second_thread(void *arg)
{
    char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
    printf("thread2 %x\n",p2);
}
void third_thread(void *arg)
{
    char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
    printf("thread3 %x\n",p3);
}
void first_thread(void *arg)
{

    int pid1 = programManager.executeThread(second_thread, nullptr, "second thread", 1);
    int pid2 = programManager.executeThread(third_thread, nullptr, "third thread", 1);
  
    // 第1个线程不可以返回
    // stdio.moveCursor(0);
    // for (int i = 0; i < 25 * 80; ++i)
    // {
    //     stdio.print(' ');
    // }
    // stdio.moveCursor(0);

    char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
    printf("thread1 %x\n",p1);

1717376584481

改正后的结果：

1717348305387

Assignment 4

LRU算法，引用串为7,0,1,2,0,3,0,4,2,3，可用帧为3时的结果

1717347573550

5. 总结

通过这次实验，我更加深刻认识到内存管理的重要意义，了解了二级页表的实现机制。了解了位图，内存池等相关概念和实现。了解了虚拟内存管理机制，页内存的分配和释放过程，最后实现用FIFO算法实现了页面置换。用LRU算法在win环境下模拟了页面置换的过程。

发表于 更新于

实验名称: Lab6 并发与锁机制

学生姓名: 庄云皓

学生学号: 22336327

1. 实验要求

Assignment 1 代码复现题

1.1 代码复现

在本章中，我们已经实现了自旋锁和信号量机制。现在，同学们需要复现教程中的自旋锁和信号量的实现方法，分别使用二者解决一个同步互斥问题，如消失的芝士汉堡问题。最后，将结果截图并说说你是怎么做的。

1.2 锁机制的实现

我们使用了原子指令 xchg来实现自旋锁。但是，这种方法并不是唯一的。例如，x86指令中提供了另外一个原子指令 bts和 lock前缀等，这些指令也可以用来实现锁机制。现在，同学们需要结合自己所学的知识，实现一个与本教程的实现方式不完全相同的锁机制。最后，测试你实现的锁机制，将结果截图并说说你是怎么做的。

提示：在 asm_utils.asm中实现你自己的原子操作 your_asm_atomic_exchange，并在 sync.cpp中做相应修改。

Assignment 2 生产者-消费者问题

2.1 Race Condition

同学们可以任取一个生产者-消费者问题，然后在lab6的代码环境下创建多个线程来模拟这个问题。在2.1中，我们不使用任何同步互斥的工具。因此，这些线程可能会产生冲突，进而无法产生我们预期的结果。同学们需要将这个产生错误的场景呈现出来，将结果截图并说说你是怎么做的。

2.2 信号量解决方法

使用信号量解决上述你模拟的生产者-消费者问题。将结果截图并说说你是怎么做的。

提示：

①经典的生产者-消费者问题有读者-写者问题、有界缓冲区问题等，可任取一个来模拟。

②模拟生产者-消费者问题的步骤：1、在代码中创建多个线程，分别代表生产者和消费者。2、编写生产者和消费者的线程函数。在这些函数中，根据问题的具体场景实现生产数据和消费数据的逻辑。3、创建并启动生产者和消费者线程。观察线程之间的交互并记录结果。4、展示没有使用同步互斥工具（如信号量）时，线程之间可能产生的冲突。5、使用信号量解决同步问题，并展示解决后的结果。

③样例视频模拟了读者-写者问题的场景：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//模拟读错误
//创建线程读第1-4条记录
programManager.executeThread(readFirstQuote, nullptr, "second thread", 1);
programManager.executeThread(readSecondQuote, nullptr, "third thread", 1);
programManager.executeThread(readThirdQuote, nullptr, "fourth thread", 1);
programManager.executeThread(readFourthQuote, nullptr, "fifth thread", 1);
//创建线程，修改第2条和第4条记录为较长内容
//由于写时间较长，写线程运行时间大于RRschedule的time quantum
programManager.executeThread(writeSecondQuote, nullptr, "sixth thread", 1);
programManager.executeThread(writeFourthQuote, nullptr, "seventh thread", 1);
//创建线程读第2条和第4条记录
//发现没有读到修改后的项，而是输出了初始项
programManager.executeThread(readSecondQuote, nullptr, "eighth thread", 1);
programManager.executeThread(readFourthQuote, nullptr, "ninth thread", 1);

而使用信号量后，可以读到修改后的项。

Assignment 3 哲学家就餐问题

假设有 5 个哲学家，他们的生活只是思考和吃饭。这些哲学家共用一个圆桌，每位都有一把椅子。在桌子中央有一碗米饭，在桌子上放着 5 根筷子。

哲学家就餐问题

当一位哲学家思考时，他与其他同事不交流。时而，他会感到饥饿，并试图拿起与他相近的两根筷子（筷子在他和他的左或右邻居之间）。一个哲学家一次只能拿起一根筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时拥有两根筷子时，他就能吃。在吃完后，他会放下两根筷子，并开始思考。

3.1 初步解决方法

同学们需要在本教程的代码环境下，创建多个线程来模拟哲学家就餐的场景。然后，同学们需要结合信号量来实现理论课教材中给出的关于哲学家就餐问题的方法。最后，将结果截图并说说你是怎么做的。

该方案可能导致死锁，请举例出现死锁的场景和原因，并提出一种解决死锁的方案。

3.2 死锁解决方法（选做）

虽然3.1的解决方案保证两个邻居不能同时进食，但是它可能导致死锁。现在，同学们需要想办法将死锁的场景演示出来。提出一种解决死锁的方法并实现。最后，将结果截图并说说你是怎么做的。

说明：

①为演示死锁场景，可以在哲学家进食的线程中添加等待时间，使哲学家们的操作更接近于同时进行。

②样例视频演示了等待时间较少——正常、等待时间较长——出现死锁。

2. 实验过程

Assignment1

1.1.1自旋锁实现方法

spinlock中private变量是两个线程有公用的变量bolt,初始化为0

  • 局部变量key初始化为1
  • 当第一个线程请求进入临界区时，将bolt和key交换，bolt为1，key为0，跳出循环进入临界区。
  • 此时其他线程如果想要进入临界区，它的key初始化为1，bolt为1，交换后key仍然为1，循环等待（自旋）

交换的过程见关键代码部分。

观察是否解决了消失的芝士汉堡问题

1.1.1信号量实现方法

在include/sync.h下定义信号量Semaphore类。类中变量couter.表示已有资源数

  • P():只要counter>0则把counter-=1;如果county已经=0则把当前线程放进等待队列，将线程状态置为blockecd
  • V():counter++,获取等待队列队首元素并唤醒。

在在first_thread里将semaphore 初始化为1，然后在调用 mother函数在mycheese_burger+=10 前P,在print汉堡剩余量之后V防止在这段时间内汉堡被偷吃。

1.2 锁机制的实现

bts指令(bit test and set)作用就是设置内容中的一个位为1, 会首先判断该位是否已经为1，是就返回1，不是则置为1,然后返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
my_spinlock_lock:
    push ebp
    mov ebp, esp
    pushad
.loop:
    mov ebx, [ebp + 4 * 2]
    mov edx, 0
    lock bts dword [ebx], edx;test and set 第零位；若为0则将其置1，并将原来的值保存进CF,
    ;第零位若为1则 CF = 1

    jc .loop ;CF为1则跳转

    popad
    pop ebp
    ret

观察这段上锁的函数，我们 .loop循环中，[ebx]的值是传进函数的参数，即 bolt变量。bts语句的作用是首先判断 bolt是否为0，如果是的话就将其改为1，将CF寄存器置0，如果是1则bolt不变，CF = 1

这段代码能实现互斥访问的原因是：初始化bolt为0，如果一个进程在进入临界区时会将bolt改为1，如果此时被另一个进程抢占的话，bolt就仍然为1，循环等待。直到原进程调用 unlock函数将bolt置为0，另一个进程才能跳出.loop循环，进入临界区域。bts指令保证了操作的原子性。

Assignment2

Assignment 2.1

一个错误场景：

观察下面这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void producer(void* arg){
    while(true){
        if(cnt < MAX_BUFFER_SIZE){
            int delay = 0xffffff;
            while(delay){
                delay--;
            }
            buffer[cnt] = 1;
            cnt++;
            printf("produced an item, cnt = %d\n",cnt);
            if(cnt > MAX_BUFFER_SIZE){
                printf("overflow\n");
        }
        }
    }
}

没有实现PV操作时的错误场景：

可以看到当前buffer数组中的元素已经有MAX_SIZE-1个时，一个线程判断if(cnt<MAX_SIZE)符合条件进入，在cnt++之前被调度下处理器。

另外一个线程调度上处理器，同样满足if(cnt<MAX_SIZE)的条件，进入临界区域，cnt++。

之前被调度下来的进程重新进入running状态时cnt也++,导致cnt>MAX_SIZE,出现溢出。

underflow的情况以此类推。

Assignment 2.2

信号量解决方案：

三个信号量

  • empty_slots：初始化值为MAX_SIZE
  • full_slots: 初始化值为0
  • mutex:初始化值为1

每次进入临界区之前，empty_slots.P()使empty_slots.counter–， mutex.P()保证互斥访问。如果不加 mutex.P()的话，可能出现的情况是：MAX_SIZE大于等于2时，那么就可能有多个线程进入product的核心代码段，产生常见的资源共享问题。

从临界区出来时，要把full_slots++，mutex解锁。

这里要注意的是：empty_slots.P()和 mutex.P()不能交换顺序，这是因为，如果交换顺序，buffer为满时会死锁，因为当一个线程进入了临界区，mutex上锁，empty_slots->counter=MAX_SIZE-1,循环等待，此时切换到另一个线程，因为已经上锁的缘故无法进行生产的.

同理 full_slots.P()和 mutex.P()也不能交换顺序

1
2
3
4
5
6
empty_slots.P();
mutex.P();
buffer[cnt] = 1;
cnt++;
mutex.V();
full_slots.V();

Assignment 3

3.1

五个线程模拟五个哲学家，设置容量为5的信号量数组模拟筷子。对哲学家按顺序从 0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为 (i+l)%5。

算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷子的时候（都恰好执行完 chopstick[i].wait();)筷子已经被拿光了，等到他们再想拿右边的筷子的时候（执行 wait(chopstick[(i+l)%5].wait())就全被阻塞了，这就出现了死锁。

3.2

  • solution1

一共有五个哲学家，只允许四位哲学家同时处于拿起筷子的状态，这样就不会出现有五个哲学家全都拿起左边的筷子导致死锁或者都拿起右边的筷子的情形。

需要设置一个信号量num,初始化为4，在拿起筷子前num.P(),放下筷子之后num.V()

  • solution2

解决这个问题有个办法是在拿起筷子前先判断左右两个筷子是否可用，可用才能拿，而且是同时拿，这样不相邻的哲学家就可以吃上饭，不会造成死锁。

实现这个思路又有两种具体的策略

    • i 条件 (chopsticks[lhs].getcounter() &&chopsticks[rhs].getcounter())成立才把左边和右边的筷子进行P操作。
    • ii采用另一个信号量 mutex进行控制，保证拿起左右手的筷子这一操作变为原子的，不能多个线程同时进行拿起左右手筷子的操作

3. 关键代码

Assignment 1

1.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
; void asm_atomic_exchange(uint32 *register, uint32 *memeory);
asm_atomic_exchange:
    push ebp
    mov ebp, esp
    pushad

    mov ebx, [ebp + 4 * 2] ; register
    mov eax, [ebx]      ; 取出register指向的变量的值
    mov ebx, [ebp + 4 * 3] ; memory
    xchg [ebx], eax      ; 原子交换指令
    mov ebx, [ebp + 4 * 2] ; memory
    mov [ebx], eax      ; 将memory指向的值赋值给register指向的变量

    popad
    pop ebp
    ret

信号量解决方案：

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
Semaphore semaphore;

int cheese_burger;

void a_mother(void *arg)
{
    semaphore.P();
    int delay = 0;

    printf("mother: start to make cheese burger, there are %d cheese burger now\n", cheese_burger);
    // make 10 cheese_burger
    cheese_burger += 10;

    printf("mother: oh, I have to hang clothes out.\n");
    // hanging clothes out
    delay = 0xfffffff;
    while (delay)
        --delay;
    // done

    printf("mother: Oh, Jesus! There are %d cheese burgers\n", cheese_burger);
    semaphore.V();
}

void a_naughty_boy(void *arg)
{
    semaphore.P();
    printf("boy   : Look what I found!\n");
    // eat all cheese_burgers out secretly
    cheese_burger -= 10;
    // run away as fast as possible
    semaphore.V();
}

1.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
my_spinlock_lock:
    push ebp
    mov ebp, esp
    pushad
.loop:
    mov ebx, [ebp + 4 * 2]
    mov eax, 1
    mov edx, 0
    lock bts dword [ebx], edx;test and set 第零位；若为0则将其置1，并将原来的值保存进CF,
    ;第零位若为1则 CF = 1

    jc .loop ;CF为1则跳转

    popad
    pop ebp
    ret

Assignment2

2.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
# define MAX_BUFFER_SIZE 1
int buffer[MAX_BUFFER_SIZE];
int cnt = 0;
void producer(void* arg){
    while(true){
        if(cnt < MAX_BUFFER_SIZE){
  

            int delay = 0xffffff;
            while(delay){
                delay--;
            }
            buffer[cnt] = 1;
            cnt++;
            printf("produced an item, cnt = %d\n",cnt);
            if(cnt > MAX_BUFFER_SIZE){
                printf("overflow\n");
        }
        }
    }
}
void consumer(void* arg){
    while(true){
        if(cnt > 0){

            int delay = 0xffffff;
            while(delay){
                delay--;
            }

            cnt--;
            printf("consumerd an item, cnt = %d\n",cnt);
            if(cnt<0){
                printf("underflow\n");
            }
            buffer[cnt] = 0;
        }
    }
}

2.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
33
34
35
36
37
38
39
40
41
42
43
# define MAX_BUFFER_SIZE 1
int buffer[MAX_BUFFER_SIZE];
int cnt = 0;
void producer(void* arg){
    while(true){
        //if(cnt < MAX_BUFFER_SIZE){
            int delay = 0xffffff;
            while(delay){
                delay--;
            }
            empty_slots.P();
            mutex.P();
            buffer[cnt] = 1;
            cnt++;
            mutex.V();
            full_slots.V();
            printf("produced an item, cnt = %d\n",cnt);
            if(cnt > MAX_BUFFER_SIZE){
                printf("overflow\n");
        }
       // }
    }
}
void consumer(void* arg){
    while(true){
        //if(cnt > 0){
            full_slots.P();// 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
            mutex.P(); // 保证在product时不会有其他线程访问缓冲区
            int delay = 0xffffff;
            while(delay){
                delay--;
            }
            cnt--;
            buffer[cnt] = 0;
            mutex.V();
            empty_slots.V(); // 通知consumer缓冲区有资源可以取走
            printf("consumerd an item, cnt = %d\n",cnt);
            if(cnt<0){
                printf("underflow\n");
            }
        //}
    }
}

Assignment3

3.2-solution1

num初始化为4，在拿起筷子前num.P(),放下筷子之后num.V()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Semaphore eaters;
int cnt = 0;
void philosopher(int id){
    while(true){
        int delay =0xffffff;
        num.P();
        printf("philosopher%d is hungry    ",id);
  
        chopsticks[id].P();
        while(delay>0){
            delay--;
        }
        //printf("philosopher%d picked up chopstick%d\n",id,id);
        chopsticks[(id+1)%MAX_SIZE].P();
  
        //printf("philosopher%d picked up chopstick%d\n",id,(id+1)%MAX_SIZE);
        printf("philosopher%d is eating\n",id);
        chopsticks[(id+1)%MAX_SIZE].V();
        //printf("philosopher%d lowered chopstick%d\n",id,id);
        chopsticks[id].V();
        num.V();
        //printf("philosopher%d lowered chopstick%d\n",id,(id+1)%MAX_SIZE);
    }
}

3.2-solution2

mutex->counter初始化为1，保证一个哲学家左右两根筷子都会被拿起

1
2
3
4
5
6
7
8
mutex.P();
       chopsticks[id].P();
       while(delay>0){
           delay--;
       }
       //printf("philosopher%d picked up chopstick%d\n",id,id);
       chopsticks[(id+1)%MAX_SIZE].P();
       mutex.V();

4. 实验结果

Assignment1 代码复现题

1.1.1使用自旋锁解决消失的芝士汉堡问题

1.1.2使用信号量解决消失的芝士汉堡问题

1714983997122

1.2使用bts实现自旋锁

1716042645677

Assignment2 生产者-消费者问题

2.1Race Condition

1715744966610

2.2采用信号量的解决方案MAX_SIZE = 1时

1716042964914

Assignment3 哲学家就餐问题

出现死锁情况：

1715774700068

避免死锁情况：

1716035988152

5. 总结

在这次实验中通过改变几个经典同步问题，我学习了自旋锁的实现，信号量的使用等基本知识，进一步了解了互斥访问的问题，使用SpinLock和信号量来给出实现线程互斥的解决方案。加深了对理论课知识的理解。

发表于 更新于

title:SYSU-2024操作系统lab3实验报告

date:2024-04-28 23:54:26

tags:os

comments:true

author:zyh

实验名称: Lab5 内核线程

学生姓名: 庄云皓

学生学号: 22336327

实验成绩:

报告时间: 2023-5-5

1. 实验要求

Assignment 1 printf的实现

学习可变参数机制，然后实现printf，你可以在材料中的printf上进行改进，或者从头开始实现自己的printf函数。结果截图并说说你是怎么做的。

Assignment 2 线程的实现

自行设计PCB，可以添加更多的属性，如优先级等，然后根据你的PCB来实现线程，演示执行结果。

Assignment 3 线程调度切换的秘密

操作系统的线程能够并发执行的秘密在于我们需要中断线程的执行，保存当前线程的状态，然后调度下一个线程上处理机，最后使被调度上处理机的线程从之前被中断点处恢复执行。现在，同学们可以亲手揭开这个秘密。

编写若干个线程函数，使用gdb跟踪 c_time_interrupt_handler、asm_switch_thread等函数，观察线程切换前后栈、寄存器、PC等变化，结合gdb、材料中“线程的调度”的内容来跟踪并说明下面两个过程。

  • 一个新创建的线程是如何被调度然后开始执行的。
  • 一个正在执行的线程是如何被中断然后被换下处理器的，以及换上处理机后又是如何从被中断点开始执行的。

通过上面这个练习，同学们应该能够进一步理解操作系统是如何实现线程的并发执行的。

（必做与选做）Assignment 4 调度算法的实现

在材料中，我们已经学习了如何使用时间片轮转算法来实现线程调度。但线程调度算法不止一种，例如

  • 先来先服务。
  • 最短作业（进程）优先。
  • 响应比最高者优先算法。
  • 优先级调度算法。
  • 多级反馈队列调度算法。

此外，我们的调度算法还可以是抢占式的。

现在，同学们需要将线程调度算法修改为上面提到的算法或者是同学们自己设计的算法。然后，同学们需要自行编写测试样例来呈现你的算法实现的正确性和基本逻辑。最后，将结果截图并说说你是怎么做的。（先来先服务为必做，其他为选做）

参考资料：https://zhuanlan.zhihu.com/p/97071815

Tips：

  • 先来先服务最简单。
  • 有些调度算法的实现可能需要用到中断。

2. 实验过程

Assignment 1

1.1可变参数机制

实现这些宏

宏 用法说明
va_list 定义一个指向可变参数列表的指针。
void va_start(va_list ap, last_arg) 初始化可变参数列表指针 ap，使其指向可变参数列表的起始位置，即函数的固定参数列表的最后一个参数 last_arg的后面第一个参数。
type va_arg(va_list ap, type) 以类型 type返回可变参数，并使 ap指向下一个参数。
void va_end(va_list ap) 清零 ap。 
1
2
3
4
5
typedef char *va_list;
#define _INTSIZEOF(n) ((sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1))
#define va_start(ap, v) (ap = (va_list)&v + _INTSIZEOF(v))
#define va_arg(ap, type) (*(type *)((ap += _INTSIZEOF(type)) - _INTSIZEOF(type)))
#define va_end(ap) (ap = (va_list)0)

注意这里的 _INTSIZIOF: ~(sizeof(int) - 1)为0xfffffffc ,任何地址与它&后将低两位清零，为了实现向上对齐，我们需要先加上(sizeof(int)-1)后再和0xfffffffc相与，此时得到的结果就是向上4字节对齐的。

1.2 实现printf增加%b和%f功能

实现了print(“%b,n),j和print(“%f”,n),分别将i以2进制和float浮点数，保留六位小数输出

让我们先解释一下printf实现的过程，我们需要用到可变参数机制，

解释一下printf中的代码：

如果 % 的下一个字符是’\0’，则退出；如果是’c’，则以字符的格式返回一个可变参数列表中的参数，并将其加入缓冲区；如果是’s’，则输出并清空缓冲区，并以char*的格式返回一个可变参数列表中的参数，并直接打印；如果是’d’，则以int的格式返回一个可变参数列表中的参数，转换为字符串后加入缓冲区；如果是’x’，则以int的格式返回一个可变参数列表中的参数，进行进制转换，然后转换为字符串，加入缓冲区；

%b的实现只需把%x中的itos(number, temp, (fmt[i] == ‘d’ ? 10 : 16));改成itos(number, temp, (fmt[i] == ‘d’ ? 10 : 2));

%f的实现参考了printf的实现

简单地说，先把浮点数分成整数部分和小数部分，然后将整数和小数分别转换为单个字符打印。因为是保留六位小数，小数先*1000000再按整数方式来打印，具体代码见关键代码部分

测试一下：

1
2
3
4
5
6
7
8
printf("print percentage: %%\n"
           "print char \"N\": %c\n"
           "print string \"Hello World!\": %s\n"
           "print decimal: \"-1234\": %d\n"
           "print hexadecimal \"0x7abcdef0\": %x\n"
           "print binary \"0b10\": %b\n"
           "print float \"3.1415\": %f\n",
           'N', "Hello World!", -1234, 0x7abcdef0, 0b10,3.1415);

Assignment 2

线程的描述

先介绍一下进程控制块PCB:

在实验中用一个结构体表示，包括栈指针，线程名，状态，优先级，线程id等内容

1
2
3
4
5
6
7
8
9
10
11
12
struct PCB
{
    int *stack;                      // 栈指针，用于调度时保存esp
    char name[MAX_PROGRAM_NAME + 1]; // 线程名
    enum ProgramStatus status;       // 线程的状态
    int priority;                    // 线程优先级
    int pid;                         // 线程pid
    int ticks;                       // 线程时间片总时间
    int ticksPassedBy;               // 线程已执行时间
    ListItem tagInGeneralList;       // 线程队列标识
    ListItem tagInAllList;           // 线程队列标识
};

解释几个变量的含义：
ticks是线程剩余的执行次数。在时间片调度算法中，每发生中断一次记为一个tick，当ticks=0时，线程会被换下处理器，然后将其他线程换上处理器执行。

ticksPassedBy是线程总共执行的tick的次数。

tagInGeneralList和tagInAllList是线程在线程队列中的标识，用于在线程队列中找到线程的PCB。这两个变量的lListItem类型表示队列中的一个元素，是一个结构体，结构体中两个指针变量分别指向前面和后面的元素。用链表来实现进程队列，链表结构详见 ‘include/list.h’

stack线程栈表示如下

1714812925884

对许多线程管理我们需要声明一个声明一个程序管理类 ProgramManager.

用于线程和进程的创建和管理，代码见 include/program.h

1
2
3
4
5
6
7
8
9
#ifndef PROGRAM_H
#define PROGRAM_H

class ProgramManager
{

};

#endif

线程的创建：

1.我们在 include/program.h中对程序管理类 ProgramManager中的变量和函数进行声明。

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
class ProgramManager
{
public:
    List allPrograms;   // 所有状态的线程/进程的队列
    List readyPrograms; // 处于ready(就绪态)的线程/进程的队列
    PCB *running;       // 当前执行的线程
public:
    ProgramManager();
    void initialize();

    // 创建一个线程并放入就绪队列

    // function：线程执行的函数
    // parameter：指向函数的参数的指针
    // name：线程的名称
    // priority：线程的优先级

    // 成功，返回pid；失败，返回-1
    int executeThread(ThreadFunction function, void *parameter, const char *name, int priority);

    // 分配一个PCB
    PCB *allocatePCB();
    // 归还一个PCB
    // program：待释放的PCB
    void releasePCB(PCB *program);

    // 执行线程调度
    void schedule();

    // zu se huan xing
    void MESA_WakeUp(PCB *program);
};

void program_exit();

2.向内存申请PCB空间（以下内容见src/kernel/program.cpp)

（1）声明PCB的空间和PCB分配状态数组

在内存中开辟一个PCB_SIZE * MAX_PROGRAM_AMOUNT个字节的空间用于分配给所有线程的thread->stack。这里我们把PCB大小设置为4096（4kb)

1
char PCB_SET[PCB_SIZE * MAX_PROGRAM_AMOUNT];//MAX_PROGRAM_AMOUNT个PCB的大小空间

再用一个bool类型数组表示PCB分配状态

1
2
// PCB的分配状态，true表示已经分配，false表示未分配。
bool PCB_SET_STATUS[MAX_PROGRAM_AMOUNT];

如果已经给一个线程分配了PCB则将该线程对应的PCB_SET_STATUS中的数置1

（2）allocatePCB和releasePCB

具体进行分配的过程我们通过program_manager中的函数

1
2
3
4
// 分配一个PCB
PCB *allocatePCB();
// 归还一个PCB
void releasePCB(PCB *program);

来实现。两个函数实现的代码放置在 src/kernel/program.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
PCB *ProgramManager::allocatePCB()
{
    for (int i = 0; i < MAX_PROGRAM_AMOUNT; ++i)
    {
        if (!PCB_SET_STATUS[i])
        {
            PCB_SET_STATUS[i] = true;
            return (PCB *)((int)PCB_SET + PCB_SIZE * i);
        }
    }

    return nullptr;
}

这个函数对PCB_SET_STATUS中的元素依次判断看该位置对应的PCB_SET空间是否已经被类配了，如果没有没有则返回第i个PCB的起始地址（对于第𝑖个PCB，PCB_SET的首地址加上i×PCBSIZE𝑖×𝑃𝐶𝐵𝑆𝐼𝑍𝐸就是第i𝑖个PCB的起始地址）

有PCB的分配就有PCB的释放，如下所示。

1
2
3
4
5
void ProgramManager::releasePCB(PCB *program)
{
    int index = ((int)program - (int)PCB_SET) / PCB_SIZE;
    PCB_SET_STATUS[index] = false;
}

releasePCB接受一个PCB指针 program，然后计算出 program指向的PCB在 PCB_SET中的位置，然后将 PCB_SET_STATUS中的对应位置设置 false即可。

（3）excuteThread的实现

在这里我们规定线程只能执行返回值为void，参数为void *的函数
我们在include/Program.h中将上面提到的这个函数定义为ThreadFunction。

1
typedef void(*ThreadFunction)(void *);

在ProgramManager类中声明一个用于创建线程的函数executeThread：

1
2
3
4
5
6
7
    // 创建一个线程并放入就绪队列
    // function：线程执行的函数
    // parameter：指向函数的参数的指针
    // name：线程的名称
    // priority：线程的优先级
    // 成功，返回pid；失败，返回-1
int executeThread(ThreadFunction function, void *parameter, const char *name, int priority);

我们在src/kernel/program.cpp中实现executeThread，如下所示。

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
int ProgramManager::executeThread(ThreadFunction function, void *parameter, const char *name, int priority)
{
    // 关中断，防止创建线程的过程被打断
    bool status = interruptManager.getInterruptStatus();
    interruptManager.disableInterrupt();

    // 分配一页作为PCB
    PCB *thread = allocatePCB();

    if (!thread)
        return -1;

    // 初始化分配的页
    memset(thread, 0, PCB_SIZE);

    for (int i = 0; i < MAX_PROGRAM_NAME && name[i]; ++i)
    {
        thread->name[i] = name[i];
    }

    thread->status = ProgramStatus::READY;
    thread->priority = priority;
    thread->ticks = priority * 10;
    thread->ticksPassedBy = 0;
    thread->pid = ((int)thread - (int)PCB_SET) / PCB_SIZE;

    // 线程栈
    thread->stack = (int *)((int)thread + PCB_SIZE);
    thread->stack -= 7;
    thread->stack[0] = 0;
    thread->stack[1] = 0;
    thread->stack[2] = 0;
    thread->stack[3] = 0;
    thread->stack[4] = (int)function;
    thread->stack[5] = (int)program_exit;
    thread->stack[6] = (int)parameter;

    allPrograms.push_back(&(thread->tagInAllList));
    readyPrograms.push_back(&(thread->tagInGeneralList));

    // 恢复中断
    interruptManager.setInterruptStatus(status);

    return thread->pid;
}

我们现在逐步地分析线程创建的逻辑。

（1）关中断

3-5行保存中断状态然后关中断，诸如PCB分配的工作实际上都需要进行线程互斥处理，我们在这里使用开关中断实现线程互斥为什么开/关中断有效呢？在后面可以看到，我们是在时钟中断发生时来进行线程调度的，因此关中断后，时钟中断无法被响应，线程就无法被调度，直到再次开中断。只要线程无法被调度，那么线程的工作也就无法被其他线程打断，因此就实现了线程互斥。

关中断后，我们需要在函数返回前，也就是第44行恢复中断。

开/关中断等相关的的函数定义在 include/interrupt.h中，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class InterruptManager
{

    ...

    // 开中断
    void enableInterrupt();
    // 关中断
    void disableInterrupt();
    // 获取中断状态
    // 返回true，中断开启；返回false，中断关闭
    bool getInterruptStatus();
    // 设置中断状态
    // status=true，开中断；status=false，关中断
    void setInterruptStatus(bool status);

    ...
};

函数的实现比较简单，放置在 src/interrupt/interrupt.cpp中，这里便不再赘述，现在我们回到 executeThread。

（2）申请PCB空间，对PCB中的内容进行初始化

第8行，关中断后，我们向 PCB_SET申请一个线程的PCB，然后我们在第14行使用 memeset将PCB清0。memeset的声明和定义分别在 include/stdlib.h和 src/utils/stdlib.cpp。

第16-25行，我们设置PCB的成员 name、status、priority、ticks、ticksPassedBy和 pid。这里，线程初始的 ticks我们简单地设置为 10倍的 priority。pid则简单地使用PCB在 PCB_SET的位置来代替。

第28行，我们初始化线程的栈。我们将栈放置在PCB中，而线程的栈是从PCB的顶部开始向下增长的，所以不会与位于PCB低地址的 name和 pid等变量冲突。线程栈的初始地址是PCB的起始地址加上 PCB_SIZE。

第29-36行，我们在栈中放入7个整数值。

  • 4个为0的值是要放到ebp，ebx，edi，esi中的。
  • thread->stack[4]是线程执行的函数的起始地址。
  • thread->stack[5]是线程的返回地址，所有的线程执行完毕后都会返回到这个地址。
  • thread->stack[6]是线程的参数的地址。

至于这4部份的作用我们在线程的调度中统一讲解。

（3）将线程放进 allPrograms和 readyPrograms

创建完线程的PCB后，我们将其放入到 allPrograms和 readyPrograms中，等待时钟中断来的时候，这个新创建的线程就可以被调度上处理器。

（4)开中断

最后我们将中断的状态恢复，此时我们便创建了一个线程。

Assignment 3

3.1一个新创建的线程是如何被调度然后开始执行?

我们来看setup.cpp中调用的汇编函数asm_switch_thread(0, firstThread);
将参数和返回地址压栈后，我们将 ebp，ebx，edi，esi 依次压栈（因为这几个存器的值可能会在被调函数中被修改，要先保护起来）。现在的栈状态如下：

1714905739957

29行[esp+5 * 4]表示PCB * cur这个指针变量的值（也就是指向空间的地址），把它赋值给eax。32行[esp+6 * 4]则是PCB *next.

注意30行保存当前栈指针esp到PCB::stack中.[eax]就是PCB * cur这个指针变量的值, 因为PCB第一个变量就是int stack,[eax]其实就是PCB::stack所在地址(int*)((int)thread+PCB_SIZE)-7

下面32-33行我们将PCB next值写入eax,将next->stack的值写入esp
也就是说，现在esp由原来线程的stack切换为了next->stack.

1714908742419

通过调试过程来具体观察一下：
初始时esp为0x7bc0,

1714840614902

33行之后，可以看到esp的值变成了thread1的stack的地址,接着36行到39行弹出thread1的栈中内容（全都是0）到四个寄存器中。因为现在的esp已经变成了thread1的stack,返回地址也是函数first_thread的首地址。ret执行后就跳转到了first_thread函数。（如下图所示，先pop4个0到寄存器，然后返回，返回地址是function的地址）

1714909688608
1714909446513
然后我们便进入了first_thread
1714909863122

3.2一个正在执行的线程是如何被中断然后被换下处理器的，以及换上处理器后又是如何从被中断点开始执行的?

现在我们着重关注RR时间片轮转调度的过程，首先在中断处理函数处设置断点：

1714910381025

观察cur->ticks和cur->ticksPassedBy的变化
1714910209537

每一次发生时钟中断时，中断处理函数都会将当前进程PCB的ticks-1,ticksPassedBy+1,当cur->ticks为0时进行进程切换。

接下来我们观察这个进程如何被换下处理器。时间片用完后进行调度，进入schedule函数内部，因为当前进程还在运行，我们把它放在ready队列的队尾，并将ticks重置。

1714911275547

接着获取ready队列的头一个元素，简单做一些变量的修改后，把ready队列头pop出来，接着我们又进入了asm_swith_thread(cur,next)

1714911725209

进行线程栈的切换，ret后返回second_thread.

1714912484030

thread1已经被换下处理器了，thread1下一次被换上处理器是具体如何执行的呢?

thread3的时间片用完以后，进入scedule函数，调用asm_swith_thread(cur,next),此时的next指向的是thread1,因为thread1已经不是新的进程了，此时它的ebp不为0.

1714913439195

注意到，这里函数返回地址132695是schedule函数中调用asm_swith_thread(cur,next)语句的地址，调用完该函数后返回原来位置。然后schedule函数执行完，继续执行完他所在的c_time_interrupt_handle后返回asm_time_interrupt_handle，该函数iret后返回了thread1执行到的位置，也就是asm_halt中的死循环。

1714913635709

1714914114783

Assignment 4

4.1FIFO

相比于assignment23修改了：

c_time_interrupt_handler()中把队cur->ticks的处理全都去掉

线程都没有死循环

void program_exit()中如果ready队列非空则进行调度。

1
2
3
4
if (!programManager.readyPrograms.empty())
{
    programManager.schedule();
}

结果见实验结果

4.1优先级调度

在ProgramManager::schedule()函数中找当前ready队列优先级最大的任务，具体代码见关键代码部分

将thread1,2,3的优先级分别设置为1,2,3,那么会依次执行thread3,2,1,结果见实验结果部分

3. 关键代码

Assignment1

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
case 'f':{
                // 接收浮点型 保留6为小数，不采取四舍五入
                float ArgFloVal = va_arg(ap, double);
                if (ArgFloVal < 0)
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    ArgFloVal = -ArgFloVal;
                }
                unsigned long val_seg = (unsigned long)ArgFloVal;// 取整数部分
                unsigned long val_temp = val_seg;      // 临时保存整数部分数据
                ArgFloVal = ArgFloVal - val_seg;// 得出余下的小数部分
                // 计算整数部分长度
                int cnt = 0;
                if (val_seg)
                {
                    while (val_seg) {
                        cnt++;
                        val_seg /= 10;
                    }
                }
                else cnt = 1;// 数字0的长度为1
                //counter += cnt;// 字符个数加上整数的长度
                // 将整数转为单个字符打印
                while (cnt)
                {
                    val_seg = val_temp / m_pow_n(10, cnt - 1);
                    val_temp %= m_pow_n(10, cnt - 1);
                    //my_send_char((char)val_seg + '0');
                    counter += printf_add_to_buffer(buffer, (char)val_seg + '0', idx, BUF_LEN);
                    cnt--;
                }
                // 打印小数点
                counter += printf_add_to_buffer(buffer,'.', idx, BUF_LEN);

                // 开始输出小数部分
                ArgFloVal *= 1000000;
                // printf("\r\n %f\r\n", ArgFloVal);
                cnt = 6;
                val_temp = (int)ArgFloVal;// 取整数部分
                while (cnt)
                {
                    val_seg = val_temp / m_pow_n(10, cnt - 1);
                    val_temp %= m_pow_n(10, cnt - 1);
                    counter += printf_add_to_buffer(buffer, (char)val_seg + '0', idx, BUF_LEN);
                    //my_send_char((char)val_seg + '0');
                    cnt--;
                }
                //ret_num += 6;
                //pStr++;
				break;
            }
            case 'd':{
             int temp = va_arg(ap, int);

                if (temp < 0)
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    temp = -temp;
                }

                itos(number, temp, 10 );

                for (int j = 0; number[j]; ++j)
                {
                    counter += printf_add_to_buffer(buffer, number[j], idx, BUF_LEN);
                }
                break;
            }
            case 'b':{
                int temp = va_arg(ap, int);

                if (temp < 0 && fmt[i] == 'd')
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    temp = -temp;
                }

                itos(number, temp, (fmt[i] == 'd' ? 10 : 2));

                for (int j = 0; number[j]; ++j)
                {
                    counter += printf_add_to_buffer(buffer, number[j], idx, BUF_LEN);
                }
                break;
            }

Assignment3

代码的解释见实验过程部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
asm_switch_thread:
    push ebp
    push ebx
    push edi
    push esi

    mov eax, [esp + 5 * 4]
    mov [eax], esp ; 保存当前栈指针到PCB中，以便日后恢复

    mov eax, [esp + 6 * 4]
    mov esp, [eax] ; 此时栈已经从cur栈切换到next栈

    pop esi
    pop edi
    pop ebx
    pop ebp

    sti
    ret

Assignment 4

优先级调度

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
void ProgramManager::schedule()
{
    bool status = interruptManager.getInterruptStatus();
    interruptManager.disableInterrupt();

    if (readyPrograms.size() == 0)
    {
        interruptManager.setInterruptStatus(status);
        return;
    }

    if (running->status == ProgramStatus::RUNNING)
    {
        running->status = ProgramStatus::READY;
        running->ticks = running->priority * 10;
        readyPrograms.push_back(&(running->tagInGeneralList));
    }
    else if (running->status == ProgramStatus::DEAD)
    {
        releasePCB(running);
    }
    //初始化max,next,nextid,ready队列的size
    int max = -1;
    PCB* next = nullptr;
    int nextid = 0;
    int size = readyPrograms.size();
    //找到优先级最大的线程
    for(int i = 0;i<size;i++){
        ListItem* item = readyPrograms.at(i);
        PCB* tmp = ListItem2PCB(item, tagInGeneralList);
        if(tmp->priority > max){
            max = tmp->priority;
            nextid = i;
            next = tmp;
        }
    }

    //ListItem *item = readyPrograms.front();
    //PCB *next = ListItem2PCB(item, tagInGeneralList);
    //从ready队列中取出，将该线程状态置为running
    PCB *cur = running;
    next->status = ProgramStatus::RUNNING;
    running = next;
    readyPrograms.erase(nextid);
    //切换线程栈，实现线程的切换
    asm_switch_thread(cur, next);

    interruptManager.setInterruptStatus(status);
}

4. 实验结果

Assignment1:

printf %b（二进制）和%f(保留六位小数)

1714908659141

Assignment2:

1714919664301

Assignment3:

见实验过程部分

Assignment4:

4.1 FIFO

1714917101307

4.2 优先级调度

1714917971082

5.实验总结

通过这次实验，学习了可变参数机制，并增添了实验中的pringf函数的功能，线程在操作系统中的描述，调度方式。复现实验很容易，但要深入理解其中的每一处细节并准确描述出来很难。我在Assignment3中开始由于对函数调用过程中栈的变化不熟悉卡了很久，后来看到其他同学的解释时才更加深入理解了 asm_switch_thread的设计,感受到了设计的巧妙之处。

发表于 更新于

实验课程: 操作系统

实验名称: Lab3 从实模式到保护模式

1. 实验要求

任务 1

1.1

复现Example 1，说说你是怎么做的并提供结果截图，也可以参考Ucore、Xv6等系统源码，实现自己的LBA方式的磁盘访问。
提示：部分需要的文件存放在src/example-1下，请根据需要将其放置于自己创建的lab3文件夹下。

1.2

在Example1中，我们使用了LBA28的方式来读取硬盘。此时，我们只要给出逻辑扇区号即可，但需要手动去读取I/O端口。然而，BIOS提供了实模式下读取硬盘的中断，其不需要关心具体的I/O端口，只需要给出逻辑扇区号对应的磁头（Heads）、扇区（Sectors）和柱面（Cylinder）即可，又被称为CHS模式。现在，同学们需要将LBA28读取硬盘的方式换成CHS读取，同时给出逻辑扇区号向CHS的转换公式。最后说说你是怎么做的并提供结果截图。

阅读全文 »

发表于 更新于

本科生实验报告

实验课程: 操作系统

实验名称: Lab2 实验入门

1. 实验要求

任务1：

1.1

根据Example1教程，复现Example 1。

1.2

修改Example 1的代码，使得MBR被加载到0x7C00后在(12,12)处开始输出你的学号。注意，学号显示的前景色和背景色必须和教程中不同。

任务2：

2.1

请探索实模式下的光标中断int 10h， 实现将光标移动至(8,8)，获取并输出光标的位置 。说说你是怎么做的，并将结果截图。

2.2

利用实模式下的中断， 从(8,8)开始输出你的学号 。说说你是怎么做的，并将结果截图。

阅读全文 »

发表于 更新于

1711196825096

常用的gdb调试指令

gdb指令 含义 实例
break *adress或b *address 在地址adress处设置断点。 break *0x7c00``b *0x7c00
break symbol或b symbol 在符号symbol处设置断点，例如symbol一般是函数名。 break setup_kernel``b setup_kernel
break filename:line_number 在文件filename处的第line_numer行设置断点 b mbr.asm:12
add-symbol-file filename address 加载符号表filename到地址address处 add-symbol-file mbr.symbol 0x7c00
x/FMT address address是内存地址，FMT格式是重复的单元个数+格式+大小。
重复的单元个数是一个数字，表示我们希望查看多少个单元。正数表示从address向后查看。负数表示从address向前查看。格式是一个字符，可以是o(octal), x(hex), d(decimal), u(unsigned decimal), t(binary), f(float), a(address), i(instruction), c(char), s(string)。``大小是一个字符，可以是b(byte, 1 byte), h(halfword, 2 byte), w(word, 4 byte), g(giant, 8 bytes)。		 x/5xw 0x8032``x/10i 0x7c00
continue或c 继续执行正在调试的程序到断点处暂停。
step或s 执行一条C语句，如果遇到函数调用语句，则会进入函数体中。
next或n 执行一条C语句，函数调用语句不会进入函数体，把函数当成一条语句执行。
stepi或si 执行一条汇编语句，如果遇到函数调用语句，则会进入函数体中。
nexti或ni 执行一条汇编语句，函数调用语句不会进入函数体，把函数当成一条语句执行。
info registers 查看所有寄存器的值
layout layout_name layout_name包含src，asm，split，regs。``src显示源代码窗口和命令窗口，asm显示汇编代码窗口和命令窗口，split显示源代码窗口、汇编代码窗口和命令窗口，regs显示寄存器窗口。 layout split
focus layout_window 转换当前窗口到layout窗口，layout_window包含src，asm，regs，cmd。任何时刻gdb的当前窗口只有一个，并且使用方向键的效果只会在当前窗口处显示。 focus cmd
file symbol_file 加载符号表，为gdb提供debug信息。 file ../build/kernel.o
set disassembly-flavor intel 设置汇编代码格式为intel风格
set architecture name 设置指令对应的CPU架构，name包含i8086(16位)，i386(32位) set architecture i386

详解子程序调用过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
asm_switch_thread:
    push ebp
    push ebx
    push edi
    push esi

    mov eax, [esp + 5 * 4]
    mov [eax], esp ; 保存当前栈指针到PCB中，以便日后恢复

    mov eax, [esp + 6 * 4]
    mov esp, [eax] ; 此时栈已经从cur栈切换到next栈

    pop esi
    pop edi
    pop ebx
    pop ebp

    sti
    ret

1.push指令

push %eax

将eax数值压入栈中，可分解为：

sub $4, %esp ——> esp = esp - 4

mov %eax, (%esp) ——> *(int32_t *)esp = eax

2.pop指令

pop %eax

将eax数值弹出栈，可分解为：

mov (%esp), %eax ——> eax = *(int32_t *)esp

add $4, %esp ——> esp = esp + 4

3.call指令

call 0x12345

调用0x12345这个地址，可分解为：

push %eip ——> 将cpu下一条要执行的指令压入栈中

mov $0x12345, %eip ——> eip = 0x12345

注意：CPU下一条指令将会从地址0x12345中取。

4.ret指令

ret

返回call之前的地址，可分解为：

pop %eip ——> 将call压入栈的指令弹出赋给eip

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于 更新于

sf

1
dfsf

1711029383714

本科生实验报告

实验课程: 操作系统

实验名称: lab1 编译内核/利用已有内核构建OS

  1. 实验要求

独立完成实验5个部分 环境配置 、 编译****Linux内核、 Qemu启动内核并开启远程调试 、制作Initramfs和 编译并启动Busybox**** 。

1.搭建OS内核开发环境包括：代码编辑环境、编译环境、运行环境、调试环境等。

2.下载并编译i386（32位）内核，并利用qemu启动内核。

3.熟悉制作initramfs的方法。

4.编写简单应用程序随内核启动运行。

5.编译i386版本的Busybox，随内核启动，构建简单的OS。

6.开启远程调试功能，进行调试跟踪代码运行。

7.撰写实验报告。

阅读全文 »