Priority | Engin Polat\'ın Windows 8 , Windows Phone 8 ve C# içerikli programcılık sitesi

Arşiv

Etiketlenen yazılar priority

Generic Priority Queue Yazalım

06 April 2013 Yorum yapılmamış

Queue yapıları, ilk gelen ilk çıkar (first in-first out, FIFO) mantığı ile çalışan listelerdir. C# dilinde yeralan Queue<T> sınıfı bu mantık ile çalışan bir yapıdadır.

Queue sınıfına Dequeue methodu ile de eklenmiş elemanları sırası ile okuyabiliriz.

Projelerimizde sıklıkla Queue sınıfına ihtiyaç duyarız. Örneğin, üye kaydı oluşturan kullanıcılara mail ile erişim bilgileri iletileceği durumda, her yeni oluşturulan üye kaydını bir queue‘ya ekleriz, arka planda çalışan bir servis, queue‘da eleman oldukça alır, veritabanında gerekli kayıtları oluşturduktan, yetkileri tanımladıktan, vs. sonra email gönderme işlemini yapar.

Bazı durumlarda bu senaryo yetersiz kalabilir. Özellikle queue‘ya eklenen elemanlar arasında önceliklendirme yapamadığımız için, yeni kullanıcıya gönderilecek mail ile şifresini unutan kullanıcıya gönderilecek şifre hatırlatma maili aynı önceliğe sahip oluyor.

Queue sınıfına öncelikler eklemeye karar verdik, peki nasıl yapacağız? Başlangıç olarak PriorityQueue sınıfı oluşturalım;

public class PriorityQueue<TPriority, TItem>
{
}

PriorityQueue sınıfına her öncelik tipi için Queue barındıracak aşağıdaki değişken tanımlamasını ekleyelim;

public class PriorityQueue<TPriority, TItem>
{
	private SortedDictionary<TPriority, Queue<TItem>> _subqueues;
}

PriorityQueue sınıfının constructor‘ında _subqueues değişkenine değer ataması yapalım;

public PriorityQueue()
{
	_subqueues = new SortedDictionary<TPriority, Queue<TItem>>();
}

Sırada bekleyen eleman var mı, varsa kaç eleman var sorularını cevaplayacak iki property ekleyelim;

public bool HasItems
{
	get { return _subqueues.Any(); }
}
public int Count
{
	get { return _subqueues.Sum(q => q.Value.Count); }
}

İlgili öncelik tipine eleman ekleme işini yapacak Enqueue method’unu yazalım;

public void Enqueue(TPriority priority, TItem item)
{
	if (!_subqueues.ContainsKey(priority))
	{
		_subqueues.Add(priority, new Queue<TItem>());
	}
 
	_subqueues[priority].Enqueue(item);
}

Eğer ilgili öncelik tipi öncelikler listesinde yoksa, ilk olarak öncelik tipine ait yeni queue oluşturuluyor, sonra eleman öncelik tipinin listesine ekleniyor.

Öncelik tipinin listesinden eleman okumak için gerekli Dequeue method’unu da yazalım;

public TItem Dequeue()
{
	if (_subqueues.Any())
	{
		KeyValuePair<TPriority, Queue<TItem>> first = _subqueues.First();

		TItem nextItem = first.Value.Dequeue();

		if (!first.Value.Any())
		{
			_subqueues.Remove(first.Key);
		}

		return nextItem;
	}
	else
	{
		throw new InvalidOperationException("Queue'da hiç eleman yok!");
	}
}

Örnek kullanım;

var queue = new PriorityQueue<int, string>();
 
queue.Enqueue(1, "A-1");
queue.Enqueue(2, "A-2");
queue.Enqueue(3, "A-3");
queue.Enqueue(1, "B-1");
queue.Enqueue(2, "B-2");
queue.Enqueue(3, "B-3");
queue.Enqueue(1, "C-1");
queue.Enqueue(2, "C-2");
queue.Enqueue(3, "C-3");

while (queue.HasItems)
{
	Console.WriteLine(queue.Dequeue());
}

// ÇIKTI
// A-1
// B-1
// C-1
// A-2
// B-2
// C-2
// A-3
// B-3
// C-3

Kaynak : http://www.blackwasp.co.uk/PriorityQueue.aspx

Thread.Sleep ve Thread.SpinWait arasındaki fark

26 February 2011 2 yorum

Thread sınıfı ile ilgili en çok karşılaştığım sorulardan birisi; “Thread.Sleep() ile Thread.SpinWait() method’ları arasındaki fark nedir?” olmuştur.

MSDN Process ve Thread dökümanları ne yazık ki bu konuda bize yeterli bilgi sağlamıyor.

Peki Thread sınıfının SpinWait() ve Sleep() method’ları arasındaki fark nedir?

Programming .Net Components kitabının yazarı Juval Löwy‘den alıntı (sayfa 192) yapacağım;

Orjinal : When a thread calls SpinWait(), the calling thread waits the number of iterations specified, and the thread is never added to the queue of waiting threads. As a result, the thread is effectively put to sleep without relinquishing the remainder of its CPU time slot.

The .NET documentation does not define what an iteration is, but it is likely mapped to a predetermined number (probably just one) of NOP (no-operations) assembly instructions. Consequently, the following SpinWait() instruction will take different time to complete on machines with different CPU clock speeds:

const long MILLION = 1000000;
Thread.SpinWait(MILLION);

SpinWait() is not intended to replace Sleep(), but is rather made available as an advanced optimization technique. If you know that some resource your thread is waiting for will become available in the immediate future, it is potentially more efficient to spin and wait, instead of using either Sleep() or a synchronization object, because those force a thread context switch, which is one of the most expensive operations performed by the operating system. Even in the esoteric cases for which SpinWait() was designed, using it is an educated guess at best. SpinWait() will gain you nothing if the resource is not available at the end of the call, or if the operating system preempts your thread because its time slot has elapsed, or because another thread with a higher priority is ready to run. In general, I recommend that you should always use deterministic programming (using synchronization objects in this case) and avoid optimization techniques.

Alıntı’nın önemli cümleleri;

Türkçesi : Eğer bir thread SpinWait() method’unu çağırırsa, parametre ile belirtilen CPU çevrimi boyunca beklemeye geçer ve Bekleyen Threadler (Waiting Threads) listesine kendini eklemez. Böylece, CPU’da bulunduğu slot’tan vazgeçmeden, uyku moduna geçmiş olur.

.NET dokümantasyonuna göre her CPU çevriminde (muhtemelen) bir adet NOP (no-operations) assembly komutu çalıştırır. Fakat, aşağıdaki SpinWait() komutu, farklı hızlarda çalışan CPU’larda farklı sürelerde tamamlanır.

const long MILLION = 1000000;
Thread.SpinWait(MILLION);

SpinWait() method’u, Sleep() method’unun yerine düşünülmemiştir, daha ileri seviye optimizasyon yapılabilmesi için amaçlanmıştır. Eğer çalışan thread’in ihtiyaç duyduğu kaynak, çok kısa süre içerisinde uygun olacaksa (mesela başka bir thread kaynak üzerinde bulunan lock’ı kaldıracaksa) Sleep() yerine SpinWait() kullanmak daha uygun olur.

Sleep() method’u (veya syncronization nesnesi), thread’in CPU üzerinde context switch yapmasına sebep olur.

Son cümle; SpinWait() method’u, çağıran thread’i, işlemci üzerinde aktif tutar, Sleep() method’u ise, thread’i belirli süre boyunca gerçek anlamda uyutur.