11 Replies - 418 Views - Last Post: 14 August 2019 - 06:50 AM Rate Topic: -----

#1 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Concurrent Processing with Semaphores

Posted 08 August 2019 - 08:25 PM

Hi everyone, I am trying to do a basic project where I have 2 processes running (A, B).

The goal is to use a single semaphore to alternate between the processes with these conditions:

1. Process A and Process B must run at least once before they run a second time
For example

"A has run 1 time(s)" -> A1
"B has run 1 time(s)" -> B1
"A has run 2 time(s)" -> A2
"B has run 2 time(s)" -> B2

The order does not matter as to whether A or B runs first but the first time A runs and the first time B runs must be that A runs before B runs for the second time and B runs before A runs for the second time

So it can go in any order such as
A1
B1,
A2,
B2

B1
A1
B2
A2

A1
B1
B2
A2

B1
A1
A2
B2

This is what I have so far

 // create the semaphore
    sem = semcreate(0);
    processA = create(concurrent, 1024, 30, "Alice", 2, "Alice", atoi(argv[1]));
    processB = create(concurrent, 1024, 30, "Bob", 2, "Bob", atoi(argv[1]));
    resume(processA);
    resume(processB);



void concurrent(char *name, int32 timesToRun)
{
    int32 count = 1;
    // block the first process that runs

    while(count < timesToRun + 1)
    {
        if(semcount(sem) < 0)
        {
            signal(sem);
        }
        kprintf("I am running as %s %d time(s)\n", name, count);
        count++;
        wait(sem);
    }
}



It is not really running how I would expect. It appears that A always runs first even though A and B have the same priority and then they both get stuck in waiting at the end, so they processes never complete or terminate.

How would you approach this?

Is This A Good Question/Topic? 0
  • +

Replies To: Concurrent Processing with Semaphores

#2 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: Concurrent Processing with Semaphores

Posted 08 August 2019 - 08:54 PM

I would set things up so that both threads/processes initially wait for the semaphore to be signaled. It'll be responsibility of the main program/primary thread to signal the semaphore for the threads to fight over. Once a thread successfully gets the semaphore, it reports that ran, then signals the semaphore AND sleeps or yields right after signaling before waiting on the semaphore again. Obviously no need to loop and wait if the thread/process has successfully received the semaphore the requisite number of times.

The sleep or yield is to give the other thread/process a chance to grab the semaphore. Unfortunately, the side effect of this of this that you'll always get A B A B, or B A B A. If you really need to have the possibility of also getting A B B A, or B A A B, you could randomly decide whether to yield or sleep right after signaling.
Was This Post Helpful? 0
  • +
  • -

#3 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 11 August 2019 - 11:09 AM

I did something like this but maybe I can refine it better?

shellcmd xsh_sync(int nargs, char *argv[])
{
    // create the semaphore
    sem1 = semcreate(1);
    sem2 = semcreate(0);
    processAlice = create(concurrentAlice, 1024, 30, "Alice", 0);
    processBob = create(concurrentBob, 1024, 30, "Bob", 0);
    resume(processAlice);
    resume(processBob);
}

void concurrentAlice()
{
    wait(sem1);
    kprintf("My first statement appears before Bob's second statement\n");
    aliceLock = TRUE;
    
    if(bobLock)
    {
        signal(sem2);
    }
    else
    {
        signal(sem1);
    }

    // critical 2
    wait(sem2);
    kprintf("This is Alice's second statement\n");
    signal(sem2);
}

void concurrentBob()
{
    wait(sem1);
    kprintf("My first statement appears before Alice's second statement\n");
    bobLock = TRUE;

    if(aliceLock)
    {
        signal(sem2);
    }
    else
    {
        signal(sem1);
    }
    // critical 2
    wait(sem2);
    kprintf("This is Bob's second statement\n");
    signal(sem2);
}


From what I see, the two functions are nearly identical in every way except for the boolean.

I was thinking that maybe I could pass in a pointer?
Was This Post Helpful? 0
  • +
  • -

#4 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 11 August 2019 - 12:14 PM

I tried doing this but I am getting caught up in a waiting state for both processes

I tried using pointers for the locks and tried swapping thinking that the point in memory would be modified and that I could pick up from there in the other process but that does not seem to be the case.

Any suggestions?

pid32 processAlice, processBob;
sid32 *sem1, *sem2;
bool8 *lock1, *lock2;
// bool8 aliceLock, bobLock;
// void concurrentAlice();
// void concurrentBob();

shellcmd xsh_sync(int nargs, char *argv[])
{
    // create the semaphore
    sem1 = semcreate(1);
    sem2 = semcreate(0);
    processAlice = create(concurrent, 1024, 30, "Alice", 6, "Bob", "Alice", sem1, sem2, lock1, lock2);
    processBob = create(concurrent, 1024, 30, "Bob", 6, "Alice", "Bob", sem1, sem2, lock2, lock1);
    resume(processAlice);
    resume(processBob);
}



the concurrent function
void concurrent(char *name1[], char *name2[], sid32 *sem1, sid32 *sem2, bool8 *lock1, bool8 *lock2)
{
    wait(sem1);
    kprintf("My first statement appears before %s's second statement\n", name1);
    // I figured that if I swapped lock1 and lock2 in the calling method that the pointers would work but I think I might be missing something
    lock1 = TRUE;
    if(lock2)
    {
        kprintf("HI\n");
        signal(sem2);
    }
    else
    {
        kprintf("Bye\n");
        signal(sem1);
    }

    // critical 2
    wait(sem2);
    kprintf("This is %s's second statement\n", name2);
    signal(sem2);
}


Was This Post Helpful? 0
  • +
  • -

#5 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: Concurrent Processing with Semaphores

Posted 11 August 2019 - 12:20 PM

With your code in post #3 and #4, you are now using two semaphores. You originally said you could only use one. It also looks like you are now allowing some kind of shared information between A and B. If all of that was allowed in this assignment, then things get so much easier.
Was This Post Helpful? 0
  • +
  • -

#6 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 11 August 2019 - 12:23 PM

I'm allowed to use more than one semaphore but I thought I could have done it with one originally. So I created 2 semaphores.

In post #3, it works for the very first one but then fails to execute 100% successfully on any subsequent runs unless I reboot the machine and run again.

In post #4, it'll print out the first message but then get caught up in a waiting state and will never finish.
Was This Post Helpful? 0
  • +
  • -

#7 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 11 August 2019 - 03:45 PM

this works fine except that it is always
A1 - B1 - A2 - B2

bool8 aliceLock, bobLock;

void concurrentAlice(char *name1[], char *name2[], sid32 *sem1, sid32 *sem2, bool8 *lock1, bool8 *lock2)
{
    // critical 1
    wait(sem1);
    kprintf("My first statement appears before %s's second statement\n", name1);
    aliceLock = TRUE;
    if(lock2)
    {
        signal(sem2);
    }
    else
    {
        //lock2 = &lock1;
        signal(sem1);
    }

    // critical 2
    wait(sem2);
    kprintf("This is %s's second statement\n", name2);
    signal(sem2);
}

void concurrentBob(char *name1[], char *name2[], sid32 *sem1, sid32 *sem2, bool8 *lock1, bool8 *lock2)
{
    wait(sem1);
    kprintf("My first statement appears before %s's second statement\n", name1);
    bobLock = TRUE;

    if(aliceLock)
    {
        signal(sem2);
    }
    else
    {
        signal(sem1);
    }
    // critical 2
    wait(sem2);
    kprintf("This is %s's second statement\n", name2);
    signal(sem2);
}



I am having trouble trying to make this more dynamic. The only thing that is really changing is the line where I am saying the lock is True.
Was This Post Helpful? 0
  • +
  • -

#8 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 13 August 2019 - 06:04 AM

I found something interesting

The run is successful for the alternating of the processes for the first run but will not work for any subsequent run.

I was confused as to why but it appears that the local variables in the function are not being removed from memory after the run is complete, so the locking is still enabled in a way.

Why is that?

In my post above this one, it shows that I have 2 boolean values and that they are set to TRUE when the function is called for the respective boolean.

For the first run, things are fine and the processes are terminated. I thought at that point that the values would also be removed from memory.

However, on any other subsequent run, I am never able to get to the second critical section because both values are locked and the wrong semaphore is being signaled.

Why is that?
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: Concurrent Processing with Semaphores

Posted 13 August 2019 - 09:16 AM

Considering that you are not really using any local variables in the code in post #7, I don't know what you are talking about regarding local variables. Yes, all the function parameters are technically "local", but they are all pointers to something. Looking at post #4, it looks like those are just essentially the same global variables you declared in the first code chunk in that post.
Was This Post Helpful? 1
  • +
  • -

#10 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: Concurrent Processing with Semaphores

Posted 13 August 2019 - 09:26 AM

I think you made a very valid point.

I was under the assumption that those global variables are local to the file I declared them in.

Does that mean that if a variable is defined globally in one file that it is accessible in other places as well?
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: Concurrent Processing with Semaphores

Posted 13 August 2019 - 10:22 AM

Yes. That is why they are called "global". :)

You could declare as global with the static modifier to limit it's scope to just the compilation unit that it is declared in, but that is a C technique because of C's lack of namespaces.

In general, you don't want to use globals. Yes, globals were the way to write code before the 80's, but after that time developers kept on running into the inherent problems with it being very hard to reason with and debug with globals, especially in multi-threaded environments.
Was This Post Helpful? 1
  • +
  • -

#12 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: Concurrent Processing with Semaphores

Posted 14 August 2019 - 06:50 AM

I'm trying to think of a way to let you discover the solution to your problem without spoon feeding you the answer. Unfortunately, I remember being in your shoes before. It took a while for me to grok how these things work. I recall finally getting that breakthrough when I going over the various possible solutions (both naive as well as correct) for the Dining Philosophers Problem. Alternatively, look at the producer/consumer problem. Maybe one of those will do the same magic for you. The key is understanding how semaphores (or simple mutexes) work, and not making them extra work that they weren't designed for but at the same time maximizing the the utility of what they were designed for.

(Actually the more I think about it, the producer/consumer problem may help you more since it is more analogous to the current problem you are facing.)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1