在C作业任务中使用线程表示路由表

Question

所以，我的学校给了我这个任务，到目前为止，它让我抓狂。我不知道该怎么开始，我肯定很乐意得到一些帮助。任务已经翻译了，所以我对翻译的结果感到非常抱歉，我警告你们，翻译得很糟糕。

这是我在这项任务中遇到的另一个问题，翻译很糟糕，我没有它的原始来源。

任务：

线程中的路由表

简介

网络计算机（本地或广域）有几个计算机（节点）在不同的位置。

要将信息从一个路口发送到另一个路口，路口并不总是节点线之间的直接链接。在这种情况下，我们将不得不通过Route发送几个节点。这两个节点之间可能根本没有连接，无法发送它们。网络节点可以用邻接矩阵来表示，其中1表示节点和0之间的直接链路没有这种关系。

1 2 35

11 1 0 0 1

21 1 1 0 1

30 1 1 1 0

40 0 1 1 0

51 1 0 0 1

真实的网络节点也可能暂时或最终消失，因此需要不断更新连接表。

在主要练习中，我们假设节点不会消失或失效，哪怕一次。

而在第4节（奖励）中，节点可以更改任务描述系统中的每个节点都将由线程表示。该计划的目的是：从节点和链路的初始网络接收数据，并更新全局路由表。每个线程都需要在他的表的行（和列）上工作，如果它和节点没有直接接触，然后搜索是否存在间接连接，如果发现是通过其他节点的间接连接，则线程将在表中标记此连接。

表格将是一个象征关系重量的数字——如果它不仅仅是在交叉路口之间

如果三个拱门的重量为3，则一个有0个弧线，重量为0，依此类推。例如：1和4之间的关系上表是重量3。第一个线程主要需要做一些事情：

• 吸收用户节点数到02

• 用户通过以下方式选择网络拓扑：id1 id2 id5；id2 id3 id5；id3 id4；示例；1 2 5、2 3 5；3 4标记列表节点的直接邻居的末尾意味着：节点1与0和5相关，节点0也与3和5相关；节点3与4相关。

• 创建初始连接表并显示在屏幕上

• 根据节点数量创建适当数量的线程
• 等待所有线程
• 在所有线程都完成并且将有更多更新之后，程序显示主表
• 以适当的消息"Final Table Network"结束
• 在消除我们构建的所有对象（例如线程属性）后结束程序互斥，互斥属性，条件变量，条件变量属性

每个节点表示线程：

• 寻找一个可能的链接路由（递归）所有与它无关的节点直接地如果找到新联系人，则通过查找最小权重来更新表格
• 为了模拟真实的系统，建议每个线程在搜索前随机休眠一段时间
• 线程应该记住找到最短的路线，并将其打印为最终搜索示例：线程N通过以下方式连接到M：N->node1->node2->..->M
• 如果线程和更新表-在他完成之前也打印他的行表更新了相应的消息：线程更新了第N行-现在的连接为：1 0 2 1 1 4关闭线程N-不更新网络表或无需打印关于更新单个值的消息-只需在完成行时发布即可

Answer 1

这是一个相当大的任务。这里没有人会帮你编写整个代码，但我会给你一些提示。

1. 为每个节点使用pthread_t

2. 使用管道man 2 pipe对连接进行建模。将管道放入矩阵

   int connections[NUMTHREADS][NUMTHREADS][2];
   

   其中，connections[i][j][0]是节点i从j接收的读取端（按列），而connections[i][j][1]是节点j发送到i的写入端（按行）。请注意，-1是一个无效的文件描述符。

3. 让其有效读取端的每个线程select（man 2 select）等待接收数据，然后用TTL广播到与其连接的所有节点（这样就不会得到无限循环）。

4. 让所有节点定期广播某种最短路径同步消息。然后，每个接收器可以不时地调整到每个节点的最短路径。让你的select暂停。

Answer 2

这是一个没有奖金的主要练习的实现，因此节点不会更改。为了简单起见，最大节点数为9。

#include <stdio.h>
#include <string.h>
#include <signal.h>
#include <pthread.h>
// A route is stored in the routing table as an integer number with the nodes
// from start to end represented by the decimal digits from lowest to highest.
int routelg(int rt)
{   // compute the length of a route
    int lg = 0;
    while (rt) ++lg, rt /= 10;
    return lg;
}
void display(int n, sig_atomic_t table[n][n])
{
    int k, l;
    printf(" "); for (k = 0; k++ < n; ) printf(" %d", k); puts("");
    printf(" "); for (k = 0; k++ < n; ) printf("--");     puts("");
    for (                    l = 0; l < n; ++l, puts(""))
    for (printf("%d|", 1+l), k = 0; k < n; ++k)
        printf("%d ", routelg(table[l][k]));
}
int n;
sig_atomic_t (*global_routing_table)[];
#define IN(lo, hi, num) lo <= num && num <= hi
int router(sig_atomic_t table[n][n], int origin, int destin, int visited[n])
{   // looking for a possible link route (recursively)
    int hops = table[origin][destin], hop, hopmin = 999999999, l;
    if (hops) return hops;  // already have the path
    visited[origin] = 1;
    for (l = 0; l < n; ++l)
        if (IN(11, 99, table[origin][l]) && !visited[l])
        {   // directly connected and not already tried
            hop = router(table, l, destin, visited);
            if (hop && hop < hopmin) hopmin = hops = hop*10+1+origin;
        }
    visited[origin] = 0;
    return hops;
}
void *route(void *arg)
{
    int i = (int)arg, k, visited[n], rt;
    sig_atomic_t (*table)[n] = global_routing_table;
    for (k = 0; k < n; ++k)
        if (!table[i][k])   // no route (yet) from here (i) to node k
        {
            memset(visited, 0, sizeof visited);
            rt = table[i][k] = router(table, i, k, visited);
            flockfile(stdout);
            printf("%d %sconnected to %d", 1+i, rt ? "" : "un", 1+k);
            char *del;
            for (del = " by:"; rt; rt /= 10, del = "->")
                printf("%s %d", del, rt%10);
            puts("");
            funlockfile(stdout);
        }
    return NULL;
}
int main()
{
    printf("number of nodes (max 9)? "), scanf("%d", &n);
    printf("topology of the network? ");
    sig_atomic_t table[n][n];
    int i;
    memset(table, 0, sizeof table);
    for (i = 0; i < n; ++i) table[i][i] = 1+i;
    do
    {   int neighbours[n];
        for (i = 0; scanf("%d ", &neighbours[i]) > 0; ++i) ;
        int o = neighbours[0];
        while (--i > 0) table[o-1][neighbours[i]-1] = o+10*neighbours[i],
                        table[neighbours[i]-1][o-1] = neighbours[i]+10*o;
    } while (getchar() == ';');
    puts("initial connectivity table:"), display(n, table);
    pthread_t threads[n];
    global_routing_table = table;
    for (i = 0; i < n; ++i) pthread_create(threads+i, NULL, route, (void *)i);
    for (i = 0; i < n; ++i) pthread_join(threads[i], NULL);
    puts("final table (0 - no route, 1..n - weight+1):"), display(n, table);
}