rahul.s
BAN USERFollowing 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;
}
Well answer really depends upon how compiler generates code, what CPU is executing code and how many CPUs are installed in host computer. Lets assume loop generates the following assembly code ( I generated through VS 2012) and if initial value of shared variable is 0 then it is not hard to prove that Min value can be 0 and Max value can be 200 (though it is highly unlikely you ever see these values)
for( int i = 0 ; i < 2 ; i++ )
012643DE mov dword ptr [ebp-8],0
012643E5 jmp odd_thread_cs+30h (012643F0h)
012643E7 mov eax,dword ptr [ebp-8]
012643EA add eax,1
012643ED mov dword ptr [ebp-8],eax
012643F0 cmp dword ptr [ebp-8],2
012643F4 jge odd_thread_cs+45h (01264405h)
{
shared_value++;
012643F6 mov eax,dword ptr ds:[0126F21Ch]
012643FB add eax,1
012643FE mov dword ptr ds:[0126F21Ch],eax
}
01264403 jmp odd_thread_cs+27h (012643E7h)
I think B+ tree should should be useful in this case.
For a b-order B+ tree with h levels of index:
Inserting a record requires O(log n on base b ) operations
Finding a record requires O(log n on base b) operations
Removing a (previously located) record requires O(log n on base b) operations
Using a stack integer of length n can be added here. Same can be done for subtraction.
Stack st1 = new Stack();
Stack st2 = new Stack();
//Adding number 129 + 138 split it and push to stack.
st1.push(1);
st1.push(2);
st1.push(9);
st2.push(1);
st2.push(3);
st2.push(8);
StringBuffer res= new StringBuffer();
int carry = 0;
for(int i =0 ; i < 3;i++){
int a = (int) st1.pop();
int b = (int) st2.pop();
int temp = a + b + carry;
if(temp > 9){
carry = 1;
temp = temp - 10;
}
else{
carry = 0;
}
res = res.append(temp);
}
System.out.println(res.reverse());
Courtesy - https://sites.google.com/site/arjunwebworld/Home/programming/programmatic-questions
- rahul.s July 16, 2013
Could you please elaborate a bit. I find it difficult to visualize how this problem is similar to connected component problem So how the DFS is applied.
- rahul.s November 26, 2018