next up previous contents index
Next: กฎของคิว Up: ทฤษฎีคิว Previous: กล่าวนำ   Contents   Index

สัญลักษณ์ของคิว

ในการบริการห้องปฏิบัติการคอมพิวเตอร์ นักศึกษาทั้งมหาวิทยาลัยที่มีสิทธิในการใช้ห้องคอมพิวเตอร์เป็นผู้ใช้งาน หรือ ``งาน'' (Jobs) ในระบบ

ในรูป 3.1 แสดงภาพความสัมพันธ์ของการใช้งานห้องปฏิบัติการคอมพิวเตอร์ ที่มีจำนวนเครื่องบริการ (Facility) จำนวนหนึ่ง ที่นักศึกษาสามารถใช้งานได้ ถ้าเครื่องคอมพิวเตอร์ถูกใช้งานทุกเครื่อง นักศึกษาที่เข้ามาใช้งานต้องรออยู่ในคิว ในคำจำกัดความของทฤษฎีคิว นักศึกษามักถูกเรียกว่า ``Customer'' หรือผู้ใช้งานระบบ

เพื่อจะสามารถวิเคาระห์ระบบได้ เราจำเป็นต้องกำหนดคุณลักษณะของระบบดังต่อไปนี้

Figure 3.1: ตัวอย่างทฤษฎีคิว: การบริการห้องปฏิบัติการคอมพิวเตอร์
\includegraphics[width=5in]{fig/computerroom.eps}

  1. กระบวนการเข้าใช้ระบบ (Arrival Process):

    ถ้านักศึกษาเข้ามาใช้ห้องปฏิบัติการ ณ. เวลา $t_1, t_2, \ldots, t_j$, ตัวแปรสุ่ม $\tau_j = t_j - t_{j-1}$ เรียกว่า ``เวลาระหว่างการเข้าใช้งาน'' (Interarrival Time) โดยทั่วไป การวิเคราะห์ของทฤษฎีการเข้าคิวจะสมมุติว่า $\tau_j$ เป็นลำดับของตัวแปรสุ่มที่ไม่ขึ้นอยู่ด้วยกัน ที่มีการกระจายเหมือนกัน (Independent and Identically Distributed (IID))

    กระบวนการเข้าใช้งาน (Arrival Process) ที่ใช้มากที่สุดเรียกว่า การเข้าใช้งานแบบพัวซอง (Poisson arrivals) ที่เป็น IID และมีการกระจายแบบ exponential

    การกระจายแบบอื่นเช่น Erlang และ Hyperexponential มีการใช้บ้าง

  2. การกระจายของเวลาบริการ (Service Time Distribution):

    ปริมาณที่สำคัญอีกประการหนึ่งคือ เวลาที่นักศึกษาเข้าใช้งานคอมพิวเตอร์ในห้องปฏิบัติการ ช่วงเวลาดังกล่าวเรียกว่าเวลาบริการ (Service Time)

    โดยทั่วไปเวลาบริการจะสมมุติให้เป็นตัวแปรสุ่ม ที่เป็น IID และมักใช้การกระจายแบบ Exponential การกระจายแบบอื่นเช่น Erlang และ Hyperexponential มีการใช้บ้าง

  3. จำนวนเครื่องบริการ (Number of Servers):

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

  4. ขนาดของระบบ (System Capacity):

    จำนวนที่มากที่สุดของนักศึกษาที่สามารถเข้ามาอยู่ในห้องปฏิบัติการคอมพิวเตอร์ในพื้นที่ทั้งหมด คือ ``ขนาดของระบบ'' ทั้งนี้รวมถึงนักศึกษาที่กำลังใช้คอมพิวเตอร์อยู่ และนักศึกษาที่รอการใช้งานอยู่ โดยทั่วระบบจะมีขนาดที่จำกัด อย่างไรก็ตามถ้าระบบมีขนาดใหญ่ประมาณค่าหนึ่ง เรามักจะสมมุติว่ามีขนาดเป็นอนันต์ เพื่อให้สามารถคำนวณได้ง่ายขึ้น

    ขนาดของระบบรวม-งานที่กำลังรับบริการ และ งานที่รอรับบริการอยู่

  5. ขนาดประชากร (Population Size):

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

  6. รูปแบบการบริการ (Service Discipline):

    การเลือกลำดับของนักศึกษาในการเข้ารับบริการในห้องปฏิบัติการเรียกว่า ``รูปแบบการบริการ''

    รูปแบบการบริการที่มีการใช้งานอย่างแพร่หลายมากที่สุดเป็นแบบ ``มาก่อนรับบริการก่อน'' หรือ First Come First Served (FCFS) ตัวอย่างรูปแบบบริการอื่นได้แก่

    1. Last Come, First Served (LCFS)
    2. Last Come, First Served with Preempt and Resume (LCFS-PR)
    3. Round-Robin (RR)
    4. Processor Sharing (PS)
    5. Infinite Server (IS) หรือ Delay Center
    6. Shortest Processing Time first (SPT)
    7. Shortest Remaining Processing Time first (SRPT)
    8. Shortest Expected Processing Time first (SERPT)
    9. Biggest In, First Serve (BIFS)
    10. Loudest Voice, First Served (LVFS)

ในการระบบชนิดของคิว เรามักจะใช้สัญกรณ์ของ Kendall ในรูปของ $A/S/m/B/K/SD$ โดยแต่ละตัวอักษรแสดงถึงพารามิเตอร์ที่ได้กล่าวมา โดยที่

การกระจายของกระบวนการเข้าใช้ระบบ และเวลาบริการมักจะแสดงโดยตัวอักษรดังต่อไปนี้

$M$ Exponential
$E_k$ Erlang with parameter $k$
$H_k$ Hyperexponential with parameter $k$
$D$ Deterministic
$G$ General

สังเกตว่าการกระจายแบบ Exponential แสดงโดยตัวอักษรย่อ $M$ ที่ย่อมาจาก Memoryless หรือไม่มีความจำ ถ้าระยะเวลาระหว่างการเข้าใช้ระบบ $\tau$ มีการกระจายแบบ Exponential ด้วยค่าเฉลี่ย $1/\lambda$ ค่าคาดหวัง (ค่าเฉลี่ย) ของการเข้าใช้ระบบครั้งต่อไปจะเป็น $1/\lambda$ เสมอ ไม่ขึ้นอยู่กับเวลาการเข้าใช้ระบบในครั้งก่อนหน้า คุณสมบัติดังกล่าวเรียกว่า Memoryless ข้อมูลการเข้าใช้ระบบในอดีตไม่สามารถช่วยในการคาดหวังการเข้าใช้ระบบในอนาคตได้

ตัวอย่าง: $M/M/3/20/1500/FCFS$ แสดงถึงระบบคิวที่มีพารามิเตอร์ดังต่อไปนี้

  1. เวลาระหว่างการเข้าใช้ระบบของงาน มีการกระจายแบบ Exponential
  2. เวลาในการบริการ มีการกระจายแบบ Exponential
  3. มีเครื่อง (หรือตัวบริการ) ในการบริการ 3 ชุด
  4. ระบบคิวมีบัฟเฟอร์สำหรับงาน 20 งาน ประกอบด้วย 3 ที่สำหรับเก็บงานที่กำลังรับบริการอยู่ และอีก 17 ที่สำหรับงานที่กำลังรอรับบริการ

    เมื่อจำนวนงานที่อยู่ในระบบมีจำนวนเท่ากับ 20 งาน งานที่เข้ามาใหม่จะไม่ได้รับบริการเนื่องจากบัฟเฟอร์เต็ม เรียกว่างานหายไป

  5. มีจำนวนงานทั้งหมด 1500 งานที่จะสามารถเข้าใช้บริการได้
  6. การบริการเป็นแบบ First Come, First Served.


next up previous contents index
Next: กฎของคิว Up: ทฤษฎีคิว Previous: กล่าวนำ   Contents   Index
Vara Varavithya 2002-03-09