前阵子遇到一个面试题,当时没有做出来,后来断断续续的用了一周的时间做了出来,但感觉也不完全对,先来看看题目,稍后再讨论。
问题
模拟一个餐馆,三个厨师,二个服务员,厨师单独做菜,2分钟一个菜,服务员单独送菜10秒一个
分析
一看这问题就知道考查的点是多线程,生产者与消费者模型的模拟类问题,《Java编程思想》中有类似的例子,但是这个问题比书中的例子要复杂一些,因为厨师和服务员都有多个,所以要考虑到厨师与服务员的管理(资源管理),以及定单的队列,因为当厨师都在忙的时候,定单必须要放入队列中。另外的最难的地方就在于如何写测试以证明程序是正常工作,这是最难的地方。关键的点应该是:
- 厨师的管理:包括安排厨师去做菜,厨师做好菜后要通知服务员去送菜,当没有厨师时,或没有菜单时都要空闲等待
- 服务员的管理:安排服务员去送菜,当没有菜时或没有服务员时都要等待
- 定单的管理:当没有厨师去做菜时,要把定单放入队列里,等待厨师,这个可以让厨师管理者一同管理;同理当没有服务员时也要放入队列,这个可以由服务员管理者来管理
- 测试用例:用一定数量的定单数来验证程序是正确的。
测试
可以先想一些测试用例:
- 当只有一个定单时,很容易,应该是做菜时间加上送菜时间就好了,同时只用一个厨师和一个服务员
- 当有二个时,因为有三个厨师和二个服务员,二道菜应该同时完成,因为资源充足,没有等待
- 当有三个时,厨师不用等,但服务员要等,所以前二个同时完成,第三个要再等一个送菜时间
- 当有四个时,当厨师在做第四道菜时,第三个已经送完,所以第四个菜要多等一个做菜时间和送菜时间
- 第五个应该与第四个同时完成
- 第六个比第五个多等一个送菜时间
实现
测试代码,也许这个测试代码应该重构,以去掉重复的,但是那样容易出错,这样虽然重复,但很直观。
package com.effectivejava.threading.basics;import junit.framework.TestCase;public class ResturauntTest extends TestCase {private Resturaunt resturaunt;/** TODO:* time to cook: 200 ms* time to deliver: 50 ms* tolerance is 100 ms* If tolerance is less than 100, cases will fail.* These three parameters are important for these tests to pass, if you change time2cook or time2deliver,* cases would fail.*/private int tolerance = 100; // in mspublic ResturauntTest() {super("ResturauntTest");}@Overridepublic void setUp() {resturaunt = new Resturaunt("Hilton's Place");}@Overridepublic void tearDown() {resturaunt.closeDoor();}public void testOneOrder() throws InterruptedException {System.out.println("============ start testing one orders =============");final Order order[] = createOrders(1);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(order[0] + " should be ready", order[0].isReady());}public void testTwoOrders() throws InterruptedException {System.out.println("============ start testing two orders =============");final Order orders[] = createOrders(2);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " hsould is ready", orders[0].isReady());assertTrue(orders[1] + " is ready", orders[1].isReady());}public void testThreeOrders() throws InterruptedException {System.out.println("============ start testing three orders =============");final Order orders[] = createOrders(3);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " is ready", orders[0].isReady());assertTrue(orders[1] + " is ready", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " is ready", orders[2].isReady());}public void testFourOrders() throws InterruptedException {System.out.println("============== start testing four orders ===============");final Order orders[] = createOrders(4);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " should be ready", orders[0].isReady());assertTrue(orders[1] + " should be ready too", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " should be ready now", orders[2].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[3] + " is ready yet", orders[3].isReady());}public void testFiveOrders() throws InterruptedException {System.out.println("======================start testing five orders=====================");final Order orders[] = createOrders(5);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " should be ready", orders[0].isReady());assertTrue(orders[1] + " should be ready too", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " should be ready now", orders[2].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[3] + " is ready yet", orders[3].isReady());assertTrue(orders[4] + " is ready", orders[4].isReady());}public void testSixOrders() throws InterruptedException {System.out.println("======================start testing six orders=====================");final Order orders[] = createOrders(6);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " should be ready", orders[0].isReady());assertTrue(orders[1] + " should be ready too", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " should be ready now", orders[2].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[3] + " is ready yet", orders[3].isReady());assertTrue(orders[4] + " is ready", orders[4].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[5] + " is ready", orders[5].isReady());}public void testSevenOrders() throws InterruptedException {System.out.println("======================start testing seven orders=====================");final Order orders[] = createOrders(7);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " should be ready", orders[0].isReady());assertTrue(orders[1] + " should be ready too", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " should be ready now", orders[2].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[3] + " is ready yet", orders[3].isReady());assertTrue(orders[4] + " is ready", orders[4].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[5] + " is ready", orders[5].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[6] + " is ready", orders[6].isReady());}public void testEightOrders() throws InterruptedException {System.out.println("======================start testing eight orders=====================");final Order orders[] = createOrders(8);int timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[0] + " should be ready", orders[0].isReady());assertTrue(orders[1] + " should be ready too", orders[1].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[2] + " should be ready now", orders[2].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[3] + " is ready yet", orders[3].isReady());assertTrue(orders[4] + " is ready", orders[4].isReady());timeToWait = tolerance;timeToWait += WaitorManager.TIME_TO_DELIVER;Thread.sleep(timeToWait);assertTrue(orders[5] + " is ready", orders[5].isReady());timeToWait = tolerance;timeToWait += CookManager.TIME_TO_COOK;Thread.sleep(timeToWait);assertTrue(orders[6] + " is ready", orders[6].isReady());assertTrue(orders[7] + " is ready", orders[7].isReady());}private Order[] createOrders(int count) {Order orders[] = new Order[count];for (int i = 0; i < count; i++) {final Order o = new Order("Pizza " + "#" + i);resturaunt.submitOrder(o);assertFalse(o + " not ready", o.isReady());orders[i] = o;}return orders;}
}
需要一个Resturant类,它仅接收定单,然后委派给CookManager和WaitorManager去做事,自己并不做事
package com.effectivejava.threading.basics;/** From this demo, we learn the lesson that why TDD is so good in development practice.* Without TDD, you are not assured that your programs work correctly.* TDD can, at least, assure you that your programs work.*/
public class Resturaunt {private String name;private int cookLimit;private int waitorLimit;private CookManager cookManager;private WaitorManager waitorManager;public Resturaunt(String name) {this.name = name;cookLimit = 3;waitorLimit = 2;System.out.println("Resturation: " + name + " is open now, Welcome everyone!");cookManager = new CookManager(this, cookLimit);waitorManager = new WaitorManager(waitorLimit);}public void submitOrder(Order o) {cookManager.prepareFood(o);}/** There is a problem: waitor #1 always do more work than waitor #2.* Because food delivery is quick to finish, so when food is preparing, waitor #1 finishes its* delivery and back to queue. When food is prepared, it is waitor #1 to deliver because it is* on the head of the queue.* Solution:* When waitor or cook is about to deliver or cook, remove it from the queue and push it onto* the queue after it finishes.*/public void foodPrepared(Order o) {waitorManager.deliverFood(o);}public void closeDoor() {cookManager.knockOff();waitorManager.knockOff();System.out.println("Resturant: " + name + " is closed now, welcome to come tomorrow!");}
}
接下来是CookManager:它要负责调度厨师们来工作,给他们分配任务,并管理定单,当没厨师时或没定单时都要空闲等待,同时还要监听,当菜做完后通知WaitorManager来送菜。因为厨师只由CookManager来管理,并不直接与外界沟通,所以Cook类可以做为CookManager的内部类
package com.effectivejava.threading.basics;import java.util.ArrayList;
import java.util.List;public class CookManager implements Runnable {public static final int TIME_TO_COOK = 200;private boolean knockedOff;private List<Cook> availableCooks;private Resturaunt resturaunt;private int cookLimit;private List<Order> ordersToPrepare;public CookManager(Resturaunt r, int cl) {knockedOff = false;resturaunt = r;cookLimit = cl;availableCooks = new ArrayList<Cook>(cookLimit);availableCooks.add(new Cook("Cook #1", this));availableCooks.add(new Cook("Cook #2", this));availableCooks.add(new Cook("Cook #3", this));ordersToPrepare = new ArrayList<Order>();new Thread(this).start();}public void prepareFood(Order o) {synchronized (ordersToPrepare) {ordersToPrepare.add(o);ordersToPrepare.notify();}}public void foodPrepared(Cook shef, Order o) {synchronized (availableCooks) {availableCooks.add(shef);availableCooks.notify();}resturaunt.foodPrepared(o);}public void run() {System.out.println("Cook manager start working...");while (!knockedOff) {synchronized (ordersToPrepare) {while (ordersToPrepare.size() < 1) {try {ordersToPrepare.wait();} catch (InterruptedException e) {e.printStackTrace();}}System.out.println("OrdersToPrepare: " + ordersToPrepare);Cook shef = null;for (Cook cook : availableCooks) {if (!cook.isCooking()) {cook.prepareFood(ordersToPrepare.remove(0));shef = cook;break;}}synchronized (availableCooks) {availableCooks.remove(shef);}}synchronized (availableCooks) {while (availableCooks.size() < 1) {try {availableCooks.wait();} catch (InterruptedException e) {e.printStackTrace();}}}}System.out.println("Cook manager knocked off");}public void knockOff() {for (Cook c : availableCooks) {c.knockOff();}knockedOff = true;}private class Cook implements Runnable {private String name;private boolean knockedOff;private Order order;private CookManager manager;public Cook(String n, CookManager m) {name = n;manager = m;order = null;new Thread(this).start();}public void prepareFood(Order o) {synchronized (this) {System.out.println(this + "Start Cooking " + o);order = o;notify();}}public void run() {while (!knockedOff) {synchronized (this) {while (order == null) {try {wait();} catch (InterruptedException e) {e.printStackTrace();}}}System.out.println(this + "Cooking " + order);try {Thread.sleep(CookManager.TIME_TO_COOK);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(this + "Food " + order + " is cooked, ready to deliver");final Order o = order;synchronized (this) {order = null;}manager.foodPrepared(this, o);}}public void knockOff() {knockedOff = true;;}public boolean isCooking() {return order != null;}@Overridepublic String toString() {return name + " ";}}
}
WaitorManager也是一样,管理待送的菜和调度Waitor
package com.effectivejava.threading.basics;import java.util.ArrayList;
import java.util.List;public class WaitorManager implements Runnable {public static final int TIME_TO_DELIVER = 50;private boolean knockedOff;private int waitorLimit;private List<Waitor> availableWaitors;private List<Order> ordersToDeliver;public WaitorManager(int wl) {knockedOff = false;waitorLimit = wl;availableWaitors = new ArrayList<Waitor>(waitorLimit);availableWaitors.add(new Waitor("Waitor #1", this));availableWaitors.add(new Waitor("Waitor #2", this));ordersToDeliver = new ArrayList<Order>();new Thread(this).start();}public void deliverFood(Order o) {synchronized (ordersToDeliver) {ordersToDeliver.add(o);ordersToDeliver.notify();}}public void foodDelivered(Waitor w) {synchronized (availableWaitors) {availableWaitors.add(w);availableWaitors.notify();}}public void run() {System.out.println("Waitor manager start working...");while (!knockedOff) {synchronized (ordersToDeliver) {while (ordersToDeliver.size() < 1) {try {ordersToDeliver.wait();} catch (InterruptedException e) {e.printStackTrace();}}System.out.println("ordertodeliver: " + ordersToDeliver);Waitor w = null;for (Waitor waitor : availableWaitors) {if (!waitor.isDelivering()) {waitor.deliverFood(ordersToDeliver.remove(0));w = waitor;break;}}synchronized (availableWaitors) {availableWaitors.remove(w);}}synchronized (availableWaitors) {while (availableWaitors.size() < 1) {try {availableWaitors.wait();} catch (InterruptedException e) {e.printStackTrace();}}}}System.out.println("Waitor manager knocked off");}public void knockOff() {for (Waitor w : availableWaitors) {w.knockOff();}knockedOff = true;}private class Waitor implements Runnable {private String name;private Order order;private boolean knockedOff;private WaitorManager manager;public Waitor(String n, WaitorManager m) {name = n;order = null;manager = m;new Thread(this).start();}public void deliverFood(Order o) {synchronized (this) {System.out.println(this + "Start delivering " + o);order = o;notify();}}public void run() {while (!knockedOff) {synchronized (this) {while (order == null) {try {wait();} catch (InterruptedException e) {e.printStackTrace();}}}System.out.println(this + " delivering " + order);try {Thread.sleep(WaitorManager.TIME_TO_DELIVER);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(this + "Food " + order + " is delivered, food is ready");synchronized (this) {order.ready();order = null;}manager.foodDelivered(this);}}public void knockOff() {knockedOff = true;}public boolean isDelivering() {synchronized (this) {return order != null;}}@Overridepublic String toString() {return name + " ";}}
}
最后是数据类型Order类,仅是一个数据
package com.effectivejava.threading.basics;public class Order {private boolean ready;private String name;public Order(String n) {name = n;ready = false;}public boolean isReady() {return ready;}public void ready() {ready = true;}@Overridepublic String toString() {return name;}
}
总结
这个问题说难不难,但是要想写的正确真不是一件容易的事,也不可能在一二个小时内解决,前前后后花了我近一周的时间才能写到现在的程度,但现在我还不敢保证正确。当然,也许牛人或者高手能很快就解决,所说明我还需要更多的努力。但至少可以证明一点:有关多线程的问题很难编写和调试。对于这个例子来说,虽然预期一和二同时完成,但很难确定它们的顺序,因为线程的运行是不确定的。对于这个例子如果把tolerance改小一个些,或者把TIME_TO_COOK,TIME_TO_DELIVER改大一些,就会有Case失败。拓展
1. N个厨师,M个服务员,基于我的程序来改,一点不难,还是难在测试上面,如何保证它是正确的。2. 服务员还有收拾桌子的任务
3. 厨师做菜的时间不固定,服务员送的时间也不固定,这样才更加真实。
真实的生活是很难模拟的,但是一个套优秀的系统和管理方式确实能大大的提高效率,就好比一些小餐馆一旦人过多了,即使只一会儿,也会让餐馆陷入混乱:菜上的慢,客人等的急,没人收拾桌子,菜做错和送错等;但是对于大餐馆来说却总能应付的来,即使是像婚庆或者酒会。
水平浅,真心希望能有牛人来实现一个版本让我参考。