Results 1 to 10 of 10

Thread: Using C to simulate linux kernel semaphores

  1. #1
    Join Date
    Nov 2003
    Posts
    21
    Rep Power
    0

    Default Using C to simulate linux kernel semaphores

    I've got and assignment that i would like some help from u guro's with. The question goes:-

    Simulate in C the linux up() and down() routines used to acquire a process release and a process lock respectively, for kernel semaphores.
    The code should be able to signal() when a process is locked by the critical section and when it is not.

  2. #2
    Join Date
    Jul 2002
    Posts
    818
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Sadly, I don't know how that's done in C. I never touch the stuff.

    In java you could simply write a 'synchronized' function that could set a global variable (eg. 1 for in use and 0 free) located in the parent thread.

    Making a function synchronized makes the entire function critical so you wouldn't have to worry about someone checking the variable while it's in the process of being set.

    The implementation above is a simplistic binary semaphore, but it tends to do the job well. I'm only assuming that C has similar constructs to allow for this implementation.

  3. #3
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Perkie - Don't try to think of the assignment as finding a function inside a C++ Library that does the simulation, instead, try to think of how you are going to simulate this logically. Let me explain.

    The best way to execute this is to think of the entire semaphore in terms of an analogy in C - similar to how CKnight puts it. You're going to need 12 variables for this particular implementation (there are many ways to do this. I'm only showing you one of them).

    Code:
    bool processorBusy = false;
    int jobOne[5] = {0, 0, 0, 0, 0};
    int jobTwo[5] = {0, 0, 0, 0, 0};
    int percentCompleted[5] = {0, 0, 0, 0, 0};
    int OneActiveThreads = 0, TwoActiveThreads = 0;
    int whichJob = 0;
    int wait=0;
    int kp=0;
    int i=0, n, aRandomNumber;
    processorBusy will act as your semaphore. When it is true, only the job currently executing will be able to run to completion, assuming that you are using the First Come, First Serve Process Scheduling algorithm, or any non pre-emptive process scheduling algorithm. If you are using a pre-emptive process sheduling algorithm, that's where things will get extremely complicated.... however, this is assuming that you are using FCFS.

    jobOne and jobTwo will act as your main applications. You notice that they are arrays. There is a reason for this. Each application running under an operating system has many of what are called threads - I'm sure you know this. Threads execute simultaneously (or apparently so). This simulation I will assume, does not take into consideration real-time thread priority (meaning that a process can execute, even while another one has the processor - semaphores would prevent that).

    The idea is that whenever one of these two jobs has access to the processor, the other one will have to wait until all processes (threads) have completed. That's basically how a semaphore works. Each array cell in either int array represents one thread. Therefore, each job has 5 threads. (In the real world, it's usually dozens or hundreds).

    wait determines how long a job has the processor for. If another job arrives and attempts to use the processor, it is put into a wait state (semaphore: V signal). So we increment wait by one for each processor cycle (I'll show you how this is done) whenever there is a job waiting on the processor. Whenever this wait variable reaches it's sentinel value, (you have to determine this) you can then decide that no more threads can be started on the Job currently using the processor. So the currently executing job will have to finish all that it is running on the processor and go from a Running state (semaphore: P) to a waiting state (Semaphore: V). The job currently in the waiting state (semaphore: V) will then start up into a ready state (semphore: P).

    The whichJob integer variable will be used to determine which job will get the processor next. To decide which job goes next, you have to setup a set of switch conditions. They should be as follows:

    • Whichever job arrives at the processor first (FCFS)
    • Whenever all threads for one job has completed
    • Whenever one job has waited too long for the processor


    These conditions can be easily represented in C. To determine how to know when a Job can start executing, you may have to use a randomizer. By this I mean, generate a random number for each thread in the job. If this number fits certain specifications (for example: odd for JobOne, even for JobTwo) then one of the two Jobs can start using the processor.

    Ofcourse, to simulate all of this, you're going to need a nested loop struture. The outer loop sets up the conditions for each job to execute, and the inner loop executes thread in the job currently running.

    kp catches keypresses from the user. The simulation can run indefinitely until the user presses a key. We can just use ESCAPE. I'll show you how to do this.

    percentCompleted is an integer array that indicates how complete a thread within each job is.

    OneActiveThreads and TwoActiveThreads indicates how many threads are active in each job. Whenever this number drops to 0, a job is complete, and the other job is allowed to start (or if there are no jobs waiting on the other side, the system decides who goes next).

    i allows the outer loop to determine whether or not the currently selected thread in either job becomes activated. This index value allows the outer loop to repeatedly step through each Job's threads and randomly determine whether or not they are active (depending on the random number generation).

    aRandomNumber is really a simplistic integer that is going to be randomly generated to determine whether a thread is going to be activated. If the number is odd, a thread in jobOne is going to be activated. If even, a thread in jobTwo is activated.

    n is just an auxiliary integer used for stepping through the arrays.

    Next I will show you sample code for executing this.

  4. #4
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Here is a highly over-simplified way of doing your assignment....

    Code:
    #include <windows.h>
    #include <time.h>
    
    //use only one of these streams
    #include <iostream> //If you're using C++
    #include <stdio.h> //If you're just using C
    
    //my preference instead of either iostream or stdio...
    #include <conio.h>
    
    bool processorBusy = false;
    int jobOne[5] = {0, 0, 0, 0, 0};
    int jobTwo[5] = {0, 0, 0, 0, 0};
    int percentCompleted[5] = {0, 0, 0, 0, 0};
    int OneActiveThreads = 0, TwoActiveThreads = 0;
    int whichJob = 0;
    int wait=0;
    int kp=0;
    int i=0, n, aRandomNumber;
    
    while (kp == 0){
       //seed the random number generator for each time a pass is made
       //through all the threads in either job. This ensures the numbers you
       //generate are as random as possible.
       if (i == 0)
          srand(time(NULL));
    
       if (jobOne[i] == 0){
             //generate a random number between 1 and 50
             aRandomNumber = 1 + (rand() % 50);
             if (aRandomNumber % 2 == 1){ //if the number is odd
                jobOne[i] = aRandomNumber;
                OneActiveThreads++;
                }
             }
    
       if (jobTwo[i] == 0){
             //generate a random number between 1 and 50
             aRandomNumber = 1 + (rand() % 50);
             if (aRandomNumber % 2 == 0) //if the number is even
                jobTwo[i] = aRandomNumber;
             }
    
       //if the random number in JobOne's current thread is less than that
       //of JobTwo....JobOne goes first on the processor
       if (jobOne[i] <= jobTwo && jobOne[i] != 0){
          processorBusy = true;
          whichJob = 1;
          }
       //...otherwise JobTwo gets the processor
       else if (jobTwo[i] != 0) {
          processorBusy = true;
          whichJob = 1;
          }
    
       //Inner loop, that increments the completeness of each active thread
       for (n = 0; n <= 5; n++){
          if (whichJob == 1){
             //if a thread is waiting to be executed, and JobTwo isn't waiting
             //too long....
             if (jobOne[n] > 0 && wait < 100){ 
                printf("Job1: Thread %d % completed", percentCompleted);
                percentCompleted[n] += 10;
    
                //When a thread has completed, nullify it's value so that it isn't 
                //incremented again
                if (percentCompleted[n] == 100){
                   jobOne[n] = 0;
                   OneActiveThreads--;
                   }
    
                //If there are threads in the other job in a waiting state
                //increment wait
                if (TwoActiveThreads > 0)
                   wait++;
    
                //If all the threads in this job have completed, exit the FOR
                //loop structure... this allows the system to decide which job
                //goes next
                if (OneActiveThreads == 0){
                   //if there are threads one the other side waiting for 
                   //execution, give them a chance to... 
                   if (wait > 0)  
                      whichJob = 2;
                   else{
                      //otherwise, let the system decide who goes next
                      whichJob = 0;
                      processorBusy = false;
                      }
                   //exit the for loop structure and reset wait...
                   wait = 0;
                   break;
                   }       
                }// if (jobOne)
    
             }// if (whichJob)
          else if (whichJob == 2){
             //if a thread is waiting to be executed, and JobOne isn't waiting
             //too long....
             if (jobTwo[n] > 0 && wait < 100){ 
                printf("Job2: Thread %d % completed", percentCompleted);
                percentCompleted[n] += 10;
    
                //When a thread has completed, nullify it's value so that it isn't 
                //incremented again, additionally, reset the percent completed
                //for that thread.
                if (percentCompleted[n] == 100){
                   jobTwo[n] = 0;
                   TwoActiveThreads--;
                   percentCompleted[n] = 0;
                   }
    
                //If there are threads in the other job in a waiting state
                //increment wait
                if (OneActiveThreads > 0)
                   wait++;
    
                //If all the threads in this job have completed, exit the FOR
                //loop structure... this allows the system to decide which job
                //goes next
                if (TwoActiveThreads == 0){
                   //if there are threads one the other side waiting for 
                   //execution, give them a chance to... 
                   if (wait > 0)  
                      whichJob = 1;
                   else{
                      //otherwise, let the system decide who goes next
                      whichJob = 0;
                      processorBusy = false;
                      }
                   //exit the for loop structure and reset wait...
                   wait = 0;
                   break;
                   }       
                }// if (jobTwo)
    
          }//for
       
       //Sleep for 400 oseconds so that you can 
       //actually SEE the simulation running
       Sleep(400);
    
       //increment i so the system can determine if the next thread in
       //either job becomes activated. There are only 5 threads in each
       //job, so i can only be a value between 0 and 4.
       if (i < 4)
          i++;
       else
          i = 0;
    
       //passively check if the user pressed escape. This does not wait for
       //input, rather it checks the keyboard register to see if the escape
       //key is held down. This is actually executed in a separate thread
       //that is managed by Windows.
       kp = GetAsyncKeyState(VK_ESCAPE);
    }
    Please bear in mind that this is SAMPLE code. That means it probably won't compile without errors and it probable has some minor logic flaws. So don't think you can copy / paste and submit for your assignment. ;D This code is just meant to guide you along the right path. In the end, you have to come up with your own code. Hopefully, this code will be of significant help for you.

    Again I stress, that there are MANY ways to implement semaphore emulation. This is just ONE of them.

    I must ask though, which Institution are you at? UWI? UTECH? IMP? Where?

  5. #5
    Join Date
    Nov 2003
    Posts
    21
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Thanks the explanation has added an insight into the problem. I'm at work presently so i not able to go through the code and see if it resembles anything that i've been tryiing so far.

    I'm at Utech part time.

  6. #6
    Join Date
    Nov 2003
    Posts
    21
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Thanks again for the help I have the program running.
    I wrote a program for an assignment that was to create an inode using C++ now he has given us this other assignment to Implement the following C routine permission(inode,mask) – this routine checks whether a specified access mode is allowed for the file associated with an inode.

  7. #7
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Glad I could help. May I ask though, who is your lecturer/tutor?

  8. #8
    Join Date
    Nov 2003
    Posts
    21
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    May I ask why

  9. #9
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Just curious. Just wanted to know who was heading it up for your stream. Janet Williams and Claudine Innis are doing it for the BCIT groups. Who's doing it for you guys?

  10. #10
    Join Date
    Nov 2003
    Posts
    21
    Rep Power
    0

    Default Re:Using C to simulate linux kernel semaphores

    Thorpe is the lecturer and tutor

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •