計算機已知一個地址，得到這個地址指向的內容，時間是常數級的嗎？如何實現的？

01-27

最近看計算機系統相關書籍產生的疑惑，相關書籍到了地址這方面就結束介紹了，並沒有說出一個地址怎麼就到了所指的內容
-----------------------------------------分割----------------
之前有一些沒表示清楚我看的是csapp虛擬存儲器這一節如果是說地址是一個虛擬地址，然後通過頁表 tlb等之類的轉化成物理地址了，這時候他要去緩存中找，通過cache offset ，cache index ，cache flag (假設他在一級緩存中)那麼這個查找是線性的還是常數的？這是我的本意

你需要讀《數字電路》接著讀《計算機組成原理》，就懂得如何不計成本的做一根內存了，你也就明白其中的道理了。接下來你可能想去看intel的CPU是如何做內存分頁的，這個在他們的文檔裡面有說。通常來講，只要不涉及到放在機械硬碟上的虛擬內存的話，那可以認為是常數級的。

如果你要強行從漸進角度分析的話。

假設流程是這樣：從寄存器里有一個數值，根據這個地址找內存要數值，需要通過寄存器的多路選擇器送上地址匯流排，到內存的解碼器再拿到數據丟上數據匯流排，再通過解碼選擇目標寄存器，鎖存到寄存器里。

寄存器和內存都需要定址。按課本上教的那種解碼器和多路選擇器實現，如果有n個寄存器，m大小的內存，這個過程電路需要的時間複雜度是O(log(log(n))+log(log(m)))。

有不對請指教。

簡單說。

一個內存單位是水庫。內存地址是閘。CPU打開對應閘，在下游等電子流過來就行了。

從虛擬地址通過TLB或者多級頁表算出物理地址，然後通過cpu內的內存控制器發出讀取信號，並把地址放到地址匯流排上(還涉及多通道，numa)，然後根據物理內存的編址方式發送片選信號到特定的內存條，選擇特定的rank（一個rank提供了數據匯流排的位寬的數據，不同通道的不同rank可以被並行載入）。

不是。

因為地址指向的不一定是內存，還有可能是外設。

論選通的重要性

對NUMA(Non-uniform memory access)系統來說，access to local memory 要快一些，祥見：

Non-uniform memory access

其他的參見@vczh 回答。

內存地址的查找其實就是一個二進位解碼器。考慮門電路的延遲，其實應該是O(lg n)的。不過反正你的內存地址不超過64/128位，可以看作常數。

補充：一級cache是全相連的，線性時間查找。所以都非常小。

首先有 Cache 的問題，如果 miss 那麼就通過地址線和數據線去讀，簡單的理解 DRAM 是一個靠行列信息選擇數據地址、靠讀寫控制信號來選擇行為（讀/寫）的矩陣，所以由於CPU頻率和內存頻率高，這個時間很短；它是由硬體決定的，可以看成常數；當然這是相對的，對於 SRAM 它已經很慢了。而且演算法的時間複雜度你總要有個輸入的量級，內存每次獲取的數據大小本身就是有限的，也不可能不是常數級啊，L123 和寄存器也是常數級呢。。

沒記錯的話，應該是cpu通過地址匯流排向內存模塊送地址，鎖存，下一個周期內存模塊將數據送到數據匯流排。時間可以認為是固定的

計算機指向的地址通常是內存，讀寫內存都需要時間，DDR3 1600的內存每秒可以讀1600M次，那你算一下就知道讀一次內存需要多少時間了。