In Hackathon 1 I have submitted this code
#include<bits/stdc++.h>
using namespace std;
struct Tree{
string name;
Tree* head;
vector<Tree*> childrens;
bool islocked;
set<Tree*> bottom;
int locked;
Tree(string n,Tree*m){
name=n;
locked=-1;
head=m;
islocked=false;
}
void add(vector<string> & str){
for(string &it:str){
childrens.push_back(new Tree(it,this));
}
}
};
struct Tree2{
Tree* val;
unordered_map<string, Tree*> mp;
Tree2(string str){
val=new Tree(str,nullptr);
}
void buildTree(vector<string>& str,int n){
queue<Tree*> q;
int k=1,i,size=str.size();
q.push(val);
while(!q.empty()){
Tree* r=q.front();
q.pop();
mp[r->name]=r;
vector<string>b;
for(i=k;i<min(size,k+n);i++){
b.push_back(str[i]);
}
r->add(b);
for(Tree* child : r->childrens){
q.push(child);
}
k=i;
}
}
void update(Tree* r, Tree* current){
while(r){
r->bottom.insert(current);
r=r->head;
}
}
bool lock(string name, int id){
Tree* r=mp[name];
if(r->islocked or r->bottom.size()) return false;
Tree* par =r->head;
while(par){
if(par->islocked) return false;
par=par->head;
}
update(r->head,r);
r->islocked=true;
r->locked=id;
return true;
}
bool upgrade(string name, int id){
Tree* r=mp[name];
if(r->islocked or r->bottom.size()==0) return false;
for(Tree* it: r->bottom){
if(it->locked!=id) return false;
}
Tree* par =r->head;
while(par){
if(par->islocked) return false;
par=par->head;
}
set<Tree* > st= r->bottom;
for(Tree* it: st){
unlock(it->name,id);
}
lock(name,id);
return true;
}
bool unlock(string name, int id){
Tree* r=mp[name];
if(!r->islocked or r->locked!=id) return false;
Tree* par =r->head;
while(par){
par->bottom.erase(r);
par=par->head;
}
r->islocked=false;
r->locked=1;
return true;
}
};
int main(){
int size,m,testcases,i,type,id;
string name;
cin>>size>>m>>testcases;
vector<string> a(size);
for(int i=0;i<size;i++){
cin>>a[i];
}
Tree2* tree=new Tree2(a[0]);
tree->buildTree(a,m);
while(testcases--){
cin>>type>>name>>id;
if(type==1){
if(tree->lock(name,id)){
cout<<"true";
}
else{
cout<<"false";
}
}
else if(type==2){
if(tree->unlock(name,id)) cout<<"true";
else cout<<"false";
}
else if(type==3){
if(tree->upgrade(name,id)) {
cout<<"true";
}
else cout<<"false";
}
cout<<"\n";
}
}
sir:Hi
me:Hy Sir
Sir:
Let’s start with your Part A explanation, can you describe your approach in brief?
Me:firstly we had lock operation . we will check all the decendents are locked or not in constant time then will check ancestors are locked or notin log(n) time
then we have unlock if node is locked and if it is locked by same id we will inform all the ancestors about its unlocking in log(n) as we have to explore all ancestors one by one
then upgrade check decendents are locked by same id or not lock the node in log(n) time and unlock all decendents on O(locked decendents * log(n))time
space complexity will be O(n)
Sir:
Could you explain why you choose certain data types in your struct?
Me:
the choice of data types in the struct Tree and struct Tree2 is influenced by the requirements and the operations performed on these structures.
Sir:
Ok, I meant to ask the use case, there are other data types which can also work for certain fields in your struct.
Me:
these were picked to help keep track of different parts of the tree. Strings hold the names of these nodes. Vectors store the child nodes under each parent node. Sets help in managing which nodes are locked or not below a particular node. And finally, the unordered map quickly matches node names with their positions in the tree.
Sir:
Are there any changes or improvements you can think of in your Part A solution?
Me:
Yes There could be improvement is complexities such as instead of using set i would have used unordered_set which would have optimised time complexity.
Sir:
Yeah, anything else
Me:Other thing would be optimizing memory management with a destructor to prevent memory leaks.
Implementing synchronization mechanisms such as mutexes or locks to control access to shared resources. This prevents multiple threads from modifying the tree structure simultaneously.
Identifying operations that can be executed independently and considering parallelizing them. Say, if multiple nodes can be locked or unlocked simultaneously without affecting each other, these operations could run concurrently.
Sir:
Yeah
In your upgrade function, can you see if there is any checks that’s redundant ?
Me:
Can You please give me some time to think?
Sir:
Yeah sure
Me:
I am not able to find any redundant check as every check is necessary
Sir:
Ok, do we need to check for ancestors in upgrade?
Me:
I am Sorry
The upgrade function already verifies that a node has locked descendants before attempting the upgrade. This indirectly implies that there are no locked ancestors, as locking a descendant would have failed if an ancestor was already locked. Therefore, the explicit check for locked ancestors (par =r->head; while(par){ if(par->islocked) return false; par=par->head; }) might be redundant.
Removing the redundant check can improve the performance of the Upgrade function by reducing the number of comparisons needed.
But If there's any uncertainty about the locking rules or potential edge cases, keeping the check provides an extra layer of safety to prevent unintentional locking conflicts
Sir:
Lock function still checks if any ancestors are locked, so even if there are few uncertainties that can be handled by lock
And a little restructure would help you out in any other case
You understood the reason correctly so that’s all that matters
Let’s continue onto Part B
Me:
Sure sir
Sir:
Part-B Question:
Let’s say you are running the lock/unlock in a multi core machine. Now you
want to let multiple threads to run lock() As we saw in part A, locking a
node has multiple validations inside. Will doing lock on two nodes
cause a race condition. If yes, how will you solve it. In short, how do
make the lock() function thread safe? - Multiple threads running it
simultaneously shouldn’t not affect the correctness. - Try to make the
critical sections more granular. ie. don’t create any big
atomic/synchronised blocks that will make parallelism suffer. Consider
each operation is atomic.
Me:
Yes, running the function on two nodes concurrently without synchronization can lead to race conditions.
The Race Conditions Would be
Firstly Multiple threads can read and write to islocked , bottom, and locked variables simultaneously, leading to inconsistent states.
Second If a thread modifies the bottom set while another thread is iterating over it, the iterator might become invalid, causing unpredictable behavior.
We can use mutexes or spinlocks to protect individual variables or small code blocks within lock(), rather than locking the entire function.
Sir:
Can you think of an approach which doesn’t rely on mutexes or any other atomic variable?
Me:
Are You asking without mutex or without semaphores also
Sir:
Both
Me:
We can use compare and swap which compares a given value with the value in memory and performs the update only if they match. so we will have exclusive access and prevents race conditions in a better way.
Sir:
Yeah
Can you share in what inputs of lock will there be race condition
And what will be the critical section?
Me:
if two threads simultaneously want the same node to lock. They both see it unlocked based on some outdated information and attempt to lock it concurrently.
if one thread locking a node while another is unlocking its ancestor. The first thread could lock based on an incorrect view of the locked descendant.
Sir:
Yeah
Me:
The critical section would be islocked (bool flag), bottom(set ) and locked(id).
Sir:
Ok
Let’s discuss on the approach if you have any ideas in mind
Me:
Either we can use compare and swap or we can have our own mutex lock.
Sir:
Ok, let’s try to solve one test case. We can try which one fits better for implementation
Me:
Do i have to implement both the locks
implement*
i mean both the approaches
Sir:
No
We can first devise an approach to solve one of the test case
Then we can theoretically assess if one might be better than other
Me:
Sure sir
Me:
We can use compare and swap but i think it would be somewhat difficult as its retry loops and context switching can introduce overhead compared to a optimized mutex.
also it relies on instructions provided by the hardware and might not be universally supported.
Sir:
It’s ok, we don’t need to think that deep for this.
Me:
approach for the mutex lock
non critical code
acauire mutex lock
critical section
release mutex lock
non critical section
approach for compare and swap
non critical code
check if 0, swap with 1
critical section
check if 1, swap with 0
non critical section
Sir:
Ok, are there any blockers in using a non mutex approach?
Me:
yes they doesn’t inherently solve the ABA problem, where a value changes back to a previously observed value, leading to incorrect behavior.
say a value is observed to be the same as expected, then changes to a different value, and then changes back to the original expected value, it will lead data inconsistency.
Sir:
Okay
For now let's come up with an approach using mutex
And solve the test cases and any race condition that may happen
Later on we can attempt to refactor it with non mutex (edited)
ME:
non critical code
acquire mutex lock
critical section
release mutex lock
non critical section
We will Acquire lock before entering critical section and release it as soon as critical section ends
Sir:
Yeah, where will you acquire lock when will you release it
Can you share some details on that?
Me:
If i use Basic approach we will use it when fct starts and release it before fct ends
This will be the naive approach and we can make it more granular
Sir:
Yeah
Me:
Should I be more specific
Sir:
Think about the drawbacks of just acquiring a lock at the start and end
Then as you know try to only acquire lock when necessary
Me:
The locks will not be released at return statements so we need to release them before every return statement.
Sir:
Yeah
First think of a simple approach, then see what drawbacks it has, based on that we can refine on the approach
Keep sharing whatever comes to your mind
Me:
There could be two critical sections
First when we want to update some value
second would be when ancestors are being updated.
Sir:
Yeah
Now think about the approach in steps, and see whether the approach solves both test cases
If not then let's try to solve them, and let me know if you have any doubts or if you're stuck somewhere
Me:
Sure sir Give me some time to think about it.
Sir:
Sure
Sir:
Any idea?
Me:
Do i need to write a sudo code
or only approach
Sir:
You can share your approach in description or using pseudo code
Once we have an approach which seems feasible we can work on implementation
Me:
Acquire the relevant mutex before accessing or modifying node state.
Release the mutex when finished.
Also having Lock Ordering:
Establish a consistent lock acquisition order to prevent deadlocks.
So, always lock parents before children.
Also we can break down the function into smaller, independently lockable steps.
Me:
Ok
Can you share pseudo code
Sir:
sure sir i will be sharing it in few minutes
Me
function lock(tree, name, id)
node = tree.find_node(name)
if node is null
return false
parent = node.parent
-> Locking All The Parents
while parent:
lock(parent.mutex)
parent = parent.parent
->Then Locking children
lock(node.mutex)
if node.islocked or node.bottom.size() > 0:
release_locks(node)
return false
update_node_state(node, id)
release_locks(node)
return trueSir:
In lock(node.mutex) you're locking all children or the current node for which lock is called?
Me:
Only the current node is being locked.
If child node tries to modify itself then he can not get lock of all parent nodes so we dont need to lock child node
Only current node and all its parents are being locked
Sir:
Okay
Now the problem with this is that while you lock all ancestors all other threads will have to wait for this one to finish
Can you think of a way to increase the parallelism
Me:
We will Acquire a Read Write lock for Parent Nodes which will allow multiple reads and single write .
Sir:
Okay
Implement this approach, then we can review for other edge cases
Me:
bool lock(string name, int id) {
Tree* r = mp[name];
unique_lock<shared_mutex> node_lock(node->mutex);
if(r->islocked or r->bottom.size()) return false;
Tree* par = r->head;
while (parent) {
shared_lock<shared_mutex> parent_lock(parent->mutex);
if(par->islocked) return false;
parent = parent->head;
}
update(r->head,r);
r->islocked=true;
r->locked=id;
return true;
}we are having unique_lock(Write Lock) for current node and shared_lock(Read Lock) for parent nodes (edited)
Sir:
If a shared_lock is acquired for a node will the unique_lock succeed for it?
Me:
No Sir.
Multiple threads can hold shared locks but only single thread can hold exclusive lock.
Sir:
Looks fine, now see if you can change the implementation to use a non mutex approach
Me:
Sure sir
Me:
Could You Give me some time?
Sir:
Sure
Me:
bool lock(string name, int id){
Tree* r=mp[name];
if(r->lockedval>0 or r->bottom.size()) return false;
r->lockedval++;
if(r->lockedval>1){
r->lockedval--;
return false;
}
Tree* par =r->head;
while(par){
if(par->lockedval>0 || r->bottom.size()>0){
r->lockedval--;
Tree *par1= r->head;
while(par1!=par){
par1->bottom.erase(r);
par1=par1->head;
}
return false;
}
par->bottom.insert(r);
par=par->head;
}
r->locked=id;
return true;
}The locking system tracks node states with a count variable, initially 0. To lock a node, a thread increments the count. If successful, it also marks the node as locked by its thread ID and updates ancestor states, ensuring no ancestors or descendants are locked.
But This would not support parallism
Sir:
This is quite close to the actual solution
There are few adjustments you will have to make as there might be minor race condition issues
Also, you can improve its parallelism
Me:
Could you please give me some time
Sir:
Yeah
Me:
could you give me some hint
Sir:
Current you're using a test and set approach
See if you can flip this
Me:
If i am updating islocked and some other thread is trying to access it. This would lead to inconsistancy .
Sir:
Any other variable that you can update?
Me:
If par->lockedval==1 then two threads can come in if block
Me:
bool lock(string name, int id){
Tree* r= m[name];
if(r->lockedval>0 or r->bottom.size()) return false;
r->lockedval++;
if(r->lockedval>1){
r->lockedval--;
return false;
}
Tree* par= r->head;
while(par){
if(par->lockedval>0 or r->bottom.size()>0){
r->lockedval--;
Tree *par1= r->head;
while(par1!=par){
par1->bottom.erase(r);
par1=par1->head;
}
return false;
}
par->bottom.insert(r);
par=par->head;
}
r->locked=id;
return true;
}If par->lockedval==1 and the process switches then it will cause an issue
Sir:
Okay, let's take an example and solve it
We have a tree
A
/
B C
Now there are two threads T1 (locking A) and T2 locking B
Now first you start what will be the conditions under which the issue you stated will happen
Once we have an example we can solve it
Me:
I Dont get it do i have to tell you the senario during context switching
Sir:
Yeah
Me:
t1 check condition1 (r->lockedval>0 || r->bottom.size()) and it will become false
than context switching take place and t2 comes and enter in while loop ,t2 will check condition2 (par->lockedval>0 or r->bottom.size()>0) and it will become false
than context switching take place
means t1 will be checking condition first and and t2 will be second to check condition
t1 start its execution and first time while loop condition will be false so set the value of r->locked and return true Then t2 will run other line and next time par will be NULL so it will come out from while loop.
and will set r->locked=id; and also return true;
Me:
Yeah, you picked the right issue
Now think when T2 checks for condition 2, the issue is we haven’t incremented the lockedval value yet
What if we make sure that it gets updated before
Again the hint: instead of test and set, you need to set and test
Me:
But I guess it will still create problem as we have to necessarily test the lock variable first and then set it.
Sir:
Okay, let’s say if I increment the lockedval first, then check for both lockedval and bottom size, see can you solve same node test case with this arrangement?
Me:
but if we have two threads they will both increase the counter and lockedval>0 will always be true (edited)
Sir:
Do we need to necessarily check with 0?
Can’t we change the condition to suite what we should allow?
Me:
yes that is true. But Then We have to define condition.
Sir:
Yeah, so try to see what needs to change, how can this approach be used to solve this
Me:
r->lockedval++;
if (r->lockedval> 1 || r->bottom.size()) {
r->lockedCount--;
return false;
}
Sir:
Yeah, this just needs to small fix, but it’s right
Now inorder to make this change also work with ancestor descendant case
See if you can apply same set and test approach there
Me:
while (par) {
par->lockedval++;
if (par->lockedval> 1 || par->bottom.contains(r)) {
par->lockedval--;
r->lockedval--;
Tree* par1 = r->head;
while (par1 != par) {
par1->bottom.erase(r);
par1 = par1->head;
}
return false;
}
par->bottom.insert(r);
par = par->head;
}Sir:
This is okay, but it has a problem.
When you increment lockedval of parent’s it locks them all and parallelism suffers (edited)
Instead of incremented lockedval of parent can we do something else with them?
Me:
can we create a new variable readval (edited)
par->readval = true;
if (par->lockedval> 1 || par->bottom.contains(r)) {
par->readval = false;
r->lockedval--;Sir:
What if you use bottom instead?
Sir:
Did you get this?
Me:
I am trying to get the solution.
while (par) {
Tree* ancestor = par;
while (ancestor) {
if (ancestor->bottom.contains(r)) {
r->lockedval--;
Tree* par1 = r->head;
while (par1 != par) {
par1->bottom.erase(r);
par1 = par1->head;
}
return false;
}
ancestor = ancestor->head;
}
par->bottom.insert(r);
par = par->head;
}Sir:
Here you’re still using test and set
What if you set bottom first then test if the parent is acquired? (edited)
Me:
while (par) {
par->bottom.insert(r);
Tree* ancestor = par;
while (ancestor) {
if (!ancestor->bottom.contains(r)) {
par->bottom.erase(r);
Tree* par1 = r->head;Sir:
if (!ancestor->bottom.contains(r)) This condition will always be false right?
Instead of checking for bottom, can you check for something else?
Me:
ancestor->islocked we can check if it is already locked
Sir:
Yeah, anything else along with this?
You had that previously
Me:
lockedval i guess
Sir:
Yeah
Me:
if (ancestor->lockedval> 1) {
par->bottom.erase(r);
ancestor = ancestor->head;
continue;
}Sir:
Any doubts?
Me:
No sir
Sir:
This should be > 1 or > 0 ?
Me:
bool lock(string name, int id){
Tree* r= m[name];
r->lockedval++;
if (r->lockedval> 1 || r->bottom.size()) {
r->lockedval--;
return false;
}
if(r->lockedval>1){
r->lockedval--;
return false;
}
Tree* par= r->head;
while (par) {
par->bottom.insert(r);
Tree* ancestor = par;
while (ancestor) {
if (ancestor->islocked) {
par->bottom.erase(r);
r->lockedval--;
Tree* par1 = r->head;
while (par1 != par) {
par1->bottom.erase(r);
par1 = par1->head;
}
return false;
}
if (ancestor->lockedval > 0) {
par->bottom.erase(r);
ancestor = ancestor->head;
continue;
}
ancestor = ancestor->head;
}
par->lockedval++;
par = par->head;
}
r->locked=id;
return true;
}Sir:
In while(par) loop, can you merge the if conditions?
Sir:
Hey you there?
Me:
YEs sir
I can merge the if statements
Sir:
Okay, can you update the code in codeshare link share above
Add any other changes you want to I’ll review it there
Me:
I will Update it.
I have updated it.
Sir:
You’re traversing on ancestors twice, do we need to?
It should have been a condition if ancestor
Sir:
Yeah
Me:
I have updated it
bool lock(string name, int id){
if (m.find(name) == m.end()) return false;
Tree* r= m[name];
if (r == nullptr) return false;
r->lockedval++;
if (r->lockedval> 1 || r->bottom.size()) {
r->lockedval--;
return false;
}
Tree* par= r->head;
while (par) {
par->bottom.insert(r);
Tree* ancestor = par;
if (ancestor->islocked || r->bottom.size()>0 ) {
par->bottom.erase(r);
r->lockedval--;
Tree* par1 = r->head;
while (par1 != par) {
par1->bottom.erase(r);
par1 = par1->head;
}
return false;
}
ancestor = ancestor->head;
par = par->head;
}
r->locked=id;
return true;
}