多线程难题 [英] Multithreading Puzzles

问题描述

我试图提出一些专注于多线程的编程难题.到目前为止，我能够提出的大多数问题都是针对特定领域的.对于尝试学习多线程应用程序核心概念的开发人员，有人会遇到任何体面的编程难题吗?

I'm trying to come up with some programming puzzles focused on multi-threading. Most of the problems I've been able to come up with, so far, have been pretty domain specific. Does anybody have any decent programming puzzles for developers attempting to learn the core concepts of multi-threading applications?

推荐答案

此链接涵盖了许多主题.

There are a number of topics covered at this link.

使用ThreadMentor进行多线程编程:教程

这里有一些直接链接到该链接上列出的问题，以及它们的初始描述.

Here are some direct links to the problems listed at that link, along with their initial descriptions.

ThreadMentor :饮食哲学家的问题
ThreadMentor:就餐哲学家的问题:左左右的版本

饮食哲学家的问题是由狄克斯特拉(E. W. Dijkstra)发明的.想象一下，有五位哲学家一生都在思考和东方生活.饭厅中间是一张圆桌，上面放着五把椅子.桌子上有一盘意大利面.但是，只有五根筷子可用，如下图所示.每个哲学家都在思考.当他饿了时，他坐下来拿起离他最近的两根筷子.如果一个哲学家能拿起两根筷子，他就会吃一会儿.哲学家吃完饭后，放下筷子开始思考.

The dining philosophers problem is invented by E. W. Dijkstra. Imagine that five philosophers who spend their lives just thinking and easting. In the middle of the dining room is a circular table with five chairs. The table has a big plate of spaghetti. However, there are only five chopsticks available, as shown in the following figure. Each philosopher thinks. When he gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he eats for a while. After a philosopher finishes eating, he puts down the chopsticks and starts to think.

ThreadMentor:香烟吸烟者的问题

此问题归因于1971年的S. S. Patil.假设一支香烟需要三种成分，即烟草，纸张和火柴.一共有三个吸烟者.他们每个人只有一种成分可以无限供应.有一个代理商可以无限供应所有三种成分.要制作香烟，吸烟者吸烟(烟叶，纸和火柴)必须具有纸烟和火柴的其他两种成分(烟叶，火柴和火柴，以及烟草和纸).代理人和吸烟者共用一张桌子.代理会随机生成两种成分，并通知需要这两种成分的吸烟者.从餐桌上取下成分后，代理商再提供另外两种.另一方面，每个吸烟者都在等待代理商的通知.收到通知后，吸烟者会拿起食材，抽烟，抽烟一段时间，然后回到餐桌上等待他的下一份食材.

This problem is due to S. S. Patil in 1971. Suppose a cigarette requires three ingredients, tobacco, paper and match. There are three chain smokers. Each of them has only one ingredient with infinite supply. There is an agent who has infinite supply of all three ingredients. To make a cigarette, the smoker has tobacco (resp., paper and match) must have the other two ingredients paper and match (resp., tobacco and match, and tobacco and paper). The agent and smokers share a table. The agent randomly generates two ingredients and notifies the smoker who needs these two ingredients. Once the ingredients are taken from the table, the agent supplies another two. On the other hand, each smoker waits for the agent's notification. Once it is notified, the smoker picks up the ingredients, makes a cigarette, smokes for a while, and goes back to the table waiting for his next ingredients.

ThreadMentor:生产者/消费者(或有界缓冲区)问题

假设我们有一个循环缓冲区，其中有两个指针，分别指向和指向两个指针，以指示下一个可用于存放数据的位置以及包含要检索的下一个数据的位置.请参见下图.有两类线程，生产者和消费者.每个生产者将一个数据项存放到该位置并向后移指针，而每个消费者则将数据项移到该位置并向后移指针.

Suppose we have a circular buffer with two pointers in and out to indicate the next available position for depositing data and the position that contains the next data to be retrieved. See the diagram below. There are two groups of threads, producers and consumers. Each producer deposits a data items into the in position and advances the pointer in, and each consumer retrieves the data item in position out and advances the pointer out.

ThreadMentor:过山车问题

假设有n名乘客和一辆过山车.乘客反复地等待乘坐该汽车，该汽车最多可容纳C位乘客，其中C≤C. .但是，汽车只有在满载时才能绕过赛道.乘车结束后，每个乘客都会在游乐园中徘徊，然后返回过山车进行另一次乘车.出于安全原因，这辆车只能骑T次然后开球.

Suppose there are n passengers and one roller coaster car. The passengers repeatedly wait to ride in the car, which can hold maximum C passengers, where C < n. However, the car can go around the track only when it is full. After finishes a ride, each passenger wanders around the amusement park before returning to the roller coaster for another ride. Due to safety reasons, the car only rides T times and then shot-off.

这还有其他限制:

1. 汽车始终与C位乘客一起乘坐；
2. 在汽车行驶时，没有乘客会跳下汽车；
3. 在汽车行驶时，没有乘客会跳上汽车；
4. 下车之前，没有乘客会要求再次乘车.

ThreadMentor :桥梁问题

对此的描述取决于图像.这是删除了图像引用的修改后的报价.

The description for this one relies on images. Here is a modified quote with image references removed.

考虑一个狭窄的桥梁，该桥梁只能允许三个方向相同的车辆同时穿越.如果桥上有三辆车，那么任何进来的车辆都必须等到桥清理完毕.

Consider a narrow bridge that can only allow three vehicles in the same direction to cross at the same time. If there are three vehicles on the bridge, any incoming vehicle must wait until the bridge is clear.

当车辆驶出桥梁时，我们有两种情况需要考虑.案例1，桥上还有其他车辆；案例2中，驶出的车辆是桥上的最后一辆.在第一种情况下，应允许同一方向的一辆新车继续行驶.

When a vehicle exits the bridge, we have two cases to consider. Case 1, there are other vehicles on the bridge; and Case 2 the exiting vehicle is the last one on bridge. In the first case, one new vehicle in the same direction should be allowed to proceed.

情况2更复杂，有两个子情况.在这种情况下，驶出的车辆是桥上的最后一辆车辆.如果有车辆在相反方向等候，则应允许其中一辆继续行驶.或者，如果没有在相反方向等候的车辆，则让在同一方向等候的车辆继续行驶.

Case 2 is more complicated and has two subcases. In this case, the exiting vehicle is the last vehicle on the bridge. If there are vehicles waiting in the opposite direction, one of them should be allowed to proceed. Or, if there is no vehicle waiting in the opposite direction, then let the waiting vehicle in the same direction to proceed.

这篇关于多线程难题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！