ระบบแฟ้มข้อมูล

ระบบแฟ้ม

แฟ้ม หรือไฟล์ (File)

หมายถึง กลุ่มของสารสนเทศที่สัมพันธ์กัน ซึ่งความสัมพันธ์เหล่านั้นกำหนดโดยผู้สร้างแฟ้ม และอาจใช้เก็บอะไรก็ได้

หมายถึง กลุ่มของระเบียนที่สัมพันธ์กัน เป็นเรื่องเดียวกัน

หมายถึง สิ่งที่บรรจุข้อมูลต่าง ๆ ไว้ในที่เดียวกัน

หมายถึง A named collection of related information that is recorded on secondary storage.

หมายถึง A collection of bytes stored as an individual entity. All data on disk is stored as a file with an assigned file name that is unique within the folder (directory) it resides in. To the computer, a file is nothing more than a string of bytes. The structure of a file is known to the software that manipulates it. For example, database files are made up of a series of records. Word processing files contain a continuous flow of text.

1. โครงสร้างแฟ้มข้อมูล

                 การจัดโครงสร้างของแฟ้มข้อมูลสามารถจัดได้หลายรูปแบบ แต่ส่วนใหญ่แล้วในทางปฏิบัติ ระบบปฏิบัติการมีวิธีการจัดโครงสร้างที่นิยมใช้งานใน 3 ลักษณะ คือ

1.             การเก็บข้อมูลแบบไม่มีโครงสร้าง        โดยจะเก็บข้อมูลเรียงเป็นลำดับต่อเนื่องกันไปดังแสดงในรูปที่  (ก) โดยแต่ละชิ้นข้อมูลมีขนาดเป็นไบต์ ซึ่งในการเก็บข้อมูลลักษณะนี้ระบบปฏิบัติการจะไม่สนใจว่าในแฟ้มมีข้อมูลอะไรอยู่ จะมองข้อมูลในรูปของไบต์ทั้งหมด ระบบปฏิบัติการดอสและยูนิกซ์ต่างก็มีโครงสร้างแฟ้มข้อมูลในลักษณะนี้ใช้งาน ซึ่งทำให้ผู้เขียนโปรแกรมสามารถจัดเก็บข้อมูลใดๆก็ได้ลงในแฟ้มข้อมูลโดยไม่จำเป็นต้องมีข้อกำหนดพิเศษใดๆ

2.             การเก็บข้อมูลแบบมีโครงสร้าง โดยจะเก็บข้อมูลในลักษณะของกลุ่มข้อมูล ซึ่งเรียกว่า เรคอร์ด ดังแสดงในรูปที่  (ข) โดยเรคอร์ดจะมีขนาดคงที่ ในการอ่านหรือบันทึกข้อมูลจะกระทำทีละ เรคอร์ด โดยกระทำกับเรคอร์ดใดในแฟ้มก็ได้

3.             การเก็บข้อมูลแบบต้นไม้ ดังแสดงในรูปที่  (ค) วิธีการนี้จะมีการแบ่งส่วนของสื่อบันทึกข้อมูลของเป็นส่วนๆ เรียกว่าบล็อก โดยแต่ละบล็อกจะมีหลายๆ เรคอร์ด และแต่ละ เรคอร์ด มีคีย์ ( Key ) เพื่อใช้ในการจำแนกเรคอร์ด ในการเข้าถึงข้อมูลในแฟ้มข้อมูลจะไม่ได้เข้าถึงข้อมูลแบบลำดับแต่การเข้าถึงข้อมูล จะเป็นการเข้าถึงโดยอาศัยคีย์ ซึ่งเป็นการเข้าถึงข้อมูลเรคอร์ดนั้นโดยตรง โดยโครงสร้างของต้นไม้จะเรียงลำดับโดยคีย์ ซึ่งทำให้การเข้าถึงข้อมูลทำได้รวดเร็วมากยิ่งขึ้น โดยอาศัยคีย์ในการเข้าถึง

(ก)

(ข)

(ค)

ภาพแสดงโครงสร้างของแฟ้มข้อมูลแบบต่างๆ

                ระบบปฏิบัติการที่มีประสิทธิภาพ จะต้องเป็นสามารถทำให้ผู้ใช้เป็นอิสระจากอุปกรณ์ (Device Independent ) ดังนั้นการเข้าถึงแฟ้มเพื่อใช้งานข้อมูลของใช้จะต้องเหมือนกันหรือมีรูปแบบเดียวกันหมดไม่ว่าจะเป็นแฟ้มหรืออุปกรณ์ใดๆ เช่น โปรแกรมที่อ่านข้อมูลจากแฟ้ม อินพุตเข้ามาเรียงลำดับข้อมูล และเขียนผลลัพธ์กลับไปที่แฟ้มเอาต์พุต ควรใช้ได้กับแฟ้มบนฟล็อปปี้ดิสก์หรือแฟ้มบนฮาร์ดดิสก์ และควรเขียนเอาต์พุตออกทางแฟ้ม จอภาพ หรือเครื่องพิมพ์ ได้โดยไม่ต้องเขียนโปรแกรมให้ตรวจสอบในแต่ละกรณี

2.  ชนิดของแฟ้มข้อมูล

                ระบบปฏิบัติการโดยทั่วไป จะสนับสนุนการทำงานกับแฟ้มได้หลายชนิด เช่น แฟ้มข้อมูลทั่วไป ไดเรกทอรี่ แฟ้มของอักขระ หรือแฟ้มของกลุ่มข้อมูล เป็นต้น โดยมีรายละเอียดของแฟ้มแต่ละชนิด ดังนี้

î        แฟ้มทั่วไป เป็นแฟ้มที่เก็บข้อมูลต่างๆ ของผู้ใช้ ซึ่งอาจจะเก็บในลักษณะใดลักษณะหนึ่งตามที่ได้แสดงไว้ในรูป

î        ไดเรกทอรี่ เป็นแฟ้มของระบบซึ่งใช้ในการจัดการโครงสร้างของระบบแฟ้มข้อมูล เช่น การจัดกลุ่มของแฟ้มประเภทเดียวกัน หรือมีความเกี่ยวข้องกันไว้ในไดเรกทอรี่เดียวกัน เป็นต้น ซึ่งจะกล่าวถึงรายละเอียดของไดเรกทอรี่ต่อไป

î        แฟ้มอักขระ แฟ้มอักขระจะมีความเกี่ยวข้องกับการรับหรือการแสดงผลข้อมูลผ่านทางพอร์ทอนุกรมซึ่งจะมีการกระทำกับข้อมูลคราวละ 1 อักขระ เช่น แป้นพิมพ์ เป็นต้น

î        แฟ้มของกลุ่มข้อมูล เป็นแฟ้มที่มีการดำเนินการกับข้อมูลในลักษณะ บล็อค หรือกระทำกับข้อมูลในแฟ้มคราวละ 1 กลุ่มข้อมูล เช่น ดิสก์ เป็นต้น

                สำหรับในบทนี้จะกล่าวเน้นเฉพาะแฟ้มทั่วไปเท่านั้น ข้อมูลที่เก็บในแฟ้มทั่วไป อาจจะอยู่ในรูปของรหัสแอสกี หรือที่เรียกว่าแฟ้มแอสกี ( ASCII File )โดยจะมีการเก็บข้อมูลเป็นบรรทัด และแต่ละบรรทัดจะแยกออกจากกันโดยอักขระขึ้นบรรทัดใหม่ ( Carriage Return Character ) หรืออักขระเลื่อนบรรทัด ( Line Feed Character ) และแต่ละบรรทัดก็ไม่จำเป็นที่จะต้องมีจำนวนตัวอักขระเท่ากัน แฟ้มแอสกีนี้สามารถแสดงผลข้อมูลได้เหมือนกับข้อมูลที่มีอยู่ในแฟ้ม กล่าวคือ ข้อมูลที่แสดงผลออกมาไม่ว่าจะโดยอุปกรณ์แสดงผลแบบใด จะมีลักษณะเหมือนกับข้อมูลในแฟ้มนั้นทุกประการ เราสามารถสร้างหรือแก้ไขแฟ้มแอสกีได้โดยใช้อีดิเตอร์ทั่วไป ซึ่งทำได้สะดวกและรวดเร็ว จึงทำให้โปรแกรมใช้งานทั่วๆ ไป นิยมทำงานกับข้อมูลโดยใช้แฟ้มแอสกี นอกจากการที่ทำงานได้ง่ายและสะดวกแล้ว ยังสามารถย้ายข้อมูลไปทำงานกับโปรแกรมอื่นได้ง่าย สำหรับแฟ้มไบนารี่ ( Binary File ) เป็นแฟ้มที่มีข้อมูลภายในไม่ใช่รหัสแอสกี เป็นแฟ้มที่สามารถปฏิบัติการได้

ภาพแสดงโครงสร้างของแฟ้มปฏิบัติการของระบบปฏิบัติการยูนิกซ์

2.  ไดเรกทอรี่ (Directory)

ในการสร้างชื่อไฟล์ในปัจจุบันจะมีการกำหนดชื่อไฟล์โดยมีส่วนประกอบ 2 ส่วน คือส่วนชื่อ และส่วนนามสกุล โดยส่วนชื่อจะเป็นคำภาษาอังกฤษ หรือภาษาใดๆที่ระบบปฏิบัติการเข้าใจ ในระบบ DOS จะอนุญาตให้ตั้งชื่อได้ไม่เกิน 8 ตัวอักษร แต่ในวินโดว์ได้กำหนดความยาวชื่อได้มากกว่า ส่วนนามสกุล จะเป็นส่วนบอกชนิดของไฟล์นั้นๆ โดยทั่วไปจะมีความยาวอยู่ระหว่าง 0 ถึง 3 ตัวอักษร แต่อาจมีบางชนิดที่ยาว 4 หรือ 5 ตัวอักษร ในการตั้งชื่อไฟล์ เราจะเขียนส่วนของชื่อ และนามสกุลต่อกัน โดยมีเครื่องหมายจุด(.) เป็นตัวคั่น

ชนิดแฟ้มข้อมูล	ลักษณะนามสกุล	หน้าที่
Executable	Exe, Com, Bin	ประมวลผลคำสั่งภาษาเครื่อง
Object	Obj, O	ทำหน้าที่คอมไพล์, หรือเป็นภาษาเครื่อง
Source Code	C, P, Pas, 177, Asm, A	เป็น Source Code ของภาษาคอมพิวเตอร์
Batch	Bat, Sh	เป็นชุดคำสั่ง
Text	Txt, Doc	ข้อมูลที่เป็นข้อความ
Word Processor	Wp, Tex, Rrf	รูปแบบของการประมวลผลข้อความ
Library	Lib, A	ข้อมูลเกี่ยวกับ Library หรือ Routine
Print or View	Ps, Dvi, Gif, Jpg	ไฟล์ที่เก็บข้อมูลเป็นรหัส ASCII หรือฐาน 2
Archive	Arc, Zip, Rar	เป็นไฟล์ หรือกลุ่มไฟล์ที่ได้ผ่านการบีบอัดข้อมูลไว้

ไดเรกทอรี่ เป็นแฟ้มประเภทหนึ่งซึ่งทำหน้าที่เก็บรวบรวมรายชื่อของแฟ้ม และข้อมูลบางอย่างที่สำคัญของแฟ้มเอาไว้ ในระบบปฏิบัติการทุกระบบจะต้องมีไดเรกทอรี่เพื่อเก็บรายชื่อแฟ้มต่างๆ เอาไว้  ผู้ใช้สามารถสร้าง ลบ ไดเรกทอรี่ได้ 

โครงสร้างของระบบไดเรกทอรี่

                โครงสร้างของไดเรกทอรี่ประกอบด้วยหน่วยย่อยหลายหน่วย แต่ละหน่วยจะเก็บข้อมูลของแฟ้ม 1 แฟ้ม โดยข้อมูลที่เก็บคือ ชื่อแฟ้ม แอตริบิวของแฟ้ม และตำแหน่งที่เก็บแฟ้มนั้น

                นอกจากนี้การเก็บข้อมูลของแฟ้มอาจจะทำได้โดยการเก็บชื่อของแฟ้มใว้ในไดเรกทอรี่ แต่จะเก็บรายละเอียดของแฟ้มไว้ที่อื่น  ดังแสดงในภาพด้านล่าง เมื่อมีการเปิดแฟ้มข้อมูล ระบบปฏิบัติการจะทำการค้นหาในไดเรกทอรี่จนกระทั่งพบแฟ้มที่ต้องการจึงทำการอ่านรายละเอียดของแฟ้ม 

                ในการจัดไดเรกทอรี่ของระบบปฏิบัติการแต่ละระบบจะแตกต่างกันออกไป แบบที่ง่ายและสะดวกที่สุด คือให้ระบบมีไดเรกทอรี่อยู่เพียงไดเรกทอรี่เดียว และให้แฟ้มทุกแฟ้มอยู่ใน ไดเรกทอรี่เดียวกัน ระบบนี้เรียกว่าระบบไดเรกทอรี่เดี่ยว ( Single Directory ) หรือไดเรกทอรี่ 1 ระดับ ( 1 Level Directory ) ดังแสดงในภาพด้านล่าง (ก) ไดเรกทอรี่แบบนี้ไม่ค่อยสะดวกในการใช้งาน ถ้ามีผู้ใช้หลายคน แต่ละคนมีแฟ้มหลายแฟ้มหลายชนิด แฟ้มทั้งหมดนี้จะอยู่ปนกันไม่สามารถจัดแบ่งแยกแฟ้มของผู้ใช้แต่ละคนออกจากกัน ถ้าเกิดกรณีที่มีการสร้างแฟ้มของผู้ใช้คนหนึ่งตรงกับแฟ้มของผู้ใช้คนอื่น (มีชื่อและส่วนขยายเดียวกัน) อาจทำให้แฟ้มของผู้นั้นทำลายแฟ้มเก่าที่มีอยู่แล้ว (โดยเขียนทับ) หรืออาจทำให้การสร้างแฟ้มนั้นทำไม่ได้

                ในระบบปฏิบัติการของไมโครคอมพิวเตอร์รุ่นเก่า ๆ เท่านั้น ที่มีการทำระบบไดเรกทอรี่เดี่ยวเพื่อแก้ปัญหาของการตั้งชื่อแฟ้มตรงกันและแฟ้มของผู้ใช้ทุกคนอยู่ปนกัน ผู้ออกแบบระบบปฏิบัติการในระยะต่อมาจึงพัฒนาโครงสร้างของระบบไดเรกทอรี่ใหม่ ให้ผู้ใช้ไดเรกทอรี่แต่ละคนสามารถสร้างไดเรกทอรี่ของตนเองได้ 1 ไดเรกทอรี่เรียกว่าเป็นไดเรกทอรี่ย่อย ( Sub-Directory ) ไดเรกทอรี่ย่อยนี้จะอยู่ภายใต้ไดเรกทอรี่เดียวกัน แสดงในรูปด้านล่าง (ข) เรียกว่า ไดเรกทอรี่ราก ( Root Directory ) ไดเรกทอรี่หนึ่งๆ อาจจะจะมีไดเรกทอรี่ย่อยได้หลายไดเรกทอรี่ และภายในแต่ละไดเรกทอรี่นี้มีแฟ้มซึ่งผู้ใช้สามารถตั้งชื่อแฟ้มและชนิดให้ตรงกับแฟ้มของผู้ใช้คนอื่นได้ถ้าแฟ้มทั้ง 2 นี้อยู่ต่างไดเร็กทอรนี่กัน เราเรียกระบบไดเรกทอรี่แบบนี้ว่า ระบบไดเรกทอรี่ 2 ระดับ ( 2 Level Directory ) อย่างไรก็ตามไดเรกทอรี่แบบนี้ก็ยังมีปัญหากับผู้ใช้ที่มีแฟ้มมากและต้องการจัดหมวดหมู่ของแฟ้ม เพื่อความสะดวกในการใช้งาน และเพื่อแก้ไขปัญหาที่เกิดกับผู้ใช้ในระบบ ไดเรกทอรี่ 2 ระดับ ระบบปฏิบัติการในรุ่นหลังๆ จึงยอมให้ผู้ใช้สามารถสร้างไดเรกทอรี่ย่อยของตนเองได้มากตามที่ต้องการ ดังแสดงในภาพด้านล่าง(ค) ทำให้ผู้ใช้สามารถแบ่งแยกแฟ้มประเภทเดียวกันให้อยู่ในไดเรกทอรี่เดียวกันไม่ปะปนรวมกับแฟ้มประเภทอื่นๆ ทำให้ไดเรกทอรี่มีลักษณะเหมือนเป็นโครงสร้างแบบต้นไม้ เราเรียกระบบไดเรกทอรี่นี้ว่าไดเรกทอรี่หลายระดับ

3. เส้นทาง (Path)

                ในการอ้างถึงแฟ้มในไดเรกทอรี่ หรือการอ้างไดเรกทอรี่ย่อยในไดเรกทอรี่ จะอ้างโดยการบอกเส้นทางหรือพาธ ( Path ) ของแฟ้มนั้นๆ เพื่อให้ระบบรู้ว่าเรากำลังอ้างถึงแฟ้มในไดเรกทอรี่ใด ซึ่งจะทำให้สามารถเข้าถึงแฟ้มที่ต้องการได้ถูกต้อง เช่น กรณีที่มีแฟ้มคนละแฟ้มซึ่งมีชื่อเดียวกันแต่อยู่ในคนละไดเรกทอรี่ การบอกเส้นทางจะทำให้ระบบทราบว่าผู้ใช้ต้องการจะอ้างถึงแฟ้มใด การอ้างถึงแฟ้มมี 2 วิธี คือ การอ้างด้วยเส้นทางสมบูรณ์ ( Absolute Path Name ) หรือเส้นทางสัมพัทธ์ ( Relative Path Name ) การอ้างถึงแฟ้มโดยใช้เส้นทางสมบูรณ์เป็นการอ้างถึงแฟ้มโดยเริ่มต้นจากไดเรกทอรี่รากแล้วตามด้วยชื่อไดเรกทอรี่ย่อยต่างๆ ไล่มาตามลำดับชั้นของไดเรกทอรี่จนกระทั่งถึงไดเรกทอรี่ย่อยที่เก็บแฟ้มนั้นแล้วจึงตามด้วยชื่อแฟ้ม เช่นในดอสจะใช้เครื่องหมาย "\" แทนไดเรกทอรี่ราก หรือ ในยูนิกซ์ใช้เครื่องหมาย "/" แทนไดเรกทอรี่ราก เช่นการอ้างเส้นทางสมบูรณ์ในระบบปฏิบัติการดอสจะมีลักษณะการอ้างดังนี้

\textbook\os\file.txt

                จากตัวอย่างเครื่องหมาย '\' ตัวแรกหมายถึงไดเรกทอรี่ราก textbook เป็นไดเรกทอรี่ย่อยระดับแรก os  เป็นไดเรกทอรี่ย่อยระดับที่สอง และ file.txt คือชื่อแฟ้มที่ต้องการอ้าง 

                ไดเรกทอรี่ย่อยจะมีไดเรกทอรี่ที่ชื่อ "." และ ".." ไดเรกทอรี่ โดย "." จะหมายถึงตัวไดเรกทอรี่ย่อยนั้นเอง และ ".." หมายถึงไดเรกทอรี่ที่อยู่เหนือขึ้นไปหนึ่งระดับ เช่นถ้าไดเรกทอรี่ปัจจุบันคือ os ดังนั้น "." จะหมายถึงตัวไดเรกทอรี่ os และ ".." หมายถึงไดเรกทอรี่ textbook ดังนั้นหากไดเรกทอรี่ปัจจุบันคือ os  และต้องการอ้างถึงแฟ้ม unix ในไดเรกทอรี่ research โดยการอ้างเส้นทางสัมพัทธ์ระบบปฏิบัติการดอสจะทำได้ดังนี้

..\..\research\unix

จากตัวอ ย่างเครื่องหมาย ".." ตัวแรก หมายถึงให้ย้อนกลับไปในไดเรกทอรี่ชั้นบน 1 ระดับ ซึ่งก็คือย้อนกลับไปที่ไดเรกทอรี่ textbook (ถึงขั้นนี้การทำงานยังคงอยู่ในไดเรกทอรี่ textbook อยู่) ".." ตัวที่สองคือการให้ย้อนกลับไปไดเรกทอรี่ที่เหนือกว่า textbook อีก 1 ระดับ research เป็นการบอกเส้นทางว่าให้เข้าไปในไดเรกทอรี่ research

3. การเข้าถึงแฟ้มข้อมูล(Access Method)

 

3.1  การเข้าถึงข้อมูลแบบเรียงลำดับ(Sequential Access)

ในการเข้าถึงข้อมูลแบบเรียงลำดับเป็นวิธีการแก้ไขที่ธรรมดาที่สุด เช่นตัวแกไข(Editor) และคอมไพล์เลอร์(Compiler) จะมีวิธีการเข้าถึงข้อมูลแบบนี้

การทำงานบนแฟ้มแบบนี้ คือ การอ่านและการเขียน การอ่านจะอ่านส่วนถัดไปของแฟ้ม และเปลี่ยนค่าตัวชี้แฟ้มข้อมูลโดยอัตโนมัติตามตำแหน่งของ I/O เหมือนกับการเขียนแบบต่อท้ายข้อมูล แต่ละแฟ้มข้อมูลสามารถกลับไปเริ่มต้นใหม่ และบางระบบโปรแกรมอาจจะสามารถข้ามไปข้างหน้า หรือข้างหลัง

สำหรับการเข้าถึงข้อมูลแบบเรียงลำดับเป็นพื้นฐานการทำงานของเทปแม่เหล็ก

                                                      3.2  การเข้าถึงแบบสุ่ม random access
                             การเข้าถึงโดยสุ่มการเข้าถึงข้อมูลที่บันทึกไว้โดยสุ่มหมายความว่าเข้าถึงได้ทุก ๆ จุดได้โดยทันทีทันใด เป็นต้นว่าการเข้าถึงข้อมูลที่เก็บในจานบันทึกซึ่งจะใช้เวลาเท่ากันหมดไม่ว่าเก็บไว้ที่จุดไหนต่างกับการเข้าถึงข้อมูลที่เก็บไว้ในแถบบันทึกหรือเทปถ้าข้อมูลที่ต้องการอยู่ตอนปลายก็จะต้องรอให้เทปเดินหน้าไปจนถึงจุดนั้นเสียก่อนการเข้าถึงข้อมูลโดยวิธีนี้ จะมีหัวอ่าน/บันทึก (read head)ต่อกับก้านโลหะที่เคลื่อนเข้า/ออกได้ เหนือจานที่หมุนรอบแกนอีกทีหนึ่ง
เปรียบเทียบ) ถ้าเปรียบกับการฟังเพลงจากจานเสียงและเทปจะทำให้เข้าใจได้ง่ายขึ้น กล่าวคือ ถ้าเป็นเทปหรือแถบบันทึก
หากจะฟังเพลงที่อยู่ในลำดับท้าย ๆก็จะต้องรอให้เทปหมุนผ่านเพลงในลำดับแรก ๆ ไปก่อน แต่ถ้าเป็นจานเสียง
เราต้องการฟังเพลงใด ก็สั่งได้ทันทีดู sequential access เปรียบเทียบ

4. การจัดระบบแฟ้ม (File system)

หมายถึง สิ่งที่ผู้ใช้เกี่ยวข้องโดยตรง แต่มักไม่รู้ตัวเนื่องจากเป็นการอำนวยความสะดวกโดยระบบปฏิบัติการอย่างอัตโนมัติ ระบบแฟ้มเป็นฐานที่ทำให้เกิดการจัดการโปรแกรม และข้อมูลในทุกการดำเนินงานของระบบซอฟท์แวร์ที่เข้าควบคุมสื่อเก็บข้อมูล

ระบบแฟ้มประกอบด้วย 3 ส่วน คือ 1)รวมรวมแฟ้ม (Collection of Files) เก็บข้อมูลที่สัมพันธ์ให้ถูกอ้างอิงได้ในรูปแฟ้มข้อมูล 2)โครงสร้างแฟ้ม (Directory Structure) จัดการอำนวยการเข้าถึงแฟ้มและจัดกลุ่มอย่างเป็นระบบ 3)พาทิชัน (Partitions) ซึ่งแยกเป็นทางกายภาพ (Physically) หรือทางตรรก (Logically) ของระบบไดเรกทรอรี่ (Directory) โดยเนื้อหาในบทนี้จะกล่าวถึงแฟ้ม และโครงสร้างไดเรกทรอรี่ รวมถึงการป้องกันแฟ้ม จากการเข้าถึงในระบบ Multiple users และระบบ File sharing

วิธีการจัดเก็บข้อมูลที่ใช้กันใน OS ทุกตัวคือ จัดเก็บข้อมูลเป็นแฟ้มข้อมูลหรือไฟล์ (file) ไฟล์คือสิ่งที่บรรจุข้อมูล,โปรแกรมหรืออะไรก็ได้ที่ผู้ใช้ต้องการรวบรวมไว้เป็นชุดเดียวกัน การอ้างถึงไฟล์หรือข้อมูลต่าง ๆ ภายในไฟล์ของโปรแกรม จะไม่มีความเกี่ยวข้องกับแอดเดรสของโปรแกรมใด ๆ ทั้งสิ้น OS มีโอเปอร์เรชั่นพิเศษที่เรียกว่า system call ไว้ให้โปรแกรมเรียกใช้ เพื่อให้สามารถจัดการงานที่เกี่ยวกับไฟล์ได้

                 4.1  การจัดเก็บแฟ้มเรียงต่อเนื่องกันตลอดทั้งแฟ้ม ( Continuous Allocation )

                                เป็นแนวคิดพื้นฐานในการจัดเก็บแฟ้มข้อมูล โดยจะจัดเก็บแฟ้มข้อมูลในรูปของลำดับบล็อกที่ต่อเนื่องกัน    เช่นหากแต่ละบล็อกมีขนาด 1 กิโลไบต์ แฟ้มข้อมูลขนาด 50 กิโลไบต์ ก็ต้องใช้เนื้อที่ขนาด 50 กิโลไบต์ที่ต่อเนื่องกันในดิสก์ ซึ่งแนวคิดในการจัดเก็บข้อมูลแบบนี้จะมีข้อดี 2 ประการคือ มีโครงสร้างไม่ซับซ้อนและใช้งานง่าย เนื่องจากในระบบแฟ้มข้อมูลแบบนี้ไม่จำเป็นต้องมีการรักษาค่าต่างๆ ของดิสก์เลย เพียงแต่ทราบตำแหน่งเริ่มต้นของแฟ้มข้อมูลก็จะสามารถทำงานได้โดยการอ่านข้อมูลต่อเนื่องกันไปเรื่อยๆ จนกว่าจะสิ้นสุดแฟ้มข้อมูล และข้อดีประการที่สองคือในการอ่านข้อมูลทั้งแฟ้มนั้นสามารถทำได้โดยใช้คำสั่งอ่านข้อมูลเพียงคำสั่งเดียวก็จะสามารถอ่านข้อมูลที่มีในแฟ้มข้อมูลนั้นได้ทั้งหมด

        4.2  การจัดเก็บแฟ้มแบบตารางแฟต (File Allocation Table : FAT )

                                ในการจัดเก็บแฟ้มแบบแฟต  ระบบปฏิบัติการต้องมีวิธีที่จะทราบว่าแต่ละบล็อคของแฟ้มจะเก็บไว้ในบล็อคใดในดิสก์ และไม่จำเป็นที่ข้อมูลของแฟ้มเดียวกันจะอยู่ใน บล็อคที่ติดกัน ซึ่งจะต้องมีลิงก์เชื่อมระหว่างบล็อคที่เก็บข้อมูลของแฟ้มแฟ้มเดียวกัน ดังนั้นใน บล็อคขนาด 512 ไบต์ จะใช้ประโยชน์ในการเก็บข้อมูลของแฟ้มเพียง 510 ไบต์ ส่วนอีก 2 ไบต์ที่เหลือจะใช้ในการเก็บหมายเลขบล็อคลำดับถัดไปที่เก็บข้อมูลแฟ้มเดียวกัน ซึ่งในกรณีที่แฟ้มมีขนาดใหญ่จะทำให้ต้องใช้เวลามากในการเข้าถึงแฟ้ม เนื่องจากต้องย้ายไปยังบล็อคต่างๆ ที่เก็บข้อมูลของแฟ้มหลายบล็อค
                นอกจากการใช้ลิงก์ลิสต์ในการควบคุมบล็อคสำหรับเก็บแฟ้มแล้ว ยังมีวิธีการอื่นๆ ที่ช่วยลดปัญหาที่เกิดขึ้น คือการทำตารางเก็บค่าหมายเลขบล็อคแต่ละบล็อคที่เก็บแฟ้มไว้แทนการเก็บไว้ที่ท้ายบล็อคนั้นๆ ซึ่งเรียกว่าตารางการจัดสรรแฟ้มหรือที่เรียกกันทั่วไปว่าตารางแฟต ดังภาพด้านล่าง โดยทั่วไปตารางการจัดสรรแฟ้มจะถูกโหลดมาเก็บไว้ในหน่วยความจำทำให้สามารถเข้าถึงแฟ้มข้อมูลได้อย่างรวดเร็ว 

ภาพแสดงแฟ้มข้อมูลแบบตารางแฟต

                จากตัวอย่างตารางแฟต จะมีการเก็บหมายเลขบล็อคของแฟ้ม 2 แฟ้ม คือแฟ้มแรก เริ่มต้นที่บล็อคหมายเลข 6 แล้วตามด้วยบล็อคหมายเลข 4 หมายเลข 6 และ หมายเลข 2 ตามลำดับ สำหรับแฟ้มที่สองเริ่มที่บล็อคหมายเลข 8 แล้วตามด้วยบล็อคหมายเลข 16 หมายเลข 15 และ หมายเลข 7 ตามลำดับ วิธีการนี้เป็นวิธีการที่ใช้ในระบบปฏิบัติการดอส และจากการที่ตารางแฟตมีความสำคัญต่อการเข้าถึงแฟ้มดอสจึงออกแบบให้มีตารางแฟต 2 ตารางที่มีข้อมูลภายในเหมือนกันโดยอีกตารางเป็นตารางแฟตสำรองในกรณีที่ตารางแรกเกิดความเสียหาย  ระบบแฟ้มแบบบแฟต

4.3  การจัดระบบแฟ้มแบบเรด (RAID)

ผู้ออกแบบฮาร์ดแวร์ ได้พยายามปรับปรุงการทำงานของดิสก์ โดยการเพิ่มประสิทธิภาพในการทำงานเพิ่มความเชื่อถือได้ของการจัดเก็บแฟ้ม และเพิ่มความจุของดิสก์ ซึ่งในการเพิ่มประสิทธิภาพของการทำงานนั้น หมายถึงการเพิ่มอัตราเร็วของการขนถ่ายข้อมูล และความเร็วในการเข้าถึงข้อมูล (โดยการเพิ่มความเร็วในการหมุนของดิสก์ เพื่อลดเวลาในการเข้าถึงข้อมูลและเพิ่มอัตราเร็วในการขนถ่ายข้อมูล) นอกจากนี้ยังได้พยายามเพิ่มความหนาแน่นของข้อมูลในดิสก์ (เพิ่มความจุข้อมูล และลดเวลาในการขนถ่ายข้อมูล)

เรดแบบเงากระจก (Mirroring RAID)

แนวคิดในการทำงานแบบเงากระจก นี้เป็นความพยายามเพิ่มความเชื่อมั่นในระบบการจัดเก็บแฟ้ม โดยการติดตั้งดิสก์ 2 ตัว (หรืออาจจะมากกว่า) ซึ่งเป็นดิสก์ที่มีขนาดและคุณสมบัติเหมือนกัน เพื่อทำการเก็บข้อมูลชุดเดียวกัน ดังนั้นเมื่อมีการจัดเก็บแฟ้มหรือข้อมูลลงในดิสก์ แฟ้มหรือข้อมูลนั้นจะถูกนำไปจัดเก็บในดิสก์ทั้ง 2 ตัว ซึ่งดิสก์ทั้ง 2 ตัวนั้นก็จะมีข้อมูลที่เหมือนกันทุกประการ ดังนั้นหากเกิดความเสียหายของข้อมูลในดิสก์ตัวใดตัวหนึ่ง ดิสก์อีกตัวหนึ่งที่จะถูกเรียกใช้งานแทนทันที ซึ่งด้วยวิธีการลักษณะนี้จะช่วยเพิ่มความเชื่อถือได้ของการจัดเก็บแฟ้มได้มากยิ่งขึ้น

เรดแบบแบ่งส่วนแฟ้ม (Striping RAID)

แนวคิดในการทำงานแบบแบ่งส่วนของแฟ้มนี้เป็นความพยายามเพิ่มความความเร็วในการทำงานและเพิ่มอัตราการขนถ่ายข้อมูลให้สูงขึ้น โดยการแบ่งส่วนของแฟ้มออกเป็นส่วนๆ และกระจายแต่ละส่วนไปจัดเก็บในดิสก์แต่ละตัวของเรด (โดยจัดเก็บในตำแหน่งของบล็อคตำแหน่งเดียวกันหมด) และเมื่อต้องการเข้าถึงข้อมูลเพื่อนำมาใช้งานก็ทำการอ่านข้อมูลจากตำแหน่งดังกล่าวพร้อมกันในทุกดิสก์ (ซึ่งจะสามารถอ่านข้อมูลจากดิสก์ทุกตัวได้ในเวลาเดียวกัน) ทำให้อัตราเร็วในการขนถ่ายข้อมูลสูงขึ้น (ซึ่งการเพิ่มขึ้นของอัตราเร็วในการขนถ่ายข้อมูลนี้จะขึ้นอยู่กับจำนวนของดิสก์ที่ใช้ในการจัดเก็บข้อมูลด้วย) เพื่อให้มองเห็นภาพการทำงานของการใช้งานเรดแบบแบ่งส่วนของแฟ้มได้ชัดเจนยิ่งขึ้นจะขอยกตัวอย่างการทำงานดังต่อไปนี้ สมมุตว่าดิสก์ตัวหนึ่งมีความจุ 200 เมกกะไบต์ แบ่งออกเป็นบล็อค และแต่ละบล็อคมีขนาด 1 กิโลไบต์ และมีอัตราเร็วในการขนถ่ายข้อมูลเท่ากับ 0.344 มิลลิวินาทีต่อ 1 บล็อค เมื่อมีการนำดิสก์ดังกล่าวไปใช้งานในรูปแบบเรดโดยมีการติดตั้งดิสก์จำนวน 2 ตัวในการทำงานก็จะสามารถขนถ่ายข้อมูลได้คราวละ 2 บล็อค โดยแต่ละบล็อคมาจากดิสก์แต่ละตัว ดังนั้นอัตราการขนถ่ายข้อมูลโดยรวมก็จะสูงขึ้นจาก 2.98 เมกกะไบต์ต่อวินาที ( 1 กิโลไบต์ / 0.000344 ) เป็น 5.95 เมกกะไบต์ต่อวินาที (2 กิโลไบต์ / 0.000344) และอัตราเร็วในการขนถ่ายข้อมูลนี้จะเพิ่มขึ้นอีกหากมีการติดตั้งดิสก์ของเรดให้มากขึ้น

แหล่งอ้างอิง

http://www.tkc.ac.th/osunun/e-booksystem/u7_6.htm

http://www.school.net.th/library/create-web/10000/generality/10000-8587.html
http://www2.rtafa.ac.th/~cs102/c2/fdata.html

การติดตาย deadlock

การติดตาย

          ในระบบคอมพิวเตอร์มีทรัพยากรต่างๆ เชื่อมโยงอยู่มากมาย แต่ ณ เวลาหนึ่งอุปกรณ์แต่ละอย่างจะถูกใช้งานได้จากโปรเซสเพียงโปรเซสเดียวเท่านั้น นอกจากนี้จะพบว่าโปรแกรมประยุกต์ หรือการใช้คอมพิวเตอร์เพื่อการทำงานด้านต่างๆ จะมีความเกี่ยวพันกับทรัพยากรมากกว่า 1 อย่าง เช่น การอ่านข้อมูลจากดิสก์เพื่อส่งไปพิมพ์ที่เครื่องพิมพ์ จะเห็นว่ามีการใช้งานทั้งดิสก์และเครื่องพิมพ์ในเวลาเดียวกัน ซึ่งการทำงานในลักษณะนี้ในระบบโปรแกรมเดียวจะไม่มีปัญหาเกิดขึ้นเนื่องจากมีเพียง
โปรเซสเดียงที่ครองทรัพยากร ไม่มีโปรเซสอื่นมาใช้งานร่วมด้วย แต่ในระบบหลายโปรแกรมปัญหา
จะเกิดขึ้น เช่น มี 2 โปรเซสต้องการที่จะใช้งานเครื่องพิมพ์เพื่อพิมพ์แฟ้มที่เก็บในดิสก์ โดยโปรเซส A ร้องขอการใช้เครื่องพิมพ์และระบบปฏิบัติการมอบเครื่องพิมพ์ให้โปรเซส A แล้ว เมื่อโปรเซส A ได้ครอบเครื่องเครื่องพิมพ์ก็จะติดต่อไปยังดิสก์เพื่ออ่านข้อมูลมาพิมพ์ แต่ในขณะนั้น ดิสก์กำลังถูกครอบ
ครองโดยโปรเซส B ในการอ่านข้อมูลเพื่อมาพิมพ์ที่เครื่องพิมพ์ ดังนั้นโปรเซส A จึงต้องคอยจนกว่า
โปรเซส B จะใช้งานดิสก์เสร็จจึงจะอ่านข้อมูลจากดิสก์ได้ ในขณะที่โปรเซส B จะปลดปล่อยดิสก์ก็ต่อเมื่อได้ครองเครื่องพิมพ์ ซึ่งโปรเซส A กำลังครอบครองอยู่ และจะปลดปล่อยเครื่องพิมพ์ก็ต่อเมื่อได้ครองดิสก์ ซึ่งจะเห็นว่าทั้งสองโปรเซสกำลังคอยซึ่งกันและกัน แต่ไม่มีโปรเซสใดสามารถทำงานต่อได้ เหตุการณ์ลักษณะนี้เรียกว่าการติดตาย (deadlock)
การติดตายสามารถเกิดขึ้นได้จากเหตุการณ์หลายเหตุการณ์ นอกเหนือจากการร้องขอใช้อุปกรณ์ เช่นในระบบฐานข้อมูล หากมีโปรแกรมหนึ่งได้ทำการล็อคระเบียนใกระเบียนหนึ่งไว้เพื่อใช้งานซึ่งเป็นการป้งกันปัญหาการแบ่งกันเข้าใช้ทรัพยากร ซึ่งก็คือระเบียนที่ตนกำลังใช้งานอยู่ เช่น โปรเซส A ทำการล็อคระเบียน R1 และโปรเซส B ทำการล็อคระเบียน R2 และทั้งสองโปรเซสต่างพยายามที่จะล็อคระเบียนของอีกฝ่ายหนึ่งเพื่อใช้งาน ซึ่งการที่จะสามารถล็อคระเบียนใดได้นั้นระเบียนนั้นต้องไม่อยู่ระหว่างการถูกล็อคไว้โดยโปรเซสใด เหตุการณ์ลักษณะนี้จะนำมาซึ่งปัญหาการติดตายเช่นเดียวกัน ดังนั้นจึงสามารถกล่าวได้ว่า การติดตายสามารถเกิดขึ้นได้ทั้งกับทรัพยากรที่เป็นฮาร์ดแวร์ และทรัพยากรที่เป็นซอฟต์แวร์

การติดตาย (Deadlock)

         ในสภาพการทำงานแบบหลายโปรแกรม หลายโพรเซสอาจจะมีการแข่งกันเข้าใช้งานทรัพยากรที่มีอยู่จำกัด โพรเซสจะมีการร้องขอใช้งานทรัพยากรถ้าในขณะนั้นทรัพยากรไม่ว่างก็จะส่งผลให้โพรเซสนั้นรอจนกว่าจะได้เข้าทำงาน ดังนั้นจึงอาจเหตุกรณีที่โพรเซสถูกให้อยู่ในสถานะการรอไปไม่มีที่สิ้นสุดเนื่องจากทรัพยากรนั้นก็ถูกร้องขอจากโพรเซสอื่นที่รออยู่เช่นกัน เช่นนี้เรียกว่าการติดตาย (Deadlock)



          ทรัพยากรในระบบมีอยู่อย่างจำกัดในการใช้งาน ดังนั้นจึงต้องเกิดการแย่งเข้าใช้ทรัพยากรนั้น ชนิดของ    ทรัพยากรในที่นี้แบ่งออกเป็น เนื้อที่ว่างในหน่วยความจำ เวลาในการประมวลผล ไฟล์ และอุปกรณ์ I/O เมื่อโพรเซสต้องการเข้าใช้ทรัพยากรต้องมีการร้องขอแล้วก็ออกจากการใช้ทรัพยากรนั้นหลังจากเสร็จสิ้นการทำงาน ณ ส่วนนั้น จำนวนการร้องขอใช้ทรัพยากรจะต้องไม่มากกว่าจำนวนทรัพยากรที่มีอยู่ในระบบ ดังนั้นสามารถลำดับการทำงานของโพรเซสใช้ทรัพยากรดังนี้

1. request ถ้าในกรณีที่การร้องขอไม่สามารถได้รับการตอบสนองทันที อาจเนื่องจากทรัพยากรขณะนั้นกำลังถูกโพรเซสอื่นใช้งาน แล้วโพรเซสที่ทำการร้องขอเข้ามาต้องรอจนกว่าจะเข้าใช้ทรัพยากรนั้นได้

2. Use : โพรเซสสามารถทำงานบนทรัพยากร (เช่น การพิมพ์งานผ่านทางเครื่องพิมพ์)

3. Release : โพรเซสออกจากการใช้ทรัพยากร

7.2 ลักษณะของการติดตาย

การติดตายสามารถเกิดขึ้นได้หากเกิดสถานการณ์ดังต่อไปนี้

1. Mutual Exclusion ต้องมีทรัพยากรอย่างน้อย 1 ตัวที่ไม่ได้อนุญาตให้ร่วมใช้งาน ดังนั้นมีเพียงโพรเซสเดียวที่สามารถเข้าใช้งาน ถ้าโพรเซสอื่นมีการร้องขอเข้าใช้งาน การร้องขอต้องถูกรอจนกว่าทรัพยากรนั้นจะว่างให้ใช้งาน

2. Hold & wait ต้องมีโพรเซสมีการใช้งานทรัพยากรอย่างน้อย 1 ตัว และกำลังรอเพื่อเข้าทำงานทรัพยากรอีกตัวที่กำลังถูกโพรเซสอื่นใช้งาน

3. No Preemption ทรัพยากรสามารถถูกปล่อยได้ตามความพอใจของโพรเซสที่กำลังใช้งาน ซึ่งก็คือหลังจากที่งานของโพรเซสนั้นเสร็จสิ้น เนื่องจากขึ้นอยู่กับความพอใจของโพรเซสว่าจะยอมปล่อยทรัพยากรออกให้ใช้งานได้เมื่อไหร่

4. Circular Wait มีเชตของ {P0, P1, ..., Pn} ของโพรเซสที่กำลังรอเช่น P0 กำลังรอทรัพยากรที่ถูกใช้โดย P1 ขณะเดียวกัน P1 ก็รอเข้าใช้ทรัพยากรที่กำลังถูกโพรเซส P2 ใช้งาน ท้ายสุดโพรเซสตัวสุดท้ายกำลังรอเข้าใช้ทรัพยากรที่โพรเซสแรกกำลังใช้งาน


การกำหนดทรัพยากรด้วยกราฟ

การติดตายสามารถอธิบายได้ด้วยกราฟอย่างง่ายๆ เรียกว่า System resource-allocation graph กราฟนี้จะประกอบไปด้วยกลุ่มของ V (Vertices) และกลุ่มของ E (edge) กลุ่มของ V แบ่งออกเป็น 2 ส่วนใหญ่คือจุดของ


P = {P1,P2,P3...,Pn} เซตนี้ประกอบด้วยโพรเซสที่กำลังทำงานในระบบ และจุดของ R = {R1,R2,R3...,Rm} เซตนี้ประกอบด้วยทรัพยากรทุกชนิดในระบบ การร้องขอสามารถแทนได้ด้วย Pi à Rj หมายถึงโพรเซส Pi ขอเข้าทำงานทรัพยากร Rj ส่วนการกำหนดให้ทรัพยากรบริการโพรเซสแทนได้ด้วย Rk à Pj หมายถึงทรัพยากร Rk กำลังถูกโพรเซส Pj ใช้งาน


       ลักษณะของกราฟที่ใช้อธิบายการติดตายมีรูปแบบดังรูปที่ 1 โดยใช้วงกลมแทนโพรเซส สี่เหลี่ยมแทนทรัพยากรที่มีในระบบ จุดที่อยู่บนช่องสี่เหลี่ยมเป็นตัวบ่งชี้ว่าทรัพยากรนี้สามารถถูกใช้งานได้พร้อมกันกี่โพรเซส ในรูปแบบต่อมาคือการขอเข้าใช้งานของโพรเซส i จะใช้ลูกศรชี้เข้าหาทรัพยากร(กล่องสี่เหลี่ยม) สุดท้ายสามารถแสดงว่าทรัพยากรนี้ได้ถูกโพรเซส i ใช้งานด้วยการชี้ลูกศรออกจากกล่องสี่เหลี่ยมโดยจะพุ่งออกจากจุดที่โพรเซสนั้นๆกำลังใช้งาน

       - P1 รอเข้าใช้งานทรัพยากร R1 ในขณะที่ทรัพยากร R1 ให้บริการโพรเซส P2 แล้ว P2 ก็กำลังรอเข้าทำงานทรัพยากร R3 ซึ่งกำลังให้บริการโพรเซส P3 ทรัพยากรR2 กำลังให้บริการทั้งโพรเซส P1 และ P2 ส่วนทรัพยากร 4 ว่างไม่มีเรียกใช้งาน ซึ่งสามารถแทนได้ด้วยลักษณะการเคลื่อนดังนี้

P1 à R1 à P2 à R3 à P3


        บทพื้นฐานของการติดตาย ถ้ากราฟไม่เป็นเป็นลูปจะไม่เกิดติดตาย แต่ถ้ากราฟมีลูปจะสามารถแยกได้ 2 กรณีคือ ถ้าทรัพยากรมีให้ใช้งานได้ทีละตัวจะเกิดการติดตาย แต่ถ้าทรัพยากรหนึ่งตัวสามารถใช้ได้พร้อมกันหลายโพรเซส จะมีโอกาสที่จะเกิดการติดตาย หรือไม่เกิดก็เป็นได้


         เพื่อป้องกันหรือควบคุมการเกิดการติดตายสามารถทำได้ 3 วิธีคือ

1. แน่ใจว่าระบบจะไม่เกิดการติดตายโดยการใช้ Protocol
2. ยอมให้ระบบเข้าสู่การติดตายได้ชั่วคราวแล้วสามารถออกมาได้
3. เมินเฉยทุกอย่าง แล้วอ้างว่าไม่เคยเกิดการติดตายในระบบ วิธีนี้ใช้อยู่ในระบบ Unix

จากที่ทราบมาแล้วว่าเหตุที่ทำให้เกิดการติดตาย
Mutual Exclusion เงื่อนไขของการเกิด mutual คือการใช้งานทรัพยากรที่อนุญาตให้ใช้ได้ทีละงาน เช่น
เครื่องพิมพ์ อีกนัยหนึ่งการร่วมใช้ข้อมูลโดยไม่ต้องการเข้า mutual ทำให้ไม่เกิดการติดตาย ตัวอย่างของไฟล์ที่สามารถอ่านได้อย่างเดียว ถ้าหลายๆโพรเซสพยายามที่จะอ่านก็สามารถเข้าอ่านได้ทันทีอย่างต่อเนื่อง อย่างไรก็ดีทรัพยากรบางชนิดไม่สามารถประกาศใช้งานร่วมกันได้
Hold / Wait รับรองได้ว่าเมื่อมีการร้องขอใช้ทรัพยากรทำงาน โพรเซสนั้นต้องไม่ได้กำลังใช้งาน
ทรัพยากรอื่นอยู่ ซึ่งสามารถทำได้หลายวิธีการเช่น บังคับให้โพรเซสร้องขอแล้วก็จัดสรรการใช้งานทรัพยากรให้กับโพรเซสนั้นๆก่อนที่จะมีการเริ่มทำงาน หรือยอมให้โพรเซสขอใช้ทรัพยากรได้เมื่อโพรเซสไม่ได้ทำงานในส่วนใดอยู่ ความแตกต่างระหว่างสองวิธีการอาจมีดังนี้ ถ้าพิจารณาโพรเซสที่ทำงานในการสำเนาไฟล์ข้อมูลจากเทปไปยังดิสก์ แล้วพิมพ์ออกทางเครื่องพิมพ์ ถ้าต้องให้โพรเซสมีการขอใช้ทรัพยากรก่อนที่จะเริ่มทำงานจริง ดังนั้นโพรเซสต้องเริ่มขอไปยังเทป แล้วดิสก์ สุดท้ายก็เป็นเครื่องพิมพ์ ดังนั้นเครื่องพิมพ์จึงต้องถูกจับจองเอาไว้ให้โพรเซสนี้ตลอดระยะเวลาในการทำงานทั้งหมดของโพรเซส ลักษณะเช่นนี้เกิดเป็นข้อเสียทางด้าน Resource Utilization ส่วนวิธีที่สองยอมให้โพรเซสร้องขอเพียงแค่ช่วงของการขอเทปและดิสก์ เพื่อสำเนาข้อมูลได้เนื่องจากโพรเซสเริ่มแรกยังไม่มีการใช้งานทรัพยากรใด แต่เมื่อกำลังใช้ในการสำเนา โพรเซสนั้นจะไม่มีสิทธิในการขอใช้เครื่องพิมพ์จนกว่าจะสำเนาเสร็จ เมื่อสำเนาเสร็จแล้วจึงต้องขอใช้ดิสก์กับเครื่องพิมพ์เพื่อสำเนาข้อมูลที่ต้องการพิมพ์มายังเครื่องพิมพ์นั้น ถ้าในระหว่างนั้นในโพรเซสอื่นอาจใช้งานเครื่องพิมพ์ หรือทรัพยากรเทปหรือดิสก์ ทำให้ต้องรอ ข้อมูลอาจสูญหาย หรือเกิดการรอในแต่ละช่วงของการร้องลักษณะเช่นนี้เป็นข้อเสียที่เกี่ยวเนื่องกับ Starvation หมายถึงสภาวะอดตาย

No Preemption ถ้าโพรเซสมีการใช้งานทรัพยากรอื่นอยู่ ดังนั้นก็จะไม่สามารถเข้าทำงานในทรัพยากร

ที่ขอใช้ไปได้ทันทีในขณะนั้น แล้วทุกๆโพรเซสที่กำลังถูกใช้ในขณะนั้นจะถูกปลดปล่อยให้ว่าง โพรเซสที่ถูกบังคับให้ออกจากการใช้บริการจะถูกเพิ่มเข้าไปในรายการของทรัพยากรที่มีโพรเซสรอใช้งาน จากนั้นโพรเซสจะเริ่มทำงานก็ต่อเมื่อโพรเซสนั้นได้รับสิทธิให้ใช้ทรัพยากรตัวเดิมได้ ในขณะที่โพรเซสอื่นๆกำลังร้องขอ

Circular Wait ก่อนที่จะเริ่มใช้วิธีการนี้ต้องทำการกำหนดลำดับของชนิดทรัพยากรทั้งหมดและเมื่อร้องขอว่าในแต่ละโพรเซสที่ขอใช้ทรัพยากรเป็นการเพิ่มจำนวนลำดับของชนิดทรัพยากรที่ได้ระบุไว้ กำหนดให้ R เป็นเซตของชนิดทรัพยากร R1 , R2 .. ,Rn เรากำหนดในแต่ละชนิดทรัพยากรเป็นเลขจำนวนเต็มเพื่อให้สามารถทำการเปรียบเทียบได้ เช่นถ้าเซต ทรัพยากรกลุ่ม R คือมีเทป ดิสก์ และเครื่องพิมพ์ และกำหนดฟังก์ชันเป็นหนึ่งต่อหนึ่ง F : R à N ; N คือเซตของจำนวนจริง ดังนั้นเราสามารถกำหนดฟังก์ชันการทำงานได้คือ

F(tape drive) = 1 , F(disk drive) = 5, F(printer) = 12

เมื่อพิจารณาในแต่ละโพรเซสสามารถร้องขอการใช้ทรัพยากรก็ต่อเมื่อเป็นกรณีที่มีการเพิ่มค่าลำดับของทรัพยากรนั้น โพรเซส i สามารถเริ่มการขอใช้โดยการเอาข้อมูลจำนวนที่ทรัพยากรนั้นๆจะสามารถให้บริการได้พร้อมกัน ขณะเดียวกันก็สามารถดูจำนวนที่ทรัพยากรนั้นสามารถให้บริการกับโพรเซส j ถ้าพบกว่าฟังก์ชันหรือค่าของทรัพยากรที่โพรเซส j ร้องขอมากกว่าค่าของทรัพยากรที่โพรเซส i ร้องขอ ดังนั้นเมื่อตรวจพบกว่ามีการเรียกใช้ทรัพยากรจำนวนมากจะมีเพียงการร้องขอเดียวเท่านั้นที่จะได้รับการทำงาน

จากข้อที่ผ่านมาเป็นการป้องกันการเกิดการติดตายโดยการจัดการกับสัญญาณที่ร้องขอใช้ทรัพยากร แต่
อาจส่งผลให้การใช้งานระบบ หรือประสิทธิภาพในการทำงานลดลง ดังนั้นจึงมีวิธีที่หลีกเลี่ยงการติดตายโดยพิจารณาจากข้อมูลของทรัพยากรที่ถูกร้องขอ เช่นในระบบที่มีเทป และเครื่องพิมพ์อย่างละตัว ดังนั้นเราอาจจัดสรรให้โพรเซส P เข้าใช้งานเทปก่อนแล้วก็ใช้งานเครื่องพิมพ์ ในขณะที่โพรเซสQ ใช้งานเครื่องพิมพ์ก่อนแล้วค่อยใช้เทป ดังนั้นนอกจากการร้องขอแล้วตรวจว่าทรัพยากรว่างหรือไม่ จึงต้องมีการดูด้วยว่าขณะนั้นทรัพยากรนั้นถูกใช้โดยใครแล้วโพรเซสไหนจะใช้อะไรก่อนหลัง นอกจากนี้อาจมีข้อมูลที่มากที่สุดที่ขอใช้ทรัพยากรชนิดนั้น รูปแบบอัลกอริทึมของการหลีกเลี่ยงการติดตายจะมีการตรวจสอบสถานของการใช้ทรัพยากรเพื่อให้แน่ใจว่าจะไม่การเกิดการรอแบบลูปอย่างสม่ำเสมอตลอดเวลา สถานะของการใช้ทรัพยากรถูกกำหนดด้วยจำนวนของทรัพยากรที่ถูกใช้งานและจำนวนทรัพยากรที่มีอยู่ในระบบ

Safe State

เมื่อโพรเซสร้องของทรัพยากรที่มีอยู่ ระบบต้องตัดสินว่าถ้าให้ใช้ทรัพยากรแล้วระบบจะยังคงอยู่ในสถานะที่ปลอดภัยหรือไม่ (Safe state หมายถึงสถานะที่ทรัพยากรสามารถให้บริการได้ทุกโพรเซส) ลักษณะของ Sequence <P1, P2, ...,Pn> จะยังคงดำเนินได้ก็ต่อเมื่อทรัพยากรที่ Pi ขอทำงาน ยังคงทำงานได้อย่างน่าพอใจ ซึ่งจะกำหนดโดยทรัพยากรที่มีในขณะนั้นบวกกับทรัพยากที่ถูกใช้งานอยู่ทั้งหมดของ Pj โดยที่ j < i นั้นหมายถึงถ้าทรัพยากรที่ Pi ต้องการยังไม่ว่างให้ใช้งาน Pi ต้องสามารถรอได้จนกว่า Pj ทำงานเสร็จ แล้วเมื่อ Pj ทำงานเสร็จ Pi สามารถเข้าทำงานทรัพยากรที่ต้องนั้นแล้วก็ออกไปเมื่อใช้งานเสร็จสิ้น เมื่อโพรเซส Pi ทำงานแล้วออกจากทรัพยากรนั้นแล้ว Pi+1 สามารถที่จะใช้งานทรัพยากรนั้นได้ต่อจากนั้น

ดังนั้นความจริงของสถานะที่ปลอดภัยจะไม่เกิดการติดตาย แต่ถ้าเป็นสถานะที่ไม่ปลอดภัยอาจเกิดการติดตายได้ ดังนั้นจึงต้องทำให้ระบบอยู่ในสถานะที่ปลอดภัย และไม่ยอมให้ระบบเข้าสู่ภาวะที่ไม่ปลอดภัยเพื่อหลีกเลี่ยงการติดตาย ตัวอย่างเช่นถ้าระบบมีเทป 12 ตัวและมีโพรเซส P0, P1 และ P2 เมื่อ P0 ต้องการใช้งานเทป 10 ตัว P 2 ต้องการใช้ 4 ตัว P3 ต้องการใช้อีก 9 ตัว สมมติว่าในเวลาที่ t0 โพรเซส 0 กำลังใช้งานเทป 5 ตัวอยู่ โพรเซส 1 ใช้งานอยู่ 2 และโพรเซส 2 ใช้งานอยู่ 2 ดังนั้นจะมีทรัพยากรเทปว่างอยู่อีก 3 ดังนั้นในเวลาที่ t0 ระบบยังอยู่ในภาวะปลอดภัย แต่ก็มีโอกาสที่จะเข้าสู่ภาวะไม่ปลอดภัยได้ สมมติที่เวลา t1 โพรเซส 2 มีการขอใช้งานเทปเพิ่มอีก 4 ตัว หรือมากกว่านั้น ดังนั้นระบบจะอยู่ในภาวะที่ไม่ปลอดภัย ดังนั้นมีเพียงโพรเซส 1 ที่จะช่วยได้คือต้องปล่อยทรัพยากรเทปให้ว่าง เพื่อให้มีทรัพยากรเหลือว่างพอให้โพรเซส 2 ใช้งานได้
อัลกอริทึมการกำหนดทรัพยากรด้วยกราฟ

claim edge Pi à Rj เป็นตัวกำหนดว่าโพรเซส Pi อาจทำการขอใช้ทรัพยากร Rj ซึ่งแทนได้ด้วยจุดปะ ดังนั้นเส้นจุดปะจะถูกเปลี่ยนให้กลายการเป็นการขอใช้งานจริง (แทนด้วยเส้นทึบ) เมื่อโพรเซสนั้นทำการขอใช้ทรัพยากรจริง ดังนั้นเมื่อทรัพยากรบริการโพรเซสเรียบร้อยแล้วก็จะเปลี่ยนกลับเป็นเส้นปะ Claim edge เหมือนเดิม สมมติถ้ามีโพรเซส 2 ขอใช้งานทรัพยากร 2 และ 1 ในขณะนั้นมีโพรเซส 1 กำลังร้องขอใช้งานด้วย แล้วทรัพยากร 1 ให้บริการโพรเซส 1 อยู่ ดังนั้นระบบมีสิทธิที่จะยอมให้โพรเซส 2 เข้าใช้งานทรัพยากร 2ได้ แต่พบว่าถ้ายอมให้มีการใช้ทรัพยากร 2 จะทำให้ระบบอยู่ในภาวะที่ไม่ปลอดภัย เนื่องจากจะเกิดการลูปรอหรือการติดตายทันที

อัลกอริทึมของนายธนาคาร (Banker Algorithm)

ในระบบที่ทรัพยากร 1 ตัวสามารถให้บริการได้พร้อมกันหลายโพรเซสการใช้กราฟแทนการใช้งานทรัพยากรจะไม่เหมาะสม จึงมีการเสนออัลกอริทึมของนายธนาคาร ซึ่งเป็นอัลกอริทึมที่ใช้งานได้จริงในระบบธนาคารที่ว่าธนาคารจะไม่จ่ายเงินที่มีอยู่ให้ตามความต้องการของลูกค้าทั้งหมดได้เป็นเวลานาน (หมายถึงมีคนถอนออกอยากเดียว ธนาคารจะไม่สามารถอยู่ได้) ดังนั้นจึงต้องมีระบบเพื่อกำหนดจำนวนสูงสุดที่จะสามารถให้บริการได้ จำนวนนี้อาจไม่จำเป็นต้องเป็นจำนวนทรัพยากรทั้งหมดที่มีอยู่ในระบบ เมื่อผู้ใช้ขอใช้กลุ่มของทรัพยากร ระบบต้องทำการตรวจสอบว่าถ้าให้ใช้แล้วระบบจะยังคงอยู่ในภาวะปลอดภัยหรือไม่ ถ้าไม่ปลอดภัยการให้ใช้ทรัพยากรต้องรอจนกว่าจะมีผู้ใช้รายอื่นทรัพยากรที่ใช้แล้วกลับเข้าสู่ระบบ

โครงสร้างของระบบนายธนาคารมีดังนี้ กำหนดให้มี n โพรเซส มีทรัพยากรในระบบทั้งหมด m ตัว

Available : เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้ Available [j]=k ดังนั้น k คือจำนวนที่ทรัพยากรชนิด j จะสามารถให้บริการได้

Max : เป็นค่าเมตริกซ์ขนาด n x m ที่กำหนดความต้องการสูงสุดของแต่ละโพรเซส ถ้า max[i,j] = k แล้วโพรเซส i อาจต้องใช้ทรัพยากร j สูงถึง k บริการ

Allocation เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้ ถ้า allocation[i,j] = k หมายถึงโพรเซส i กำลังใช้งานทรัพยากรชนิด j อยู่เป็นจำนวน k บริการ

Need : เมตริกซ์ขนาด n x m เพื่อบ่งบอกจำนวนทรัพยากรที่เหลือที่ยังต้องการใช้ของแต่ละโพรเซส เช่น Need[i,j] = k หมายถึงโพรเซส i ยังคงต้องการใช้งานทรัพยากร j อยู่อีก k บริการ พบกว่า need[i,j] = Max[i,j] – Allocation[i,j]
อัลกอริทึมที่ปลอดภัย

อัลกอริทึมที่หาได้ว่าระบบปลอดภัยหรือไม่ สามารถทำได้ดังนี้

1. กำหนดให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n x m โดยเริ่มทำงานที่ work := available และ finish[i] เป็นเท็จ โดยที่ i มีค่าตั้งแต่ 1, 2 , 3 ... n
2. หาค่า i ทั้ง 2 ฟังกัชัน คือ finish[i] := false , Needi =< Work ถ้าไม่ตามเงื่อนไข ข้ามไปยังขั้นที่ 4
3. Work := Work + allocation, finish[i] := true กลับไปยังขั้นที่ 2
4. ถ้า finish[i] = true สำหรับทุกค่าของ i แล้วระบบจะอยู่ในภาวะปลอดภัย

เวลาในการใช้ทำงานอัลกอริทึมนี้เท่ากับ m x n2
อัลกอริทึมของการขอใช้ทรัพยากร

กำหนดให้ Request i เป็นเวกเตอร์ของการขอใช้งานสำหรับโพรเซส i ถ้า requesti[j] = k หมายถึง

โพรเซส i ต้องการทำงาน k บริการจากทรัพยากร j เมื่อมีการขอใช้งานทรัพยากรโดยโพรเซส i ก็จะเกิดการทำงานดังต่อไปนี้

1. ถ้า Requesti =< Needi ไปยังขั้นตอนที่ 2 นอกจากนั้น ให้แสดงข้อความเตือน เนื่องจากโพรเซสมีการใช้ทรัพยากรมากว่าที่คาดการณ์ไว้
2. ถ้า Requesti =< Available ไปยังขั้นตอนที่ 3 นอกจากนี้โพรเซส i ต้องรอเนื่องจากทรัพยากรไม่มีให้ใช้งาน
3. มีการตั้งระบบลวงเพื่อใช้ทรัพยากรที่โพรเซส i ขอใช้ โดยการใส่ค่าในตัวแปรต่อไปนี้

Available := Available – Request;

Allocationi := Allocationi + Requesti;

Needi := Needi – Requesti;



ถ้าผลของการกำหนดค่าการให้ใช้ทรัพยากรออกมาพบว่าระบบอยู่ในภาวะปลอดภัย ก็จะจบสิ้นการ

ทำงานแล้วยอมให้โพรเซส i ใช้งานทรัพยากรนั้นจริงๆ อย่างไรก็ตามถ้าผลออกมาว่าไม่ปลอดภัย โพรเซส i ต้องรอ Requesti แล้วก็จะกลับไปสู่ค่าสถานะเก่า

     แสดงข้อมูลการใช้งานของระบบพบกว่ามี 5 โพรเซสในการทำงาน P0 – P 4 และมีทรัพยากรให้ใช้งานได้ 3 ตัว คือ A, B และ C ทรัพยากร A มีให้ใช้ได้ถึง 10 ตัว ทรัพยากร B ใช้ได้ถึง 5 ตัว และทรัพยากร C ใช้ได้ถึง 7 ตัว สมมติว่าที่เวลา t0 เกิดเหตุการณ์ดังรูปที่ 5 ดังนั้นจะสามารถหา Need := Max – allocation ดังรูปที่ 6 พบว่าระบบอยู่ในภาวะปลอดภัยแน่นอน และลำดับของความปลอดภัยเป็น <P1,P3,P4,P2,P0>


สมมติให้โพรเซส 1 มีการขอใช้งานทรัพยากรเพิ่ม 1 ตัว ของ A และจากทรัพยากร C อีก 2 ตัว ดังนั้น request1 := (1,0,2) ซึ่งสามารถตรวจสอบได้จาก

Request1 =< Available : (1,0,2) <= (3,3,2) เป็นจริงดังนั้นจึงต้องทำการสร้างระบบจำลองขึ้นมาเพื่อ

ตรวจสอบภาวะของระบบดังรูปที่ 7 หลังจากนั้นไปเข้าไปทำอัลกอริทึมที่ปลอดภัยเพื่อหาลำดับความปลอดภัย และได้ลำดับออกมาดังนี้ <P1, P3, P4, P0, P2> แต่เราพบกว่าถ้าโพรเซส P4 มีการขอใช้ทรัพยากร(3,3,0) จะไม่มีให้ใช้งานได้ และถ้า P0 ขอใช้งาน (0,2,0) ก็จะใช้ไม่ได้เช่นกันเนื่องจากจะทำให้อยู่ในภาวะไม่ปลอดภัย



7.5 การตรวจจับการติดตาย

ระบบต้องมีการจัดการดังต่อนี้

- อัลกอริทึมที่ตรวจสอบภาวะของระบบว่าจะเกิดการติดตายหรือไม่ (การตรวจจับ)

- อัลลกอริทึมที่จะกู้ระบบจากการติดตาย
กรณีที่มี 1 บริการในทรัพยากร 1 ตัว

ถ้าทุกทรัพยากรสามารถใช้บริการได้เพียง 1 โพรเซสแล้วเราสามารถกำหนดอัลกอริทึมของการตรวจจับการติดตายด้วยการใช้กราฟแสดงทรัพยากรที่เรียกว่ากราฟ Wait-for การติดตั้งดูแลการใช้กราฟสามารถทำได้โดยกำหนดให้ โหนดแทนโพรเซส สัญลักษณ์ Pi à Pj หมายถึงโพรเซส i กำลังรอโพรเซส j โดยจะทำการแปลงจากกราฟแทนทรัพยากรเป็น wait-for กราฟที่มีแต่โพรเซส จากนั้นจึงอ้างใช้อัลกอริทึมเพื่อทำการค้นหาตรวจดูว่ากราฟที่ได้เกิดเป็นลูปขึ้นหรือไม่ ซึ่งใช้ order n2 โดยที่ n คือจำนวนของเส้นตรงที่อยู่ในกราฟ
กรณีที่สามารถให้บริการมากกว่า 1 ในทรัพยากร 1 ตัว

ลักษณะจะคล้ายกับอัลกอริทึมของนายธนาคาร โดยมีโครงสร้างดังนี้

Available : เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้

Allocation เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้

Request เป็นเวกเตอร์ขนาด n x m เพื่อบ่งบอกการร้องทรัพยากรของแต่ละโพรเซสในขณะนั้น เช่น

Request[i,j] = k หมายถึงโพรเซส i กำลังขอใช้ทรัพยากรจาก j เป็นจำนวน k บริการ

อัลกอริทึมของการตรวจจับมีดังนี้

1. ให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n และ m เริ่มค่าที่ work := available สำหรับทุกค่าของ i ถ้า allocation != 0 แล้ว finish[i] = false นอกนั้นค่า finish[i] = true
2. ทำการหา i ดังต่อไปนี้
- finish[i] := false

- Requesti =< Work
ถ้าไม่เป็นตามนี้ข้อไปข้อ 4
3. Work := Work + Allocation;

Finish[i] := true ;

กลับไปยังข้อ 2

4. ถ้า finish[i] = false สำหรับบางค่าของ i ที่ 1 =< i =< n แล้วระบบจะอยู่ในภาวะการติดตาย ยิ่งกว่านั้นถ้า

finish[i] = false แล้วโพรเซส i จะถูกติดตาย

อัลกอริทึมนี้ใช้เวลาในการทำงาน order = m x n2


             ไม่เกิดการติดตาย เมื่อเราใช้อัลกอริทึมการตรวจจับสามารถได้ลำดับออกเป็น <P0, P2, P3, P1, P4> ที่ทำให้ค่า i เป็นจริงทุกค่า สมมติว่าถ้าให้โพรเซส 2 มีการขอใช้ทรัพยากรเพิ่มอีก 1 ในทรัพยากร C ดังนั้นค่า request จะเป็นไปตามรูปที่ 9 ระบบสามารถเกิดการติดตายแน่นอนเนื่องจากโพรเซส 0 ก็ไม่สามารถปล่อยทรัพยากร C ให้โพรเซส 2 ใช้เนื่องจากโพรเซส 0 ไม่ได้มีการใช้งานทรัพยากร C เลย
การใช้งานอัลกอริทึมตรวจจับ

จะมีการใช้งานอัลกอริทึมก็ต่อเมื่อ

- การติดตายเกิดขึ้นบ่อยอย่างไร

- จะมีโพรเซสจำนวนเท่าไหร่ที่ถูกกระทบเมื่อเกิดการติดตาย

ถ้ามีการใช้อัลกอริทึมตรวจจับในลักษณะวนลูป อาจพบหลายลูปในทรัพยากรกราฟและดังนั้นจะไม่

สามารถบอกได้ว่าโพรเซสใดที่ทำให้เกิดการติดตาย
การกู้คืนจากการเกิดตาย
การกู้คืนด้วยการออกจากระบบ

กำจัดการติดตายด้วยการให้โพรเซสออกจากระบบ ซึ่งมี 2 วิธี

- ให้โพรเซสติดตายออกจากระบบทั้งหมด : วิธีนี้ชัดเจนในการกำจัดการติดตายแต่ผลเสียมีมากเนื่องจากโพรเซสอาจทำงานมาเป็นเวลานานดังนั้นผลลัพธ์ที่ได้ในแต่ละงานของโพรเซสจะหายทั้งหมด ต้องเสียเวลาในการทำงานใหม่ทั้งหมด

- ออกทีละโพรเซสจนกว่าการติดตายจะหายไป : เนื่องจากต้องมีการคิดถึงสิ่งที่สูญเสียไปเมื่อออกจากระบบทั้งหมด ดังนั้นจึงใช้การออกทีละโพรเซสแล้วลูปตรวจจับไปจนกว่าจะไม่พบการติดตาย

ดังนั้นการใช้วิธีการใดต้องคำนึงแล้วเลือกจาก

1. ความสำคัญของโพรเซส

2. โพรเซสนั้นใช้เวลาในการประมวลผลมานานเท่าใด อีกนานเท่าไรจึงจะเสร็จ

3. ทรัพยากรที่โพรเซสนั้นใช้งาน

4. มีกี่โพรเซสที่ต้องถูกออกจากระบบ

5. โพรเซสนั้นเป็นแบบ interactive หรือ bath
วิธีการยึดทรัพยากร

แก้ปัญหาการติดตายด้วยการยึดทรัพยากร จากโพรเซสอื่นเพื่อให้อีกโพรเซสทำงานได้แล้วส่งผลให้ระบบไม่เกิดการติดตาย ดังนั้นจึงต้องพิจารณาเน้นที่จุดต่างๆดังนี้

1. การเลือกทรัพยากรที่จะยึด จะต้องเลือกให้เกิดความเสียหายน้อยที่สุด หมายถึงเลือกทรัพยากรที่จะยึดคืนให้น้อยที่สุด หรือคำนึงถึงเวลาที่จะสามารถแก้ปัญหาได้

2. การย้อนกลับ ต้องพิจารณาด้วยว่าการกลับเริ่มทำงานใหม่ของโพรเซส ดังนั้นต้องมีการเก็บค่าสเตตของโพรเซสที่กำลังทำงานไว้ก่อนเริ่มงานใหม่

3. การอดตาย ต้องให้มั่นใจว่าเมื่อยึดไปแล้วจะไม่เกิดการอดตายเนื่องจากโพรเซสไม่มีโอกาสได้ใช้ทรัพยากรอีกเลย

แหล่งอ้างอิง
http://webcache.googleusercontent.com/