लिनक्स शेड्यूलर को समझना

Question

मैं लिनक्स कर्नेल और निम्न स्तर के प्रोग्रामिंग के लिए नया हूं। मैं जानना चाहता था कि समय जटिलता में लिनक्स शेड्यूलर ओ (1) कैसे होना चाहिए।

मैं निम्न आलेख जो बहुत जानकारीपूर्ण है भर में आया था, लेकिन मैं pargraph मैं नीचे http://www.ibm.com/developerworks/linux/library/l-scheduler/

reproduced है समझने में कुछ समस्या अनुसूचक का काम सरल है: उच्चतम प्राथमिकता के आधार पर कार्य का चयन निष्पादित करने के लिए सूची। इस प्रक्रिया को और अधिक कुशल बनाने के लिए, बिटमैप का उपयोग परिभाषित करने के लिए किया जाता है जब कार्य किसी प्राथमिकता सूची में होते हैं। इसलिए, अधिकांश आर्किटेक्चर पर, एक खोज-प्रथम-बिट-सेट निर्देश है जो 32 32 बिट शब्दों में से एक में उच्चतम प्राथमिकता बिट सेट को खोजने के लिए उपयोग किया जाता है (140 प्राथमिकताओं के लिए)। निष्पादित करने के लिए कार्य खोजने में लगने वाला समय सक्रिय कार्यों की संख्या पर निर्भर करता है, बल्कि प्राथमिकताओं की संख्या पर निर्भर करता है। यह 2.6 शेड्यूलर को ओ (1) प्रक्रिया बनाता है क्योंकि शेड्यूल करने का समय सक्रिय कार्यों की संख्या के बावजूद निश्चित और निर्धारिती दोनों है।

140 कतारों के लिए 32 बिट्स के 5 शब्द क्यों? कौन सी खोज-प्रथम-बिट-सेट निर्देश 140 कतारों में से एक को चुनने में मदद करता है?

Answer 1

थोड़ा क्षेत्र एक भी मान का उपयोग करता है उदाहरण के लिए बूलियन राज्यों के एक नंबर का प्रतिनिधित्व करने, अगर हम एक 8 बिट पूर्णांक उपयोग कर रहे थे तो हम कह सकते हैं कि:

17 (decimal) = 00010001 (binary) 

कौन सा होगा इंगित करता है कि 4 और 8 वीं बुलियन मूल्य सत्य हैं, जहां अन्य सभी बूलियन मान झूठे हैं। कुल 8 बूलियन राज्यों में ट्रैक किया जा सकता है क्योंकि 8 बिट्स हैं।

हम 140 राज्यों ट्रैक करना चाहते हैं के रूप में (प्रत्येक पंक्ति के लिए 1, सच है कि कतार का संकेत एक कार्य शामिल हैं), 140 बिट के लिए आवश्यक हैं, और स्टोर करने के लिए 140/32 = 4.375, हम कम से कम 5 32 बिट पूर्णांकों की जरूरत है ताकि के रूप में सभी बूलियन राज्यों।

Answer 2

कुछ इस तरह:

int bitmap_idx = priority/BITS_PER_WORD; 
int bitmap_bit = priority%BITS_PER_WORD; 

isSet = (bitmap[bitmap_idx]&(1<<bitmap_bit)); //test 
bitmap[bitmap_idx] |= 1<<bitmap_bit;    //set 

प्राथमिकता सरणी के साथ विशेष प्रक्रिया तक पहुंचने के लिए प्रयोग किया जाता है और यह कैसे बिटमैप्स अनुसूचक जो बारी-बारी पर struct prio_array

लेख आपको बताया निर्भर करता है में उपयोग किया जाता है पुराना है यह http://www.informit.com/articles/article.aspx?p=101760&seqNum=2