2 
typedef struct _readyQ {
    pcb_t *pcb;
    struct _readyQ  *next;
} readyQ;

static readyQ *ready_queue_head = NULL, *ready_queue_tail = NULL;
static void submit_ready_request(pcb_t *pcb);

static void submit_ready_request(pcb_t *pcb)
{
    readyQ *r;
    /* Build I/O Request */
    r = malloc(sizeof(readyQ));
    assert(r != NULL);
    r->pcb = pcb;
    r->next = NULL;

    pthread_mutex_lock(&readyQ_mutex);
    /* Add request to head of queue */
    if (ready_queue_tail != NULL)
    {
        ready_queue_tail->next = r;
        ready_queue_tail = r;
    }
    else
    {
        ready_queue_head = r;
        ready_queue_tail = r;
    }
    pthread_mutex_unlock(&readyQ_mutex);
}

最初头/尾都是NULL。所以，当我第一次通过 submit_ready_request 添加时，我会去其他部分

ready_queue_head = r;
ready_queue_tail = r;

都指向同一个 readyQ r。

现在，当我添加另一个时，它将转到

ready_queue_tail->next = r;
ready_queue_tail = r;

我想知道在这种情况下， ready_queue_head->next执行上面的代码后会指向 r 吗？

因为我试图通过这个删除，但它不起作用

readyQ *r;
r = malloc(sizeof(readyQ));
if (ready_queue_head != NULL) {   //not empty so remove
       r = ready_queue_head;  
       if(ready_queue_head->next != NULL){   
          ready_queue_head = ready_queue_head->next; 
        } else {    //only one in the queue
          ready_queue_head = NULL;
          ready_queue_tail = NULL;
       }
}
4

4 回答 4

2

我怀疑当您说它不起作用时，您的意思r是在“删除”两个节点后它不为空。如果是这样，则错误是删除代码中的此分配：

r = malloc(sizeof(readyQ));

如果列表为空，那将是结果（可能不需要）。如果列表不为空，则该内存会立即泄漏。它可能应该只是：

r = NULL;
于 2013-04-01T23:19:50.630 回答
1

我没有看到任何错误（除了虚假的 malloc），因此编译了您的代码并且没有收到任何段错误或其他错误。我唯一改变的是删除互斥锁。可能故障出在互斥体中？您的出队代码是否受互斥锁保护？

同样在回答您关于 ready_queue_head->next 的问题时，是的，它会按您的预期工作。实际上，您可以将出队代码简化为：

r = ready_queue_head;  
ready_queue_head = ready_queue_head->next; 
if (ready_queue_head == NULL){   
    ready_queue_tail = NULL;
}
于 2013-04-01T23:49:48.983 回答
1

首先，malloc()弹出操作不需要。其次，你的 push 和 pop 都过于迂腐。非常仔细地盯着这个推送和弹出逻辑，在你知道它是如何工作的之前不要合并它。您需要考虑两者如何协同工作才能真正掌握简单性。

首先是推送逻辑。以下假设r是新分配的节点，其 next 指针为 NULL：

if (ready_queue_head != NULL)
    ready_queue_tail->next = r;
else
    ready_queue_head = r;
ready_queue_tail = r;

同样，流行逻辑

r = ready_queue_head;
if (r != NULL) 
   ready_queue_head = r->next

在您的脑海中考虑一些测试用例。

推送逻辑

  • 当你在一个空列表中插入一个新节点时会发生什么？由于列表为空，因此头指针将​​为 NULL，因此头指针和尾指针最终都将引用新节点。
  • 插入一个包含一个元素的列表怎么样？由于头指针非空，所以尾指针也必须有效，所以将其next指针设置为新节点，然后将尾指针指向新节点。
  • 如果在插入之前列表中有多个节点，这种情况会改变吗？一点也不。

流行逻辑

  • 当您从空队列请求弹出时会发生什么？由于头指针在空队列上为 NULL，因此返回值r也将为 NULL。
  • 当您从单元素队列请求弹出时会发生什么？头指针引用单个元素，因此r将正确设置。因为r是非空的，所以头指针前进到它的next指针，这将是空的。列表现在为空（head 为 NULL）并且返回节点指针已设置。
  • 一个包含多个节点的列表呢？单节点弹出中的所有内容都适用，但头指针在退出时不会为 NULL，因此列表仍然不是空的（但比以前短了一个元素。同样，返回节点指针r已正确设置。

无论如何，我希望它有所帮助。很难理解尾指针在这一切中的参与程度有多么小，但在你想了一会儿之后就不知道了。作为奖励，这是明显复杂的 is-empty 逻辑。

return (ready_queue_head != NULL);
于 2013-04-02T00:42:39.040 回答
-1 
r = malloc(sizeof(readyQ));

上面的语句不会为结构分配内存。相反，它将为指向结构的指针分配内存。

于 2013-04-01T23:23:51.597 回答