Main Memory

Lại phải vật lộn với một mớ hệ điều hành haizzz.

Như đã biết bộ nhớ là trung tâm trong hoạt động của hệ thống máy tính hiện đại. Bộ nhớ chứa mảng lớn các words hay bytes, mỗi trong số chúng có địa chỉ riêng. CPU lấy các instructions từ bộ nhớ dựa theo giá trị của program counter (pc). Nhiều instructions có thể gây ra việc loading thêm hay lưu trữ thêm đến các địa chỉ bộ nhớ xác định.

Một vòng thực thi lệnh tiêu biểu như sau: thứ nhất, lấy một instruction từ bộ nhớ. instruction này sau đó được decoded và có thể tạo ra các operands được fetch từ bộ nhớ. Sau khi lệnh được thực thi trên các operands, kết quả trả lại được lưu trong bộ nhớ. memory unit được xem như là một stream của các memory addresses, không biết làm thế nào chúng được sinh ra (bởi instruction counter (ic),  bởi indexing, indirection, literal address ...) hay chúng là gì ? (là lệnh hay dữ liệu). Theo đó chúng ra lờ đi việc làm thế nào chương trình sinh ra memory address thay vào đó chúng ta tập trung chú ý vào sequence các memory addresses sinh ra bởi chương trình đang chạy (running program).

1. Basic hardware
main memory và các registers được xây dựng bên trong processor chỉ là những nơi lưu trữ (storage) mà CPU có thể truy cập trực tiếp. Có nhiều machine instructions lấy các memory addresses như là các arguments, nhưng không một machine instructions nào sử dụng disk addresses. Do đó bất cứ lệnh nào được thực thi, hay bất cứ dữ liệu nào được sử dụng bới lệnh phải nằm trong bộ lưu trữ có thể truy cập trực tiếp. Nếu dữ liệu không nằm trong bộ nhớ, nó cần phải được di chuyển vào đó trước khi CPU operate trên chúng.
Registers được xây dựng sẵn trong CPU có thể được truy cập đến trong thời hạn một vòng của CPU clock.
Hầu hết CPU có thể decode các instructions và thực hiện được các operations đơn giản trên register contents ở tộc độ một hay nhiều operations trên clock tick. Điều này lại không đúng đối với bộ nhớ chính. Những gì có thể được truy cập via một giao dịch (transaction ) trên memory bus. hoàn thành một memory access có thể mất nhiều cycles của CPU clock. Trong những trường hợp như vậy processor cần phải stall, bởi vì nó không có dữ liệu yêu cầu để hoàn thành instruction mà nó được excuting. Hoàn cảnh như vậy là không thể chấp nhận đươc bởi vì tần số của memory addresses. Biện pháp khắc phục là thêm vào fast memory giữa CPU và main memory. Một memory buffer được sử dụng để accommodate tốc độ khác nhau, được gọi là cache. Chúng ta không chỉ concern về tốc độ truy cập bộ nhớ vật lý mà chúng ta còn phải đảm bảo correct operation để bảo vệ OS từ các user processes và thêm vào đó bảo vệ các user processes từ cái khác. Sự bảo vệ này phải được cung cấp từ hardware. Nó có thể được implemented theo một vài cách. Chúng ta outline một trường hợp có thể.

Thứ nhất chúng ta phải đảm bảo rằng mỗi process có một không gian bộ nhớ riêng biệt. Để làm được việc đó chúng ta cần phải xác định được cái range của legal addresses mà process có thể truy cập đến và phải đảm bảo rằng process chỉ có thể truy cập duy nhất đến những legal addresses đó. Chung ta có thể cung cấp sự bảo vệ đó bằng cách sử dụng 2 thanh ghi : limit và base. Thanh ghi base chứa địa chỉ hợp lệ nhỏ nhất mà process có thể truy nhập đến, thanh ghi limit chứa kích thước của range.

Việc bảo vệ không gian bộ nhớ được hoàn thành bởi có một CPU hardware thực hiện nhiệm vụ so sánh mọi địa chỉ sinh ra tại user mode với các registers. Bất cứ một nỗ lực nhằm vào việc truy nhập đến OS memory hoặc memory của user khác bởi một chương trình thực thi trong user mode sẽ rơi vào trap của OS, những gì "chăm sóc" sư nỗ lực này như là một fatal error. Cơ chế này nhằm ngăn một user program (cố ý hay tai nạn) thực hiện việc modifying code hay cấu trúc dữ liệu của OS hay của user khác.

Các thanh ghi limit và base chỉ có thể được loaded bởi OS những gì sử dụng một special priviled instruction. Bởi vì priviled instructions chỉ có thể được thực thi tại kernel mode, và bởi vì chỉ có OS thực thi trong kernel mode, chỉ có OS mới có thể load các thanh ghi limit và base. Cơ chế này giúp cho OS có thể thay đổi được các thanh ghi nhưng ngăn không cho user thay đổi nội dung thanh ghi.

OS thực thi trong kernel mode, nó được cấp các quyền truy nhập không giới hạn đến cả OS memory và cả user memory. Sự cung cấp này cho phép OS load các chương trình người dùng vào bộ nhớ của người dùng, để dump out nhiều chương trình trong trường hợp nó có lỗi, để truy cập và modify các parameters của các system calls và so on.

2. Address Binding

Thông thường, một chương trình đặt trong đĩa như là một binary excutable file. Để được thực thi, chương trình phải được mang vào trong bộ nhớ và đặt bên trong một process nào đó. Phụ thuộc vào cơ chế quản lý bộ nhớ ta sử dụng, process có thể di chuyển giữa đĩa và bộ nhớ trong suốt quá trình thực thi của nó. Các processes được đặt trên đĩa chờ đợi đến lượt mình thực thi có thể form thành input queue.

Thủ tục thông thường là ta lựa chọn một process trong input queue vào load process đó vào trong bộ nhớ. Như mỗi lần process được thực thi nó tiến hành truy nhập đến các instructions và data từ bộ nhớ. Cuối cùng khi process kết thúc thì không gian bộ nhớ của nó được khai báo là available.

Hầu hết OS cho phép một user process reside bên trong bất cứ phần nào của physical memory. Do đó, mặc dù không gian địa chỉ của máy tính bắt đầu là 00000, địa chỉ đầu tiên của user process không cần là 00000. Cách tiếp cận này ảnh hưởng đến các địa chỉ mà user program sử dụng. Trong hầu hết trường hợp user program có thể trải qua một vài bước, một số bước trong đó là optional trước khi thực thi. Các địa chỉ có thể được biểu diễn theo những cách khác nhau trong các bước. Addresses trong source program là biểu tượng (ví dụ như count). compiler sẽ thực hiện bind các symbolic addresses đến các relocatable addresses (ví dụ như: "14 bytes bắt đầu từ mở đầu của module này" ). editor hoặc loader bind các relocatable addresses đến absolute addresses (ví dụ như 74014). Mỗi binding là việc maping từ một không gian địa chỉ này đến một không gian địa chỉ khác.

Theo cách cổ điển, việc binding của instructions và data đến memory addresses có thể hoàn thành tại bất cứ step nào trong dây chuyền sau:
* compile time : nếu bạn biết rằng tại compile time nơi mà process sẽ được reside bên trong bộ nhớ khi đó absolute code được sinh ra. Cho ví dụ, nếu bạn biết rằng user process sẽ được reside trong memory bắt đầu từ location R, khi đó generated compiler code sẽ bắt đầu ở vị trí đó và mở rộng lên từ đó. Nếu sau đó starting location thay đổi, sau đó sẽ cần phải recompile this code. MSDOS .COM format programs được bind tại compile time.

* loading time : Nếu không biết được rằng tại compile time nơi process sẽ reside trong bộ nhớ, khi đó compiler sẽ sinh ra relocatable code. Trong trường hợp đó final binding sẽ được delayed cho đến loading time. Nếu starting address thay đổi chúng ta chỉ cần reload user code để kết hợp giá trị vừa thay đổi.

* excution time : nếu một process được di chuyển trong suốt quá trình thực thi của nó từ một memory segment sang memory segment khác, khi đó binding sẽ được delayed cho đến run time. Special hardware sẽ phải có sẵn cho cơ chế này làm việc. Hầu hết HĐH hiện nay sử dụng method này.

Một phần quan trọng là xét xem có bao nhiêu binding khác nhau được implement hiệu quả trong hệ thống máy tính và thảo luận về hardware support thích hợp.

Ta có thể mô tả multi step của processing một user program:
Ban đầu một source program trong giai đoạn compile time sẽ đi qua một bộ compiler or assembler kết quả sẽ sinh ra object module.
Tại giai đoạn load time object module sinh ra trong giai đoạn compile time sẽ kết hợp với các object module khác nhờ vào linkage editor kết quả sinh ra sẽ là load module. Cũng trong giai đoạn load time này còn có sự xuất hiện của loader với nhiệm vụ kết hợp load module và system library.
Trong giai đoạn execution time kết của sự kết hợp phía trên sẽ được kết hợp với các thư viện liên kết động và kết quả sẽ là các in-memory binary memory image.

3. Không gian địa chỉ ảo và không gian địa chỉ vật lý

Một địa chỉ được sinh bởi CPU thường được nhắc tới như là một logical address, trái lại một địa chỉ được nhìn như là một memory unit , đó là một thứ được load vào trong memory-address register của memory, đó thường được nhắc tới như physical address. Các phương thức address-bindings tại compile time và load time sinh ra các địa chỉ physical và logical giống hệt nhau, tuy nhiên execution-time address-binding scheme đưa ra kết quả các địa chỉ logical và physical khác nhau. Trong trường hợp đó chúng ta thường refer logical address như là virtual address. Tập hợp của tất cả logical addresses sinh ra bởi chương trình được gọi là logical address space, tập hợp tất cả các physical addresses tương ứng với các logical addresses được gọi là physical address space. Do đó trong executable-time address binding scheme, không gian địa chỉ logical và physical là khác nhau.

run-time mapping từ virtual đến physcal addresses dưới sự hỗ trợ của một thiết bị phần cứng đó là memory-management unit (MMU). Chúng ta có thể sử dụng các methods khác để hoàn thành việc mapping này. Chúng ta sẽ thực hiện mapping với một MMU scheme đơn giản đó là một sự tổng quát của base-register scheme. base register bây giờ được gọi là relocation register. giá trị của relocation register sẽ được cộng vào mọi địa chỉ sinh ra bởi process tại thời điểm địa chỉ được gửi tới memory. MS DOS chạy trên họ processor 8086 sử dụng 4 relocation registers khi loading và running processes.

User program không bao giờ thấy được real physical addresses. user program giải quyết với logical addresses. memory-mapping hardware converts logical addresses vào trong physical addresses.

Chúng ta có 2 kiểu địa chỉ : logical address (trong range từ 0 đến max) và physcal addresses (trong range từ R + 0 đến R + max, trong đó R là base value). users chỉ sinh ra địa chỉ logical và nghĩ rằng process run trong locations 0 đến max. Tuy nhiên logical addresses phải được map đến physical addresses trước khi chúng được sử dụng.

4. Dynamic Loading
Toàn bộ chương trình và tất cả dữ liệu của process phải nằm trong physical memory để process được thực thi. Do đó kích thước của process bị giới hạn bởi kích thước của physical memory. Để sử dụng tốt hơn memory-space, chúng ta có thể sử dụng dynamic loading, với dynamic loading một routine sẽ không được load cho đến khi nó được gọi. Tất cả các routines được giữ trên disk trong một relocatable load format. main program được load vào trong bộ nhớ và được thực thi. Khi một routine cần gọi một routine khác, calling routine đầu tiên kiểm tra có hay không routine khác đã được loaded. Nếu chưa có thì relocatable link loader được gọi để load routine mong muốn vào trong memory và update program's address tables để phản ánh sự thay đổi đó. Sau đó control được chuyển đên routine mới được loaded.
Lợi thế của dynamic routine là một unused routine sẽ không bao giờ được loaded. Phương thức này hữu dụng khi một lượng lớn code cần được handle không thường xuyên, ví dụ như error routines. Trong trường hợp đó mặc dù chương trình là lớn nhưng phần cần được handle là nhỏ.

Dynamic loading không yêu cầu một special support từ OS. Nó thuộc về trách nhiệm của user để thiết kế chương trình của họ để tạo lợi thế với phương thức này. OS có thể giúp programers qua việc cung cấp library routines để implement dynamic loading.

5. Dynamic linking và Shared libraries
Một vài OS chỉ support static linking, nơi những system language libraries được treated giống như bất cứ object module khác và được combined bởi loader vào trong binary program image. Dynamic linking ngược lại, tương tự với dynamic loading. Ở đây, mặc dù, linking, hơn loading, được trì hoãn cho tới excution time. Đặc tính này được sử dụng với system libraries, như là language subroutine libraries. Nếu không có facility đó, mỗi chương trình trên hệ thống phải include một bản sao language library của nó. với requirement như vậy sẽ lãng phí disk space và main memory.

Với dynamic linking, một stub đượ included trong image cho mỗi library routine tham chiếu tới. Stub là một piece of code nó chỉ ra làm thế nào để locate một memory-resident library thích hợp hoặc làm thế nào để load memory nếu routine không present. Khi stub excuted, nó kiểm tra xem có routine cần thiết đã có sẵn trong bộ nhớ hay chưa. Nếu chưa có, chương trình sẽ load routine vào trong memory. Hay một cách khác, Stub sẽ thay thế chính nó bằng địa chỉ của routine và executes routine. Do đó, next time particular code segment được reached, library routine được thực thi trực tiếp, không phải gánh chịu thêm chi phí cho dynamic linking. Dưới cơ chế này, tất cả các processes sử dụng language library chỉ thực thi duy nhất một bản sao của library code.

Tính năng này có thể mở rộng sang library updates (ví dụ như bug fixes ). Một library có thể được thay thế bởi new version, và tất cả programs tham chiếu đến thư viện đó sẽ tự động sử dụng new version. Nếu không có dynamic linking, tất cả các chương trình như trên sẽ phải được relinked để đạt được truy cập đến new library. Vì thế chương trình sẽ không vô tình execute các thư viện mới, không tương thích, các thông tin về version có thể đươc included trong cả chương trình và thư viện. Nhiều hơn 1 version của library có thể được loaded vào trong memory, và các chương trình sử dụng thông tin về version để quyết định xem bản sao nào của library được sử dụng. Versions với những sự thay đổi nhỏ sẽ giữ nguyên version number, trái lại versions với những sự thay đổi quan trọng sẽ tăng con số này. Do đó, chỉ các chương trình được biên dịch với new library version sẽ bị ảnh hưởng bởi bất cứ sự thay đổi không tương thích kết hợp trong nó. Các chương trình cũ được linked trước khi new library được cài đặt sẽ tiếp tục sử dụng older library. Hệ thống đó được biết đến như shared libraries.

Không giống như dynamic loading, dynamic linking yêu cầu sự trợ giúp từ OS. Nếu các processes trong memory được bảo vệ tránh khỏi những processes khác, khi đó OS chỉ là một thực thể để kiểm tra xem có hay không một needed routine nằm trong memory space của process khác hay là có thể cho phép nhiều process truy nhập đến cùng memory addresses.

6. SWAPPING
Một process phải được nằm trong memory để excuted. Tuy nhiên, một process có thể được swapped tạm thời ra ngoài memory đên một backing store và sau đó được đưa trở về cho continued excution. Cho ví dụ, trong một môi trường mutiprogramming với round-robin CPU scheduling algorithm. khi một quantum hết hạn, memory manager sẽ bắt đầu swap out process vừa kết thức, và swap một process khác vào trong memory space đã được giải phóng. Cũng trong lúc này, CPU sẽ scheduler sẽ allocate một time slice cho một số process khác trong bộ nhớ. khi mỗi process kết thúc quantum của nó, nó được swapped với process khác. CPU có thể swap processes đủ nhanh để một vài processes sẽ nằm trong bộ nhớ, ready to execute, khi CPU scheduler muốn reschedule CPU. Thêm vào đó, quantum phải đủ rộng để cho phép một số lượng tính toán hợp lý được hoàn thành giữa swaps.

Một biến đổi của chính sách swapping này được sử dụng cho priority-based scheduling algorithms. Nếu một process có độ ưu tiên cao hơn đến và wants service, memory manager có thể swap out process có độ ưu tiên nhỏ và sao đó load và thực thi process có độ ưu tiên lớn hơn. Khi hoàn thành xong process có độ ưu tiên lớn hơn, process có độ ưu tiên thấp hơn có thể  được swap trở lại để thực thi tiếp. Biến thể này của swapping thỉnh thoảng còn được gọi là roll out, roll in.

Thông thường, một process được swap out sẽ được swapped back lại trong cùng memory space nó chiếm lúc trước khi bị swap out. Sự hạn chế này được chi phối bởi phương thức address binding. Nếu binding kết thúc tại assembly hay là load time, sau đó process không thể dễ dàng đến location khác. Nếu execution binding được sử dụng, process có thể được swap vào bên trong memory space khác, bởi vì physical address được tính toán trong suốt execution time.

Swapping yêu cầu một backing store. backing store phổ biến có thể là một fast disk. Nó phải đủ lớn để chứa các bản sao của tất cả memory images cho tất cả users, và nó phải cung cấp truy nhập trực tiếp đến các memory images. Hệ thông duy trì một ready queue bao gồm tất cả processes sở hữu memory images lưu trên backing store hoặc trong memory và ready to run. Bất cứ khi nào CPU scheduler quyết định thực thi process, nó gọi một dispatcher. dispatcher sẽ kiểm tra xem có hay không next process trong queue nằm trong memory. Nếu không có, và nếu không có free memory region, dispatcher swap out process hiện hành trong memory và swap in process mong muốn. Nó sau đó reload registers và chuyển điều khiển đến selected process.

context switch time trong hệ thống swapping là khá cao, để có thể tính được context switch time, ta giả sử user process có kích thước là 100 MB và backing store là một standard hard disk với transfer rate là 50MB/s. Tốc độ thực để transfer 100MB-process đến main memory hay lấy từ memory ra là
                               100MB/50MB per second  =  2 seconds.

Giả sử độ trễ trung bình là 8 miliseconds và swap time là 2008 miliseconds. Bởi vì chúng ta vừa phải swap in và swap out thế nên tổng thời gian swap là 4016 miliseconds.

Chú ý rằng phần chính của swap time là transfer time. Tổng thời gian transfer tỷ lệ trực tiếp với lượng memory swapped. Nếu chúng ta có một computer system với 4G main memory và OS chiếm 1G, kích thước tối đa của user process là 3G. Tuy nhiên, nhiều user processes có thể nhỏ hơn so với mức này