Results 1 to 10 of 10
Like Tree1Likes
  • 1 Post By Norm

Thread: Semaphores

  1. #1
    Ameer3881 is offline Member
    Join Date
    Apr 2012
    Posts
    15
    Rep Power
    0

    Angry Semaphores

    Why does my release method for S not work? It allows me to run the function, without the benefit of the signal working. It does not increment the value of S, and doesn't allow the sleeping scheduler to run, even though it signals it right after "Process i is done". The S functions work in other sections of the code, but does not allow me to release in the thread part of the code. I put a comment where I am having the problem in giant text.

    To help understand the program, There are 5 threads being run, semaphore S signals the scheduler, which unblocks the process with the lowest ID. The part where I put i == 1, that just means I am still furbishing the scheduler and how it should run, but I DEFINITELY KNOW, that the first process to arrive has to be serviced (as a rule).


    Java Code:
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Random;
    import java.util.concurrent.Semaphore;
    class Process extends Thread 
    {
    	private static volatile Semaphore[] B;
    	private static volatile Semaphore S;
    	private static volatile int count = 0;
    	private static volatile boolean [] needCriticalSection;
    	ArrayList ProcessWaiting;
    	private int id;
    	private int totalP;
    	private int priority; // Inverts the lower process ID to reflect a higher priority.
    
    	private static Semaphore MutexA;
    	
    	  public Process(int i, int n) {
    		this.id = i;
    		this.totalP = n;
    		MutexA = new Semaphore(1,false);
    		 B = new Semaphore[totalP];
    		needCriticalSection = new boolean [totalP];
    		needCriticalSection[0] = false;
    		S = new Semaphore(0,false);
    		ProcessWaiting = new ArrayList();
    		for(int j = 1; j < totalP; j ++)
    		{
    			B[j] = new Semaphore(0,false);
    			needCriticalSection[j] = false;
    		}
    	}
    
    	
    	  public int sleepRNG(int highpoint) throws InterruptedException
    	  {
    	   Random r = new Random();
    	   int sleeptime=r.nextInt(highpoint);
    	   sleep(sleeptime);
    	   return sleeptime;
    	  }
    
    public void run()
      {
    	
    	if(id == 0) // scheduler
    	{
    		System.out.println("Scheduler ready");
    		while(true)
    		{
    			try {
    				S.acquire();
    			} catch (InterruptedException e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    			
    			System.out.println("Scheduler being used");
    			ProcessWaiting = new ArrayList<Integer>();
    				for(int i = 0; i < needCriticalSection.length; i ++)
    				{
    					if(needCriticalSection[i] == true)
    					{
    						ProcessWaiting.add(i);
    					}
    					
    				}
    			    Object obj = Collections.min(ProcessWaiting);
    			    int higherPriority = (Integer) obj;
    			    B[higherPriority].release();
    		}		
    	}
    	else // processes
    	{
    
    		try 
    		{
    			sleepRNG(50);
    		} 
    		catch (InterruptedException e) 
    		{
    			e.printStackTrace();
    		}
    
    		try
    		{
    		MutexA.acquire();
    		}
    		catch(InterruptedException a)
    		{
    			
    		}
    		count ++;
    		MutexA.release();
    		
    		if(count == 1)	//very first thread runs first
    		{
    			B[id].release();
    			//System.out.println(id);
    
    		}
    
    		System.out.printf("Process %d is REQUESTING access to the CS \n", id);
    		needCriticalSection[id] = true;
    		while(true)
    		{
    			try {
    				B[id].acquire();
    			} catch (InterruptedException e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    			
    			System.out.printf("Process %d is INSIDE the CS \n", id);
    			needCriticalSection[id] = false;
    			
    			try 
    			{
    				sleepRNG(75);
    			} 
    			catch (InterruptedException e) 
    			{
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    
    			System.out.printf("Process %d is FINISHED with the CS \n", id);
    			S.release(); // BIG HUGE BUG, SMASH IT PLEASE!!! <------
    			
    			
    		}
    		
    	}
    
      }
    }
    Last edited by Ameer3881; 04-09-2012 at 11:41 PM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Semaphores

    How do you execute the code? I don't see a main() method.
    Ameer3881 likes this.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    Ameer3881 is offline Member
    Join Date
    Apr 2012
    Posts
    15
    Rep Power
    0

    Default Re: Semaphores

    Java Code:
    package semaphores;
    
    import java.io.IOException;
    import java.util.concurrent.Semaphore;
    
    public class Main {
    	public static void main(String[] args) throws IOException {
    	
    		int numberOfProcesses = 5;
    		
    		int N = numberOfProcesses + 1;
    		Process[] p = new Process[N];
    		      for (int i = 0; i < N; i++)
    		      {
    		        p[i] = new Process(i, N);
    		        p[i].start();
    		      }
    
    	}
    
    }

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Semaphores

    Please post the program's output and add comments to it explaining what is wrong and show what the output should be.
    If you don't understand my response, don't ignore it, ask a question.

  5. #5
    Ameer3881 is offline Member
    Join Date
    Apr 2012
    Posts
    15
    Rep Power
    0

    Default Re: Semaphores

    On some occasions, my code works :


    Scheduler ready
    Process 3 is REQUESTING access to the CS
    Process 5 is REQUESTING access to the CS
    Process 1 is REQUESTING access to the CS
    Process 3 is INSIDE the CS
    Process 2 is REQUESTING access to the CS
    Process 4 is REQUESTING access to the CS
    Process 3 is FINISHED with the CS
    Scheduler being used
    Process 1 is INSIDE the CS
    Process 1 is FINISHED with the CS
    Scheduler being used
    Process 2 is INSIDE the CS
    Process 2 is FINISHED with the CS
    Scheduler being used
    Process 4 is INSIDE the CS
    Process 4 is FINISHED with the CS
    Scheduler being used
    Process 5 is INSIDE the CS
    Process 5 is FINISHED with the CS
    Scheduler being used
    Exception in thread "Thread-0" java.util.NoSuchElementException
    at java.util.ArrayList$Itr.next(ArrayList.java:794)
    at java.util.Collections.min(Collections.java:628)
    at semaphores.Process.run(Process.java:70)


    In all these occasions, all other processes request the Critical Section (the random computation / sleep time stuff) by the time the first process that enters finishes.

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Semaphores

    java.util.NoSuchElementException
    Does the arraylist have any elements when this happens?

    Is what you posted the correct output from the program or was there a problem?
    If there is a problem, can you explain what it is?
    If you don't understand my response, don't ignore it, ask a question.

  7. #7
    Ameer3881 is offline Member
    Join Date
    Apr 2012
    Posts
    15
    Rep Power
    0

    Default Re: Semaphores

    No that's not the error (I expected that too happen, its caused when the last process leaves to wake up the scheduler (in the rare case it outputs the above code). The other 80% of the time, the first thread to arrive gets woken up, GREAT, says that its done, but dosen't make a meaningful call to signal the scheduler for the next event. What is supposed to happen is, the first thread to run gets released. That thread, when its finished, wakes up the schedule with Semaphore S. Line 128 is where the bug is located. The first process enters the CS and finishes, but when it does a semaphore S release to wake up the schedule, process 0 (the scheduler) never wakes up from its slumber.

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Semaphores

    Why are you calling min() on an empty list?

    How does execution get out of the while(true) loop? The value of id does not change inside of the loop
    If you don't understand my response, don't ignore it, ask a question.

  9. #9
    Ameer3881 is offline Member
    Join Date
    Apr 2012
    Posts
    15
    Rep Power
    0

    Default Re: Semaphores

    I will have a base case there when count == totalP - 1 (the scheduler); For now, I am worried about why the scheduler is not being signaled.

    What happens :
    Scheduler ready
    Process 2 is REQUESTING access to the CS
    Process 1 is REQUESTING access to the CS
    Process 2 is INSIDE the CS
    Process 3 is REQUESTING access to the CS
    Process 5 is REQUESTING access to the CS
    Process 2 is FINISHED with the CS
    Process 4 is REQUESTING access to the CS

    Whats supposed to happen :

    Scheduler ready
    Process 2 is REQUESTING access to the CS
    Process 1 is REQUESTING access to the CS
    Process 2 is INSIDE the CS
    Process 3 is REQUESTING access to the CS
    Process 5 is REQUESTING access to the CS
    Process 2 is FINISHED with the CS
    //call scheduler here, signal function called, but still sleeping.
    Process 4 is REQUESTING access to the CS

  10. #10
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Semaphores

    For debugging the code I recommend that you add lots more println statements to show state and execution flow.
    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. Semaphores
    By MuslimCoder in forum Threads and Synchronization
    Replies: 0
    Last Post: 04-15-2010, 05:55 AM
  2. Waiting on multiple semaphores at the same time
    By flok in forum Threads and Synchronization
    Replies: 3
    Last Post: 11-10-2009, 03:31 PM

Tags for this Thread

Posting Permissions

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