![]() ![]() The moment addLock is used, we know blocking between the two method will occur. Because values are not added directly into removeStack, so it being empty means nothing about the actual queue. This might seem like a basic example of a dequeue implementation, but that is not true. ![]() If it isn't you simply pop and return that value. You then check if the removeStack is empty or not. You start by entering a synchronized block of removeLock, this is quite expected, given how the stacks require usage of the locks. This already tells us that blocking will occur. However, it is already obvious that for the dequeue to work, addStack must be accessed, and thus addLock must be touched. Otherwise, this is quite straightforward. Although, the use of notifyAll may cause a problem. This is both not defined in the requirements, and will cause blocking between the threads. I'm assuming this is a blocking queue then. The notifying part, tells us that there is waiting somewhere. Take the addition lock, add an element, notify about this addition, and release the lock. In reality, implementing it generically isn't that different or complicated, since an underlying data structure that supports generics is used. I would recommend using a Dequeue instead.Īnother clear part is that it is an int only implementation. Luckily, as we will see, most of this doesn't have much functionality impact, but rather more of a performance issue. Not only is Stack a outdated collection class, you must also be aware that it extends Vector and each method in it is synchronized. The usage of the Stack class however, is a problem. Again, good thought, a single lock must be responsible for all the usage of a specific data source. You also have 2 stacks, each corresponding to a lock. You have 2 locks, a good thought to try and separate the methods. The first clear thing is that you are using locks, which means blocking is likely. So one can either not use locks, or try to limit their affects. This is actually problematic, because as long as a lock is used, blocking will occur. ![]() However, the catch here is Enqueue and Dequeue need to be parallel. This is pretty basic, and has many ways to implement. Implement a thread-safe queue with an underlying stack. Let's start by talking about the requirements. Private final Object removeLock = new Object() Private final Object addLock = new Object() * Queue Implementation with Stack as underlying data-structure and with pop the element from removeStack and returnīelow is the java code : import.Dequeue operation : If removeStack is empty then addStack is checked if it is empty, if not then all the elements from addStack are popped and pushed to removeStack.Enqueue operation : enqueue inside synchronized block on addLock, once item added, invoke notifyAll on addLock.Two Stacks : addStack and removeStack with individual Lock Objects addLock and removeLock.enqueue thread must not wait for dequeue thread.ĭuring my search (java based solutions) I could only find the blocking version of this problem where enqueue and dequeue are blocking for each other.īelow is my attempt for this, please correct me if I am wrong or in case I missed something. (This is only for understanding and learning purpose) The language for the solution : JavaĪ Queue with FIFO behavior needs to be implemented by having underlying data structure as Stack.Įnqueue and Dequeue need to be parallel and need not block each other, i.e. This is a mix of data structure and multi threading concept based question. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |