Кіріспе
Сақтау кеңістігін тиімсіз пайдалану
Компьютерлік сақтау құралдарында фрагментация – сақтау кеңістігінің, негізгі жадтың немесе қосалқы жадтың тиімсіз пайдаланылуы, бұл сыйымдылықты немесе өнімділікті, көбінесе екеуін де төмендететін құбылыс. Фрагментацияның нақты салдары қолданылатын сақтау кеңістігін бөлу жүйесіне және фрагментацияның түріне байланысты. Көп жағдайда фрагментация сақтау кеңістігінің "босқа кетіп қалуына" әкеледі, және осы жағдайда термин босқа кеткен кеңістіктің өзіне де сілтеме жасайды.
Негізгі принцип
Негізгі жадтың фрагментациясында, компьютерлік бағдарлама компьютер жүйесінен жад блоктарын сұрағанда, блоктар бөліктерге бөлінеді. Компьютерлік бағдарлама бір бөлікті пайдалануын аяқтағанда, оны жүйеге қайтарады, соның арқасында ол кейін басқа немесе сол бағдарламаға қайтадан бөлінуге қолжетімді болады. Бөліктің мөлшері және бағдарлама оны қанша уақыт пайдаланатыны әртүрлі болуы мүмкін. Компьютерлік бағдарлама өмірлік циклы барысында көптеген жад бөліктерін сұрап, босата алады. Бағдарлама іске қосылғанда, бос жад аймақтары ұзын және үздіксіз болады. Уақыт өте келе және пайдаланылуымен, ұзын үздіксіз аймақтар кішірек үздіксіз аймақтарға бөліне бастайды. Соңында, бағдарламаға үлкен, үздіксіз жад блоктарын алу мүмкін болмай қалуы мүмкін.
Түрлері
Фрагментацияның үш түрлі, бірақ өзара байланысты нысаны бар: сыртқы фрагментация, ішкі фрагментация және деректер фрагментациясы, олар жеке немесе бірлесіп кездесуі мүмкін. Фрагментация көбінесе жылдамдық немесе қарапайымдылық артуы үшін қабылданады. Осындай құбылыстар процессорлар сияқты басқа ресурстар үшін де орын алады; төменде қараңыз.
Ішкі бөлшектеу
Жад бетін бөлу ішкі фрагментацияны тудырады, себебі қажет болса да, қажет болмаса да, толық жад беті бөлінеді. Жадты бөлу ережелеріне сәйкес, кейде компьютер жады қажетті мөлшерден артық бөлінеді. Мысалы, бағдарламаларға жад тек белгілі бір бөліктермен (әдетте 4 байттың еселігімен) беріледі, сондықтан егер бағдарлама 29 байт сұраса, ол 32 байттық бөлікті алады. Осылайша, артық жад ысырап болады. Мұндай жағдайда пайдаланылмаған жад, бос орын деп аталады, және ол бөлінген аймақтың ішінде орналасады. Бұл тәсіл, тоқсанды бөлімдер деп аталады, жадты тиімсіз пайдалануға әкеледі – кез келген процесс, оның мөлшеріне қарамастан, толық бөлімді иеленеді. Бұл ысырапты ішкі фрагментация деп атайды. Басқа типтегі фрагментациядан айырмашылығы, ішкі фрагментацияны қайтару қиын; көбінесе оны жоюдың ең жақсы жолы – дизайнды өзгерту. Мысалы, динамикалық жадты бөлуде жад жинағы (memory pools) ішкі фрагментацияны айтарлықтай азайтады, себебі орын шығындары көптеген объектілерге таратылады.
bytes, it will actually get a chunk of 32 bytes. When this happens, the excess memory goes to waste. In this scenario, the unusable memory, known as slack space, is contained within an allocated region. This arrangement, termed fixed partitions, suffers from inefficient memory use any process, no matter how small, occupies an entire partition. This waste is called internal fragmentation. Unlike other types of fragmentation, internal fragmentation is difficult to reclaim; usually the best way to remove it is with a design change. For example, in dynamic memory allocation, memory pools drastically cut internal fragmentation by spreading the space overhead over a larger number of objects.
Сыртқы бөлшектеу
Сыртқы фрагментация бос жад шағын блоктарға бөлінген кезде және бөлінген жад арасында таралып кеткенде пайда болады. Бұл кейбір жадты бөлу алгоритмдерінің әлсіздігі, олар бағдарламалар қолданатын жадты тиімді реттеп бере алмайды. Нәтижесінде, бос жад бар болғанымен, оны пайдалануға болмайды, себебі ол жеке-жеке өте кішкентай бөліктерге бөлінген, ал қолданбаның талаптарын қанағаттандыру үшін олар тым кішкентай. "Сыртқы" термині пайдалануға жарамсыз жад бөлінген аймақтардың сыртында екенін көрсетеді. Мысалы, бағдарлама жадтың үш тізбекті блогын бөліп, содан кейін ортаңғы блокты босатады делік. Жадты бөлуші осы бос жад блогын болашақ бөлулер үшін пайдалана алады. Бірақ, егер бөлінетін жадтың көлемі осы бос блоктан үлкен болса, онда ол бұл блокты пайдалана алмайды. Сыртқы фрагментация файлдық жүйелерде де кездеседі, себебі әртүрлі өлшемдегі көптеген файлдар құрылады, өлшемдері өзгереді және жойылады. Егер көптеген кішкентай бөліктерге бөлінген файл өшірілсе, әсері одан да нашарлайды, себебі сонда осындай кішкентай бос орындар қалады. 0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Түсініктемелер Сақтау үшін барлық жадтан бастаңыз. А Б С 0x1000 өлшемді А, В және С үш блогы бөлінді. А С Блок В босатылды. В қолданған жадтың В-ден үлкен блокқа қосылмағанын ескеріңіз. А C блогы В блогының бос орынына жылжытылды, бұл қалған орынды 0x4000 өлшемді үлкен блок үшін пайдалануға мүмкіндік берді.
Деректердің бөлшектелуі
Деректердің фрагментациясы жадтағы деректер жинағы бір-біріне жақын емес көптеген бөліктерге бөлінген кезде пайда болады. Бұл әдетте сыртқы фрагментацияға ұшыраған үлкен объектіні сақтауға тырысудың салдары болып табылады. Мысалы, файлдық жүйедегі файлдар әдетте блоктар немесе кластерлер деп аталатын бірліктерде басқарылады. Файлдық жүйе құрылған кезде файл блоктарын біріктіріп сақтауға бос орын болады. Бұл жылдам тізбекті файлдарды оқуға және жазуға мүмкіндік береді. Алайда, файлдар қосылғанда, жойылғанда және көлемі өзгергенде бос орын сыртқы фрагментацияға ұшырайды, жаңа деректерді орналастыру үшін тек кішкентай бос кеңістіктер қалады. Жаңа файл жазылғанда немесе қолданыстағы файл кеңейтілгенде, операциялық жүйе жаңа деректерді жаңа, тізбектес емес дерек блоктарына орналастырады, қолданыстағы бос кеңістіктерге сыйып қалу үшін. Жаңа дерек блоктары қажетті түрде шашыраңқы болады, оқу/жазу басқарылымының іздеу уақытына және айналу кешігуіне байланысты қол жеткізуді баяулатады және қосымша орындарды басқаруға байланысты қосымша шығындар тудырады. Бұл файлдық жүйе фрагментациясы деп аталады. Белгілі бір көлемдегі жаңа файл жазылған кезде, егер осы файлдан үлкен бос кеңістіктер болса, операциялық жүйе деректердің фрагментациясын болдырмау үшін файлды осы кеңістіктердің кез келгеніне орналастыра алады. Файлды орналастыруға болатын бос кеңістіктерді таңдау үшін әртүрлі алгоритмдер бар; олардың әрқайсысы қоқыс жинау мәселесіне қатысты эвристикалық жуықтап шешім болып табылады. "Ең жақсы сәйкес келетін" алгоритмі жеткілікті үлкен ең кішкентай бос кеңістікті таңдайды. "Ең нашар сәйкес келетін" алгоритмі ең үлкен бос кеңістікті таңдайды. "Бірінші сәйкес келетін" алгоритмі жеткілікті үлкен алғашқы бос кеңістікті таңдайды. "Келесі сәйкес келетін" алгоритмі әрбір файлдың қай жерде жазылғанын қадағалайды. "Келесі сәйкес келетін" алгоритмі "бірінші сәйкес келетін" алгоритмінен жылдам, ал ол өз кезегінде "ең жақсы сәйкес келетін" алгоритмінен жылдам, бұл "ең нашар сәйкес келетін" алгоритмімен бірдей жылдамдыққа ие. Сығу сыртқы фрагментацияны жойғандай, деректер фрагментациясын да деректерді қайта ұйымдастыру арқылы жоюға болады, яғни байланысты бөліктерді бір-біріне жақын орналастыруға болады. Мысалы, дискідегі блоктарды қайта орналастыру арқылы әрбір файлдың блоктары тізбектес болуын қамтамасыз ету – дискіні дефрагментациялау құралының негізгі міндеті. Көптеген дефрагментациялау құралдары бос орын фрагментациясын азайтуға немесе жоюға да тырысады. Кейбір қоқыс жинағыштар, автоматты жад басқаруды жүзеге асыратын құралдар, кэштің өнімділігін жақсарту үшін байланысты объектілерді бір-біріне жақын жылжытады (бұл сығу деп аталады). Деректер фрагментациясын ешқашан сезінбейтін төрт жүйе бар – олар әрқашан әрбір файлды тізбектес түрде сақтайды. Төрт жүйенің де кемшіліктері бар, олар кем дегенде уақытша деректер фрагментациясына мүмкіндік беретін жүйелермен салыстырғанда: Әрбір файлды тізбектес жазыңыз. Егер файлды сақтауға жеткілікті тізбектес бос орын болмаса, жүйе файлды сақтауға тырыспайды, тіпті жойылған файлдардан жиналған бос орын жеткілікті болса да. Егер файлды сақтауға жеткілікті бос орын болмаса, файлды сақтауға жеткілікті үлкен бір тізбектес бос аймаққа айналдыру үшін көшіру коллекторын пайдаланыңыз. Бұл файлды фрагменттерге бөлуден және оларды қолданыстағы бос орынға орналастырудан әлдеқайда көп уақыт алады. Файлды кез келген бос блокқа, белгіленген өлшемді блоктарда сақтау арқылы жазыңыз. Егер бағдарламашы тым кішкентай блок өлшемін таңдаса, жүйе кейбір файлдарды – блок өлшемінен үлкен файлдарды – сақтамайды, тіпті файлды сақтауға жеткілікті бос блоктар көп болғанда да. Егер бағдарламашы тым үлкен блок өлшемін таңдаса, ішкі фрагментацияға көп орын кетіп қалады. Кейбір жүйелер динамикалық бөлуді мүлдем болдырмайды, олар қажет болатын барлық файлдар үшін алдын ала (тізбектес) орынды сақтайды. Мысалы, MultiFinder әрбір қолданбаны іске қосқанда, бағдарламашы оның бағдарламасы қанша RAM қажет екенін мәлімдегендей, RAM-нің бір бөлігін бөліп береді.
Simply write each file contiguously. If there isn't already enough contiguous free space to hold the file, the system immediately fails to store the file—even when there are many little bits of free space from deleted files that add up to more than enough to store the file. If there isn't already enough contiguous free space to hold the file, use a copying collector to convert many little bits of free space into one contiguous free region big enough to hold the file. This takes a lot more time than breaking the file up into fragments and putting those fragments into the available free space. Write the file into any free block, through fixed size blocks storage. If a programmer picks a fixed block size too small, the system immediately fails to store some files—files larger than the block size—even when there are many free blocks that add up to more than enough to store the file. If a programmer picks a block size too big, a lot of space is wasted on internal fragmentation. Some systems avoid dynamic allocation entirely, pre storing (contiguous) space for all possible files they will need—for example, MultiFinder pre allocates a chunk of RAM to each application as it was started according to how much RAM that application's programmer claimed it would need.
Салыстыру
Сыртқы фрагментациямен салыстырғанда, қосымша шығындар мен ішкі фрагментация жадының ысырабы және өнімділіктің төмендеуі тұрғысынан аз шығынға әкеледі. Ол былай анықталады: 0% фрагментация – барлық бос жад бір үлкен блоктан тұрады дегенді білдіреді; фрагментация 90% (мысалы) – 100 МБ бос жад бар, бірақ сақтау үшін жадтың ең үлкен бос блогы тек 10 МБ ғана. Сыртқы фрагментация файлдық жүйелерде негізгі жад (RAM) сақтау жүйелерімен салыстырғанда аз мәселе тудырады, себебі бағдарламалар әдетте RAM сақтау сұраныстарын тікелей блоктармен орындауды қажет етеді, ал файлдық жүйелер логикалық тұрғыдан тікелей көрінетін файлды құрастыру үшін қолжетімді блоктардың (фрагменттердің) кез келген жиынтығын пайдалануға бейімделген. Сондықтан, егер толық томнан жоғары фрагменттелген файл немесе көптеген кішкентай файлдар жойылса, содан кейін жаңадан босатылған орынға тең өлшемдегі жаңа файл жасалса, жаңа файл жою арқылы босатылған сол фрагменттерді қайта пайдаланады. Егер жойылған файл бір файл болса, жаңа файл сол ескі файл сияқты фрагменттелген болады, бірақ кез келген жағдайда жаңа файлды құру үшін барлық (жоғары фрагменттелген) бос орынды пайдалануға ешқандай кедергі болмайды. RAM-да, керісінше, қолданылатын сақтау жүйелері көбінесе кішкентай, тікелей емес бос блоктардан сұранысты қанағаттандыру үшін үлкен блокты құрастыра алмайды, сондықтан сұраныс орындалмайды және бағдарлама сол жадқа қажет болған жұмысты істей алмайды (егер ол сұранысты бірнеше кішкентай жеке сұраныстар ретінде қайта жіберсе).
Fragmentation of 0% means that all the free memory is in a single large block; fragmentation is 90% (for example) when 100 MB free memory is present but largest free block of memory for storage is just 10 MB. External fragmentation tends to be less of a problem in file systems than in primary memory (RAM) storage systems, because programs usually require their RAM storage requests to be fulfilled with contiguous blocks, but file systems typically are designed to be able to use any collection of available blocks (fragments) to assemble a file which logically appears contiguous. Therefore, if a highly fragmented file or many small files are deleted from a full volume and then a new file with size equal to the newly freed space is created, the new file will simply reuse the same fragments that were freed by the deletion. If what was deleted was one file, the new file will be just as fragmented as that old file was, but in any case there will be no barrier to using all the (highly fragmented) free space to create the new file. In RAM, on the other hand, the storage systems used often cannot assemble a large block to meet a request from small noncontiguous free blocks, and so the request cannot be fulfilled and the program cannot proceed to do whatever it needed that memory for (unless it can reissue the request as a number of smaller separate requests).
Сақтау қатесі
Фрагментациядан туындаған ең ауыр проблема – процестің немесе жүйенің ресурстардың ерте таусылуынан істен шығуы: егер үзіліссіз блок сақталуы тиіс болса, ал сақталмаса, іс жүзінде сәтсіздік орын алады. Фрагментация осыған себеп болады, тіпті ресурстың жеткілікті көлемі болғанымен, бірақ үзіліссіз мөлшерде болмаса. Мысалы, егер компьютерде 4 ГБ жад болса, ал 2 ГБ бос болса, бірақ жад 1 МБ қолданылған, 1 МБ бос күйінде кезектесіп орналасса, онда 1 ГБ үзіліссіз жадты сұрау 2 ГБ бос болғанына қарамастан қанағаттандырыла алмайды. Мұны болдырмау үшін, бөлуші сәтсіздікке ұшыраудың орнына фрагментацияны жою (немесе жадты жинақтау циклын) немесе басқа ресурстарды қайтаруды, мысалы, үлкен қоқыс жинау циклын іске қосуы мүмкін, содан кейін сұранысты орындай алады деген үмітте. Бұл процестің жалғасуына мүмкіндік береді, бірақ өнімділікке елеулі түрде әсер етуі мүмкін.
Жүгіру қабілетінің төмендеуі
Фрагментация бірнеше себептермен өнімділіктің төмендеуіне әкеледі. Ең бастысы, фрагментация ресурсты бөлу және оған қол жеткізу үшін қажетті жұмысты арттырады. Мысалы, қатты дискіде немесе таспалы дискіде, тізбекті деректерді оқу өте жылдам, бірақ басқа мекенжайға іздеу баяу болғандықтан, фрагменттелген файлды оқу немесе жазу көптеген іздеуді қажет етеді, бұл құрылғының тозуын арттырумен қатар, әлдеқайда баяу болады. Сонымен қатар, егер ресурс фрагменттелмесе, бөлу сұраныстарын тегін аймақтың басынан бір блокты қайтару арқылы қанағаттандыруға болады. Ал егер ол фрагменттелген болса, сұрау жеткілікті үлкен бос блокты іздеуді қажет етеді, бұл көп уақыт алады немесе сұрауды бірнеше кіші блоктармен орындауды қажет етеді (мүмкін болса), бұл бөлудің фрагменттелуіне және бірнеше бөлікті басқару үшін қосымша шығындарға әкеледі. Тағы бір мәселе – фрагментация кэшті мерзімінен бұрын толтырып, жеке деректерді емес, блоктарды сақтайтындықтан, соққыға (thrashing) әкелуі мүмкін. Мысалы, егер бағдарламаның 256 КиБ жұмыс жиынтығы болса және ол 256 КиБ кэшке ие компьютерде (мысалы, L2 нұсқаулар + деректер кэші) жұмыс істесе, бүкіл жұмыс жиынтығы кэшке сыяды және осылайша, кемінде кэш сәйкестігі бойынша жылдам орындалады. Сонымен қатар, оның 64 аудармалық буфері (TLB) бар делік, әрқайсысы 4 КиБ бетке арналған: әр жадқа қол жеткізу үшін виртуалдыдан физикалыққа аударма қажет, егер бет кэште болса (осы жерде TLB) бұл жылдам болады. Егер жұмыс жиынтығы фрагменттелмеген болса, онда ол дәл 64 бетке сыяды (беттік жұмыс жиынтығы 64 беттен тұрады) және барлық жад іздеулері кэштен қызмет ала алады. Бірақ егер жұмыс жиынтығы фрагменттелген болса, онда ол 64 бетке сыймайды және орындалу соққыға байланысты баяулайды: жұмыс барысында TLB-ден беттер қайта-қайта қосылады және алынып тасталады. Сондықтан жүйелік жобалаудағы кэш өлшемі фрагментацияны ескеру үшін қосымша резервке ие болуы керек. Жад фрагментациясы жүйелік администраторлар кездесетін ең ауыр проблемалардың бірі. Уақыт өте келе ол жүйенің өнімділігін төмендетеді. Соңында, жад фрагментациясы қолдануға жарамды бос жадтың толық жоғалуына әкелуі мүмкін. Жад фрагментациясы – ядролық бағдарламалау деңгейіндегі проблема. Қолданбаларды нақты уақыт режимінде есептеу кезінде фрагментация деңгейі 99%-ға дейін жете алады және жүйелік апаттарға немесе басқа тұрақсыздықтарға әкелуі мүмкін. Мұндай жүйелік апаттарды болдырмау қиын, өйткені жад фрагментациясының күрт өсуін болжау мүмкін емес. Дегенмен, жүйе тым көп жад фрагментациясы болған жағдайда барлық бағдарламаларды орындауды жалғастыра алмаса да, жақсы жобаланған жүйе жад блоктарын жүйе өзі пайдаланатын бөліктерден көшіру арқылы бос жадты аз және үлкен блоктарға біріктіруге немесе ең жаман жағдайда, кейбір бағдарламаларды тоқтатып, олардың жадын босату арқылы және содан кейін бос жадтың жалпы сомасын фрагменттеу арқылы күрделі фрагментация жағдайын қалпына келтіре алады. Бұл кем дегенде жүйелік сәтсіздік сияқты нағыз апаттың алдын алады және жүйенің кейбір бағдарламаларды орындауын, бағдарламалық деректерді сақтауын және т.б. мүмкіндік береді. Сондай-ақ, фрагментация – жүйелік бағдарламалық жасақтаманың құбылысы екенін атап өту маңызды; әртүрлі бағдарламалық жасақтама әртүрлі дәрежеде фрагментацияға бейім, және жад фрагментациясының нәтижесінде процестерді тоқтатуға немесе өлтіруге мәжбүр болмайтын жүйені жобалау мүмкін.
Аналогты құбылыстар
Фрагментация жадты бөлудегі мәселе ретінде жақсы танымал болғанымен, ұқсас құбылыстар басқа ресурстарда да, әсіресе процессорларда кездеседі. Мысалы, уақытты бөлісу арқылы алдын ала көп тапсырмалылықты қолданатын, бірақ процестің тоқтатылғандығын тексермейтін жүйеде, өзінің уақыт тілімінің бір бөлігін орындайтын, бірақ содан кейін тоқталып, уақыт тілімінің қалған бөлігін жалғастыра алмайтын процесс, нәтижесінде уақыт тілімінің ішкі фрагментациясынан уақытты босқа жұмсайды. Ең бастысы, уақытты бөлісудің өзі процестерді үздіксіз бір рет орындаудың орнына, фрагменттелген уақыт тілімдерінде орындау арқасында процестердің сыртқы фрагментациясына әкеледі. Процестерді ауыстырудың құны және бірдей кэштерді пайдаланатын бірнеше процестердің кэш жүктемесінің артуы өнімділіктің төмендеуіне алып келуі мүмкін. Параллель жүйелерде, әсіресе таратылған жүйелерде, процестер тобы ілгерілеу үшін өзара әрекеттесуі керек болса, егер процестер бөлек уақытта немесе бөлек машиналарда (уақыт бойынша немесе машиналар бойынша фрагменттелген) жоспарланған болса, бір-біріне күтуге немесе бір-бірімен байланысуға жұмсалатын уақыт өнімділікті күрт төмендетуі мүмкін. Оның орнына, жоғары өнімді жүйелерге осы топтың бірдей уақытта іске қосылуы (coscheduling) қажет.