编程知识 cdmana.com

UCORE operating system learning (7) UCORE lab7 synchronization and mutual exclusion

1. ucore lab7 Introduce

  ucore In the previous experiment, we implemented the process / Thread mechanism , And in lab6 The preemptive thread scheduling mechanism is implemented in . The thread based preemption mechanism in the system may be interrupted at any time , Is blocked and suspended so that other threads get CPU. Concurrent execution of multiple threads , It's a big boost cpu Intensive applications cpu throughput , Make the computer system valuable cpu Hardware resources have been fully utilized .

   The obvious advantage of the concurrent system is that the kernel provides a mechanism of operation , But it also brings some problems , Among them, the first is thread safety .

Concurrency brings thread safety problems

   Thread safety refers to a program in which multiple threads execute in parallel with shared data , Thread safe code can ensure that all threads can execute normally and correctly through synchronization mechanism , There will be no data pollution and other accidents .

   Take a classic example : In high-level languages, for a shared integer variable i( hypothesis i=5) On going i++ operation , In the final machine code will be broken down into several more detailed machine instructions :

  1. Read the variable from the corresponding address of the memory i Value ( A high-level language variable is represented as a memory address at the machine level ), write in cpu In the register of ( The assumption is edx)

  2. For registers edx Conduct +1 operation ( After operation edx The value in the register is 5+1=6)

  3. take edx The value of is written to the variable i In the corresponding memory space ( At the high level of language , write in edx After the new value in i Turned into 6)

   Before passing lab5/lab6 Learning from , We know that i++ During each step of the execution of a specific sequence of machine instructions , The operating system may interrupt the execution of the corresponding thread through clock interrupt , Context switch of thread . Machine instructions are atomic , But a single instruction in a high-level language may correspond to multiple machine instructions , May be interrupted during execution , There is no guarantee of continuity of execution .

Examples of thread safety issues

   for example , There are two threads that execute concurrently a、 Threads b, Shared variables between threads i(i=5) the i++ operation .

The execution of two threads i++ The machine instruction flow is in chronological order :  

  1. Threads a Read variables in memory i Value , Write to register edx( Now in memory i The value of is 5,edx The value of is 5).

  2. Threads a Make edx Conduct +1 operation , Now the register edx The value of is 6.

  3. The operating system handles clock interrupts , Discover threads a Has run out of time , Hang it up , Save thread a The context of ( The thread a In the register context of edx=6); And schedule threads b Start getting cpu perform .

  4. Threads b Read variables in memory i Value , Write to register edx( Now in memory i The value of is 5,edx The value of is 5).

  5. Threads b Make edx Conduct +1 operation , Now the register edx The value of is 6.

  6. The operating system handles clock interrupts , Discover threads b Has run out of time , Hang it up , Save thread b The context of ( The thread b In the register context of edx=6); And schedule threads a Start getting cpu perform .

  7. Threads a Resume the scene and move on , After restoring the scene edx The value of is written back to the variable in memory i In the corresponding memory address , Write back the variable i=6.

  8. The operating system handles clock interrupts , Discover threads a Has run out of time , Hang it up ; And schedule threads a Start getting cpu perform .

  9. Threads b Resume the scene and move on , After restoring the scene edx Write the value of the in memory variable i In the corresponding memory address , Write back the variable i=6.

   In the above example , Due to the preemptive scheduling of the operating system and the high-level language i++ The non atomicity of the operation , So that the original initial value is 5 The variable of i, Twice in execution i++ What you get later is not what you expect 7, It's wrong 6. It's just two concurrent threads operating on a shared variable , The actual program will involve more concurrent threads and shared variables , The correctness of the multithreaded concurrent program cannot be guaranteed .

Operating system to solve the means of thread safety problems

   In the vast majority of cases , Program correctness is more important than performance . The operating system introduces preemptive scheduling thread concurrency mechanism at the same time , We also need to provide corresponding means to solve the problem of thread safety .

   Solving thread safety problems , There are two main ideas : One is to eliminate the concurrency of programs ; The other is to prevent multiple threads from accessing shared resources simultaneously ( Shared memory 、 Shared files 、 Sharing peripherals and so on ) The interview of , That is, mutual exclusion : When a thread accesses a shared resource , Other threads can't do the same .

   The first idea is that I/O Used by intensive applications , That's the whole program ( process ) There is only one thread working in , Provided through the underlying operating system i/o The multiplexing mechanism works , In the early redis as well as nodeJS It works in a single thread model . Because there is no scenario of concurrent execution of multiple threads in single thread applications , Eliminate the concurrency of threads , Naturally, there is no need to deal with thread safety issues .

   And the operating system to solve the thread safety problem is the second way of thinking ( The general operating system is used for simultaneous processing of a large number of processes 、 Thread service , So you can't go back and ban concurrency ), Some mechanisms are used to restrict concurrent threads from accessing shared variables that may cause thread safety problems , Ensure mutual exclusion of access .

   In the theory books about the principle of operating system, many methods for realizing mutual exclusion mechanism are introduced , and ucore stay lab7 It mainly realizes “ Semaphore ” and “ Condition variables, ” These two are more efficient 、 Mainstream 、 Based on sleep / Synchronization and mutual exclusion mechanism of wake-up mechanism .lab7 Take the dining problem of philosophers as an example , Through semaphores Semaphore And the pipeline Monitor Solve the classic thread synchronization problem in the field of concurrency .

   adopt lab7 Learning from , Will be able to learn the underlying operating system to achieve thread synchronization 、 Mutual exclusion mechanism , Understanding semaphores 、 Condition variables, 、 The working principle of synchronous mutual exclusion mechanism, such as pipe program ; It can also be applied to higher levels such as java Medium synchronized、AQS Pessimistic locking 、 Tube side monitor、notify/wait And so on thread concurrent synchronization mechanism has a deeper understanding .

  lab7 It's based on previous experiments , You need to understand the previous experiment before you can better understand lab7 The content in .

Please refer to my blog about the previous experiment :

  1. ucore Operating system learning ( One ) ucore lab1 System startup process analysis

  2. ucore Operating system learning ( Two ) ucore lab2 Physical memory management analysis

  3. ucore Operating system learning ( 3、 ... and ) ucore lab3 Virtual memory management analysis

  4. ucore Operating system learning ( Four ) ucore lab4 Kernel thread management

  5. ucore Operating system learning ( 5、 ... and ) ucore lab5 User process management

  6. ucore Operating system learning ( 6、 ... and ) ucore lab6 Thread scheduler

2.  ucore lab7 Analysis of experimental details

  ucore stay lab7 The content of is roughly divided into the following parts :

  1.  Implementation of waiting queue

  2.  Realize the semaphore

  3.  Using semaphores to solve the dining problem of philosophers

  4.  Based on the semaphore, the conditional variable is realized

  5.  Based on semaphore and condition variable, the tube side is realized

  6.  Using management to solve the dining problem of philosophers

2.1 Implementation of waiting queue

Waiting for the queue to introduce

   Mentioned earlier ,ucore stay lab7 The synchronization mechanism implemented in is based on sleep / Wake up mechanism . In order to ensure the mutual exclusion of thread access to critical area , After the previous thread has entered the critical area , Subsequent threads that want to access the critical area will be blocked to wait for the previous thread to leave the critical area , After the thread that has entered the critical area has left the critical area, the blocked thread will be awakened again to obtain the qualification to enter the critical area .

   When many threads are concurrent , There may be more than one thread blocked in the corresponding critical area , Therefore, the waiting queue structure is abstracted (wait_queue) Used to maintain this set of blocked threads . When a thread is blocked in a critical area due to mutual exclusion , Add it to the waiting queue and give up cpu Enter the blocking state ; When the thread that previously obtained access to the critical section leaves , Then select one blocked from the corresponding waiting queue 、 The thread in the waiting state wakes up , The awakened thread can then enter the critical area .

   Using the waiting queue , So that there is at most one thread in the critical section all the time , Guaranteed mutex ; The thread is dormant in the waiting queue ( Blocking )/ Wake up action , The synchronization of critical access between threads is realized .

   Waiting queues, of course, are not only suitable for thread concurrent synchronization , When a thread enters a wait state to wait for a specific completion event ( Sleep regularly for a period of time 、 Waiting for a jam IO Reading and writing completion and so on ), The bottom layer can be realized by waiting queue .

Wait for the queue to implement

  ucore stay /kern/sync In the catalog wait.c、wait.h The waiting queue is implemented in wait_queue、 Wait for the queue node item wait_t And related functions .

  ucore The bottom layer of the waiting queue is realized by the bidirectional linked list structure . Similar to the previous experiment , Provides a macro definition le2wait Used to access the wait_link Node item wait_t structure .

Waiting queue structure :

/**
 *  Waiting in line 
 * */
typedef struct {
    //  Waiting for the head node of the queue ( The sentinel node )
    list_entry_t wait_head;
} wait_queue_t;

struct proc_struct;

/**
 *  Wait for the queue node item 
 * */
typedef struct {
    //  Associated threads 
    struct proc_struct *proc;
    //  Wake up sign 
    uint32_t wakeup_flags;
    //  The waiting queue to which the node belongs 
    wait_queue_t *wait_queue;
    //  Wait for the queue node 
    list_entry_t wait_link;
} wait_t;

#define le2wait(le, member)         \
    to_struct((le), wait_t, member)

Wait for the underlying operation of the queue structure :

//  initialization wait_t Wait for the queue 
void wait_init(wait_t *wait, struct proc_struct *proc);
//  Initialize wait queue 
void wait_queue_init(wait_queue_t *queue);
//  take wait The node item is inserted into the waiting queue 
void wait_queue_add(wait_queue_t *queue, wait_t *wait);
//  take wait Item removed from waiting queue 
void wait_queue_del(wait_queue_t *queue, wait_t *wait);
//  Waiting in the queue wait The next item of the node 
wait_t *wait_queue_next(wait_queue_t *queue, wait_t *wait);
//  Waiting in the queue wait The previous item of the node 
wait_t *wait_queue_prev(wait_queue_t *queue, wait_t *wait);
//  Get the first item in the waiting queue 
wait_t *wait_queue_first(wait_queue_t *queue);
//  Get the last item in the waiting queue 
wait_t *wait_queue_last(wait_queue_t *queue);
//  Whether the waiting queue is empty 
bool wait_queue_empty(wait_queue_t *queue);
// wait Whether the item is in the waiting queue 
bool wait_in_queue(wait_t *wait);
// take wait Item is removed from the waiting queue ( If it exists ) #define wait_current_del(queue, wait) \ do { \ if (wait_in_queue(wait)) { \ wait_queue_del(queue, wait); \ } \ } while (0) #endif /* !__KERN_SYNC_WAIT_H__ */
/**
 *  initialization wait_t Wait for the queue 
 * */
void
wait_init(wait_t *wait, struct proc_struct *proc) {
    // wait Item and proc Establishing correlation 
    wait->proc = proc;
    //  The state of waiting 
    wait->wakeup_flags = WT_INTERRUPTED;
    //  Join the wait queue 
    list_init(&(wait->wait_link));
}

/**
 *  Initialize wait queue 
 * */
void
wait_queue_init(wait_queue_t *queue) {
    //  Wait for the queue head node to initialize 
    list_init(&(queue->wait_head));
}

/**
 *  take wait The node item is inserted into the waiting queue 
 * */
void
wait_queue_add(wait_queue_t *queue, wait_t *wait) {
    assert(list_empty(&(wait->wait_link)) && wait->proc != NULL);
    // wait Items are associated with the waiting queue 
    wait->wait_queue = queue;
    //  take wait Before the item is inserted into the head node 
    list_add_before(&(queue->wait_head), &(wait->wait_link));
}

/**
 *  take wait Item removed from waiting queue 
 * */
void
wait_queue_del(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_del_init(&(wait->wait_link));
}

/**
 *  Waiting in the queue wait The next item of the node 
 * */
wait_t *
wait_queue_next(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_entry_t *le = list_next(&(wait->wait_link));
    if (le != &(queue->wait_head)) {
        // *wait The next item of is not the header node , Returns it 
        return le2wait(le, wait_link);
    }
    return NULL;
}

/**
 *  Waiting in the queue wait The previous item of the node 
 * */
wait_t *
wait_queue_prev(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_entry_t *le = list_prev(&(wait->wait_link));
    if (le != &(queue->wait_head)) {
        // *wait The previous term of is not a head node , Returns it 
        return le2wait(le, wait_link);
    }
    return NULL;
}

/**
 *  Get the first item in the waiting queue 
 * */
wait_t *
wait_queue_first(wait_queue_t *queue) {
    //  Get the next item of the header 
    list_entry_t *le = list_next(&(queue->wait_head));
    if (le != &(queue->wait_head)) {
        //  The next term of the head node is not the head node , Returns it 
        return le2wait(le, wait_link);
    }
    //  The next term of the head node is still the head node , Indicates that the waiting queue is empty ( only one wait_head The sentinel node )
    return NULL;
}

/**
 *  Get the last item in the waiting queue 
 * */
wait_t *
wait_queue_last(wait_queue_t *queue) {
    //  Get the previous item of the header node 
    list_entry_t *le = list_prev(&(queue->wait_head));
    if (le != &(queue->wait_head)) {
        //  The preceding term of a head node is not a head node , Returns it 
        return le2wait(le, wait_link);
    }
    //  The preceding term of the head node is still the head node , Indicates that the waiting queue is empty ( only one wait_head The sentinel node )
    return NULL;
}

/**
 *  Whether the waiting queue is empty 
 * */
bool
wait_queue_empty(wait_queue_t *queue) {
    return list_empty(&(queue->wait_head));
}

/**
 * wait Whether the item is in the waiting queue 
 * */
bool
wait_in_queue(wait_t *wait) {
    return !list_empty(&(wait->wait_link));
}
View Code

Waiting for the queue to sleep / Wake up and other high-level operations :

   Wait for the queue to sleep on the thread 、 The corresponding advanced operation of wake-up depends on 、 Add, delete, modify and query the underlying waiting queue .

//  Will wait for... In the queue wait The thread corresponding to the item wakes up 
void wakeup_wait(wait_queue_t *queue, wait_t *wait, uint32_t wakeup_flags, bool del);
//  Will wait for the thread corresponding to the first item in the queue to wake up 
void wakeup_first(wait_queue_t *queue, uint32_t wakeup_flags, bool del);
//  Wake up all threads corresponding to all items in the waiting queue 
void wakeup_queue(wait_queue_t *queue, uint32_t wakeup_flags, bool del);
//  Make corresponding wait Item to join the current waiting queue ; Causes the current thread to block and sleep , Mounted in the waiting queue 
void wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state);
/**
 *  Will wait for... In the queue wait The thread corresponding to the item wakes up 
 * */
void
wakeup_wait(wait_queue_t *queue, wait_t *wait, uint32_t wakeup_flags, bool del) {
    if (del) {
        //  take wait Item is removed from the waiting queue 
        wait_queue_del(queue, wait);
    }
    //  The reason for setting the wake-up flag 
    wait->wakeup_flags = wakeup_flags;
    //  Wake up the corresponding thread 
    wakeup_proc(wait->proc);
}

/**
 *  Will wait for the thread corresponding to the first item in the queue to wake up 
 * */
void
wakeup_first(wait_queue_t *queue, uint32_t wakeup_flags, bool del) {
    wait_t *wait;
    if ((wait = wait_queue_first(queue)) != NULL) {
        wakeup_wait(queue, wait, wakeup_flags, del);
    }
}

/**
 *  Wake up all threads corresponding to all items in the waiting queue 
 * */
void
wakeup_queue(wait_queue_t *queue, uint32_t wakeup_flags, bool del) {
    wait_t *wait;
    if ((wait = wait_queue_first(queue)) != NULL) {
        if (del) {
            do {
                wakeup_wait(queue, wait, wakeup_flags, 1);
            } while ((wait = wait_queue_first(queue)) != NULL);
        }
        else {
            do {
                wakeup_wait(queue, wait, wakeup_flags, 0);
            } while ((wait = wait_queue_next(queue, wait)) != NULL);
        }
    }
}

/**
 *  Make corresponding wait Item to join the current waiting queue ; Causes the current thread to block and sleep , Mounted in the waiting queue 
 * */
void
wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state) {
    assert(current != NULL);
    wait_init(wait, current);
    current->state = PROC_SLEEPING;
    current->wait_state = wait_state;
    wait_queue_add(queue, wait);
}
View Code

2.2 Realize the semaphore

   Semaphores are the implementation of a synchronous mutual exclusion mechanism , It exists in all kinds of operating system kernels nowadays , It was first created by famous computer scientists Dijkstra Put forward .

ucore Semaphore definition :

   The definition and use of semaphores are very simple and basic , Contains the value of a semaphore value And a waiting queue for thread synchronization .

/**
 *  Semaphore 
 * */
typedef struct {
    //  Semaphore value 
    int value;
    //  The waiting queue corresponding to the semaphore 
    wait_queue_t wait_queue;
} semaphore_t;

/**
 *  Initialize semaphores 
 * */
void
sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    //  Initialize wait queue 
    wait_queue_init(&(sem->wait_queue));
}

   The main operations of semaphores are down and up, Corresponding to Dijkstra When a semaphore is presented P/V operation .

   Semaphore is the basic structure of synchronous mutex , Its down/up The operation has to be atomic , Context switch cannot be interrupted . There are many ways to make software programs atomic , because ucore It runs on a single core 80386cpu Upper , For simplicity, we directly use the method of closing interrupt to realize the atomicity of semaphore operation ( Multicore cpu Under the circumstances , It's not enough to turn off a single core interrupt , If you turn off all core interrupts, the performance loss is too high , We need to take lock bus and other means to achieve software atomicity ).

Semaphore down operation :

   Semaphore down operation , It's a request for a semaphore .

   When the semaphore value Greater than 0 when , It can also hold the current thread into the critical area .

   When the semaphore value The value is equal to 0 when , No more threads can be accommodated , In this case, the current thread needs to be blocked on the waiting queue of semaphore , Waiting for the semaphore up Operation to wake it up .

/**
 *  Semaphore down operation   Subtract the semaphore 
 *  When the semaphore value Block the current thread on semaphore when insufficient , Wait for other threads up Wake it up during operation 
 * */
static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    //  Temporarily shut down interrupt , Ensure that the semaphore is down Operations are atomic operations 
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        //  The semaphore corresponds to value Greater than 0, And the right to use 
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }

    //  The semaphore corresponds to value Less than or equal to 0, Need to block the current thread 
    wait_t __wait, *wait = &__wait;
    //  Make the current thread hang in the blocking queue of semaphore 
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    //  Resume interrupt , Atomic operation ends 
    local_intr_restore(intr_flag);

    //  The current thread is blocked , Make a schedule 
    schedule();

    local_intr_save(intr_flag);
    //  After wake up , Atomic operations remove the current item from the waiting queue of semaphores 
    wait_current_del(&(sem->wait_queue), wait);
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        //  If the ID of waiting for the thread to wake up is the same as the parameter set before wait_state atypism , Return its status to the caller for further judgment 
        return wait->wakeup_flags;
    }
    return 0;
}

Semaphore up operation :

   Semaphore up operation , Is to increase the value of a semaphore .

   When increasing the semaphore value, it is found that the waiting queue of the current semaphore is empty , No thread is currently blocked 、 Need to enter the critical area of semaphore control , Simply add the semaphore value to 1.

   When increasing the semaphore, the waiting queue is not empty , Indicates that there are threads that want to enter the critical area , But because the condition of semaphore is not satisfied , Blocked out of the critical zone . At this point, the earliest blocked thread is selected from the waiting queue of semaphores , Wake it up , So that it can enter the critical region .

/**
 *  Semaphore up operation   Add semaphore or wake up a thread blocked on semaphore ( If any )
 * */
static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    //  Temporarily shut down interrupt , Ensure that the semaphore is up Operations are atomic operations 
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            //  The waiting queue of semaphore is empty , Indicates that no thread is waiting on the semaphore 
            //  Semaphore value Add 1
            sem->value ++;
        }
        else {
            assert(wait->proc->wait_state == wait_state);
            //  Wake up the corresponding waiting thread in the waiting queue 
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

   Semaphore down And up The operational relationship is very close , Looking at each other can better understand how it works .

Mutex semaphore :

  value The value is initialized to 1 The semaphore is special , It's called a binary semaphore , Also called mutex semaphores . Mutex semaphores can be used as mutex The mutex , It is used to ensure that the data in the critical area will not be accessed concurrently by threads .

2.3  Using semaphores to solve the dining problem of philosophers

Introduction to the dining problem of philosophers

   The problem with eating philosophers is Dijkstra This paper presents a classical multi thread synchronization problem . Maybe the scene is on a circular round table , There are five philosophers sitting , And there are five forks and five bowls on the table . A philosopher usually thinks , When he was hungry, he tried to take the fork closest to him , Only when he gets two forks can he eat . After dinner , Put down the fork and continue to think .

   The basic way to solve the dining problem of philosophers is to use threads to simulate philosophers , Each thread corresponds to an active philosopher . But because of 5 Philosophers with concurrent activities scramble for the only 5 Put a fork , And philosophers can eat only when they have two forks at the same time , If there is no good synchronization mechanism for this 5 A philosopher thread to coordinate , So philosophers and threads are prone to deadlock with each other ( for example , Five philosophers picked up their left fork at the same time , I can't pick up the fork on my right , Waiting for each other . Philosophers will never be able to eat , They starve to death ).

   Use Dijkstra The proposed semaphore mechanism can solve the dining problem of philosophers , Let's see below. ucore How to use semaphores to solve the dining problem of philosophers in .

Philosophers thread subject execution logic :

  ucore Of lab7 Medium check_sync Function is the whole lab7 The total control function of the experiment . stay check_sync Use the first half of kern_thread Function creates N(N=5) A philosopher kernel thread , Used to perform philosopher_using_semaphore, Simulating the dining problem of philosophers .

  philosopher_using_semaphore The Chinese philosophers repeatedly operated as follows :

  1. Philosophers think ( adopt do_sleep System call to sleep block , Think like a philosopher )

  2. adopt phi_take_forks_sema The function tries to pick up both forks at the same time ( If you can't get the left and right fork , It's going to get stuck )

  3. Philosophers eat ( adopt do_sleep System call to sleep block , Simulating the dining of philosophers )

  4. adopt phi_put_forks_sema Function puts down the left and right forks at the same time

   Pick up the fork phi_take_forks_sema Function and put down the fork phi_put_forks_sema All of them are synchronized through the internal signal , In the following further analysis .

#define N 5 /*  The number of philosophers  */
#define LEFT (i-1+N)%N /* i Next door number of  */
#define RIGHT (i+1)%N /* i The number to the right of  */
#define THINKING 0 /*  Philosophers are thinking  */
#define HUNGRY 1 /*  Philosophers want forks  */
#define EATING 2 /*  Philosophers are eating noodles  */
#define TIMES  4 /*  eat 4 Second meal  */
#define SLEEP_TIME 10

void check_sync(void){
    int i;

    //check semaphore  Semaphores solve the problem 
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){
        sem_init(&s[i], 0);
        int pid = kernel_thread(philosopher_using_semaphore, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_semaphore failed.\n");
        }
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }

    ...  Condition variables, ( Tube side ) Solve the dining problem of philosophers ( Temporary neglect )
}


//---------- philosophers problem using semaphore ----------------------
int state_sema[N]; /*  An array that records everyone's status  */
/*  A semaphore is a special integer variable  */
semaphore_t mutex; /*  Critical regions are mutually exclusive  */
semaphore_t s[N]; /*  Every philosopher has a semaphore  */

/**
 *  Philosophers thread subject execution logic 
 * */
int philosopher_using_semaphore(void * arg) /* i: Philosopher number , from 0 To N-1 */
{
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_sema\n",i);
    while(iter++<TIMES)
    { /*  Infinite loop  */
        cprintf("Iter %d, No.%d philosopher_sema is thinking\n",iter,i); /*  Philosophers are thinking  */
        //  Use sleep blocking to simulate thinking ( Philosopher thread blocking N second )
        do_sleep(SLEEP_TIME);
        //  The philosopher tried to get the fork on both sides ( If you don't get it, it's blocked )
        phi_take_forks_sema(i); 
        /*  You need two forks , Or blocked  */
        cprintf("Iter %d, No.%d philosopher_sema is eating\n",iter,i); /*  eating  */
        //  Use sleep blocking to simulate meals ( Philosopher thread blocking N second )
        do_sleep(SLEEP_TIME);
        //  It's over , Put the fork back on the table .
        //  When it was discovered that there was a philosopher nearby who tried to eat with a fork on the left and right, but failed to get it , Trying to wake up the corresponding philosophers 
        phi_put_forks_sema(i); 
        /*  Put both forks back on the table at the same time  */
    }
    cprintf("No.%d philosopher_sema quit\n",i);
    return 0;    
}

Pick up the fork / Put down the fork function analysis :

  phi_take_forks_sema Function representation Philosophers try to pick up the fork and want to eat ; and phi_put_forks_sema Function representation Philosophers put down their left and right forks after dinner .

   Both are via global mutexes mutex Of down Operation for global mutual exclusion , Ensure that only one philosopher thread can enter the critical area at the same time , Pick up the resource fork in the critical area / Drop operation . Mutually exclusive to different threads , Ensure that there is no concurrency problem when checking the status of the left and right forks . In the back, right mutex Of up Operation is used to release mutex Mutex semaphore , To get out of the critical zone , Wake up may be blocked in mutex Other philosopher threads in semaphores , Let's jam in mutex Another thread in the semaphore is able to enter the critical region .

phi_take_forks_sema Function analysis :

   In execution phi_take_forks_sema When you take a fork , Through the key phi_test_sema Function to judge the condition , Judge the current philosopher thread i Whether or not the philosopher thread of left and right has not dined .

   If the conditions are met ( While holding the fork ,phi_test_sema Former philosophers i Has been preset to HUNGRY Hungry ), On behalf of the current philosophers i You can eat ( He picked up his left and right fork , It also means that its neighboring philosophers can't eat ).

   If the condition is not satisfied, it will be in phi_take_forks_sema Last , By down(&s[i]) Blocking in the semaphore s[i] On , Waiting for him to be awakened by philosophers who have finished eating on both sides .

phi_put_forks_sema Function analysis :

    In execution phi_put_forks_sema When you put down the fork , First, by setting state_sema[i] The status of is Thinking, For philosophers i I've finished eating and I'm thinking again . At the same time, philosophers i After putting down the fork , adopt phi_test_sema(LEFT) and phi_test_sema(RIGHT) To judge whether the neighboring philosophers are also in a state of starvation during their own meal , But I was blocked because I couldn't get the fork for a while (LEFT and RIGHT Macro uses modulus , Solve the problem of subscript loop calculation ). If it does exist , adopt phi_test_sema function Try Ask the neighboring philosophers to have dinner ( Maybe the philosopher next door to the blocked philosopher is still eating , Then it is still unable to wake it up for dinner ; And you have to wait until the philosophers on the other side finish eating Try Wake it up ).

   Through mutex semaphores mutex Implementation of critical zone resources - The mutex of fork access , Avoid the occurrence of inaccurate judgment of fork state during concurrency ; At the same time, using semaphore array semaphore_t s[N] Take from philosophers 、 Put down the fork to synchronize , So that philosophers have limited resources at fork 、 Eat in an orderly manner in conflict situations , No deadlock 、 Hunger and other phenomena .

/**
 *  philosopher i Pick up the left and right fork 
 */
void phi_take_forks_sema(int i) /* i: Philosophers number from 0 To N-1 */
{ 
    //  To get a fork, you need to pass through mutex Semaphores are mutually exclusive , Prevent concurrent problems ( Enter the critical area )
    down(&mutex);
    //  Record the philosophers i The fact of hunger ( perform phi_take_forks_sema Try to get a fork , Explain that philosophers i Into the HUNGRY Starvation )
    state_sema[i]=HUNGRY;
    //  Try to get two forks at the same time 
    phi_test_sema(i);
    //  Get out of the critical area ( Wake up may be blocked in mutex Other threads on )
    up(&mutex);
    // phi_test_sema If you succeed in getting the fork and entering the dining state , Will execute first up(&s[i]), Re execution down(&s[i]) Will not block 
    //  conversely , If phi_test_sema I didn't get the fork in the game , be down(&s[i]) Will make philosophers i Blocking in the semaphore s[i] On 
    down(&s[i]);
}
/**
 *  philosopher i Put down the fork 
 */
void phi_put_forks_sema(int i) /* i: Philosophers number from 0 To N-1 */
{ 
    //  To put a fork through mutex Semaphores are mutually exclusive , Prevent concurrent problems ( Enter the critical area )
    down(&mutex); /*  Enter the critical area  */
    //  The philosopher's meal is over ( perform phi_put_forks_sema Put down the fork , It shows that the philosopher has finished eating , Re enter THINKING Thinking state )
    state_sema[i]=THINKING;
    //  When philosophers i Dinner is over , When you put down the fork . Need to judge left 、 Is the philosopher near the right also in a state of starvation during the period of their own meals , But because he took the fork from his meal, he couldn't get the left and right forks at the same time .
    //  So philosophers i After putting down the fork, you need to try to judge after you put down the fork , Left / Right next to 、 Can a hungry philosopher have a meal , If you can, wake up the blocked philosopher thread , And put it into the dining state (EATING)
    phi_test_sema(LEFT); /*  Let's see if the left neighbor can have dinner now  */
    phi_test_sema(RIGHT); /*  Let's see if the right neighbor can have dinner now  */
    up(&mutex); /*  Get out of the critical area q( Wake up may be blocked in mutex Other threads on ) */
}

/**
 *  Judge philosophers i Can I pick up the left fork and the right fork 
 */
void phi_test_sema(i) /* i: Philosophers number from 0 To N-1 */
{ 
    //  When philosophers i In a state of hunger (HUNGRY), And the philosophers around it are not eating (EATING)
    if(state_sema[i]==HUNGRY&&state_sema[LEFT]!=EATING
            &&state_sema[RIGHT]!=EATING)
    {
        //  philosopher i I'm hungry (HUNGRY), And the forks on the left and right are not used .
        //  To put philosophers into a state of dining (EATING)
        state_sema[i]=EATING;
        //  Wake up the philosopher thread blocked on the corresponding semaphore ( When it's a philosopher thread i Do it yourself phi_test_sema(i) when , Then the semaphore is added directly 1, Offset phi_take_forks_sema Medium down operation , It means eating with a fork without getting into a blocking state )
        up(&s[i]);
    }
} 

2.4 Implementation of condition variables and tube

   The function of condition variables and semaphores is very similar , Condition variables provide a similar thread synchronization mechanism , And semaphore down/up The operation corresponds to wait and signal operation . In the original definition, a conditional variable can be implemented on the basis of semaphores ; In turn, semaphores can be implemented with realized conditional variables .

  ucore The conditional variable in is based on the semaphore , It is also a condition Monitor An important part of the structure .

Condition variables, condvar Structure definition :

/**
 *  Condition variables, 
 * */
typedef struct condvar{
    //  Conditional variable dependent semaphore , For blocking / Wake up the thread 
    semaphore_t sem;        // the sem semaphore  is used to down the waiting proc, and the signaling proc should up the waiting proc
    //  The number of threads waiting on the condition variable 
    int count;              // the number of waiters on condvar
    //  Having the conditional variable monitor Tube side 
    monitor_t * owner;      // the owner(monitor) of this condvar
} condvar_t;

Tube side monitor Structure definition :

/**
 *  Tube side 
 * */
typedef struct monitor{
    //  Mutexes that control concurrency by the process ( Should be initialized to 1 The mutex semaphore of )
    semaphore_t mutex;      // the mutex lock for going into the routines in monitor, should be initialized to 1
    //  The semaphore of each concurrent thread is coordinated within the pipeline ( The thread can suspend itself through this semaphore , Other concurrent threads or awakened threads can wake it up in turn )
    semaphore_t next;       // the next semaphore is used to down the signaling proc itself, and the other OR wakeuped waiting proc should wake up the sleeped signaling proc.
    //  Sleep in next The number of threads in the semaphore 
    int next_count;         // the number of of sleeped signaling proc
    //  The condition variable to which the tube belongs ( It could be an array , Corresponding n Conditional variables )
    condvar_t *cv;          // the condvars in monitor
} monitor_t;
/**  * Initialize the tube side  * */ void      monitor_init (monitor_t * mtp, size_t num_cv) {     int i;     assert(num_cv>0);     mtp->next_count = 0;     mtp->cv = NULL;     // The mutex semaphore value of the tube is set to 1( Not locked during initialization )     sem_init(&(mtp->mutex), 1); //unlocked     // The coordinated semaphore of the tube side is set to 0, When any thread finds that the condition is not met , Immediately block on the semaphore     sem_init(&(mtp->next), 0);     // Allocate memory space for conditional variables ( Parameters num_cv Specifies the number of condition variables owned by the pipe )     mtp->cv =(condvar_t *) kmalloc(sizeof(condvar_t)*num_cv);     assert(mtp->cv!=NULL);     // Construct conditional variables corresponding to the number of     for(i=0; i<num_cv; i++){         mtp->cv[i].count=0;         // The condition variable semaphore is set to 0, When any thread finds that the condition is not met , Immediately block on the semaphore         sem_init(&(mtp->cv[i].sem),0);         mtp->cv[i].owner=mtp;     } }

The wait operation of conditional variable is implemented :

  cond_wait The conditions of variable realization wait operation . Conditional variable wait Operation and semaphore down The function is similar to . When the condition corresponding to the condition variable is not satisfied , Through the semaphore down operation , Block the current thread 、 Wait on the semaphore to which the condition variable belongs .

// Suspend calling thread on a condition variable waiting for condition Atomically unlocks 
// mutex and suspends calling thread on conditional variable after waking up locks mutex. Notice: mp is mutex semaphore for monitor's procedures
/**
 *  Conditional variables block waiting operations 
 *  Block the current thread on the condition variable , Wait for other threads to pass through cond_signal Wake it up .
 * */
void
cond_wait (condvar_t *cvp) {
    //LAB7 EXERCISE1: YOUR CODE
    cprintf("cond_wait begin:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    /*
     *         cv.count ++;
     *         if(mt.next_count>0)
     *            signal(mt.next)
     *         else
     *            signal(mt.mutex);
     *         wait(cv.sem);
     *         cv.count --;
     */

    //  The number of threads blocked on the current condition variable plus 1
    cvp->count++;
    if(cvp->owner->next_count > 0)
        //  There are other blocked threads in the corresponding pipeline 
        //  Wake up the blocking in the corresponding tube side to coordinate the semaphore next Thread in 
        up(&(cvp->owner->next));
    else
        //  If there are no other threads blocked in the corresponding pipeline 
        //  Release the corresponding tube side mutex Binary semaphore 
        up(&(cvp->owner->mutex));
    //  Block the current thread on the condition variable 
    down(&(cvp->sem));
    // down return , It means it has been awakened again , Condition variables, count reduce 1
    cvp->count --;
    cprintf("cond_wait end:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

Implementation of wake-up operation for conditional variables :

  cond_signal Function is used to implement the signal operation . Conditional variable signal Operation and semaphore up The function is similar to . When the condition corresponding to the condition variable is satisfied , Through the semaphore up operation , Wake up the thread blocked in the corresponding condition variable .

// Unlock one of threads waiting on the condition variable. 
/**
 *  Condition variable wake up operation 
 *  Unlock ( Wake up the ) A thread waiting on the current condition variable 
 * */
void 
cond_signal (condvar_t *cvp) {
    //LAB7 EXERCISE1: YOUR CODE
    cprintf("cond_signal begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    /*
     *      cond_signal(cv) {
     *          if(cv.count>0) {
     *             mt.next_count ++;
     *             signal(cv.sem);
     *             wait(mt.next);
     *             mt.next_count--;
     *          }
     *       }
     */
    //  If the number of threads waiting on the condition variable is greater than 0
    if(cvp->count>0) {
        //  The current thread needs to be blocked in the coordination semaphore of the pipe next On ,next_count Add 1
        cvp->owner->next_count ++;
        //  Make the thread blocking on the condition variable proceed up operation , Wake up the thread 
        up(&(cvp->sem));
        //  The coordination semaphore that causes the current thread to block in the pipeline next On 
        //  Ensure that there is only one active thread in the pipeline critical area , Shilling is stuck in next On the semaphore ; The thread waiting to be awakened leaves the critical area and then reverses itself from next Wake up on the semaphore 
        down(&(cvp->owner->next));
        //  The current thread is awakened by another thread from down Function ,next_count reduce 1
        cvp->owner->next_count --;
    }
    cprintf("cond_signal end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

The interaction between conditional variables and the tube side :

   Carefully compare the implementation of condition variables and semaphores , It will be found that the general implementation ideas are consistent . but ucore The condition variables implemented in are working as part of the tube side , So in wait and signal During the operation, additional coupling with the corresponding tube side is provided owner The place of interaction .

   The thread that enters the critical section in the tube side finds that the condition is not satisfied and changes the condition variable wait In operation , It is necessary to release the lock in the critical area of the tube side , stay wait When the operation suspends itself, other threads that want to enter the pipeline get access to the critical section .

   When a thread in a critical section of a pipe finds that a condition is satisfied , Of the corresponding conditional variable will be executed signal Operation to wake up a thread waiting on it . But because of the mutual exclusion of the critical region on the tube side , Cannot allow more than one thread to run in a critical section , So execute signal The thread of operation needs to suspend its own blocking in the pipe process first next On the semaphore , Make the awakened thread monopolize the critical area resource . When the awakened thread leaves the critical area , It will also wake up and hang up in time next The corresponding thread on the semaphore .

2.5  Using management to solve the dining problem of philosophers

   In the concurrent environment, multiple threads sleep alternately through the synchronization mechanism such as condition variables / Wake up the , Logical execution flow is not coherent , Therefore, the realization of condition variable and tube side appears to be relatively round , It's puzzling . By learning how to use management process to solve the dining problem of philosophers , Look at using the tube side / How do conditional variables synchronize and mutually exclusive threads , Deepen the understanding of conditional variables 、 Understanding of the working mechanism of management process . 

   stay checkSync The second half of the function , It's about how to use management to solve the dining problem of philosophers . stay check_sync The second half of creates N(N=5) A philosopher kernel thread , Used to perform philosopher_using_condvar function , Simulating the dining problem of philosophers .

philosopher_using_condvar The Chinese philosophers repeatedly operated as follows ( The overall process and the implementation of semaphore are roughly the same ):

  1. Philosophers think ( adopt do_sleep System call to sleep block , Think like a philosopher )

  2. adopt phi_take_forks_condvar The function tries to pick up both forks at the same time ( If you don't get the left and right fork , Get stuck in a jam )

  3. Philosophers eat ( adopt do_sleep System call to sleep block , Simulating the dining of philosophers )

  4. adopt phi_put_forks_condvar Function puts down the left and right forks at the same time , Back to thinking

   Pick up the fork phi_take_forks_condvar Function and put down the fork phi_put_forks_condvar All the functions inside are synchronized by conditional variables , In the following further analysis .

checkSync function :

void check_sync(void){
    int i;

    //check semaphore
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){
        sem_init(&s[i], 0);
        int pid = kernel_thread(philosopher_using_semaphore, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_semaphore failed.\n");
        }
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }

    //check condition variable
    monitor_init(&mt, N);
    for(i=0;i<N;i++){
        state_condvar[i]=THINKING;
        int pid = kernel_thread(philosopher_using_condvar, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_condvar failed.\n");
        }
        philosopher_proc_condvar[i] = find_proc(pid);
        set_proc_name(philosopher_proc_condvar[i], "philosopher_condvar_proc");
    }
}

Pick up the fork in tube pass implementation / Put down the fork function analysis :

   phi_take_forks_condvar Functional expression philosophers try to pick up the fork and want to eat ; and phi_put_forks_condvar The function expresses that the philosopher puts down his left and right fork after dinner .

   Both pass Semaphores in mutexes mutex Of down Operation for global mutual exclusion , Ensure that only one philosopher thread can enter the critical area at the same time , Pick up the resource fork in the critical area / Drop operation , Mutually exclusive to different threads , Ensure that there is no concurrency problem when checking the status of the left and right forks .

   When leaving the critical area of the tube side ( notes into routine in monitor and leave routine in monitor The critical area code of tube side is between ), The current thread depends on whether there are other threads in the pipeline (mtp->next_count>0) And there are different operations . When it is found that next When there are other threads blocking on the semaphore , Wake up first next Threads on semaphores ( Blocked in next The thread on is to wake up the thread waiting on a condition variable , In order to ensure that the critical area is mutually exclusive, it is voluntarily blocked , Therefore, the awakened thread needs to wake up for the first time after leaving the critical area ); And if the next There are no dormant threads in the semaphore , So it's similar to the implementation of semaphores , Release mutex The mutex , Wake up a thread that may be waiting on it .

   Above ucore The logic of thread interaction is based on Hoare Semantic , In addition, there is MESA Semantic management and Hansen Semantic Management (MESA Management and Hansen The pipeline implementation is similar to the previous semaphore to realize the dining of philosophers ).

  Hoare Tube in signal Waking up other threads will cause you to sleep , It strictly guarantees the mutual exclusion of threads in critical area , More reliable in theory , It is common in the theory of textbooks . because Hoare The semantic management process needs to introduce an additional waiting queue (next Semaphore ), Therefore, its performance is not as good as the other two semantics , In reality, very few places are used .

phi_take_forks_condvar function ( At the same time pick up the left and right fork ):

void phi_take_forks_condvar(int i) {
    //  To get a fork, you need to pass through mutex Semaphores are mutually exclusive , Prevent concurrent problems ( Enter the critical area )
    down(&(mtp->mutex));
//--------into routine in monitor--------------
    // LAB7 EXERCISE1: YOUR CODE
    // I am hungry
    // try to get fork
    // I am hungry
    //  Record the philosophers i The fact of hunger ( perform phi_take_forks_condvar Try to get a fork , Explain that philosophers i Into the HUNGRY Starvation )
    state_condvar[i]=HUNGRY;
    //  Try to get two forks at the same time 
    phi_test_condvar(i);
    if (state_condvar[i] != EATING) {
        // state_condvar[i] State not for EATING, explain phi_test_condvar Trying to eat with a fork failed 
        cprintf("phi_take_forks_condvar: %d didn't get fork and will wait\n",i);
        //  Wait for the condition variable blocked in the tube side cv[i] On 
        cond_wait(&mtp->cv[i]);
    }
//--------leave routine in monitor--------------
    if(mtp->next_count>0){
        //  When leaving the critical area of the tube side , If a thread is found waiting in mtp->next On 
        //  In the current experiment , The current thread executing here may be blocked in cond_wait Other threads in the wake up , The corresponding thread is passed through phi_test_condvar Of cond_signal Operation to wake up the current thread 
        //  perform cond_signal In order to ensure that there is no concurrent thread access in the critical section of the pipeline , When other threads wake up , It's going to get stuck in the tube next On the semaphore , Wait for the thread leaving the critical section to wake it up 
        up(&(mtp->next));
    }else{
        //  When leaving the critical area of the tube side , There are no other threads waiting for mtp->next On , Release the mutex directly mutex that will do ( Wake up may be blocked in mutex Other threads on )
        up(&(mtp->mutex));
    }
}

phi_put_forks_condvar function ( Put down the left and right forks at the same time ):

void phi_put_forks_condvar(int i) {
    //  To put a fork through mutex Semaphores are mutually exclusive , Prevent concurrent problems ( Enter the critical area )
    down(&(mtp->mutex));

//--------into routine in monitor--------------
    // LAB7 EXERCISE1: YOUR CODE
    // I ate over
    // test left and right neighbors
    // I ate over
    //  The philosopher's meal is over ( perform phi_put_forks_condvar Put down the fork , It shows that the philosopher has finished eating , Re enter THINKING Thinking state )
    state_condvar[i]=THINKING;
    // test left and right neighbors
    //  When philosophers i Dinner is over , When you put down the fork . Need to judge left 、 Is the philosopher near the right also in a state of starvation during the period of their own meals , But because he took the fork from his meal, he couldn't get the left and right forks at the same time .
    //  So philosophers i After putting down the fork, you need to try to judge after you put down the fork , Left / Right next to 、 Can a hungry philosopher have a meal , If you can, wake up the blocked philosopher thread , And put it into the dining state (EATING)
    phi_test_condvar(LEFT); //  Let's see if the left neighbor can have dinner now 
    phi_test_condvar(RIGHT); //  Let's see if the right neighbor can have dinner now 
//--------leave routine in monitor--------------
    // lab7 The reference answer to 
    if(mtp->next_count>0){
        cprintf("execute here mtp->next_count>0 \n\n\n\n\n\n");
        up(&(mtp->next));
    }else{
        cprintf("execute here mtp->next_count=0 \n\n\n\n\n");
        up(&(mtp->mutex));
    }

    //  I don't think putting a fork is the same as taking it , There will be no mtp->next_count>0 The situation of , Just release the mutex ( If there's a problem with understanding here , Also please correct me )
    //  When the fork thread is in phi_put_forks_condvar When it leaves the critical area of the tube side , There are only two cases 
    // 1.  No neighbors were found to be able to eat , It won't be blocked 
    // 2.  I was blocked by a fork before I found out I had a neighbor , Now it's time for dinner ,phi_test_condvar Medium cond_signal Will temporarily block themselves in next On the semaphore 
    //  But soon the neighboring philosopher thread wakes itself up as soon as it leaves the critical region , stay cond_signal In the operation after being awakened mtp->next_count It will reduce itself , And into 0
    //
    //  In both cases , Because the tube itself has a mutex Mutex semaphore , So there won't be two threads blocking at the same time next In the semaphore , Therefore, it will not appear in the reference answer mtp->next_count>0 The situation of 
    // up(&(mtp->mutex));
} 

phi_test_condvar function ( Judge philosophers i If you can pick up the fork and start eating ):

void phi_test_condvar (i) {
    //  When philosophers i In a state of hunger (HUNGRY), And the philosophers around it are not eating (EATING)
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        //  philosopher i I'm hungry (HUNGRY), And the forks on the left and right are not used .
        //  To put philosophers into a state of dining (EATING)
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        //  Wake up the philosopher thread blocked on the corresponding semaphore 
        cond_signal(&mtp->cv[i]) ;
    }
}

2.6 The difference between semaphore and tube side

   The semaphore is a simple 、 Efficient synchronization and mutual exclusion mechanism , But it's also because it's too low-level , So you need to be very careful when writing thread synchronization code , Careful consideration of the use of each semaphore can ensure the correctness of the program , It's a huge burden on the minds of developers .

   And if we look at the tube side as a whole structure , You will find that although the pipe program abstracts the code logic that controls synchronization into a fixed template, it becomes easy to use , But it is seriously coupled with the critical area business logic code to be protected , It is very difficult for operating system developers to embed the code of synchronization of management control into the corresponding application .

   Therefore, the operating system usually only provides semaphores and condition variables, which are lower level 、 Low coupling synchronization and mutual exclusion mechanism ; The management mechanism is more implemented by the compiler of high-level language at the language level , In order to simplify the complexity of programmers developing complex concurrent synchronization programs . High level language compiler compiles local machine code , The semaphore or conditional variable mechanism provided by the operating system bottom layer can be used to implement the pipeline in the code logic block that needs to be synchronized .

   for example java In the method definition, simply add synchronized Keyword can control the execution of this method in multithreading environment . This is because when compiling into bytecode , Compared with the common method, some additional tubes are inserted Monitor Related synchronization control code ( The semaphore that the bottom layer of the tube depends on 、 The conditional variable mechanism still depends on the corresponding operating system platform , Just being jvm The difference is masked , Give Way java Programmers don't perceive ).

3. summary

   adopt ucore Of lab7 Learning from , Let me understand the waiting queue 、 Semaphore 、 Condition variables and general working principle of tube side , It's also true of what you'll normally come into contact with java Medium synchronized、AQS、Reentrantlock The underlying mechanism has been further understood .

  lab7 I have gained a lot from my study , But this is not enough for the study of thread synchronization related fields . Both belong to interprocess communication IPC The classic problem of the field is apart from the dining problem of philosophers , And readers / Writer questions, etc ; For thread safety issues , In addition to using hibernation / Wake up the blocking mode of thread context switch , And use CAS Wait to try again ; Except for semaphores 、 Conditional variables are based on the thread synchronization mode in the single machine system , And based on Distributed Systems , The mechanism of multi machine thread synchronization through the network and so on . Although there is not enough knowledge to understand , But through ucore Operating system learning , It has laid a foundation for me to learn relevant knowledge in the field , It also gives me the confidence that I can finally integrate this knowledge .

   The full code comments for this blog are in my github On :https://github.com/1399852153/ucore_os_lab (fork From the official warehouse ) Medium lab7_answer.

   I hope my blog can help with the operating system 、ucore os Interested people . There are many shortcomings , Please give me more advice .

版权声明
本文为[Bear Restaurant]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201225000607294l.html

Scroll to Top