Informatica Interview Question
Country: India
Interview Type: In-Person
public class SyncThread {
/**
* Please see the below code its very simple.
*
*/
final Object o = new Object();
volatile int count; // counter
volatile boolean isT1started = false;
final String ResourceA1="A1", ResourceA2 ="A2", ResourceB1="B1", ResourceB2="B2";
// Thread T1
Runnable T1 = new Runnable() {
@Override
public void run() {
while(count<5){
synchronized (o) {
try {
isT1started = true;
System.out.println(ResourceA1);
o.notify();
o.wait();
} catch (Exception e) {
e.printStackTrace();
}
}
synchronized (o) {
try {
System.out.println(ResourceA2);
o.notify();
o.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
};
// Thread T2
Runnable T2 = new Runnable() {
@Override
public void run() {
while(count<5){
try {
synchronized (o) {
System.out.println(ResourceB1);
o.notify();
o.wait();
}
synchronized (o) {
System.out.println(ResourceB2);
System.out.println("============count completed:"+ (++count));
o.notify();
o.wait();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
};
void startThread(){
int i=1;
Thread t1 = new Thread(T1);
Thread t2 = new Thread(T2);
t1.start();
// makes sure that Thread t1 is started before t2
while(!isT1started){
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
// Now start thread t2
t2.start();
}
public static void main(String[] args) {
new SyncThread().startThread();
}
}
You can fix it simply by moving waiting into Thread 2. Something like
Runnable T2 = new Runnable()
{
@Override
public void run()
{
while (count < 5)
{
try
{
//Ensure T2 Runs always after T1
while (isT1started)
{
System.out.println("T1 has not run once so T2 Starts waiting");
Thread.sleep(500);
}
Following is my code using Events kernel objects in C++.
HANDLE h[4] = {0};
void A1(void)
{
std::cout<< "A1\n";
}
void A2(void)
{
std::cout<< "A2\n";
}
void B1(void)
{
std::cout<< "B1\n";
}
void B2(void)
{
std::cout<< "B2\n";
}
DWORD WINAPI Thread1(LPVOID t1)
{
WaitForSingleObject(h[0],INFINITE);
A1();
SetEvent(h[2]);
WaitForSingleObject(h[1],INFINITE);
A2();
SetEvent(h[3]);
return 0;
}
DWORD WINAPI Thread2(LPVOID t2)
{
WaitForSingleObject(h[2],INFINITE);
B1();
SetEvent(h[1]);
WaitForSingleObject(h[3],INFINITE);
B2();
return 0;
}
int main(int argc, char* argv[])
{
int temp=0;
int i=0;
HANDLE hThread[2] = {0};
h[0] = CreateEvent(NULL,FALSE,TRUE,NULL); // For A1. Signaled State.
h[1] = CreateEvent(NULL,FALSE,FALSE,NULL); // For A2. Non-signaled state.
h[2] = CreateEvent(NULL,FALSE,FALSE,NULL); // For B1. Non-signaled state.
h[3] = CreateEvent(NULL,FALSE,FALSE,NULL); // For B2. Non-signaled state.
hThread[0] = CreateThread(NULL, 0, Thread1, &temp, 0, NULL);
hThread[1] = CreateThread(NULL, 0, Thread2, &temp, 0, NULL);
WaitForMultipleObjects(2,hThread,true,INFINITE);
WaitForMultipleObjects(2,h,true,INFINITE);
while(i<2)
CloseHandle(hThread[i++]);
i=0;
while(i<4)
CloseHandle(h[i++]);
getchar();
return 0;
}
ammm .... this code is wrong ... as you are assuming that Thread 1 should be started before Thread 2 ....
What if OS preempts the thread1 just after start of execution but before reaching any executable statement.......and what if OS schedules thread 2 ecen if it is started after Thread 2 ??? .... In this case your program will fail..... right ???
The basic principle about multithreading is .....,Done make any assumptions about the sequence in which threads will execute .... Because you never know how OS will schedule them at run time .....
Here is an implementation using a ConcurrentLinkedQueue, let me know what you folks think
public class SequencingUsingBoundedBlockingQueue {
private static class Resource {
public final String name;
public Resource(String name) {
this.name = name;
}
public void useResource() {
System.out.println("Resource " + name + " used.");
}
}
private final Queue<Resource> queue;
public SequencingUsingBoundedBlockingQueue() {
queue = new ConcurrentLinkedQueue<Resource>();
queue.add(new Resource("A"));
queue.add(new Resource("B"));
queue.add(new Resource("C"));
queue.add(new Resource("D"));
}
private static class Actor implements Runnable {
private final Set<String> resources;
private final Queue<Resource> queue;
public Actor(Set<String> resources, Queue<Resource> queue) {
this.resources = resources;
this.queue = queue;
}
@Override
public void run() {
while (!queue.isEmpty()) {
Resource r = queue.peek();
if (r == null) {
break;
}
if (resources.contains(r.name)) {
queue.remove().useResource();
}
}
}
}
public static void main(String args[]) throws Exception {
SequencingUsingBoundedBlockingQueue problem = new SequencingUsingBoundedBlockingQueue();
Set<String> setA = new HashSet<String>();
setA.add("A"); setA.add("B");
Set<String> setB = new HashSet<String>();
setA.add("C"); setA.add("D");
(new Thread(new Actor(setB, problem.queue))).start();
(new Thread(new Actor(setA, problem.queue))).start();
Guys how about this , controlling the access using 4 mutexes.
#include <pthread.h>
#include <iostream>
using namespace std;
pthread_mutex_t m;
pthread_mutex_t a1,a2,b1,b2;
extern "C" void *fun1(void *)
{
pthread_mutex_lock(&a1);
cout<<endl<<"A1"<<endl;
pthread_mutex_unlock(&a1);
pthread_mutex_lock(&b2);
pthread_mutex_lock(&b1);
cout<<endl<<"A2"<<endl;
pthread_mutex_unlock(&b1);
pthread_mutex_unlock(&b2);
return NULL;
}
extern "C" void *fun2(void *)
{
pthread_mutex_lock(&b1);
pthread_mutex_lock(&a1);
cout<<endl<<"B1"<<endl;
pthread_mutex_unlock(&a1);
pthread_mutex_unlock(&b1);
pthread_mutex_lock(&b2);
cout<<endl<<"B2"<<endl;
pthread_mutex_unlock(&b2);
return NULL;
}
main()
{
pthread_t thread_id1,thread_id2;
pthread_create(&thread_id1,NULL,&fun1,NULL);
pthread_create(&thread_id2,NULL,&fun2,NULL);
pthread_join(thread_id1,NULL);
pthread_join(thread_id2,NULL);
}
interface TaskA {
public void execute();
}
class TaskA1 implements TaskA {
public void execute() { System.out.println("TaskA1"); }
}
class TaskA2 implements TaskA {
public void execute() { System.out.println("TaskA2"); }
}
interface TaskB {
public void execute();
}
class TaskB1 implements TaskB {
public void execute() { System.out.println("TaskB1"); }
}
class TaskB2 implements TaskB {
public void execute() { System.out.println("TaskB2"); }
}
class TaskManager {
private LinkedList<TaskA> taskAQ = new LinkedList<TaskA>();
private LinkedList<TaskB> taskBQ = new LinkedList<TaskB>();
boolean flag = true;
public synchronized void addTaskA(TaskA a) {
taskAQ.add(a);
notifyAll();
}
public synchronized void addTaskB(TaskB b) {
taskBQ.add(b);
notifyAll();
}
public synchronized void doTaskA() {
try {
while(taskAQ.size() == 0)
wait();
while(flag == false) //supposed to be taskb's turn
wait();
}catch(InterruptedException e) {}
TaskA a = taskAQ.poll();
a.execute();
flag = false;
notify();
}
public synchronized void doTaskB() {
try {
while(taskBQ.size() == 0)
wait();
while(flag == true)
wait();
}catch(InterruptedException e) {}
TaskB b = taskBQ.poll();
b.execute();
flag = true;
notify();
}
}
class ThreadA extends Thread {
private TaskManager tm;
public ThreadA (TaskManager t) { tm = t;}
public void run() {
while(true)
tm.doTaskA();
}
}
class ThreadB extends Thread {
private TaskManager tm;
public ThreadB (TaskManager t) { tm = t;}
public void run() {
while(true)
tm.doTaskB();
}
}
class ThreadP extends Thread {
private TaskManager tm;
public ThreadP(TaskManager t) { tm = t;}
public void run() {
TaskA a1 = new TaskA1();
TaskA a2 = new TaskA2();
TaskB b1 = new TaskB1();
TaskB b2 = new TaskB2();
tm.addTaskA(a1);
tm.addTaskA(a2);
tm.addTaskA(new TaskA() {
public void execute() { System.out.println("Anonymous TaskA3");}
});
tm.addTaskB(b1);
tm.addTaskB(b2);
tm.addTaskB(new TaskB() {
public void execute() { System.out.println("Anonymous TaskB3");}
});
}
}
public class test {
public static void main(String args[]) {
TaskManager tm = new TaskManager();
ThreadA a = new ThreadA(tm);
ThreadB b = new ThreadB(tm);
ThreadP p = new ThreadP(tm);
a.start();
b.start();
p.start();
}
}
public class Test2 implements Runnable{
String first = "";
String second = "";
static Integer lock = 1;
public Test2(String first, String second) {
this.first = first;
this.second = second;
}
@Override
public void run() {
synchronized (lock) {
System.out.println(first);
lock.notify();
try {
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(second);
lock.notify();
}
}
public static void main(String[] args) {
Thread t1 = new Thread(new Test2("A1", "A2"));
Thread t2 = new Thread(new Test2("B1", "B2"));
t1.start();
t2.start();
}
}
package informatica;
public class Multi{
public static Boolean mutex1 =false;
public static final Object obj= new Object();
//public static Boolean mutex2 =false;
class T1 extends Thread{
public void A1(){
System.out.println("IN A1");
}
public void A2(){
System.out.println("IN A2");
}
public void run(){
synchronized (obj) {
if(mutex1==false){
A1();
mutex1=true;
//System.out.println("Notifying");
obj.notify();
}else{
//System.out.println("Else of A1");
try {
obj.wait();
if(mutex1==false){
A1();
mutex1=true;
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
synchronized (obj) {
if(mutex1==false){
A2();
mutex1=true;
//System.out.println("Notifying");
obj.notify();
}else{
//System.out.println("Else of A1");
try {
obj.wait();
if(mutex1==false){
A2();
mutex1=true;
obj.notify();
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
/*
if(mutex1==false){
A1();
mutex1=true;
}
while(true){
if(mutex1==false){
A2();
mutex1=true;
break;
}else{
try{
Thread.sleep(100);
}catch(Exception e){
e.printStackTrace();
}
}
}
*/
}
}
class T2 extends Thread{
public void B1(){
System.out.println("IN B1");
}
public void B2(){
System.out.println("IN B2");
}
public void run(){
synchronized (obj) {
//System.out.println("Sync of B1");
if(mutex1==true){
B1();
mutex1=false;
obj.notify();
}else{
//System.out.println("Else of B1");
try {
obj.wait();
if(mutex1==true){
B1();
mutex1=false;
obj.notify();
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
synchronized (obj) {
//System.out.println("Sync of B1");
if(mutex1==true){
B2();
mutex1=false;
obj.notify();
}else{
//System.out.println("Else of B1");
try {
obj.wait();
if(mutex1==true){
B2();
mutex1=false;
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
/*
while(true){
if(mutex1==true){
B1();
mutex1=false;
break;
}else{
try{
Thread.sleep(100);
}catch(Exception e){
e.printStackTrace();
}
}
}
while(true){
if(mutex1==true){
B2();
mutex1=false;
break;
}else{
try{
Thread.sleep(100);
}catch(Exception e){
e.printStackTrace();
}
}
}
*/
}
}
public static void main(String[] args) {
Multi m = new Multi();
T1 t1= m.new T1();
T2 t2= m.new T2();
t2.start();
t1.start();
}
}
import java.util.concurrent.Semaphore;
public class ThreadAlternate {
public static void main(String[] args) {
String[] s1 = {"A1","A2","A3"};
String[] s2 = {"B1","B2","B3"};
MyThread t1 = new MyThread(s1, true);
MyThread t2 = new MyThread(s2, false);
t1.start();
t2.start();
}
}
class MyThread extends Thread{
static Semaphore s1 = new Semaphore(1);
static Semaphore s2 = new Semaphore(1);
boolean flag = false;
static{
try {
s2.acquire();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
String[] arr;
public MyThread(String[] strArray, boolean flag) {
this.arr = strArray;
this.flag = flag;
}
public void run() {
for (int i = 0; i < arr.length; i++) {
if(flag){
try {
s1.acquire();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.err.println(arr[i]);
s2.release();
}else{
try {
s2.acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.err.println(arr[i]);
s1.release();
}
}
}
}
import java.util.concurrent.Semaphore;
public class ThreadAlternate {
public static void main(String[] args) {
String[] s1 = {"A1","A2","A3"};
String[] s2 = {"B1","B2","B3"};
MyThread t1 = new MyThread(s1, true);
MyThread t2 = new MyThread(s2, false);
t1.start();
t2.start();
}
}
class MyThread extends Thread{
static Semaphore s1 = new Semaphore(1);
static Semaphore s2 = new Semaphore(1);
boolean flag = false;
static{
try {
s2.acquire();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
String[] arr;
public MyThread(String[] strArray, boolean flag) {
this.arr = strArray;
this.flag = flag;
}
public void run() {
for (int i = 0; i < arr.length; i++) {
if(flag){
try {
s1.acquire();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.err.println(arr[i]);
s2.release();
}else{
try {
s2.acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.err.println(arr[i]);
s1.release();
}
}
}
}
let X and Y be two binary semaphores where X = 1 and Y = 0
Thread1 Thread2
{ {
wait(X) wait(Y)
print(A1) print(B1)
signal(Y) signal(X)
wait(X) wait(Y)
print(A2) print(B2)
signal(Y) signal(X)
} }
Tell if the above logic will work or not.
Your logic wont work. According to ur logic,
A1 B1 A1 can be printed, as after printing B1 you are doing signal(X).
if Thread 1 is scheduled just after this, A1 can again be printed.
To maintain the order, you need to use 4 mutuxes
m_A1 = 1, m_A2 = 0, m_B1 = 0, m_B2 = 0;
thread1() {
wait(m_A1);
print A1
signal(m_B1)
wait(m_A2)
print A2
signal(m_B2)
}
thread2{
wait(m_B1)
print B1
signal(m_A2)
wait(m_B2)
print B2
signal(m_A1)
}
package com.home;
/**
* App
*
*/
public class App
{
public static String CLASS_NAME = "App :";
public static void main( String[] args )
{
Thread T1 = new Thread(r1);
Thread T2 = new Thread(r1);
try{
T1.start();
T2.start();
T2.join();
} catch(Exception e){
e.printStackTrace();
System.out.println("error :" +e.getMessage());
}
}
static volatile boolean t2Start = false;
static Runnable r1 = new Runnable(){
public void run() {
try {
System.out.println("t2Start:" + t2Start);
if(!t2Start){
synchronized (this) {
System.out.println(Thread.currentThread().getName());
System.out.println("A1");
t2Start = true;
}
synchronized (this) {
System.out.println(Thread.currentThread().getName());
System.out.println("B1");
}
}
if(t2Start){
synchronized (this) {
System.out.println(Thread.currentThread().getName());
System.out.println("A2");
}
synchronized (this) {
System.out.println(Thread.currentThread().getName());
System.out.println("B2");
}
}
} catch (Exception e) {
e.printStackTrace();
System.out.println("ERRORA: " + e.getMessage());
}
}
};
}
public class Example
{
public static void main(String[] args) throws InterruptedException
{
final Object o = new Object();
Thread t1 = new Thread(new Runnable()
{
@Override
public void run()
{
synchronized (o)
{
System.out.println("A1");
try
{
o.wait();
} catch (InterruptedException e)
{
e.printStackTrace();
}
System.out.println("A2");
o.notify();
}
}
});
Thread t2 = new Thread(new Runnable()
{
@Override
public void run()
{
try
{
Thread.sleep(100);
} catch (InterruptedException e)
{
e.printStackTrace();
}
synchronized (o)
{
System.out.println("B1");
o.notify();
try
{
o.wait();
} catch (InterruptedException e)
{
e.printStackTrace();
}
System.out.println("B2");
}
}
});
t1.start();
t2.start();
t1.join();
t2.join();
}
}
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <condition_variable>
using namespace std;
class Semaphore {
private:
mutex mtx;
condition_variable cv;
int counter;
public:
Semaphore(int value) {
counter = value;
}
void wait() {
unique_lock <mutex> lck(mtx);
cv.wait(lck, [&] {return counter > 0; }); //what does & do??
counter--;
}
void signal() {
unique_lock <mutex> lck(mtx);
counter++;
cv.notify_one();
}
};
Semaphore tA(1), tB(0);
void threadA() {
tA.wait();
cout << "A1-";
tB.signal();
tA.wait();
cout << "A2-";
tB.signal();
}
void threadB() {
tB.wait();
cout << "B1-";
tA.signal();
tB.wait();
cout << "B2";
}
int main() {
thread t1(threadA);
thread t2(threadB);
getchar();
return 0;
}
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <condition_variable>
using namespace std;
class Semaphore {
private:
mutex mtx;
condition_variable cv;
int counter;
public:
Semaphore(int value) {
counter = value;
}
void wait() {
unique_lock <mutex> lck(mtx);
cv.wait(lck, [&] {return counter > 0; }); //what does & do??
counter--;
}
void signal() {
unique_lock <mutex> lck(mtx);
counter++;
cv.notify_one();
}
};
Semaphore tA(1), tB(0);
void threadA() {
tA.wait();
cout << "A1-";
tB.signal();
tA.wait();
cout << "A2-";
tB.signal();
}
void threadB() {
tB.wait();
cout << "B1-";
tA.signal();
tB.wait();
cout << "B2";
}
int main() {
thread t1(threadA);
thread t2(threadB);
t1.join();
t2.join();
getchar();
return 0;
}
{{
public class SequencePrinter {
public static void main(String args[])
{
Threads T1 = new Threads("a1","a2");
Threads T2 = new Threads("b1","b2");
T1.start();
T2.start();
}
}
class Threads extends Thread
{
String s1 = null;
String s2 = null;
int count = 0;
Threads(String s1, String s2)
{
this.s1 = s1;
this.s2 = s2;
this.count = 0;
}
public void run()
{
if(count == 0)
{
System.out.println(this.s1);
count++;
this.yield();
}
if(count == 1)
{
System.out.println(this.s2);
}
}
}
}}
We will have 2 mutexes (m1, m2) and 2 Threads (T1, T2)
Initialize m1 =1(since we intend to start T1 first ) and b=0.
T1's resources are A1, A2, A3,...
T2's resources are B1, B2, B3,...
T1
while(1){
1. wait(m1)
2. prints (item from T1's resources) // prints A1, A2
3. signal(m2)
}
T2
while(1){
4 wait(m2)
5. prints (item from T2's resources) // prints B1, B2
6. signal(m1)
}
Step 4 in T2 gets blocked until step 3 in T1 is executed and step 1 in T1 gets blocked until step 6 in T2 is executed. which ensures that both the threads are waiting to print 1 element each alternatively.
For the 1st time, step 1 in T1 runs as m1 = 1.
Mutual Exlcusion, Progress and Bounded waiting is guarenteed by this process.
- srujana October 01, 2012