[Voide]

Long time browser, but only just made an account here on DIC.

I'm currently in an operating systems class at University of Houston. I will absolutely admit that this is a Lab for our class, but I am -not- looking for ANYONE to do my homework.

The code of the lab is as follows:

import java.lang.*;
import java.io.*;
import java.util.*;

public class Counter{

private int count1 = 0, count2 = 0;
private int max_count = 100000;
private int number_of_threads = 10;
private int threads_quit;

	public Counter()
	{
		threads_quit = 0;
		startThreads();
	}
	
	public synchronized int getNextNumber1()
	{
		int temp;
		if(count1 < max_count) 
		{  	temp = count1;
			count1 = count1 + 1;
		        return(temp);
		}
		else return(-1);
	}
	
	public synchronized int getNextNumber2()
	{
		int temp;
		if(count2 < max_count) 
		{  	temp = count2;
			count2 = count2 + 1;
		        return(temp);
		}
		else return(-1);
	}

	public synchronized int threads_quit_increase() 
	{
		threads_quit = threads_quit + 1;
		if (threads_quit < number_of_threads) return (0);
		else return (-1); 
	}
	
	public void startThreads()
	{
		int i = 0;
		for(i = 0; i < number_of_threads; i++)
		{
			CounterThread ct = new CounterThread(this, i);
			ct.start();
		}
	}
	
	public static void main(String args[])
	{
		Counter a = new Counter();
	}
	
	class CounterThread extends Thread
	{
		Counter parent;
		int number;
		
		public CounterThread(Counter parent, int number)
		{
			this.parent = parent;
			this.number = number;
		}
		
		public void run()
		{
			int n1=parent.getNextNumber1(), n2=parent.getNextNumber2();
			
			while (n1 != -1 && n2 != -1 && n1 == n2)
			{
				n1=parent.getNextNumber1();
				n2=parent.getNextNumber2();
			}
			if (n1 != n2)
				System.out.println("Two counters are discrepant!");

			System.out.println("Thread ID " + number + " is quitting!");
			if (threads_quit_increase() == -1)
				System.out.println("All threads have quitted. Done!");
		}
	}
}

Our assignment is to modify the code in such a way where the 2 threads are never discrepant. While the code works with a max_count of 1000, as soon as you increase the max_count one of the threads always runs away from the other.

This is a lesson in Synchronization, if someone would be willing to explain how it works in this program I would be extremely grateful. I've read up on it but when I try to apply it to this Lab I get lost.

Thank you in advance.

[SwiftStriker00]

In the high level view sycronization is a way of protecting data. Lets say you wanted to get the max_count on won thread while another was trying to modify it. There are a few things that could potentially happen.
1) You could not guaranteeing when the variable is modified, even if you called the get method first, the set method may finish first. This means the data you accessed could possibly be incorrect.
2) Maybe not in this simple case, but another issue you run into is, what if an object was being modified by a setter, but not complete when the get runs? You could have incomplete, or corrupted data
3) Your system could crash with that bad data for any number of reasons.

So what we do is synchronize data and methods. Basically its teaching threads how to take turns. When the first thread enters a synchronized method, it sets a flag saying "im being used, and im using all associated data." Now if any subsequent threads come along and try and use that method, or data. they will be BLOCKED. Which means they will sit and wait until either the first thread finishes and changes the flag back, or times-out. I'm sure you will get to techniques to deal with the latter a bit later.

[CasiOo]

Java uses monitors to get mutex. By writing synchronized when you declare the method, you tell that the method should be a part of the monitor. Also you can make synchronized blocks, not only methods.

Wikipedia has an okay explanation of mutex.

[blackcompe]

Threads are unpredictable. Take this probable case for example. One thread gets pre-empted right after getNextNumber1() so that count1 is incremented but count2 isn't; they become unsynchronized. The next thread comes in and increments count1 (now it's 2 above count2) and then increments count2, so that they're different by 1 (discrepant). The loop condition fails and the thread ends. Snychronized methods are completely worthless in the situation I present, which is why your getting discrepant counters.

I got rid of all the print statements and put ones for when the discrepant counters are found.

public void run() {
    int n1 = parent.getNextNumber1(), n2 = parent.getNextNumber2();

    while (n1 != -1 && n2 != -1 && n1 == n2) {
        n1 = parent.getNextNumber1(); 
        n2 = parent.getNextNumber2(); 
    }
    if (n1 != n2) {
        System.out.println("Two counters are discrepant!");
    }
}

I was actually able to get discrepant counters at max_count equal to 500.

Given the case I present to you above, how can you prevent that from happening? There is a way to disable other threads from accessing parent using synchronization while a pre-empted thread is not finished its work. That's the key.

This post has been edited by blackcompe: 02 February 2012 - 04:16 PM

[Voide]

So to resolve the issue of the cores not updating one by one I need a way to block the synchronization until each thread has taken its turn to increment the thread?

Thanks again, you both have been helpful.

CasiOo, on 02 February 2012 - 03:42 PM, said:

Java uses monitors to get mutex. By writing synchronized when you declare the method, you tell that the method should be a part of the monitor. Also you can make synchronized blocks, not only methods.

Wikipedia has an okay explanation of mutex.

Could you elaborate on the synchronized blocks? Or link me to a good source to read about it?

[blackcompe]

Take atomicity from the ACID concept. Each thread has a unit of work. That unit of work requires accessing shared variables in parent. No other threads can intervene during that period. That's what you need to use synchronization for.

[ianian112]

blackcompe, on 02 February 2012 - 04:13 PM, said:

Threads are unpredictable. Take this probable case for example. One thread gets pre-empted right after getNextNumber1() so that count1 is incremented but count2 isn't; they become unsynchronized. The next thread comes in and increments count1 (now it's 2 above count2) and then increments count2, so that they're different by 1 (discrepant). The loop condition fails and the thread ends. Snychronized methods are completely worthless in the situation I present, which is why your getting discrepant counters.

I got rid of all the print statements and put ones for when the discrepant counters are found.

public void run() {
    int n1 = parent.getNextNumber1(), n2 = parent.getNextNumber2();

    while (n1 != -1 && n2 != -1 && n1 == n2) {
        n1 = parent.getNextNumber1(); 
        n2 = parent.getNextNumber2(); 
    }
    if (n1 != n2) {
        System.out.println("Two counters are discrepant!");
    }
}

I was actually able to get discrepant counters at max_count equal to 500.

Given the case I present to you above, how can you prevent that from happening? There is a way to disable other threads from accessing parent using synchronization while a pre-empted thread is not finished its work. That's the key.

I'm really sad I could only +1 this once. His answer is vague enough that you need to think about how to solve the problem, but clear enough that it puts you on the right path. Thanks blackcompe, I really enjoyed that challenge