एक अखंड यूनिक्स जैसा ओएस विकसित करना - ढेर (4)

पिछले लेख में, हमने कर्नेल सिस्टम लॉग लागू किया था। अब एक गतिशील मेमोरी मैनेजर को लागू करने का समय आ गया है।

सामग्री की तालिका

1. बिल्ड सिस्टम (मेक, जीसीसी, गैस)। प्रारंभिक बूट (मल्टीबूट)। लॉन्च (qemu)। सी लाइब्रेरी (strcpy, memcpy, strext)।
2. सी लाइब्रेरी (स्प्रिंटफ, स्ट्रैची, स्ट्रैम्प, स्ट्रेटोक, वा_लिस्ट ...)। लाइब्रेरी को कर्नेल मोड और उपयोगकर्ता एप्लिकेशन मोड में बनाना।
3. कर्नेल सिस्टम लॉग। वीडियो मेमोरी टर्मिनल का आउटपुट (kprintf, kpanic, kassert)।
4. डायनेमिक मेमोरी, हीप (kmalloc, kfree)।
5. मेमोरी और इंटरप्ट हैंडलिंग (GDT, IDT, PIC, syscall) का संगठन। अपवाद।
6. वर्चुअल मेमोरी (पेज डायरेक्टरी और पेज टेबल)।
7. प्रक्रिया। समयबद्धक। मल्टीटास्किंग। सिस्टम कॉल (मार, निकास, पीएस)।
8. कर्नेल की फ़ाइल प्रणाली (initrd), योगिनी, और इसके आंतरिक। सिस्टम कॉल (निष्पादन)।
9. चरित्र डिवाइस ड्राइवर। सिस्टम कॉल (ioctl, fopen, fread, fwrite)। सी लाइब्रेरी (fopen, fclose, fprintf, fscanf)।
10. कर्नेल के लिए एक पूर्ण कार्यक्रम के रूप में शेल।
11. उपयोगकर्ता सुरक्षा मोड (रिंग 3)। टास्क स्टेटस सेगमेंट (tss)।

गतिशील कर्नेल मेमोरी। एक गुच्छा

कर्नेल हीप इंटरफ़ेस इस तरह दिखेगा:

void *kmalloc(size_t size); void kfree(void *addr); 

चूंकि अभी तक कोई ढेर नहीं हैं, इसलिए कब्जे वाले और मुक्त स्मृति क्षेत्रों के रिकॉर्ड संग्रहीत करने होंगे।
सीमित आकार के एक सरणी में। छोटा आयाम, द्वारा कम हीप क्षमता
छोटे टुकड़े। लिनक्स पर, उदाहरण के लिए, कई कर्नेल संरचनाएं पुन: प्रयोज्य में संग्रहीत की जाती हैं
मेमोरी जो रिलीज़ होने पर (स्लैब) आकार नहीं बदलती। लेकिन हम अभी भी इससे बहुत दूर हैं,
क्योंकि विकास एक पुनरावृत्त प्रक्रिया है।

कोई भी तत्व जो किसी सरणी के माध्यम से आयोजित सूची का एक तत्व होने का इरादा रखता है
एक इंटरफ़ेस को लागू करने के लिए आवश्यक है।

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 

C में कोई इंटरफेस नहीं हैं, लेकिन उनकी जरूरत नहीं है। हम किसी भी ऑब्जेक्ट के पॉइंटर को टाइप स्ट्रक्चर स्लिस्ट_हेड_टी * पर डालते हैं यदि यह ऑब्जेक्ट भौतिक रूप से इस तरह दिखता है:

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

लेकिन इतना है कि सामान्यीकृत एल्गोरिथ्म उस सरणी के आयाम को जानता है जिसमें सूची संग्रहीत की जाएगी
और इसके तत्व का आकार, सूची का पहला और अंतिम तत्व और सरणी का पता जिसमें
एक सूची संग्रहीत की जाती है, ऑपरेटिंग सूची के प्रत्येक फ़ंक्शन को दूसरे पॉइंटर की आवश्यकता होगी
सूची परिभाषा संरचना के लिए:

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; }; 

सूची के संचालन के कार्य इस तरह दिखाई देंगे:

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry); 

फ़ंक्शन एल्गोरिथम सम्मिलित करें:
सरणी में एक निःशुल्क स्लॉट खोजें।
इसे एक नए तत्व से भरें।
तार्किक (भौतिक रूप से नहीं) समीपवर्ती सूची आइटमों के बिंदुओं को ठीक करें।
व्यस्त के रूप में मार्क स्लॉट।
सूची की शुरुआत और अंत समायोजित करें।

सूची से निकालने के लिए फ़ंक्शन की एल्गोरिथ्म:
तार्किक (भौतिक रूप से नहीं) समीपवर्ती सूची आइटमों के बिंदुओं को ठीक करें।
सूची की शुरुआत और अंत समायोजित करें।
मुफ्त के रूप में मार्क स्लॉट।

डायनामिक मेमोरी को निम्नलिखित मदों के साथ एक सूची द्वारा वर्णित किया गया है:

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed); 

इस तरह के रिकॉर्ड से गतिशील मेमोरी का वर्णन करने वाला एक सरणी इस तरह दिखता है:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

स्मृति क्षेत्रों की सूची को परिभाषित करना इस तरह दिखता है:

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks}; 

इसलिए, हमने गतिशील मेमोरी का वर्णन किया है। एक निश्चित सीमा के भीतर सभी मेमोरी
मनमाने आकार के ब्लॉक में विभाजित है, जिनमें से प्रत्येक खाली हो सकता है,
या तो व्यस्त है। इसके अलावा, प्रत्येक ब्लॉक को ध्वज के साथ एक सरणी तत्व द्वारा वर्णित किया जाता है is_valid = true,
जो एक सूची आइटम है।

अब सबसे सरल ढेर आवंटन एल्गोरिथ्म (kmalloc) पर विचार करें:
यदि कोई मुफ्त ब्लॉक नहीं है, तो आवश्यक आकार के एक नए ब्लॉक का चयन करें (लेकिन अधिकतम हीप आकार से अधिक नहीं)।

अन्यथा, हम सभी मुक्त ब्लॉकों के माध्यम से देखते हैं। यदि हम एक मुफ़्त ब्लॉक पाते हैं, तो उसके आकार को देखें। यदि यह पर्याप्त है, तो इसे लें। यदि कोई अधिशेष है तो अतिरिक्त के आकार का एक नया खाली ब्लॉक बनाएं। अन्यथा, यदि यह अपर्याप्त और बाद वाला है, तो हम ढेर सीमा का विस्तार करते हैं (लेकिन अधिकतम से अधिक नहीं)।

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } 

मेमोरी मुक्त एल्गोरिथ्म समान होगा (kfree):
एक ब्लॉक का पता लगाएं जिसका पता शुरू होने वाले पते से शुरू होता है। जांचें कि वह व्यस्त है। मुक्त के रूप में चिह्नित करें।

यदि एक ब्लॉक में उसके साथ एकजुट होने के लिए दाएं या बाएं एक निशुल्क पड़ोसी है।

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); } 

वह सब है। अगली बार तक!

संदर्भ

अब, वीडियो ट्यूटोरियल खोलें
और समानांतर में गिट रिपॉजिटरी देखें (आपको एक सबक 4 शाखा की आवश्यकता है)

संदर्भ

1. जेम्स मोलॉय। अपना खुद का खिलौना यूनिक्स-क्लोन ओएस रोल करें।
2. दाँत। डॉस, विंडोज, यूनिक्स के लिए असेंबलर
3. कलाश्निकोव। असेंबलर आसान है!
4. ताननबाम। ऑपरेटिंग सिस्टम। कार्यान्वयन और विकास।
5. रॉबर्ट लव। लिनक्स कर्नेल विकास प्रक्रिया का विवरण।