双向链表创建期间的上下文切换 [英] context switch during doubly linked list creation

问题描述

莫里斯·巴赫 (Maurice Bach) 的《Unix 操作系统的设计》中有一个例子这提到了双向链表如何可能由于以下原因被破坏创建期间的上下文切换.(他继续说，通过在代码的关键区域提高处理器级别可以防止这种情况发生，但我无法理解他试图首先显示问题的推理)他包含的示例代码如下如下:

There's an example in Maurice Bach's The Design of the Unix Operating System that mentions how it's possible for a doubly linked list to be destroyed due to a context switch during its creation. (He goes on to say that this is prevented by raising the processor level during such critical regions of code, but I'm having trouble understanding his reasoning that tries to show the problem in the first place) The sample code that he includes is as follows:

struct queue {

} *bp, *bp1;
bp1 -> forp = bp -> forp;
bp1 -> backp = bp;
bp -> forp = bp1;
/* consider possible context switch here */
bp1 -> forp -> backp = bp1;

他写的图表最初显示:

              |     |
              | bp1 |

->    |    |    ->         |    |
<-    | bp |    <-         |    |

然后，显示最终状态:

->  |    |  ->  |     |   -> |    |
<-  | bp |  <-  | bp1 |      |    |
       ^
                               /
         ----------------------- 

我正在尝试遍历逻辑，但我不知道为什么代码会导致到一个断开的双向链表，如图所示.有人可以解释发生了什么在上下文切换期间导致此问题?

I'm trying to walk through the logic, but i can't tell why the code would lead to a broken doubly linked list as shown. Can someone explain what's occuring during the context switch to cause this problem?

(p.s. 会被标记为双向链表，但没有标记创建权限)

(p.s. would have tagged as doubly-linked-list, but no tag creation permissions)

推荐答案

我没有仔细阅读的错误 - Maurice 在图表之前的页面中说如果另一个进程操作指针，上下文切换将如何破坏代码"在原始进程再次运行之前在链表上."我很困惑，因为我试图从图表和代码中获取足够的信息，这两者都没有提到被切换到的进程将在内存中处理相同的数据结构的事实(尽管存在上下文切换..仍然不是一个 100% 清晰/有动机的例子恕我直言).无论哪种方式，当我将上下文从读取一页切换到下一页时，显然我自己的内核有一些数据损坏..

My mistake in not reading carefully enough - Maurice says in the page before the diagrams how the context switch would break the code IF another process "were to manipulate the pointers on the linked list before the original process ran again." I was confused because I was trying to get enough information from just the diagram and the code, neither of which mentioned the fact that the process being switched to would be handling the same data structure in memory (despite there having been a context switch.. still not a 100% clear/motivated example imho). Either way, apparently my own kernel had a bit of data corruption when i made the context switch from reading one page to the next..

这篇关于双向链表创建期间的上下文切换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！