ucore lab7

lab7

The experiment purpose

• Understand the design and implementation of synchronous mutual exclusion of operating system ;
• Understand the underlying support technology ： Disable interrupt 、 Timer 、 Waiting in line ;
• stay ucore Understand semaphores （semaphore） Specific implementation of the mechanism ;
• Understand the management mechanism , stay ucore Add tube based in the kernel （monitor） The conditional variable of （condition
  variable） Support for ;
• Understand the classic process synchronization problem , And can use the synchronization mechanism to solve the problem of process synchronization .

Experimental content

Experiment 6 completed the scheduling framework and specific scheduling algorithm of user processes , Multiple processes can be scheduled to run . If multiple processes need to work together or access shared resources , Then there is the problem of how to synchronize and orderly compete . This experiment , Mainly familiar ucore Process synchronization mechanism — Semaphore （semaphore） Mechanism , And the solution to the dining problem of philosophers based on semaphores . Then master the concept and principle of tube pass , And refer to the semaphore mechanism , Realize the conditional variable mechanism based on management and solve the dining problem of philosophers based on conditional variables .

In this experiment , stay kern/sync/check_sync.c Provides a semaphore based solution to the dining problem of philosophers . At the same time, you need to complete the exercise , That is to say, it is based on the pipe process （ It mainly uses conditional variables and mutually exclusive semaphores flexibly ） The solution to the dining problem of philosophers . The philosopher's dining problem is described as follows ： There are five philosophers , Their lifestyle alternates between thinking and eating . Philosophers share a round table , There are five chairs around , Take a seat each . There are five bowls and five chopsticks on the round table , When a philosopher thinks , He doesn't talk to others , When I'm hungry, I try to use the left side 、 Right is closest to his chopsticks , But he may not get any . Only when he gets two chopsticks , Before eating , After dinner , Put down your chopsticks and continue to think .

practice

Requirements for experimental report ：

• be based on markdown Format to complete , Text based
• Fill in the report required in each basic exercise
• After finishing the experiment , Please analyze ucore_lab Reference answers provided in , Please explain the difference between your implementation and the reference answer in the experiment report
• List the knowledge points you think are important in this experiment , And corresponding OS Knowledge points in principle , And briefly explain your meaning of the two , Relationship , Understanding of differences and other aspects （ It may also appear that the knowledge points in the experiment have no corresponding principle knowledge points ）
• List what you think OS Principle is very important , But there is no corresponding knowledge point in the experiment

practice 0： Fill in the existing experiment

This experiment relies on experiments 1/2/3/4/5/6. Please take your experiment 1/2/3/4/5/6 Fill in the code in this experiment. There are “LAB1”/“LAB2”/“LAB3”/“LAB4”/“LAB5”/“LAB6” The corresponding part of the notes . And ensure that the compilation passes . Be careful ： In order to execute correctly lab7 Test application for , It may be necessary to test the completed experiments 1/2/3/4/5/6 Code for further improvements .

Use meld Compare directories ,

You can know , We need to modify the following documents ：

• proc.c
• default_pmm.c
• pmm.c
• swap_fifo.c
• vmm.c
• trap.c
• sched.c

There is no need to modify this time , It can be used directly .

practice 1: Understand the implementation of kernel level semaphores and the dining problem of philosophers based on kernel level semaphores （ No coding required ）

Finish the exercise 0 after , I suggest you compare （ You can use meld Wait for the documents diff Comparison software ） Completed by individuals lab6 And practice 0 Just revised after completion lab7 The difference between , Analysis and understanding lab7 Implementation process using semaphores . perform make grade, Most test cases should pass .

Please give the design description of kernel level semaphore in the experimental report , And say that it roughly implements the flow process .

Please give the user status process in the experiment report / Thread provides the design scheme of semaphore mechanism , It also compares and explains the similarities and differences of semaphore providing mechanisms at the kernel level .

The dining problem of philosophers ：

uCore The main code of philosophers' dining in is relatively simple ： Every philosopher picks up a fork , Eat , Then put down the fork .

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  */

struct proc_struct *philosopher_proc_sema[N];

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  */
        do_sleep(SLEEP_TIME);
        phi_take_forks_sema(i);
        /*  You need two forks , Or blocked  */
        cprintf("Iter %d, No.%d philosopher_sema is eating\n",iter,i); /*  eating  */
        do_sleep(SLEEP_TIME);
        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 / When you put down the fork , Due to the need to modify the status of the current philosopher , At the same time, the status is Global shared variables , So you need to acquire locks to prevent conditional competition .

When putting the fork back on the table , If the two philosophers on the left and right of the current philosopher are in Starvation , That is, when you are ready to eat but do not have a knife and fork , If the conditions are met , Then awaken these two philosophers and let them continue to eat .

void phi_take_forks_sema(int i) /* i： Philosophers number from 0 To N-1 */
{
    
        down(&mutex); /*  Enter the critical area  */
        state_sema[i]=HUNGRY; /*  Record the philosophers i The fact of hunger  */
        phi_test_sema(i); /*  Trying to get two forks  */
        up(&mutex); /*  Get out of the critical area  */
        down(&s[i]); /*  If you don't get a fork, it will block  */
}
void phi_put_forks_sema(int i) /* i： Philosophers number from 0 To N-1 */
{
    
        down(&mutex); /*  Enter the critical area  */
        state_sema[i]=THINKING; /*  The philosopher's meal is over  */
        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  */
}

phi_test_sema The function is used to set the philosopher's eating state . If the current philosopher meets the eating conditions , Then update the philosopher status , Execute the corresponding of philosopher lock V operation , With Wake up the The thread corresponding to the philosopher waiting for the fork .

void phi_test_sema(i) /* i： Philosophers number from 0 To N-1 */
{
    
    if(state_sema[i]==HUNGRY&&state_sema[LEFT]!=EATING
            &&state_sema[RIGHT]!=EATING)
    {
    
        state_sema[i]=EATING;
        up(&s[i]);
    }
}

Please give the design description of kernel level semaphore , And explain the general implementation process ：

First , Learn about semaphores ：

Semaphore

Semaphores are the implementation of a synchronous mutual exclusion mechanism , It exists in all kinds of operating system kernels nowadays . be relative to spinlock Application object of , The application object of semaphore is the process that runs for a long time in the critical area . Processes waiting for semaphores need sleep to reduce occupancy CPU The cost of .

struct semaphore {
    
int count;
queueType queue;
};
void semWait(semaphore s)
{
    
s.count--;
if (s.count < 0) {
    
/* place this process in s.queue */;
/* block this process */;
}
}
void semSignal(semaphore s)
{
    
s.count++;
if (s.count<= 0) {
    
/* remove a process P from s.queue */;
/* place process P on ready list */;
}
}

Based on the implementation of appeal semaphore, it can be considered , When more than one （>1） When processes can mutually exclusive or cooperate synchronously , A process will stop at a certain position because it cannot meet a certain condition set by the semaphore , Until it receives a specific signal （ Indicates that the conditions are met ）. To signal , You need to use a special variable called semaphore . Is the passing semaphore s Transmitting signals , Semaphore V The operation adopts the process executable primitive semSignal(s); Is the passing semaphore s Received signal , Semaphore P The operation adopts the process executable primitive semWait(s); If the corresponding signal is still not sent , Then the process is blocked or sleep , Until it is sent .

Semaphore structure

typedef struct {
    
    int value;
    wait_queue_t wait_queue;
} semaphore_t;

semaphore_t It is the most basic recording semaphore （record semaphore) structure , Contains integer values for counting value, And a process waiting queue wait_queue, A waiting process will hang on this waiting queue .

This experiment synchronizes the underlying support of mutual exclusion

stay ucore The underlying mechanisms provided in include interrupt switch control and test_and_set Related atomic operation machine instructions .kern/sync.c Control function of switch interrupt implemented in local_intr_save(x) and local_intr_restore(x), They are based on kern/driver Under the document intr_enable()、intr_disable() Functionally implemented . The specific calling relationship is ：

 Close the interrupt ：local_intr_save --> __intr_save --> intr_disable --> cli
 Open the interrupt ：local_intr_restore--> __intr_restore --> intr_enable --> sti

The final cli and sti yes x86 The machine instructions for , Finally, the off interrupt and on interrupt are realized , That is, set up eflags Bits related to interrupts in registers . Interrupt by closing , It can prevent the current control flow from being interrupted by other interrupt event processing . Since it cannot be interrupted , That means that the current process running in the kernel cannot be interrupted or rescheduled , That is, it realizes the mutually exclusive operation of the critical area . So in the case of a single processor , Mutual exclusion protection of critical area can be realized through switch interruption , The general writing method of critical area code that needs mutual exclusion is ：

local_intr_save(intr_flag);
{
    
 Critical area code 
}
local_intr_restore(intr_flag);
……

stay ucore The most important semaphore operation in is P Operation function down(semaphore_t *sem) and V Operation function up(semaphore_t *sem). But the specific implementation of these two functions is _down(semaphore_t *sem, uint32_t wait_state) Functions and __up(semaphore_t *sem, uint32_t wait_state) function , The specific implementation of the two is described as follows ：

__down(semaphore_t *sem, uint32_t wait_state, timer_t *timer)：

 static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    
    bool intr_flag;                                      
    local_intr_save(intr_flag);         // Close the interrupt 
    if (sem->value > 0) {
                   // You can get the semaphore 
        sem->value --;                  //value Minus one 
        local_intr_restore(intr_flag);  // Open the interrupt 
        return 0;
    }
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state); // Add the current process to the waiting queue 
    local_intr_restore(intr_flag);  // Turn on interrupt 

    schedule();             // Schedule next process 

    local_intr_save(intr_flag);  // Awakened , Close the interrupt 
    wait_current_del(&(sem->wait_queue),wait);  // Remove the current process from the waiting queue 
    local_intr_restore(intr_flag); // Turn on interrupt 

    if (wait->wakeup_flags != wait_state) {
    
        return wait->wakeup_flags;
    }
    return 0;
}

So in summary ：

First turn off the interrupt , Then judge the current semaphore value Is it greater than 0. If it is >0, It indicates that the semaphore can be obtained , So let value Minus one , And open the interrupt to return ; If not >0, It indicates that the semaphore cannot be obtained , Therefore, you need to add the current process to the waiting queue , And turn on the interrupt , Then run the scheduler to select another process to execute . If you are V Operation wake up , Then associate itself wait Remove from waiting queue （ This process needs to be interrupted first , Open and interrupt after completion ）.

__up(semaphore_t *sem, uint32_t wait_state)：

static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    
    bool intr_flag;                           
    local_intr_save(intr_flag);           // Close the interrupt 
    {
     
        wait_t *wait;
       if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
     // No process waiting 
            sem->value ++;  //value Add one 
        }
        else {
    
            assert(wait->proc->wait_state == wait_state);   // There are processes waiting 
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1); // The first one. wait Delete , Wake-up process .
        }
    }
    local_intr_restore(intr_flag); // Turn on interrupt 
}

Summarize the process ：

First, turn off the interrupt , If the semaphore corresponds to wait queue No process is waiting , Directly put the signal quantity value Add one , Then open the interrupt and return ; If there is a process waiting and the reason for the process waiting is semophore Set up , Call wakeup_wait Function will waitqueue Waiting for the first wait Delete , And put this wait The associated process wakes up , Finally, the interrupt returns .

wait for queue wait_queue Defined in another structure ：

//  For waiting queue , Storing the thread currently waiting PCB And wake-up reason and wait queue and wait queue flag for restoring structure 
typedef  struct {
    
    struct proc_struct *proc;     // Wait for the pointer of the process 
    uint32_t wakeup_flags;        // The reason why the process was put into the waiting queue is marked 
    wait_queue_t *wait_queue;     // Point to this wait The structure belongs to wait_queue
    list_entry_t wait_link;       // To organize wait_queue in wait Connection of nodes 
} wait_t;

In the semaphore structure value The meaning is as follows ：

• value>0, Express Number of free shared resources
• vlaue<0, That represents the semaphore The number of processes in the waiting queue
• value=0, Express The wait queue is empty

about V Operation and P operation , Use them separately up and down Function to correspond to , Can be used to achieve kernel level semaphore design .

Question answering

• Please give the user status process in the experiment report / Thread provides the design scheme of semaphore mechanism , It also compares and explains the similarities and differences of semaphore providing mechanisms at the kernel level .

User mode process / The data structure of thread semaphore is the same as that of kernel state . User state process / The semaphore related operations of threads are completed through system calls . Whenever a user process calls a semaphore correlation function , Will enter the system call , Processed by the kernel , Then return to user mode to continue execution . Compared with the semaphore mechanism provided for the kernel , User state process / Threads need to execute privileged instructions such as interrupt operations , You need to enter the kernel state through system calls and use the kernel semaphore mechanism .

The kernel is a user mode process / When a thread provides a semaphore mechanism , You need to design multiple application program interfaces , User mode threads can only use kernel services through these interfaces provided by the kernel . In view of Linux Standard interface provided , These interfaces provided by the kernel can be ：

/*Initialize semaphore object SEM to VALUE. If PSHARED then share it with other processes. */
int sem_init (sem_t *__sem, int __pshared, unsigned int __value);
/* Free resources associated with semaphore object SEM. */
//  Release all the resources used by the semaphore 
int sem_destroy (sem_t *__sem);

/* Open a named semaphore NAME with open flags OFLAG. */
//  Start a new semaphore , And use the given flag To specify its flag 
sem_t *sem_open (const char *__name, int __oflag, ...);

/* Close descriptor for named semaphore SEM. */
//  Close the descriptor used by the current semaphore 
int sem_close (sem_t *__sem);

/* Remove named semaphore NAME. */
int sem_unlink (const char *__name);

/* Wait for SEM being posted. This function is a cancellation point and therefore not marked with __THROW. */
//  One P operation , If sem value > 0, be sem value--; Otherwise, it will block until sem value > 0
int sem_wait (sem_t *__sem);

/* Test whether SEM is posted. */
int sem_trywait (sem_t *__sem);

/* Post SEM. */
//  One V operation , Put the specified semaphore  sem  The value of the add  1, Wake up any thread waiting for the semaphore .
int sem_post (sem_t *__sem);

/* Get current value of SEM and store it in *SVAL. */
//  Gets the value of the current semaphore 
int sem_getvalue (sem_t *__restrict __sem, int *__restrict __sval);

• The same thing
  • The core implementation logic is the same
• Difference
  • Kernel semaphore mechanism can directly call kernel services , User mode services need to access kernel mode services through the interface provided by the kernel , This involves the relevant mechanism of user state to kernel state .
  • Kernel semaphores are stored in the kernel stack ; But the semaphore of user state is stored in the user stack .

practice 2: Complete the kernel level conditional variables and the philosophers' dining problem based on kernel level conditional variables （ Need to code ）

First, master the management mechanism , Then, based on the semaphore implementation, complete the conditional variable implementation , Then the solution to the dining problem of philosophers is realized by using the management mechanism （ Based on conditional variables ）.

perform ：make grade
. If the displayed application tests all output ok, Is basically correct . If it's just a program that can't pass , such as matrix.c, Can be carried out

make run-matrix

Command to debug it separately . See the appendix for the general implementation results .

Please give the design description of kernel level condition variables in the experimental report , And say that it roughly implements the flow process .

Please give the user status process in the experiment report / Thread provides the design scheme of conditional variable mechanism , It also compares and explains the similarities and differences of the mechanism of providing conditional variables to the kernel level .

Please answer in the experiment report ： Whether the conditional variable can be completed without semaphore mechanism ？ If not , Please give reasons , If you can , Please give the design description and specific implementation .

Based on the semaphore implementation, complete the conditional variable implementation , Give the design description of kernel level condition variables , And explain the general implementation process .

The tube side consists of a lock and several conditional variables , The following is the structure code of tube pass and condition variables

typedef struct monitor monitor_t;

typedef struct condvar{
    
    semaphore_t sem;        //  Semaphore corresponding to conditional variable 
    int count;              //  The total number of waiting processes waiting for the current condition variable 
    monitor_t * owner;      //  Parent process of current condition variable 
} condvar_t;

typedef struct monitor{
    
    semaphore_t mutex;      //  Pipe lock , Only one process can execute the management code at a time . The value is initialized to 1
    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.
    int next_count;         // the number of of sleeped signaling proc
    condvar_t *cv;          //  An array of all condition variables stored in the current pipe 
} monitor_t;

Be careful ：monitor In structure next The functions of semaphores are combined below cond_signal Explain to understand .

Member variables in the pipe mutex Is a binary semaphore , It is the key element to allow only one process to enter the management process at a time , Ensure mutually exclusive access . Conditional variables in the tube side cv Through execution wait_cv, Will make waiting for a certain condition C For real processes to leave the tube and sleep , And let other processes enter the pipe to continue execution ; And a certain process entering the pipe set conditions C True and execute signal_cv when , Be able to wait for a certain condition C For real, the sleep process is awakened , So as to continue to enter the tube side for execution . Member variable semaphore in the tube next And plastic variables next_count Is to match the process to the condition variable cv Set for the operation of , This is due to sending signal_cv The process of A Will wake up the sleep process B, process B Execution will cause the process A sleep , Until the process B Leave the tube , process A In order to proceed , This synchronization process is through semaphores next Accomplished ; and next_count Indicates that due to sending singal_cv And the number of sleep processes .

Tube side

Management is introduced to centralize and encapsulate all access to shared resources and the synchronization operations required .Hansan Definition of tube side ：“ A manager defines a data structure and can be executed by concurrent processes （ In this data structure ） A set of operations , This set of operations can synchronize the process and change the data in the pipe ”. It can be seen from the above definition that , The tube side consists of four parts ：

• Shared variables inside the tube ;

• The condition variables inside the tube side ;

• Processes executed concurrently inside the management process ;

• A statement that sets the initial value of shared data locally within the pipe process .

Data structures confined to the tube , It can only be accessed by the operation process limited to the tube side , It cannot be accessed by any operation process outside the tube ; On the other hand , The operation process limited in the pipeline also mainly accesses the data structure in the pipeline . thus it can be seen , The tube side is equivalent to an isolation zone , It encloses shared variables and several processes that operate on them , When all processes want to access critical resources , All have to go through the tube to get into , And only one process is allowed to enter the process at a time , Therefore, it is necessary to ensure that processes are mutually exclusive .

Condition variables, （CV）

A conditional variable CV It can be understood as the waiting queue of a process , The process in the queue is waiting for a condition C Become true . Each conditional variable is associated with an assertion “ Assertion ( Program )”)Pc. When a process waits for a condition variable , This process does not count as occupying the pipe , Therefore, other processes can enter the pipe and execute , Change the state of the tube side , Notification condition variable CV Its associated assertion Pc True in current state .

So for conditional variables CV There are two main operations ：

• wait_cv： Called by a process , Wait for assertion Pc After being satisfied, the process can resume execution . When the process hangs on the condition variable and waits , It is not considered to occupy the pipe .
• signal_cv： Called by a process , To point out the assertion Pc Now it's true , Thus, the waiting assertion can be awakened Pc The satisfied process continues .

condvar_t The definition of

typedef struct condvar{
    
    semaphore_t sem; // Used to send out wait_cv Wait for a condition of operation C Sleep for the real process 
    int count;       //  The number of sleep processes on this condition variable 
    monitor_t * owner; //  The host process of this condition variable 
} condvar_t;

The definition of conditional variables also includes a series of member variables , Semaphore sem Used to send wait_cv Wait for a condition of operation C Sleep for the real process , And let go signal_cv The process of operation passes through this sem To wake up the process of sleep .count Indicates the number of sleep processes waiting on this conditional variable .owner Indicates which pipe is the host of this condition variable .

monitor_init() function ：

Initialize condition variables , Set up next_count by 0, Yes mutex,next To initialize , sem_init(&(mtp->mutex), 1); //unlocked
And assign num individual condvar_t, Set up cv Of count by 0, initialization cv Of sem and owner.

for(i=0; i<num_cv; i++){
    

mtp->cv[i].count=0;
sem_init(&(mtp->cv[i].sem),0);
mtp->cv[i].owner=mtp;
}

cond_signal() function : Wake up the thread sleeping on the condition variable

If cv Of count>0, Description yes proc Waiting for the , Then you need to wake up and wait cv.sem Upper proc, And make yourself sleep , meanwhile monitor.next_count++, Execute after being awakened monitor.next_count–; If cv Of count == 0, No explanation proc Waiting for the cv.sem, Return function directly .

First process B Judge cv.count, If not greater than 0, It means that there is currently no sleep process , Therefore, there is no awakened object , Just return the function directly ; If it is greater than 0, This indicates that there is currently a sleep process A, Therefore, we need to wake up and wait in cv.sem The process of sleep A. Because only one process is allowed to execute in the pipe , So once the process B Awaken others （ process A）, Then you need sleep . So let monitor.next_count Add one , And let yourself （ process B） Sleep on semaphore monitor.next On . If you wake up , This makes monitor.next_count Minus one .

for(i=0; i<num_cv; i++){
    

if(cvp ->count > 0){
    
cvp->owner -> next_count ++;
up(&(cvp->sem));
down(&(cvp -> owner->next));// This is it. Hoare Mechanism , Directly switch back to the process waiting for the condition variable , When the execution is finished , This thread can execute  count--
cvp -> owner -> next_count --;
 }

cond_wait The implementation of the

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);
      cvp->count++; // Add one to the number of processes that need sleep 
      if(cvp->owner->next_count > 0) 
         up(&(cvp->owner->next)); // Wake up the next process in the process list 
      else
         up(&(cvp->owner->mutex)); // Wake up and sleep in monitor.mutex Progress on  
      down(&(cvp->sem));  // Wait for this process  
      cvp->count --;  // The number of sleep processes waiting for this condition after waking up will be reduced by one 
    cprintf("cond_wait end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

It can be seen that if the process A Yes cond_wait function , Indicates that this process waits for a condition C Not true , Need sleep . Therefore, it indicates the number of sleep processes waiting for this condition cv.count One more . Then there are two situations .

Situation 1 ： If monitor.next_count If it is greater than 0, Indicates that there is greater than or equal to 1 Process execution cond_signal Function and fell asleep , I slept in monitor.next On the semaphore . Suppose these processes form S Process linked list . So we need to wake up S A process in the process list B. The process then A Sleep in cv.sem On , If you wake up , Then let cv.count Minus one , Indicates that the number of sleep processes waiting for this condition is one less , Can continue .

Situation two ： If monitor.next_count If less than or equal to 0, Indicates that there is currently no process execution cond_signal Function and fell asleep , What needs to be awakened is the process that cannot enter the pipe due to mutual exclusion conditions , So wake up and sleep in monitor.mutex Progress on . The process then A Sleep in cv.sem On , If you wake up , Then let cv.count Minus one , Indicates that the number of sleep processes waiting for this condition is one less , It can be continued ！

The realization of philosophers' dining problem based on conditional variables and management

• This problem involves two functions , Namely phi_take_forks_condvar and phi_put_forks_condvar. It is similar to the dining problem of philosophers realized by semaphores , The general logic is consistent .
• First , Philosophers need to try to get knives and forks , If the knife and fork are not obtained , Then wait for the knife and fork .

phi_put_forks_condvar The function means to release the fork occupied by the current philosopher , And wake up neighboring philosophers who wait because they don't have resources ：

• First, get the lock of the tube , Change your status to THINKING;
• Check whether the neighboring philosophers meet the eating conditions after releasing the occupation of the fork , If meet , Wake it up from waiting
• Release the lock , Leave the tube

phi_take_forks_condvar The function means that the specified philosopher tries to get two forks for the meal he needs , If not, block , The specific implementation process is ：

• Lock the tube , Change the status of philosophers to HUNGER;
• Judge whether the neighboring philosophers are eating ;
• If you can eat , Change your status to EATING, Then release the lock , Just leave the tube ;
• If you can't eat , Wait on your corresponding condition variable , Wait for the neighboring philosophers to awaken themselves when they release resources ;

void phi_take_forks_condvar(int i) {
    
     down(&(mtp->mutex));
//--------into routine in monitor--------------
     // LAB7 EXERCISE1: YOUR CODE
     // I am hungry
     state_condvar[i]=HUNGRY; /*  Record the philosophers i The fact of hunger  */
     // try to get fork
     phi_test_condvar(i);
     if (state_condvar[i] != EATING) {
    
          cprintf("phi_take_forks_condvar: %d didn't get fork and will wait\n",i);
          cond_wait(&mtp->cv[i]);
      }
//--------leave routine in monitor--------------
      if(mtp->next_count>0)
         up(&(mtp->next));
      else
         up(&(mtp->mutex));
}

after , When philosophers put down their knives and forks , If the philosophers on both sides meet the conditions, they can eat , Then set the corresponding condition variable .

void phi_put_forks_condvar(int i) {
    
     down(&(mtp->mutex));
//--------into routine in monitor--------------
     // LAB7 EXERCISE1: YOUR CODE
     // I ate over
     state_condvar[i]=THINKING; /*  The philosopher's meal is over  */
     // test left and right neighbors
     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--------------
     if(mtp->next_count>0)
        up(&(mtp->next));
     else
        up(&(mtp->mutex));
}

Here is the code for philosophers to try to eat

void phi_test_condvar (i) {
    
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
    
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        cond_signal(&mtp->cv[i]) ;
    }
}

Because every philosopher can only occupy all the necessary resources or not occupy resources at all , Therefore, there will be no partial occupation of resources , Thus, deadlock is avoided ; Ultimately, all philosophy will succeed .

experimental result ：

function make qemu View the run results ：

function make grade Check your grades ：

Extended exercises Challenge ： stay ucore Implements simplified deadlock and reentry detection mechanisms

stay ucore Implement a detection mechanism under , Be able to work in multiple processes / When a thread runs a synchronous mutual exclusion problem , It is necessary to dynamically judge whether the current system has deadlock , Whether multiple processes enter the critical zone .
If you find that , Let the system enter monitor state , Print out your detection information .

Extended exercises Challenge ：　 Reference resources Linux Of RCU Mechanism , stay ucore Implementation of simplified RCU Mechanism

stay ucore
Next realize Linux Of RCU Synchronous mutual exclusion mechanism . Can read related Linux Kernel books or query online materials , Can understand RCU Design and implementation details of , Then simplify the implementation in ucore in .
An experimental report is required to explain your design idea , And provide test cases . Here are some references ：

• http://www.ibm.com/developerworks/cn/linux/l-rcu/
• http://www.diybl.com/course/6_system/linux/Linuxjs/20081117/151814.html