【MIT6.S081-2020Fall】Lab: locks

內(nèi)存分配實驗

內(nèi)存分配實驗準備

環(huán)境配置

• commit lab0的代碼

git commit -am lab0

• 切換到lock分支

git fetch

git checkout lock

make clean

• make; make qemu并執(zhí)行kalloctest觀察鎖競爭情況

實驗?zāi)康?/h3>

1. 為每個CPU維護一個空閑頁面鏈表，每個鏈表都有自己的鎖**

? → 不同CPU上的分配和釋放可以并行執(zhí)行

2. 當某個CPU的空閑頁面用盡時，需要借用另一CPU的空閑頁面**

? → 雖然“借用”時可能引入鎖競爭，但這種情況較少發(fā)生

? 完成實驗后，需通過kalloctest的3個測試 (測試時間可能較長)

1. 舉一個例子說明修改前的kernel/kalloc.c中如果沒有鎖會導(dǎo)致哪些進程間競爭(races)問題

答：

1. Double Free問題：如果沒有鎖來保護釋放內(nèi)存的操作，多個進程可能會同時嘗試釋放同一塊內(nèi)存。這可能導(dǎo)致內(nèi)存被釋放多次，破壞內(nèi)存管理的一致性。當后續(xù)的內(nèi)存分配請求發(fā)生時，可能會分配到之前已經(jīng)被釋放但未及時回收的內(nèi)存塊，從而導(dǎo)致不可預(yù)測的錯誤和安全問題。
2. 內(nèi)存泄漏問題：如果沒有鎖來保護內(nèi)存分配的操作，多個進程可能會同時嘗試分配內(nèi)存。這可能導(dǎo)致內(nèi)存分配失敗，因為內(nèi)存池可能在分配之前已經(jīng)被其他進程用盡。此時，一些進程可能無法獲得所需的內(nèi)存，導(dǎo)致內(nèi)存泄漏。
3. 數(shù)據(jù)不一致性問題：如果多個進程同時修改內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)，沒有適當?shù)逆i來同步這些操作，就可能導(dǎo)致數(shù)據(jù)結(jié)構(gòu)的損壞，從而破壞了內(nèi)存管理的一致性。
4. 性能問題：沒有適當?shù)逆i來管理內(nèi)存池，可能導(dǎo)致競爭條件，降低了系統(tǒng)的性能。競爭條件會導(dǎo)致進程等待或頻繁地重試內(nèi)存分配/釋放操作，從而增加了系統(tǒng)的負載和延遲。

2. 說明修改前的kernel/kalloc.c中鎖競爭contention問題及其后果

答：

1、修改前的kalloc.c代碼中，只有一個內(nèi)核內(nèi)存分配器（kmem），這會導(dǎo)致在很多線程想要獲取鎖，想要CPU 調(diào)度分配內(nèi)存的時候造成擁塞情況，導(dǎo)致大量的線程獲取鎖失敗，使得程序運行效率降低。

3. 解釋acquire和release中push_off/pop_off的作用

答：“acquire” 和 “release” 中的 “push_off” 和 “pop_off” 是通常用于實現(xiàn)中斷禁用（中斷屏蔽）的操作。這些操作通常在多任務(wù)操作系統(tǒng)中用于確保獲取鎖或釋放鎖的相關(guān)代碼的原子性執(zhí)行，以防止并發(fā)執(zhí)行的任務(wù)相互干擾。

4. 對上頁實驗內(nèi)容的實現(xiàn)思路、代碼設(shè)計、測試結(jié)果

實驗思路

1、為每個CPU維護一個空閑頁面鏈表，我們可以通過修改kalloc.c代碼中的kmem結(jié)構(gòu)體，修改為長度為NCPU的結(jié)構(gòu)體數(shù)組，再init函數(shù)中，初始化8個結(jié)構(gòu)體中的鎖，進行free操作的時候，注意獲取當前CPU的id，然后對對應(yīng)id的CPU進行釋放

實現(xiàn)的核心代碼：

struct
{struct spinlock lock;struct run *freelist;
} kmem[NCPU];

2、當其它CPU空閑的時候，我們怎樣借用其它CPU來完成任務(wù)呢？我們可以進行一個簡單的for循環(huán)遍歷，當發(fā)現(xiàn)這個CPU是空閑的，那么我們就可以借用這個CPU

實現(xiàn)的核心代碼

  if (!r){for (int j = 0; j < NCPU; j++){if (i != j){// 嘗試獲取鎖acquire(&kmem[j].lock);if (kmem[j].freelist){// 如果獲取到了，那么就分配,并退出r = kmem[j].freelist;kmem[j].freelist = r->next;release(&kmem[j].lock);break;}release(&kmem[j].lock);}}}

代碼設(shè)計

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"void freerange(void *pa_start, void *pa_end);extern char end[]; // first address after kernel.// defined by kernel.ld.struct run
{struct run *next;
};struct
{struct spinlock lock;struct run *freelist;
} kmem[NCPU];void kinit()
{for (int i = 0; i < 8; i++)initlock(&kmem[i].lock, "kmem");freerange(end, (void *)PHYSTOP);
}void freerange(void *pa_start, void *pa_end)
{char *p;p = (char *)PGROUNDUP((uint64)pa_start);for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)kfree(p);
}// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(void *pa)
{struct run *r;if (((uint64)pa % PGSIZE) != 0 || (char *)pa < end || (uint64)pa >= PHYSTOP)panic("kfree");// Fill with junk to catch dangling refs.memset(pa, 1, PGSIZE);r = (struct run *)pa;int i = r_tp();push_off();acquire(&kmem[i].lock);r->next = kmem[i].freelist;kmem[i].freelist = r;release(&kmem[i].lock);pop_off();
}// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{struct run *r;push_off();int i = r_tp();acquire(&kmem[i].lock);r = kmem[i].freelist;if (r)kmem[i].freelist = r->next;release(&kmem[i].lock);if (!r){for (int j = 0; j < NCPU; j++){if (i != j){// 嘗試獲取鎖acquire(&kmem[j].lock);if (kmem[j].freelist){// 如果獲取到了，那么就分配,并退出r = kmem[j].freelist;kmem[j].freelist = r->next;release(&kmem[j].lock);break;}release(&kmem[j].lock);}}}pop_off();if (r)memset((char *)r, 5, PGSIZE); // fill with junkreturn (void *)r;
}

測試結(jié)果

同步互斥實驗?zāi)繕?/h3>

Q1：關(guān)系分析，請寫出題目中存在的互斥和同步的關(guān)系

答：同步關(guān)系包含互斥關(guān)系

1、店面的窗口屬于臨界區(qū)資源，且煎餅果子占用了該窗口后，即將該臨界區(qū)資源上鎖，雞蛋灌餅不能再占用該臨界區(qū)資源，反之亦然，此過程既體現(xiàn)了同步關(guān)系又體現(xiàn)了互斥關(guān)系

2、同學們排隊購買早餐，并且根據(jù)自己的需求站成了兩隊，體現(xiàn)出來同步關(guān)系，不至于讓整個隊伍亂掉，有序地進行，去獲取窗口上的資源，符合FIFO思想、同學們位于同步阻塞態(tài)，但是當8點后，沒買到的同學到其它窗口去了，又體現(xiàn)出來非阻塞態(tài)

Q2：上述關(guān)系可以抽象為幾個進程? 寫出偽代碼描述和實現(xiàn)思路

答：上述幾個關(guān)系可以抽象為4個進程

實現(xiàn)思路：

1、可以先定義四個wait函數(shù)，分別表示煎餅果子等待籃子為空，雞蛋灌餅等待籃子為空，第一支隊伍等待雞蛋灌餅被添上，第二支隊伍等待煎餅果子被添上，然后在主函數(shù)中fork四個線程，宏觀并行跑這四個函數(shù)，知道到達早上8點收攤位置

2、因為題目說每天都會出現(xiàn)從一開始就排隊直到 8 點結(jié)束,所以我們可以默認；兩邊排隊的人數(shù)都足夠多，當然實際中我們還可以為隊伍人物增加設(shè)置一個人數(shù)信號量

偽代碼展示