多线程拼图 [英] 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 : The Dining哲学家的问题:左右手版本

哲学家进餐问题是由 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:吸烟者的问题

这个问题是由 S. S. Patil 在 1971 年提出的.假设一支香烟需要三种成分，烟草、纸和火柴.有三个连锁吸烟者.它们中的每一个都只有一种无限供应的成分.有一个代理可以无限供应所有三种成分.要制作香烟，吸烟者有烟草(分别是纸和火柴)必须有另外两种成分纸和火柴(分别是烟草和火柴，以及烟草和纸).代理人和吸烟者共用一张桌子.代理随机生成两种成分并通知需要这两种成分的吸烟者.一旦从桌子上取走成分，代理就会提供另外两个.另一方面，每个吸烟者都在等待代理的通知.接到通知后，吸烟者拿起配料，抽了支烟，抽了一会，然后回到餐桌等待下一个配料.

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:生产者/消费者(或有界缓冲区)问题

假设我们有一个循环缓冲区，其中有两个指针 in 和 out 来指示下一个可用于存放数据的位置以及包含下一个要检索的数据的位置.见下图.有两组线程，生产者和消费者.每个生产者在 in 位置存入一个数据项并将指针前移，每个消费者在 out 位置检索数据项并将指针前移.

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＜0.n.但是，汽车只有在满载时才能绕轨道行驶.乘坐完后，每位乘客都会在游乐园周围闲逛，然后返回过山车再次乘坐.出于安全考虑，该车只骑了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屋！