英文:
Looking for an Appropriate synchronization java code for this problem
问题
public class Bus {
public Bus() {
}
public void depart() {
System.out.println("I am departing from the bus stand....");
}
}
import java.util.ArrayList;
import java.util.concurrent.Semaphore;
public class Rider {
public void invokeBoard() {
System.out.println("I am boarding the bus");
}
}
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;
public class BusStandManager {
boolean isArrived;
int n;
Semaphore count_mutex;
Semaphore bus_mutex;
ArrayList<Rider> waiting_stage_queue;
ArrayList<Rider> bus_stand_queue;
public BusStandManager() {
this.isArrived = false;
this.n = 0;
this.count_mutex = new Semaphore(1);
this.bus_mutex = new Semaphore(1);
this.waiting_stage_queue = new ArrayList<>();
this.bus_stand_queue = new ArrayList<>();
}
public void putRider() {
Rider rider = new Rider();
try {
count_mutex.acquire();
if (n < 50 && !isArrived) {
n = n + 1;
bus_stand_queue.add(rider);
} else {
waiting_stage_queue.add(rider);
}
count_mutex.release();
} catch (InterruptedException e) {
System.out.println("Thread is suspended");
}
}
public void load_bus() {
try{
bus_mutex.acquire();
Bus bus = new Bus();
isArrived = true;
if (n != 0) {
for (Rider rider : bus_stand_queue) {
rider.invokeBoard();
}
n = 0;
}
bus.depart();
} catch (InterruptedException ie) {
System.out.println("Thread is suspended");
}
}
public void execute() {
ExecutorService executorService = Executors.newFixedThreadPool(10);
// method reference introduced in Java 8
executorService.submit(this::putRider);
executorService.submit(this::load_bus);
// close executorService
executorService.shutdown();
}
}
public class Main {
public static void main(String[] args) {
BusStandManager busStandManager = new BusStandManager();
busStandManager.execute();
}
}
英文:
Problem
Riders come to a bus stop and wait for a bus. When the bus arrives, all the waiting riders invoke boardBus, but anyone who arrives while the bus is boarding has to wait for the next bus. The capacity of the bus is 50 people; if there
are more than 50 people waiting, some will have to wait for the next bus. When all the waiting riders have boarded, the bus can invoke depart. If the bus arrives when there are no riders, it should depart immediately. Note that busses and riders will continue to arrive throughout the day. Assume inter-arrival time of busses and riders are exponentially distributed with a mean of 20 min and 30 sec, respectively.
For this problem, I need a concurrent program which can satisfy mutual exclusion and synchronization in java with clear explanation. Can anyone help me?
The Bus
public class Bus {
public Bus() {
}
public void depart() {
System.out.println("I am departuring from the busstand....");
}
}
The Rider
import java.util.ArrayList;
import java.util.concurrent.Semaphore;
public class Rider{
public void invokeBoard() {
System.out.println("I am boarding to the .... in the bus");
}
}
The Bus stand Manager
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;
public class BusStandManager {
boolean isArrived;
int n;
Semaphore count_mutex;
Semaphore bus_mutex;
ArrayList<Rider> waiting_stage_queue;
ArrayList<Rider> bus_stand_queue;
public BusStandManager() {
this.isArrived = false;
this.n = 0;
this.count_mutex = new Semaphore(1);
this.bus_mutex = new Semaphore(1);
this.waiting_stage_queue = new ArrayList<>();
this.bus_stand_queue = new ArrayList<>();
}
public void putRider() {
Rider rider = new Rider();
try {
count_mutex.acquire();
if (n < 50 && !isArrived) {
n = n + 1;
bus_stand_queue.add(rider);
} else {
waiting_stage_queue.add(rider);
}
count_mutex.release();
} catch (InterruptedException e) {
System.out.println("Thread is suspended");
}
}
public void load_bus() {
try{
bus_mutex.acquire();
Bus bus = new Bus();
isArrived = true;
if (n != 0) {
for (Rider rider : bus_stand_queue) {
rider.invokeBoard();
}
n = 0;
}
bus.depart();}
catch (InterruptedException ie){
System.out.println("Thread is suspended");
}
}
public void execute() {
ExecutorService executorService = Executors.newFixedThreadPool(10);
// method reference introduced in Java 8
executorService.submit(this::putRider);
executorService.submit(this::load_bus);
// close executorService
executorService.shutdown();
}
}
The Usage
public class Main {
public static void main(String[] args) {
BusStandManager busStandManager = new BusStandManager();
busStandManager.execute();
}
}
答案1
得分: 2
这个问题在并发编程中很常见。Grant Hutchins 对这个问题提出了一个很棒的解决方案。
他使用了 3 个信号量和一个计数器来得到解决方案。
waiting = 0;
mutex = new Semaphore(1)
bus = new Semaphore(0)
boarded = new Semaphore(0)
waiting - 乘客在候车区的数量。
mutex - 用于保护 waiting 变量。
bus - 用于告诉乘客巴士是否在场内。
boarded - 用于告诉巴士乘客已上车。
巴士进程代码
mutex . wait ()
n = min ( waiting , 50)
for i in range ( n ):
bus . signal ()
boarded . wait ()
waiting = max ( waiting -50 , 0)
mutex . signal ()
depart ()
这里,mutex 用于锁定 waiting 变量,因为每当巴士到达时,都不能增加 waiting。n 是 waiting 和 50 中的最小值,因为如果有 70 名乘客,我们只能将 50 名乘客送上巴士,如果有 30 名乘客,我们可以将所有乘客送上巴士。根据这个最小条件,我们最多将 50 名乘客送上巴士。然后对于每个乘客,巴士发出信号表明它已到达,所以乘客可以上巴士。
在 50 名乘客上了巴士之后,如果初始阶段的乘客少于 50 名,waiting 将被设置为零,否则我们从乘客中减去 50,因为已经上了 50 名乘客。
然后我们释放 mutex,这样新的乘客就可以来增加值。
乘客代码
mutex . wait ()
waiting += 1
mutex . signal ()
bus . wait ()
board ()
boarded . signal ()
乘客线程等待 mutex,当它获得锁时,它将增加 waiting 以表示正在等待巴士。乘客线程正在等待巴士,因此当巴士到达时,乘客线程可以进入 board 方法。然后乘客执行 board() 方法,它会发出信号表示乘客已上车。因此巴士将再次发出信号来接纳另一个线程。
我们还有另一个解决方案,它在这本书中有描述。Java 实现可以在这个GitHub 链接中找到。
英文:
This problem is a common problem in concurrent programming. Grant Hutchins did a fantastic solution to this problem.
He used 3 semaphores and a counter to get a solution
waiting = 0;
mutex = new Semaphore(1)
bus = new Semaphore(0)
boarded = new Semaphore(0)
waiting - number of riders in the boarding area.
mutex - this is used to protect the waiting variable.
bus - It is used to tell the riders that the bus in the court or not.
boarded - It is used to tell the bus that rider is boarded.
The bus process code
mutex . wait ()
n = min ( waiting , 50)
for i in range ( n ):
bus . signal ()
boarded . wait ()
waiting = max ( waiting -50 , 0)
mutex . signal ()
depart ()
Here, the mutex is used to lock the waiting variable since whenever the bus arrives no one can increment waiting.
n is minumum of waiting and 50 since if we have 70 riders we can only 50 riders to the bus and if we have 30 riders we can take all riders to the bus. With this minimum condition, we take only 50 riders to the bus.
Then for each rider bus signal that it's arrived so the rider can get into the bus.
After 50 riders are boarded in the bus, waiting will be set to zero if we have riders less than 50 in the initial stage otherwise we decrement 50 from riders since 50 riders are boarded.
then we release the mutex so the new rider can come and increase the value.
Rider code
mutex . wait ()
waiting += 1
mutex . signal ()
bus . wait ()
board ()
boarded . signal ()
rider thread waits for the mutex when it gets the lock it will increase waiting to tell that it is waiting for the bus.
The rider thread is waiting for the bus so when the bus arrives bus rider thread can go to the board method. then the rider executes the board() method it will signal that rider is boarded. so the bus will signal again to board another thread.
We have another solution as well It is desribed in this book.
Java implementation can be found in this github link
`
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论