نظام الملفات وتنفيذه
دراسة شاملة لمفاهيم أنظمة الملفات، هياكل الأدلة، طرق الوصول، الحماية، بالإضافة إلى التنفيذ الفعلي على الأقراص بما في ذلك طرق التخصيص وإدارة المساحات الفارغة.
File System and Implementation
Comprehensive study of file system concepts, directory structures, access methods, protection, and physical implementation on disks including allocation methods and free-space management.
أهداف التعلم
- شرح وظيفة أنظمة الملفات ووصف واجهاتها.
- تقييم المفاضلات في تصميم أنظمة الملفات، بما في ذلك طرق الوصول، مشاركة الملفات، أقفال الملفات، وهياكل الأدلة.
- تحديد طرق حماية نظام الملفات.
- وصف تفاصيل تنفيذ أنظمة الملفات المحلية وهياكل الأدلة.
- تقييم طرق تخصيص الكتل وخوارزميات الكتل الحرة والمفاضلات بينها.
- استكشاف كفاءة نظام الملفات وقضايا الأداء.
- Explain the function of file systems and describe their interfaces.
- Evaluate file-system design tradeoffs, including access methods, file sharing, file locking, and directory structures.
- Define file-system protection methods.
- Describe the details of implementing local file systems and directory structures.
- Evaluate block allocation and free-block algorithms and trade-offs.
- Explore file system efficiency and performance issues.
1 مفهوم الملف وخصائصه
1 File Concept and Attributes
الملف هو مساحة عناوين منطقية متجاورة تخزن البيانات، ويمتلك خصائص مثل الاسم، المعرف، الحجم، والحماية.
A file is a contiguous logical address space storing data, possessing attributes like name, identifier, size, and protection.
الملف يمثل وحدة التخزين المنطقية الأساسية. يتم تعريف محتوياته بواسطة منشئه ويمكن أن يكون نصاً، برنامجاً، أو بيانات ثنائية.
تشمل خصائص الملف: الاسم (المعلومة الوحيدة المقروءة للبشر)، المعرف (رقم فريد داخل النظام)، النوع، الموقع (مؤشر لمكانه على الجهاز)، الحجم، الحماية (من يمكنه القراءة/الكتابة/التنفيذ)، والوقت والتاريخ وهوية المستخدم. تُحفظ هذه المعلومات في هيكل الدليل (Directory Structure) على القرص.
A file represents the basic logical storage unit. Its contents are defined by its creator and can be text, programs, or binary data.
File attributes include: Name (only human-readable info), Identifier (unique tag/number), Type, Location (pointer to device location), Size, Protection (read/write/execute controls), and Time, date, and user ID. This information is kept in the directory structure maintained on the disk.
الخصائص الممتدة (Extended Attributes) قد تشمل معلومات إضافية مثل المجموع الاختباري (Checksum) للملف لضمان سلامة البيانات.
فصل البيانات الوصفية (Metadata) عن بيانات الملف الفعلية يسمح لنظام التشغيل بإدارة الملفات بكفاءة دون الحاجة لقراءة محتوى الملف بالكامل.
Extended attributes may include additional info like a file checksum for data integrity.
Separating metadata from actual file data allows the OS to manage files efficiently without needing to read the entire file content.
لماذا يُعتبر 'الاسم' هو الخاصية الوحيدة المقروءة للبشر في الملف؟ Why is the 'Name' considered the only human-readable attribute of a file?
لأن باقي الخصائص (مثل المعرف، الموقع، الحجم) يتعامل معها نظام التشغيل كأرقام أو مؤشرات ثنائية لتسريع المعالجة، بينما الاسم مصمم خصيصاً لراحة المستخدم في التعرف على الملف.
Because other attributes (like identifier, location, size) are handled by the OS as binary numbers or pointers for processing speed, whereas the name is specifically designed for user convenience in identifying the file.
2 عمليات الملفات والأقفال
2 File Operations and Locking
نظام التشغيل يوفر عمليات أساسية (إنشاء، قراءة، كتابة، حذف) ويستخدم الأقفال (Locking) لمنع التعارض عند وصول عدة عمليات لنفس الملف.
The OS provides basic operations (create, read, write, delete) and uses locking to prevent conflicts when multiple processes access the same file.
العمليات الأساسية تشمل: Create, Write (عند موقع مؤشر الكتابة)، Read (عند موقع مؤشر القراءة)، Reposition (Seek)، Delete، و Truncate. لتجنب البحث المتكرر في الدليل، يُستخدم الأمر Open لنقل معلومات الملف إلى الذاكرة، و Close لإزالتها.
أقفال الملفات (File Locking): تشبه أقفال القارئ/الكاتب. القفل المشترك (Shared) يسمح لعدة عمليات بالقراءة، بينما القفل الحصري (Exclusive) يمنع الآخرين أثناء الكتابة. الأقفال إما إلزامية (Mandatory) حيث يمنع نظام التشغيل الوصول، أو استشارية (Advisory) حيث يجب على العمليات التحقق من حالة القفل بنفسها.
Basic operations include: Create, Write (at write pointer), Read (at read pointer), Reposition (Seek), Delete, and Truncate. To avoid repeated directory searches, Open moves file info to memory, and Close removes it.
File Locking: Similar to reader-writer locks. A Shared lock allows multiple processes to read, while an Exclusive lock prevents others during writing. Locks are either Mandatory (OS denies access) or Advisory (processes must check lock status themselves).
الأقفال الاستشارية شائعة في أنظمة UNIX، مما يعطي مرونة للمطورين ولكن يتطلب برمجة حذرة.
الأقفال الإلزامية (شائعة في Windows) تضمن سلامة البيانات بقوة ولكن قد تؤدي إلى مشاكل مثل الجمود (Deadlocks) إذا لم تُدار بشكل صحيح.
Advisory locks are common in UNIX, giving developers flexibility but requiring careful programming.
Mandatory locks (common in Windows) strictly enforce data integrity but can lead to issues like deadlocks if not managed properly.
ما هو الخطر المحتمل عند استخدام الأقفال الإلزامية (Mandatory Locks)؟ What is a potential risk when using Mandatory Locks?
الخطر الأكبر هو حدوث الجمود (Deadlock) إذا احتفظت عملية بقفل حصري وانهارت أو دخلت في حلقة مفرغة، مما يمنع جميع العمليات الأخرى من الوصول للملف.
The biggest risk is Deadlock; if a process holds an exclusive lock and crashes or enters an infinite loop, it prevents all other processes from accessing the file.
3 طرق الوصول
3 Access Methods
يمكن قراءة الملفات إما بالتسلسل (بايت تلو الآخر) أو بالوصول المباشر (القفز إلى كتلة محددة فوراً).
Files can be read either sequentially (byte by byte) or via direct access (jumping to a specific block instantly).
- الوصول التسلسلي (Sequential Access): تتم قراءة/كتابة السجلات بالترتيب (read next, write next). لا يمكن التخطي للأمام أو الخلف إلا بإعادة الضبط (Reset).
- الوصول المباشر (Direct Access): يسمح بالقفز إلى أي كتلة منطقية (read n, write n). مفيد لقواعد البيانات.
- طرق أخرى: تُبنى فوق الطرق الأساسية، مثل استخدام الفهارس (Index). يتم الاحتفاظ بفهرس في الذاكرة لتحديد موقع البيانات بسرعة (مثل ISAM من IBM).
- Sequential Access: Records are read/written in order (read next, write next). Cannot skip ahead or back without a Reset.
- Direct Access: Allows jumping to any logical block (read n, write n). Useful for databases.
- Other Methods: Built on top of base methods, involving the creation of an index. An index is kept in memory for fast determination of data location (e.g., IBM's ISAM).
يمكن محاكاة الوصول التسلسلي على ملف ذو وصول مباشر باستخدام متغير يمثل الموضع الحالي (Current Position - cp).
عند كل قراءة، يتم قراءة الكتلة `cp` ثم زيادة `cp` بمقدار 1.
Sequential access can be simulated on a direct-access file using a Current Position (cp) variable.
On each read, block `cp` is read, and `cp` is incremented by 1.
لماذا يُعتبر الوصول المباشر ضرورياً لأنظمة قواعد البيانات؟ Why is direct access essential for database systems?
لأن قواعد البيانات تحتاج إلى استرجاع سجلات محددة بسرعة بناءً على استعلامات المستخدم، والبحث التسلسلي في ملف ضخم سيكون بطيئاً جداً وغير عملي.
Because databases need to retrieve specific records quickly based on user queries, and searching sequentially through a massive file would be far too slow and impractical.
4 هياكل الأدلة
4 Directory Structures
تتطور هياكل الأدلة من مستوى واحد بسيط إلى شجرة هرمية، وصولاً إلى رسوم بيانية تسمح بمشاركة الملفات والروابط المعقدة.
Directory structures evolve from a simple single-level to a hierarchical tree, up to graphs that allow file sharing and complex links.
يُنظم الدليل منطقياً لتحقيق الكفاءة، التسمية المريحة، والتجميع. الأنواع تشمل:
- الدليل ذو المستوى الواحد (Single-Level): دليل واحد لجميع المستخدمين. يعاني من مشاكل التسمية (لا يمكن تكرار الأسماء) والتجميع.
- الدليل ذو المستويين (Two-Level): دليل منفصل لكل مستخدم. يحل مشكلة التسمية بين المستخدمين ولكن لا يدعم التجميع الداخلي.
- الدليل الشجري (Tree-Structured): هرمي، يسمح للمستخدمين بإنشاء أدلة فرعية. البحث فعال والتجميع ممتاز.
- الرسم البياني غير الدوري (Acyclic-Graph): يسمح بمشاركة الأدلة الفرعية والملفات (روابط/Links). يطرح مشكلة المؤشرات المعلقة (Dangling pointers) عند حذف الملف الأصلي.
- الرسم البياني العام (General Graph): يسمح بوجود حلقات (Cycles). يتطلب خوارزميات لجمع القمامة (Garbage collection) واكتشاف الحلقات.
Directories are organized logically for efficiency, naming, and grouping. Types include:
- Single-Level: One directory for all users. Suffers from naming and grouping problems.
- Two-Level: Separate directory for each user. Solves naming across users but lacks internal grouping.
- Tree-Structured: Hierarchical, allows subdirectories. Efficient searching and grouping.
- Acyclic-Graph: Allows shared subdirectories and files (links/aliasing). Introduces dangling pointer problems if the original file is deleted.
- General Graph: Allows cycles. Requires garbage collection and cycle detection algorithms.
لحل مشكلة المؤشرات المعلقة في Acyclic-Graph، تُستخدم تقنيات مثل المؤشرات العكسية (Backpointers) لحذف جميع الروابط، أو استخدام عداد المراجع (Entry-hold-count) حيث لا يُحذف الملف فعلياً إلا عندما يصل العداد إلى الصفر.
To solve dangling pointers in Acyclic-Graphs, techniques like Backpointers (to delete all links) or Entry-hold-count (reference counting, where the file is only deleted when the count reaches zero) are used.
كيف يمنع نظام التشغيل حدوث حلقات (Cycles) في دليل الرسم البياني العام؟ How does the OS prevent cycles in a General Graph directory?
إما بالسماح بالروابط (Links) للملفات فقط وليس للأدلة الفرعية، أو بتشغيل خوارزمية اكتشاف الحلقات (Cycle detection algorithm) في كل مرة يتم فيها إضافة رابط جديد.
Either by allowing links only to files and not to subdirectories, or by running a cycle detection algorithm every time a new link is added.
5 حماية نظام الملفات
5 File System Protection
تتحكم الحماية في من يمكنه الوصول للملفات ونوع العمليات المسموحة (قراءة، كتابة، تنفيذ) باستخدام قوائم الوصول أو المجموعات.
Protection controls who can access files and what operations are allowed (read, write, execute) using access lists or groups.
يجب أن يكون مالك/منشئ الملف قادراً على التحكم في أنواع الوصول (Read, Write, Execute, Append, Delete, List).
في أنظمة UNIX: يتم تصنيف المستخدمين إلى ثلاث فئات: المالك (Owner)، المجموعة (Group)، والعامة (Public). يتم تمثيل الصلاحيات بـ 3 بتات (RWX). على سبيل المثال، `761` تعني: المالك له كل الصلاحيات (7 = 111)، المجموعة لها قراءة وكتابة (6 = 110)، والعامة لهم تنفيذ فقط (1 = 001). يمكن إرفاق مجموعة بملف باستخدام أمر `chgrp`.
في أنظمة Windows: تُستخدم قوائم التحكم في الوصول (ACL) لتحديد صلاحيات دقيقة لكل مستخدم أو مجموعة.
The file owner/creator should control access types (Read, Write, Execute, Append, Delete, List).
In UNIX: Users are classified into three classes: Owner, Group, and Public. Permissions are represented by 3 bits (RWX). For example, `761` means: Owner has all (7 = 111), Group has read/write (6 = 110), Public has execute only (1 = 001). A group is attached to a file using `chgrp`.
In Windows: Access-Control Lists (ACL) are used to specify fine-grained permissions for individual users or groups.
استخدام المجموعات (Groups) في UNIX يقلل من حجم البيانات الوصفية المطلوبة للحماية مقارنة بقوائم ACL الكاملة، ولكنه أقل مرونة.
أنظمة الملفات الحديثة تدعم كلاهما.
Using Groups in UNIX reduces the metadata size required for protection compared to full ACLs, but it is less flexible.
Modern file systems often support both.
ماذا يعني إذن الوصول `rwxr-xr--` في نظام UNIX؟ What does the access permission `rwxr-xr--` mean in UNIX?
المالك لديه قراءة وكتابة وتنفيذ (rwx = 7)، المجموعة لديها قراءة وتنفيذ (r-x = 5)، والعامة لديهم قراءة فقط (r-- = 4).
Owner has read, write, execute (rwx = 7); Group has read, execute (r-x = 5); Public has read only (r-- = 4).
6 طبقات نظام الملفات
6 File System Layers
يُبنى نظام الملفات في طبقات متدرجة من البرامج التطبيقية وصولاً إلى الأجهزة المادية، لتقليل التعقيد.
The file system is built in layers from application programs down to physical devices to reduce complexity.
يتكون نظام الملفات من الطبقات التالية (من الأعلى للأسفل):
- البرامج التطبيقية (Application Programs)
- نظام الملفات المنطقي (Logical File System): يدير البيانات الوصفية (Metadata)، يترجم اسم الملف إلى رقم/مقبض باستخدام كتلة تحكم الملف (FCB/inodes)، ويدير الحماية والأدلة.
- وحدة تنظيم الملفات (File-organization module): تفهم الملفات والعناوين المنطقية، وتترجم رقم الكتلة المنطقية إلى رقم كتلة مادية. تدير المساحة الحرة.
- نظام الملفات الأساسي (Basic File System): يرسل أوامر مثل 'استرجع الكتلة 123' إلى مشغل الجهاز، ويدير الذاكرة المخبئية (Caches) والمخازن المؤقتة (Buffers).
- التحكم في الإدخال/الإخراج (I/O Control): مشغلات الأجهزة (Device Drivers) التي تدير الأجهزة المادية وترسل أوامر منخفضة المستوى.
- الأجهزة (Devices).
The file system consists of the following layers (top to bottom):
- Application Programs
- Logical File System: Manages metadata, translates file name into file number/handle using File Control Blocks (FCB/inodes), and manages protection and directories.
- File-organization module: Understands files and logical addresses, translates logical block # to physical block #. Manages free space.
- Basic File System: Issues commands like 'retrieve block 123' to device drivers, manages memory buffers and caches.
- I/O Control: Device drivers that manage physical devices and output low-level hardware commands.
- Devices.
التصميم الطبقي يقلل التعقيد والتكرار، ولكنه يضيف عبئاً إضافياً (Overhead) قد يقلل من الأداء بسبب كثرة استدعاءات الدوال بين الطبقات.
Layering reduces complexity and redundancy but adds overhead that can decrease performance due to multiple function calls across layers.
في أي طبقة يتم تحويل العنوان المنطقي للملف إلى عنوان مادي على القرص؟ In which layer is the logical address of a file translated into a physical address on the disk?
في وحدة تنظيم الملفات (File-organization module).
In the File-organization module.
7 هياكل نظام الملفات في الذاكرة
7 In-Memory File System Structures
لتسريع العمليات، يحتفظ نظام التشغيل بجداول في الذاكرة الرئيسية مثل جدول الملفات المفتوحة لتجنب قراءة القرص باستمرار.
To speed up operations, the OS keeps tables in main memory, like the open-file table, to avoid constant disk reads.
الهياكل الموجودة في الذاكرة تشمل:
- جدول التثبيت (Mount table): يخزن معلومات عن أنظمة الملفات المثبتة ونقاط التثبيت.
- جدول الملفات المفتوحة على مستوى النظام (System-wide open-file table): يحتوي على نسخة من FCB لكل ملف مفتوح حالياً ومعلومات أخرى.
- جدول الملفات المفتوحة لكل عملية (Per-process open-file table): يحتوي على مؤشرات تشير إلى الإدخالات المناسبة في جدول النظام العام، بالإضافة إلى معلومات خاصة بالعملية (مثل مؤشر القراءة/الكتابة الحالي).
In-memory structures include:
- Mount table: Stores file system mounts, mount points, and types.
- System-wide open-file table: Contains a copy of the FCB of each currently open file and other info.
- Per-process open-file table: Contains pointers to appropriate entries in the system-wide table, along with process-specific info (like current read/write pointer).
فصل جدول النظام العام عن جدول العملية الفردية يوفر الذاكرة ويسمح لعدة عمليات بمشاركة نفس الملف المفتوح (نفس الـ FCB) مع الاحتفاظ بمؤشرات قراءة/كتابة مستقلة لكل عملية.
Separating the system-wide table from the per-process table saves memory and allows multiple processes to share the same open file (same FCB) while maintaining independent read/write pointers for each process.
ماذا يحدث في الذاكرة عند استدعاء دالة `open()` لملف؟ What happens in memory when the `open()` function is called for a file?
يبحث النظام في الدليل على القرص، وينسخ الـ FCB الخاص بالملف إلى جدول الملفات المفتوحة العام، ثم ينشئ إدخالاً في جدول العملية يشير إلى الجدول العام.
The OS searches the directory on disk, copies the file's FCB into the system-wide open-file table, and creates an entry in the per-process table pointing to the system-wide entry.
8 تنفيذ الأدلة
8 Directory Implementation
يمكن تنفيذ الأدلة كقائمة خطية بسيطة (بطيئة) أو كجدول تجزئة (سريع ولكن معقد).
Directories can be implemented as a simple linear list (slow) or a hash table (fast but complex).
- القائمة الخطية (Linear List): قائمة بأسماء الملفات مع مؤشرات لكتل البيانات. سهلة البرمجة ولكنها تستهلك وقتاً طويلاً في التنفيذ (وقت بحث خطي). يمكن تحسينها باستخدام قائمة مرتبة أبجدياً أو شجرة B+.
- جدول التجزئة (Hash Table): قائمة خطية مدمجة مع هيكل بيانات تجزئة. يقلل بشكل كبير من وقت البحث في الدليل. من عيوبه حدوث التصادمات (Collisions) عندما ينتج عن اسمين نفس قيمة التجزئة، ويكون فعالاً فقط إذا كانت الإدخالات ذات حجم ثابت، أو يتطلب استخدام تقنية السلسلة (Chained-overflow).
- Linear List: A list of file names with pointers to data blocks. Simple to program but time-consuming to execute (linear search time). Could be improved by keeping it ordered alphabetically via linked list or B+ tree.
- Hash Table: Linear list with a hash data structure. Greatly decreases directory search time. Drawbacks include collisions (two file names hashing to the same location) and it is only good if entries are fixed size, or requires chained-overflow.
في الأنظمة الحديثة، تُفضل أشجار B-trees أو B+ trees لتنفيذ الأدلة لأنها توفر بحثاً وإدراجاً وحذفاً بكفاءة O(log n) وتتعامل بشكل ممتاز مع التخزين على الأقراص.
In modern systems, B-trees or B+ trees are preferred for directory implementation because they provide O(log n) search, insertion, and deletion, and are highly optimized for disk storage.
لماذا لا تُستخدم جداول التجزئة دائماً لتنفيذ الأدلة رغم سرعتها؟ Why aren't hash tables always used for directory implementation despite their speed?
بسبب تعقيد التعامل مع التصادمات، وصعوبة دعم أحجام متغيرة لأسماء الملفات، وعدم قدرتها على عرض الملفات بترتيب أبجدي بسهولة.
Due to the complexity of handling collisions, difficulty in supporting variable-length file names, and their inability to easily list files in alphabetical order.
9 طرق تخصيص الكتل
9 Allocation Methods
يحدد نظام التشغيل كيفية تخزين الملفات على القرص إما ككتلة واحدة متصلة (Contiguous)، أو كسلسلة مترابطة (Linked)، أو باستخدام جدول فهارس (Indexed).
The OS determines how to store files on disk: as one continuous chunk (Contiguous), a chained sequence (Linked), or using an index table (Indexed).
- التخصيص المتجاور (Contiguous): يحتل الملف مجموعة من الكتل المتتالية. يوفر أفضل أداء وسهل الإدارة (يحتاج فقط موقع البداية والطول). مشاكله: إيجاد مساحة كافية، معرفة حجم الملف مسبقاً، والتجزئة الخارجية (External fragmentation).
- التخصيص المترابط (Linked): كل ملف هو قائمة مرتبطة من الكتل. لا توجد تجزئة خارجية. مشاكله: بطيء جداً في الوصول العشوائي، وموثوقية ضعيفة (تلف مؤشر واحد يفسد الملف). FAT هو تحسين لهذه الطريقة بوضع المؤشرات في جدول بداية القرص.
- التخصيص المفهرس (Indexed): يمتلك كل ملف كتلة فهرس (Index block) تحتوي على مؤشرات لجميع كتل البيانات. يدعم الوصول العشوائي ولا يعاني من تجزئة خارجية، لكنه يستهلك مساحة إضافية لكتلة الفهرس.
- Contiguous: File occupies a set of contiguous blocks. Best performance, simple (needs starting location and length). Problems: finding space, knowing file size in advance, and external fragmentation.
- Linked: Each file is a linked list of blocks. No external fragmentation. Problems: slow random access, reliability (one bad pointer ruins the file). FAT is a variation storing pointers in a table at the volume start.
- Indexed: Each file has its own index block of pointers to data blocks. Supports random access, no external fragmentation, but has index block overhead.
للملفات الكبيرة جداً في التخصيص المفهرس، تُستخدم آليات مثل: المخطط المترابط (Linked scheme) لربط كتل الفهارس، أو المخطط متعدد المستويات (Multi-level indexing).
نظام UNIX UFS يستخدم مخططاً هجيناً (Combined Scheme) يحتوي على مؤشرات مباشرة، وأحادية، وثنائية، وثلاثية غير مباشرة لدعم ملفات بأحجام هائلة مع الحفاظ على سرعة الملفات الصغيرة.
For very large files in Indexed allocation, mechanisms like Linked scheme (linking index blocks) or Multi-level indexing are used.
UNIX UFS uses a Combined Scheme with direct, single, double, and triple indirect pointers to support massive files while keeping small files fast.
| Contiguous | Linked | Indexed | |
|---|---|---|---|
| الوصول العشوائي (Random Access) Random Access | ممتاز وسريع Excellent and fast | بطيء جداً Very slow | جيد (يتطلب قراءة الفهرس) Good (requires reading index) |
| التجزئة الخارجية (External Fragmentation) External Fragmentation | يعاني منها بشدة Suffers heavily | لا توجد None | لا توجد None |
| العبء الإضافي (Overhead) Overhead | قليل جداً Minimal | مؤشرات في كل كتلة Pointers in every block | كتلة فهرس كاملة لكل ملف Entire index block per file |
لماذا يعتبر نظام UNIX UFS الهجين مثالياً لمعظم أنظمة الملفات؟ Why is the UNIX UFS combined scheme ideal for most file systems?
لأن معظم الملفات في النظام تكون صغيرة الحجم، والمؤشرات المباشرة توفر وصولاً سريعاً جداً لها. وفي نفس الوقت، يوفر النظام القدرة على تخزين ملفات ضخمة جداً عند الحاجة باستخدام المؤشرات غير المباشرة.
Because most files in a system are small, and direct pointers provide extremely fast access to them. At the same time, it provides the capability to store massive files when needed using indirect pointers.
10 إدارة المساحة الحرة
10 Free-Space Management
يتتبع نظام التشغيل الكتل الفارغة على القرص باستخدام مصفوفة بتات (Bit Vector) أو قائمة مرتبطة (Linked List).
The OS tracks empty disk blocks using a Bit Vector (bitmap) or a Linked List.
يحتفظ نظام الملفات بقائمة المساحات الحرة. الطرق تشمل:
- متجه البتات (Bit Vector / Bit Map): كل كتلة تُمثل ببت واحد (1 = حر، 0 = مشغول). يسهل العثور على كتل متجاورة، لكنه يتطلب مساحة إضافية في الذاكرة.
- القائمة المرتبطة (Linked List): ربط الكتل الحرة معاً. لا يوجد هدر للمساحة، لكن يصعب الحصول على مساحة متجاورة وبطيء في التصفح.
- التجميع (Grouping): تخزين عناوين n-1 من الكتل الحرة في أول كتلة حرة، لتسريع الوصول.
- العد (Counting): الاحتفاظ بعنوان أول كتلة حرة وعدد الكتل الحرة المتجاورة التي تليها.
- خرائط المساحة (Space Maps): تُستخدم في ZFS للأنظمة الضخمة، حيث تُقسم المساحة إلى وحدات (metaslabs) وتُدار باستخدام سجلات (Logs) وأشجار متوازنة.
The file system maintains a free-space list. Methods include:
- Bit Vector / Bit Map: Each block is represented by 1 bit (1 = free, 0 = occupied). Easy to get contiguous files, but requires extra memory space.
- Linked List: Linking free blocks together. No waste of space, but hard to get contiguous space and slow to traverse.
- Grouping: Storing addresses of next n-1 free blocks in the first free block.
- Counting: Keeping the address of the first free block and the count of following contiguous free blocks.
- Space Maps: Used in ZFS for massive systems, dividing space into metaslabs managed via logs and balanced trees.
حساب رقم الكتلة في متجه البتات يتم عبر المعادلة: `(عدد البتات لكل كلمة) * (عدد الكلمات ذات القيمة 0) + إزاحة أول بت قيمته 1`.
المعالجات الحديثة تمتلك تعليمات برمجية مدمجة لإرجاع إزاحة أول بت '1' بسرعة فائقة.
Block number calculation in a bit vector: `(number of bits per word) * (number of 0-value words) + offset of first 1 bit`.
Modern CPUs have built-in instructions to return the offset of the first '1' bit extremely fast.
إذا كان حجم القرص 1 تيرابايت وحجم الكتلة 4 كيلوبايت، كم حجم الذاكرة المطلوب لتخزين متجه البتات؟ If the disk size is 1 Terabyte and block size is 4 Kilobytes, how much memory is required to store the bit vector?
عدد الكتل = 1 تيرابايت / 4 كيلوبايت = 2^40 / 2^12 = 2^28 كتلة. نحتاج 2^28 بت، أي ما يعادل 32 ميجابايت من الذاكرة.
Number of blocks = 1 TB / 4 KB = 2^40 / 2^12 = 2^28 blocks. We need 2^28 bits, which equals 32 Megabytes of memory.