Dosya (veri yapısı)
Gelen bilgi işlem , bir dosya olarak da adlandırılan kuyruk (İngilizce kuyruk ) bir olan veri yapısı ilkesine dayalı " ilk giren ilk çıkar " veya FIFO, kısaltma FIFO (tarafından İngilizce olarak anılacaktır " ilk giren ilk çıkar, içinde » ): İlk kuyruğa eklenen öğeler ilk kaldırılacaklardır.
Açıklama
Yapı bir kuyruk gibi çalışır : İlk gelenler ilk çıkanlardır ( PEPS , FIFO İlk giren ilk çıkar için İngilizce ). Son giren ilk çıktığında (LIFO, LIFO Son giren , ilk çıkar İngilizce) bir yığın ( yığın ) olur.
Stokları takip etmek için kullanılan algoritmalar, stok yönetiminde kullanılan yöntemle tutarlı olmalıdır .
Bir bağlanmış liste sadece olan addQueue ve removeHead işlemleri vardır kullanılan bir sıra oluşturur. Kuyruk bir diziye dayanıyorsa , yapı, biri son gelene, diğeri çıkışa karşılık gelen iki indeks kaydeder.
Kuyruklar, çeşitli kökenlere sahip veri bloklarının sıralı işlenmesini organize etmek için kullanılır.
Kuyruklar teorisi telefon şebekelerinin boyutlandırma için geliştirilmiş, kullanıcı sayısını bağlar mevcut kanalların sayısı, kanalın ortalama işgal süresi ve bekleme süreleri beklenebilir.
Yöntemin sınırlamaları
Olarak bilgisayar yazılımı , göreli olarak basit, bu planlama yalan avantajı; ancak süreçleri kısa yürütme süresiyle cezalandırır : gerçekten, çok fazla hesaplama süresi gerektiren bir işlemin ardından başlatılırsa, küçük bir görev (örneğin, yalnızca bir yazıcıyı yöneten bir sunucuda, bir sayfa yazdırın), küçük görev, yerine getirilmeden önce çok daha fazla zaman (yüz sayfa yazdırmak) gerektiren görevin bitmesini beklemek zorunda kalacaktır. Tek işlemcili makinelerin olduğu günlerde, bu, işlemlerin mantıksal bir sırayla gerçekleştirilmesini sağlamak için en güvenilir teknikti.
Bu algoritma, uygulama kolaylığı ve düşük maliyeti nedeniyle bir önbellek satırı değiştirme politikası olarak da kullanılır . Bununla birlikte, bu kullanımda Belady anomalisi olarak bilinen bir anormallik sunar : kuyruktaki kat sayısının artması, performans üzerinde olumsuz bir etkiye sahip olabilir.
Başvurular
Bu yapı örneğin kullanılır:
- genel olarak, işlenmeyi beklemesi gereken işlemleri geçici olarak saklamak;
- böylece istekleri geldikleri sırayla işleyen ve bunları bir kuyruğa (kuyruk veya kuyruk olarak da adlandırılır) yerleştiren baskı sunucuları ;
- bir işletim sisteminde herhangi bir ayrıcalık tanımadan her göreve makine zamanı ayırması gereken belirli çok görevli motorlar ;
- Bir genişlik kastetmek algoritma ziyaret düğümleri depolamak için bir kuyruk kullanır;
- her tür tampon oluşturmak için (İngilizce " tamponlar " olarak );
- Olarak envanter yönetimi, algoritmalar fiziksel tutarlılık / değerlemesini sağlamak için, fiziksel envanter yönetimi saygı.
İlkeller
İşte kuyrukları işlemek için yaygın olarak kullanılan ilkel öğeler. Kuyruk işleme ilkelleri için bir standardizasyon yoktur. Bu nedenle isimleri gayri resmi olarak belirtilmiştir.
- "Thread": kuyruğa bir eleman ekler. Karşılık gelen İngilizce terim enqueue'dur .
- "Kaydırma": kuyruktaki bir sonraki öğeyi döndürür ve kuyruktan kaldırır. Karşılık gelen İngilizce terim dequeue'dur .
- "Satır boş mu?" ": Kuyruk boşsa" true ", aksi takdirde" false "döndürür.
- "Kuyruktaki öğe sayısı": kuyruktaki öğe sayısını döndürür.
C # Örneği
C # Örneği
using System;
namespace ExempleFile
{
public class File
{
private object[] _File;
private int _PointeurDeTete;
private int _PointeurDeQueue;
private int _Taille;
private int _NbreElements;
#region Constructeur
public File(int Taille)
{
this._Taille = Taille;
this._File = new object[Taille];
this._PointeurDeTete = 0;
this._PointeurDeQueue = 0;
this._NbreElements = 0;
}
#endregion
#region Fonctions
public virtual void Enfiler(object item)
{
lock (this)
{
if (this.EstPleine())
{
throw new Exception("La file est pleine !");
}
else
{
this._File[this._PointeurDeQueue] = item;
this._NbreElements++;
// Pointer sur le prochain elément libre,
// revenir à zéro si on est au bout de la file
this._PointeurDeQueue = this._PointeurDeQueue + 1;
if (this._PointeurDeQueue >= this._File.Length)
{
this._PointeurDeQueue = 0;
}
}
}
}
public virtual object Defiler()
{
lock (this)
{
object item = null;
if (this.EstVide())
{
throw new Exception("La file est vide !");
}
else
{
item = this._File[this._PointeurDeTete];
this._NbreElements--;
// Faire pointer le pointeur de queue sur le prochain élément valide,
// revenir à zéro si on est au bout de la file
this._PointeurDeTete = this._PointeurDeTete + 1;
if (this._PointeurDeTete >= this._File.Length)
{
this._PointeurDeTete = 0;
}
}
return item;
}
}
public virtual bool EstVide()
{
return (this._NbreElements == 0);
}
public virtual bool EstPleine()
{
return (this._NbreElements == this._Taille);
}
public int NbreElements
{
get { return this._NbreElements; }
}
#endregion
}
}
Notlar ve referanslar
-
kuyruğu ise Fransızcadan ödünç İngilizce terim vardır dosya bir atar dosyası bu dilde .
-
Krş Alfred Aho , John Hopcroft ve Jeffrey Ullman ( çeviren. J.-M. Moreau), Veri yapıları ve algoritmalar , Paris, InterÉditions,1995, 450 p. ( ISBN 978-2-7296-0194-2 ) , "Temel soyut veri türleri", s. 58-62
-
Bachelet 2011 .
-
Michel Fleutry , Ansiklopedik elektronik sözlüğü: İngilizce-Fransızca , Paris, Sözlük evi,1991, 1054 s. ( ISBN 2-85608-043-X ) , s. 699 ; (en) RL Brewster , Telekomünikasyon teknolojisi , Chichester, İngiltere, Ellis Horwood,1986, s. 45.
-
Krş “ Kuyruklar ” üzerine, Université P. ve M. Curie Paris - Bilgisayar işletim sistemleri
Ayrıca görün
Kaynakça
İlgili Makaleler
Dış bağlantılar