IGNORANT

操作系统实验——线程同步

最近刚做了最后一次实验,实现多线程同步(多线程对同一个缓冲区的使用问题),涉及到信号量的设计,这正是我知识点盲区,所以写得有点久了。

于是参考此处,略补了一点知识:https://github.com/Wangzhike/HIT-Linux-0.11/tree/master/5-semaphore

下面进入正题(开始抄老师ppt)。

实验内容

实现信号量

编辑文件kernel/sem.c,实现如下四个函数
int sys_sem_create(int value)
value是信号量的初值
分配内存要用kmalloc,不能用malloc
成功返回信号量ID,否则返回-1
int sys_sem_destroy(int semid)
释放内存要用kfree,不能用free
成功返回0,否则返回-1
int sys_sem_wait(int semid)
P操作,要用save_flags_cli/restore_flags和函数sleep_on
成功返回0,否则返回-1
int sys_sem_signal(int semid)
V操作,要用save_flags_cli/restore_flags和函数wake_up
成功返回0,否则返回-1
把这四个函数做成系统调用,分别是sem_create/destroy/wait/signal

设计生产者/消费者

预备知识

信号量

关于信号量
可以参考文章: Linux 0.11下信号量的实现和应用

EPOS互斥

EFLAGS组成如下:

EPOS提供的中断API:

Sample:

uint32_t flags;
save_flags_cli(flags);

临界区

restore_flags(flags)

线程睡眠/唤醒API

睡眠
void sleep_on(struct wait_queue **head)
参数head是睡眠队列的头指针
唤醒
void wake_up(struct wait_queue **head, int n)
参数n表示要唤醒的线程个数,n小于0表示唤醒该队列中的所有线程
sleep_onwake_up必须在关中断环境中运行,即用save_flags_cli/restore_flags保护

Sample:

struct wait_queue *wq_kbd = NULL;//!!!非常重要!!!
uint16_t   buf_kbd;
//从键盘读按键信息
int sys_getchar()
{
     uint32_t flags;
     save_flags_cli(flags);
     
     //睡眠等待用户按键
     sleep_on(&wq_kbd);
     
     restore_flags(flags);
     return buf_kbd;
}
//键盘中断处理函数
void isr_keyboard(uint32_t irq, struct context *ctx)
{
     buf_kbd = read_data_from_kbd();
      
     //注意:在ISR中,中断已经被关闭
     //唤醒1个等待用户按键的线程
     wake_up(&wq_kbd, 1);     
}

实验步骤

信号量系统调用实现

kernelkernel.h中定义结构体类型Semaphore,并声明需要用到的相关全局变量,并且声明系统调用服务例程函数

// lab4
typedef struct Semaphore {
    int id;                     // semaphore identifier
    int val;                 // semaphore value
    struct wait_queue* wq;   // wait queue
    struct Semaphore* next;  // next semaphore
} Sem_t;
// global variables
extern int GSID;            // allocate global semaphore identifier
extern Sem_t* g_sem_head;   // header of semaphore link
extern Sem_t* g_sem_slctd;  // selected semaphore in temporary use
int sys_sem_create(int value);
int sys_sem_destroy(int semid);
int sys_sem_wait(int semid);
int sys_sem_signal(int semid);

需要对Semaphore结构体类型说明的是:
Sem_tstruct Semaphore的别名
id来自于GSID的值,作用是标识唯一的信号量结构体,后面通过它来寻找对应的信号量结构体首地址
val是信号量的值,在每一次P/V操作后会增1/减1
wq 是存放要使用该信号量的线程的等待队列的头指针
next使用next指针把所用信号量串成一个单向链表。

在kernelsem.c中完成对全局变量的初始化,以及对系统调用服务例程函数的实现


int GSID = 0;                // allocate global semaphore identifier
Sem_t* g_sem_head = NULL;   // header of semaphore link
Sem_t* g_sem_slctd = NULL;  // selected semaphore in temporary use

// insert semaphore into link
void InsertSem(Sem_t* new) {
    if (!g_sem_head)       // No semaphore
        g_sem_head = new;  // to be header
    else {
        Sem_t* p_Sem = g_sem_head;
        while (p_Sem->next)  // locate to the tail semaphore
            p_Sem = p_Sem->next;
        p_Sem->next = new;  // insert into this link
    }
}

// return the addr of semaphore by its id
Sem_t* AddrSem(int sid) {
    Sem_t* p_Sem = g_sem_head;
    while (p_Sem)
        if (p_Sem->id == sid)
            return p_Sem;
        else
            p_Sem = p_Sem->next;
    return NULL;
}

// create a new semaphore
int sys_sem_create(int value) {
    Sem_t* new_Sem = (Sem_t*)kmalloc(sizeof(Sem_t));
    // if failed to alloc space
    if (!new_Sem) return -1;
    // else
    new_Sem->id = GSID;
    new_Sem->val = value;
    new_Sem->wq = NULL;
    new_Sem->next = NULL;
    InsertSem(new_Sem);
    return GSID++;
}

int sys_sem_destroy(int sid) {
    if (!g_sem_head) return -1;
    Sem_t* del = AddrSem(sid);  // to be destroyed
    if (del == g_sem_head) {   // if the destroying semaphore is the link header
        if (g_sem_head->next)  // and if exist others next to the header
            g_sem_head = g_sem_head->next;  // update header
        kfree(del);
        del = NULL;
        return 0;
    } else {                        // else, not the header
        Sem_t* p_Sem = g_sem_head;  // find the prev semaphore
        while (p_Sem && (p_Sem->next != del)) p_Sem = p_Sem->next;
        // if p_Sem not NULL, p_Sem is prev semaphore, else, no prev one
        if (p_Sem) {
            p_Sem->next = del->next;
            kfree(del);
            del = NULL;
            return 0;
        }
    }
    return -1;
}

int sys_sem_wait(int sid) {
    Sem_t* w_Sem = AddrSem(sid);
    if (!w_Sem) return -1;  // no this semaphore
    if(sid==2)
        printk("w id val=%d\n",w_Sem->val);
    w_Sem->val--;
    if (w_Sem->val < 0) {
        uint32_t flags;
        save_flags_cli(flags);
        sleep_on(&(w_Sem->wq));  // let thread get into wait queue
        restore_flags(flags);
    }
    return 0;
}

int sys_sem_signal(int sid) {
    Sem_t* w_Sem = AddrSem(sid);
    if (!w_Sem) return -1;  // no this semaphore
    if(sid==2)
        printk("s id val=%d\n",w_Sem->val);
    w_Sem->val++;
    if (w_Sem->val <= 0) {
        uint32_t flags;
        save_flags_cli(flags);
        wake_up(&(w_Sem->wq), 1);  // wake up a thread from wait queue
        restore_flags(flags);
    }
    return 0;
}

注:AddrSem(sid)可以得到id为sid的信号量x地址,但使用AddrSem(sid-1)来得到链表中信号量x的前一个信号量地址是有缺陷的,因为sid-1的信号量可能已被destroy。但本实验不涉及这个问题,你可以采用AddrSem(sid-1)先得到sid-1的信号量地址Y,然后Y->next自然便是信号量x的地址。

系统调用的添加,参考前几次实验的添加步骤,大致如下:

  1. \userapp\include\syscall.h 声明系统调用API
  2. \userapp\lib\syscall-wrapper.S 定义封装例程
  3. \include\syscall-nr.h 定义系统调用号
  4. \kernel\kernel.h 声明系统调用服务例程函数sys_xxx
  5. \kernel\sem.c 实现系统调用服务例程函数
  6. \kernel\machdep.c 在系统调用分发函数syscall()中根据系统调用号加入SYSCALL_xxx分支。
    跳过。

生产者/消费者设计

后面主要是创建线程,使用线程,画图之类的折腾,略述。
userappmain.c中,声明全局变量,信号量ID,buffer大小

#define ar_Size 25
#define bfN 8
int emp_Sem, ful_Sem, mut_Sem[bfN];  // empty,full,mutex semaphore
int buf[bfN][ar_Size];  // the buffer size, we have {bfN} buffers and each can
                        // contain {ar_Size} integers
void main(void* pv){
    ……
    emp_Sem = sem_create(bfN);
    ful_Sem = sem_create(0);
    int i;
    for (i = 0; i < bfN; i++) mut_Sem[i] = sem_create(1);
    ……
}

注:互斥信号量数量取决于buffer的数量,这样可使生产者在填充新的缓冲区同时,可以让消费者清除旧的缓冲区(针对多消费者多生产者情况)。若只一个,那么只有等生产者线程填充完新的缓冲区,消费者才能清除旧的缓冲区,尽管两者使用的缓冲区并不是同一个。即使生产者线程用完了自己的时间片,由于共用了同一互斥信号量,消费者线程得到时间片也进不了临界区,直到生产者线程完成新缓冲区的填充。

下面说说生产者与消费者线程函数的创建,模板如下(具体代码见尾部):
生产者线程函数模板:

void tsk_foo_producer(void* pv) {
    int seqN = 0;  // 缓冲区编号

    while (1) {
        sem_wait(emp_Sem);
        sem_wait(mut_Sem[seqN]);
        
        // 填充缓冲区代码区
        
        sem_signal(mut_Sem[seqN]);
        sem_signal(ful_Sem);
        seqN = (seqN + 1) % bfN;  // 切换到下一个缓冲区
    }
    task_exit(0);
}

消费者线程函数模板:

void tsk_foo_consumer(void* pv) {
    int seqN = 0;  // 缓冲区编号
    while (1) {
        sem_wait(ful_Sem);
        sem_wait(mut_Sem[seqN]);
        
        // 清空缓冲区代码区
        
        sem_signal(mut_Sem[seqN]);
        sem_signal(emp_Sem);
        seqN = (seqN + 1) % bfN;  // 切换到下一个缓冲区
    }
    task_exit(0);
}

实验结果

可以直观地从图中看出,当缓冲区满了,生产者还想生产时,必须等待消费者消费一个缓冲区;缓冲区空时,消费者还想消费,必须等待生产者生产完一个。

感谢

感谢洪明坚老师的ppt,感谢学长们的实验报告,感谢网上大神的笔记。

代码附录

main.c

/*
 * vim: filetype=c:fenc=utf-8:ts=4:et:sw=4:sts=4
 */
#include <inttypes.h>
#include <math.h>
#include <netinet/in.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <syscall.h>
#include "graphics.h"

extern void* tlsf_create_with_pool(void* mem, size_t bytes);
extern void* g_heap;

// lab4
#include "lab4.h"

/**
 * GCC insists on __main
 *    http://gcc.gnu.org/onlinedocs/gccint/Collect2.html
 */
void __main() {
    size_t heap_size = 32 * 1024 * 1024;
    void* heap_base = mmap(NULL, heap_size, PROT_READ | PROT_WRITE,
                           MAP_PRIVATE | MAP_ANON, -1, 0);
    g_heap = tlsf_create_with_pool(heap_base, heap_size);
}

/**
 * 第一个运行在用户模式的线程所执行的函数
 */


void main(void* pv) {
    printf("task #%d: I'm the first user task(pv=0x%08x)!\r\n", task_getid(),
           pv);

    // TODO: Your code goes here
    test_lab4();

    while (1)
        ;
    task_exit(0);
}

lab4.h

#ifndef _LAB4_
#define _LAB4_

#define ar_Size 25
#define max_Elem 100
#define bfN 8
// global variables
uint16_t scr_X;         // screen width
uint16_t scr_Y;         // screen length
uint16_t buf_Xlen;   // each buffer's width
uint16_t line_Ylen;  // each line's height
float line_LenR;     // the ratio of transforming elements in array to a line's
                     // length
int emp_Sem, ful_Sem, mut_Sem[bfN];  // empty,full,mutex semaphore
int buf[bfN][ar_Size];  // the buffer size, we have {bfN} buffers and each can
                        // contain {ar_Size} integers

// Drwa a line, width = 15
void DrawLine(int x0, int y0, int length, COLORREF cr) {
    int i, j;
    for (i = 0; i < 15; i++) {
        for (j = 0; j < length; j++) {
            setPixel(x0 + j, y0 + i, cr);
        }
    }
}

// Draw the bar to show priority
void DrawPrioBar(int length, int LorR) {
    int seqN;
    COLORREF cr;
    if (LorR == -1) {
        seqN = 8;
        cr = RGB(0, 255, 0);
    } else {
        seqN = 9;
        cr = RGB(255, 0, 0);
    }
    int x0 = seqN * buf_Xlen + 10;
    int i, j;
    for (i = 0; i <= 20; ++i)
        for (j = 0; j <= 39 * 2; ++j) setPixel(x0 + i, j, cr);
    for (i = 0; i <= 20; ++i)
        for (j = 0; j <= length * 2; ++j)
            setPixel(x0 + i, j, RGB(119, 136, 153));
}

// set time delay for thread action
void DrawDelay(long lMs) {
    long lRemainingMilliSecond = (lMs) % 1000;
    long lNanoSecond = lRemainingMilliSecond * 1000000;
    struct timespec ts_sleep, ts_remaining;
    ts_sleep.tv_sec = (lMs) / 1000;
    ts_sleep.tv_nsec = lNanoSecond;
    nanosleep(&ts_sleep, &ts_remaining);
}

// swap lines between a_lineNum and b_lineNum in the seqNum buffer
void SwapBufLine(int* array, int seqNum, int a_lineNum, int b_lineNum) {
    DrawLine(seqNum * buf_Xlen, a_lineNum * line_Ylen,
             buf[seqNum][a_lineNum] * line_LenR, RGB(0, 0, 0));
    DrawLine(seqNum * buf_Xlen, a_lineNum * line_Ylen,
             buf[seqNum][b_lineNum] * line_LenR,
             RGB(255, 0, buf[seqNum][b_lineNum]));
    DrawLine(seqNum * buf_Xlen, b_lineNum * line_Ylen,
             buf[seqNum][b_lineNum] * line_LenR, RGB(0, 0, 0));
    DrawLine(seqNum * buf_Xlen, b_lineNum * line_Ylen,
             buf[seqNum][a_lineNum] * line_LenR,
             RGB(255, 0, buf[seqNum][a_lineNum]));
    int tmp = array[a_lineNum];
    array[a_lineNum] = array[b_lineNum];
    array[b_lineNum] = tmp;
}

// Bubble Sort
void BubbleSort(int* array, int seqNum) {
    int i, j;
    // Draw again, unnecessary,just for beauty
    for (i = 0; i < ar_Size; i++)
        DrawLine(seqNum * buf_Xlen, i * line_Ylen, buf[seqNum][i] * line_LenR,
                 RGB(255, 0, buf[seqNum][i]));
    // start to sort this buffer
    for (i = 0; i < ar_Size; i++)
        for (j = ar_Size - 1; j > i; j--)
            if (array[j] < array[j - 1]) {
                SwapBufLine(array, seqNum, j, j - 1);
                DrawDelay(55);
            }
}

// controller can change the priority
void tsk_foo_control(void* pv) {
    int key;
    int* tid_List = (int*)pv;
    int tid_A = tid_List[0];
    int tid_B = tid_List[1];

    while (1) {
        // Draw priority bar first
        DrawPrioBar(getpriority(tid_A), -1);
        DrawPrioBar(getpriority(tid_B), 1);
        key = getchar();  // wait for input
        switch (key) {
            case 0x4800: {  // UP
                setpriority(tid_A, getpriority(tid_A) - 2);
            } break;
            case 0x5000: {  // DOWN
                setpriority(tid_A, getpriority(tid_A) + 2);
            } break;
            case 0x4d00: {  // RIGHT
                setpriority(tid_B, getpriority(tid_B) - 2);
            } break;
            case 0x4b00: {  // LEFT
                setpriority(tid_B, getpriority(tid_B) + 2);
            } break;
            default: {
            }
        }
    }
    task_exit(0);
}

// producer: generate rand arrays and put into buffer
void tsk_foo_producer(void* pv) {
    int seqN = 0;  // the sequence number of buffer
    srand(time(NULL));
    int i;
    while (1) {
        sem_wait(emp_Sem);
        sem_wait(mut_Sem[seqN]);
        // output the buffer
        for (i = 0; i < ar_Size; i++) {
            buf[seqN][i] = rand() % max_Elem;
            DrawLine(seqN * buf_Xlen, i * line_Ylen, buf[seqN][i] * line_LenR,
                     RGB(0, 255, buf[seqN][i]));
            DrawDelay(40);
        }
        sem_signal(mut_Sem[seqN]);
        sem_signal(ful_Sem);
        seqN = (seqN + 1) % bfN;  // next buffer
    }
    task_exit(0);
}

// consumer: sort the array in buffer outside critical region
void tsk_foo_consumer(void* pv) {
    int seqN = 0;  // the sequence number of buffer
    while (1) {
        sem_wait(ful_Sem);
        sem_wait(mut_Sem[seqN]);
        BubbleSort(buf[seqN], seqN);
        // clear the buffer
        DrawDelay(200);
        int i;
        for (i = 0; i < ar_Size; i++)
            DrawLine(seqN * buf_Xlen, i * line_Ylen, buf_Xlen, RGB(0, 0, 0));
        sem_signal(mut_Sem[seqN]);
        sem_signal(emp_Sem);
        seqN = (seqN + 1) % bfN;  // next buffer
    }
    task_exit(0);
}

// test function
void test_lab4() {
    // enter the gui
    int graphMode = 0x143;
    init_graphic(graphMode);
    // initialize the semaphore
    emp_Sem = sem_create(bfN);
    ful_Sem = sem_create(0);
    int i;
    for (i = 0; i < bfN; i++) mut_Sem[i] = sem_create(1);
    // initial the parameter used to draw
    scr_X = g_graphic_dev.XResolution;
    scr_Y = g_graphic_dev.YResolution;
    buf_Xlen = scr_X / (bfN + 2);
    line_Ylen = scr_Y / (ar_Size);
    line_LenR = (buf_Xlen / (float)max_Elem);

    // alloc stack space
    unsigned int st_Size = 1024 * 1024;
    unsigned char *stk_Pro, *stk_Con, *stk_Ctr;
    stk_Pro = (unsigned char*)malloc(st_Size);
    stk_Con = (unsigned char*)malloc(st_Size);
    stk_Ctr = (unsigned char*)malloc(st_Size);
    // create threads
    int tid_Pro, tid_Con, tid_Ctr;
    tid_Pro = task_create(stk_Pro + st_Size, tsk_foo_producer, (void*)0);
    tid_Con = task_create(stk_Con + st_Size, tsk_foo_consumer, (void*)0);
    int tid_List[2] = {tid_Pro, tid_Con};
    tid_Ctr = task_create(stk_Ctr + st_Size, tsk_foo_control, (void*)tid_List);
    // initial the priorities
    setpriority(tid_Pro, 10);
    setpriority(tid_Con, 10);
    setpriority(tid_Ctr, 1);  // nice = -19

    // exit all threads
    task_wait(tid_Pro, NULL);
    task_wait(tid_Con, NULL);
    task_wait(tid_Ctr, NULL);
    free(stk_Pro);
    free(stk_Con);
    free(stk_Ctr);

    // free the semaphore
    sem_destroy(emp_Sem);
    sem_destroy(ful_Sem);
    for (i = 0; i < bfN; i++) sem_destroy(mut_Sem[i]);
}

#endif  //_LAB4_

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »