Хуудаслалт

Компьютерийн үйлдлийн системд хуудаслалт **Paging** гэдэг бол  санах ойн зохицуулалтын нэгэн арга бөгөөд ямар ч компьютер нь хоёр дах санах ойдоо өгөгдлийг хадгалж болох ба түүнчлэн үндсэн санах ойдоо хэрэглэхээр өгөгдлийг буцааж хэрэглэх арга юм.

Хуудаслалтын аргад үйлдлийн систем нь хуудас (page) гэж нэрлэгдэх ижил хэмжээтэй блокуудаас өгөгдлөө буцааж олгодог. Хуудаслалтын  давуу талууд нь санах ойн сементчиллээс илүү нь фикик хаягийн процессийн орон зайг  зэрэгцээ бус(noncontiguous) гэж зөвшөөрдөг. Хуудаслалтынг хэрэглэхээс өмнө систем нь бүхий л прорамуудыг хадгалахын тулд зэрэгцээ байлгахаар тохируулдаг байсан, энэ нь олон төрлийн хадгалалт болон хэсэгчллийн асуудлаас болон үүсдэг байсан. Хуудаслалт гэдэг бол үйлдлийн систем дэх виртуаль санах ойн хамгийн чухал хэсэг юм.

## Тойм
Хуудаслалтын үндсэн  функц нь гүйцэтгэгдсэний дараа  програм хуудасанд хандахыг оролдоход физик санах ойд хаяглагдаагүй бол үүнийг хуудаслалтын алдаа гэдэг. Үүнийг үйлдлийн систем нь хянаж байдаг.Иймээс үйлдлийн систем идгээр таван асуудлыг хянаж байдаг.
# Determine the location of the data in auxiliary storage. 
# Obtain an empty page frame in RAM to use as a container for the data.
# Load the requested data into the available page frame.
# Update the page table to show the new data.
# Return control to the program
RAM-д бүх өгөгдлийг хадгалах зай байхгүй болтол нь хадгалах хэрэгтэй байдаг, хоосон хуудасны хүрээний процесс нь RAM-наас өөр нэг хуудсыг устгахыг хамруулдаггүй. Хэрэв бүх хуудсын хүрээнүүд нь  хоосон биш байвал, өгөдлийн багтаамж нь хуудасын хүрээг хоосон хуудасын хүрээ үүсгэж өгөхийг шаарддаг. Хэрэв өгөгдөл нь хуудсын хүрээнд орсон бол энэ нь RAM-д уншигдаж эхлэхээс эхлээд солигддог,түүнчлэн өөрийн хоёр дах санах ой дээрх байрлалдаа бичигдсэн байх ёстой.

### Үндсэн арга
Үндсэн аргууд нь физик санах ойг байнгын-хэмжээтэй блок хүрээ(frame),логик санах ойг ижил-хэмжээтэй блокуудад хувааж хуудасуудыг бий болгоно.
Процесс ажиллаж эхлэхэд хуудасууд нь аль нэг хоосон санах ойн хүрээнд  ачаалагддаг. Backing store нь санах ойн хүрээтэй ижил хэмжээтэй байнгын-хэмжээтэй блок болгон хуваагддаг. Бүх хаяг нь ТПБ-с тавигддаг бөгөөд 2 хэсэгт хуваагддаг, хуудасны тоо,хуудасны салаалт.
Хуудасны тоо нь хуудсын хуснэгтийн индэкс болон хэрэглэгддэг. Хуудсын хүснэгт нь физик санах ой дах хуудас болгоны үндсэн хаягуудыг агуулдаг. Хуудсын хэмжээ нь техник хангамжаар тодорхойлогддог. Хуудсын хэмжээнд нь хоёрын чадлаар 512 байт-с 16 Мбайт-р хуудас болгонд байралдаг. Чадлын 2 нь хуудсын хэмжээг өөрчлөн логик хачг болгодог. Логик хаяг нь хуудсын тоо,хуудсын салаалтанд хурдан хувирдаг.
Логик хаягийн хэмжээ нь 2(m) зэрэгт байдаг бол хуудсын хэмжээ нь 2(n)байна. Хаягийн ахлах битүүд нь хуудсын тоо харин бага битүүд нь хуудсын салаалт болно. Түүнчлэн энэ нь зөвхөн програмаар зохицуулагдахгүй бөгөөд үүнийг дэмжиж ажиллах техникийн төрлүүд байна.

### Техник хангамжийн дэмжлэг 
* Техник хангамжууд нь хуудаслалтыг(paging) дэмждэг.Бүхий л хаяг төв процессороор(CPU) боловсруулагдан 2 хэсэгт хуваагддаг. Үүнд хуудасны дугаар(page number) болон хуудасны эхлэл(page offset) орно. Хуудасны дугаар нь хуудасны хүснэгтэд(page table) индекс хийхэд хэрэглэгддэг. Хуудасны хүснэгт нь шуурхай санах ойд байршиж байгаа хуудас бүрийн хаягийг багтаадаг. Энэхүү хаягууд нь хуудасны эхлэлтэй нэгдэж шуурхай санах ойн хаягийг тогтоон санах ой руу илгээдэг.

Хуудасны хэмжээ нь техник хангамжаар тогтоогддог ба ерөнхийдөө 2 хүчин зүйлтэй. 512 байт болон 16MB-н хооронд өөрчлөгддөг мөн компьютерийн архитектураас хамаардаг. Эдгээр 2 хүчин зүйл зүйлээс хуудасны хэмжээ нь логик хаягийг хөрвүүлэн хуудасны дугаарлуу явуулдаг ба хуудасны дугаар нь индекс хэлбэрээр хуудасны хүснэгрүү мөн хуудасны эхлэл нь үүнийг хуудасанд байрлуулдаг.

Энэ  дэмжлэг нь үйлдлийн системийн хуудсын хүснэгтийг хадгалах арга юм. Ихэнх хуудсын хүснэгтүүд нь нэг нэг процессуудаас тогтоно. Түүнчлэн заагч нь хуудсын хүснэгтийн бүртгүүрийн утга болон хадгалагдана. Диспетчер нь  процессийг ажиллуулж эхлэхэд хэрэлэгчийн бүртгүүр лүү хандан хуудсын хүснэгтийн байрлаж байгаа техник хангамжийг заадаг.

Хуудсын хүснэгт нь олон аргаар биелж болно, үүний нэг нь бүртгүүр ашиглан. Энэ бүртүүр нь маш өндөр хурдны логикоор хийгддэг,ТПБ-н диспетчер нь энэ бүртүүрийн ачааллана.Түүнчлэн хуудсын хүснэгт нь үндсэн санах ой болон хуудсын хүснэгтийн үндсэн бүртгүүрт байралдаг. Энэ арга нь бүртгүүр бүрийг  нэг нэгээр ашигладаг учраас удаан байдаг. Үүнийг шийдэх хамгийн энгийн хялбар арга бол TLB(translation look-aside buffer). TLB нь маш хурдтай ажилладаг санах ой юм. TLB хандахад хоёр хандалттай: түлхүүр болон утга. Түүнчлэн TLB-Д хандахад хурдтай байдаг гэвч TLB-д хандах боломж нь маш бага байдаг ихэнх 64-1024-н хооронд байдаг.   
TLB хуудсын хүснэгтэд хэд хэд аргаар хэрэглэгдэж болно. Логик хаяг ТПБ-с тавигдахад хуудсын тоо нь TLB-д дүрслэгдэнэ. Хэрэв хуудсын тоо олдвол хүрээний тоо хурдан тавигдаж санах ой руу хандахад хэрэглэгдэнэ. Хэрвээ TLB-д хуудсын тоо орож ирэхгүй бол санах ойн тулгуур хийгдсэн байх ёстой. Хэрэв TLB-д хандалт нь дууссан бол үйлдлийн систем нь шинэ зай гаргахыг эрмэлзэнэ.

## Prepaging 
Бидний хуудаслалтын системд зориулан гаргадаг олон шийдвэрүүдийн ихэнх нь шинэчлэгдсэн алгоритм болон хуваарьлалтын бодлогод тулгуурлан хийгддэг ба эдгээр олон төрлийн шийдлүүдийн нэг нь хуудсыг урьдчилан дугаарлах буюу prepaging юм.

Demand paging буюу хэрэгцээт хуудаслалтыг хийхэд нөлөөлөх нэг гол шинж чанар нь процесс эхлэх үед үүсэх хэт олон хуудасны алдаа юм. Энэхүү асуудал нь санах ой руу өгөгдлийн анхны байрлалыг хийх гэж оролдсон оролдлогоос үүсдэг боловч бусад үед ч мөн адил ижил тохиолдолд хүрэх боломжтой. Жишээлбэл, түр цуцлагдсан процесс дахин эхлэхэд бүх хуудсууд  нэг дискэн дээр байрлах бөгөөд тэд бүгд хуудасны алдаагаараа дамжуулан системд нэвтрэх ёстой. Prepaging буюу урьдчилан хуудаслалт нь энэхүү дээд хэмжээнд хийгдэх энхдагч хуудаслалтаас зайлсхийх гэсэн нэгэн оролдлого юм. Энэхүү стратеги нь бүх хэрэгцээт хуудсуудыг нэгэн зэрэг санах ойд оруулж ирэх явдал юм.

### Prepaging хэрхэн ажиллах вэ? 
Solaris тэргүүтэй зарим үйлдлийн системүүд хуудсын фреймүүдийг жижиг хэмжээний файлд урьдчилан хуудасладаг. Ажиллах горимын загварыг ашиглаж байгаа системд бид процесс бүрт түүний ажиллах талбарт хэрэглэгдэх хуудсуудын жагсаалтыг хадгалдаг. Хэрэв оролт гаралтын хүлээлт үүсэх, хоосон фрейм байхгүй байх зэрэг шалтгааны улмаас процесс түр цуцлагдвал бид тухайн процессийн ажлын талбарыг санана. Ингээд оролт гаралтын төхөөрөмжийн хүлээлт дуусах, боломжтой фрейм гарах зэргээр процессийг дахин үргэлжлүүлэхэд процессийг дахин эхлэхээс өмнө тухайн ажлын талбарт харгалзах санах ойг дуудан оруулж ирнэ.

### Prepaging ашигтай юу? 
Урьдчилан хуудаслалт нь зарим тохиолдолд давуу талтай боловч урьдчилан хуудаслалтыг хэрэглэх нь гарсан хуудасны алдаа бүрт хариулан ажиллахаас хямд байж чадах эсэх нь асуудалтай. Урьдчилан хуудаслалт хийж санах ойд оруулсан процессуудын зарим нь ашиглагдахгүй ч байх магадлалтай. Жишээлбэл, нийт урьдчилан хуудаслагдсан S  хуудасны бутархай хэсэг болох P нь хэрэглэгдэж байгаа гэе (0 =< P =< 1). Тэгвэл нийт S*P тооны хадгалагдсан хуудасны алдааны зардал нь S*(1-P) тооны хэрэггүй хуудсыг урьдчилан хуудаслах зардлаас их үү бага уу гэдгийг бодолцох хэрэгтэй. Хэрэв P нь  0-рүү дөхсөн бол урьдчилан хуудаслалт нь ашиггүй бөгөөд 1-рүү дөхсөн бол урьдчилан хуудаслалт нь ашигтай.

## Эх сурвалж 
* Silberschatz, A, Galvin, P.B & Gagne, G. 2005. Operating System Concepts. 7th Edition. John Wiley & Sons, Inc.

Ангилал: Үйлдлийн систем