Ranked Relevance Algoritmaları

Giriş
Nesneleri sıralarken doğal sıralama yanında, birden fazla özelliği puan vererek ilgi sıralaması da yapılabilir. Bu işlem için belli kriterlerin önem sırasına göre puan vermek gerekir.

Basit Bir Algoritma
Kriterler
Tam eşleme = 8
Tüm aramanın eşanlamlı eşleşmesi = 4
Bazı kelimelerin eşanlamlı eşleşmesi = 2
Değiştirilme tarihi = 1

Eğer 2 nin üsleri şeklinde puanlama yaparsak, üsteki bir kriter sebebiyle yüksek puan alan bir dokümana, daha alt seviyedeki bir dokümanın erişmesi, alt seviyedeki tüm kriterleri sağlasa dahi mümkün olmayacaktır.

Blocking,Non-Blocking ve Asenkron I/O

Blocking I/O

Blocking I/O ile sistem çağrısı yapan uygulama veri hazır oluncaya kadar bloke olur. Buradan aldığım şekilde durumu görmek mümkün.

Örneğin recvfrom metoduyla blocking mod ile çalışırken aşağıdakine benzer bir akış gerçekleşir.

Not : Linux üzerinde MSG_DONTWAIT seçeneği ile blocking modda olan bir socket non-blocking moddaymış gibi kullanılabilir. Örneğin :

status = send( sock, buffer, buflen, MSG_DONTWAIT );

Ancak bu kod portable değildir ve gönderilmek istenen verinin hepsi, bir kısmı ya da hiçbir kısmı gitmiş olabilir. Five pitfalls of Linux sockets programming başlıklı yazıda bu konuya değinilmiş.

Non-Blocking I/O

Açılan file descriptor (örneğin socket) fcntl() metodu ile non-blocking moda geçirilir.

fcntl başlıklı yazıda bu metod ile ilgili daha detaylı bilgi bulabilirsiniz.


File descriptor non-blocking moda  geçirildikten sonra select(), epoll() veya benzeri I/O çoklama çağrıları ile aşağıdakine benzer bir şekilde kullanılabilir.

I/O Çoklama (I/O Multiplexing)

I/O çoklama ile blocking sistem çağrıları yapmak yerine select(), poll(), epoll() gibi sistem çağrıları yaparak giriş/çıkış işlemleri çoklanıyor.

select() sistem çağrısı
select() sistem çağrısı en çok bilinen ve kullanılan Non-Blocking I/O sistem çağrılarındandır. "Berkeley socketleri" ile gelen bu sistem çağrısı Posix standardına da girmiştir.

Aşağıdaki şekli buradan aldım ve select() sistem çağrısının nasıl çalıştığını gösteriyor.

Şekilden de görüldüğü gibi fd_set veri yapısı aslında bir bit array. n_fds parametresi ise bit array içinde en büyük file descriptor değerinden bir tane daha büyük olmalı.
read_fds
Socketin okumaya hazır olup olmaması en çok kullanılan parametre.

write_fds
Parametre olarak geçilen write_fds çok kullanılmıyor. Socketler genellikle yazmaya hazır oluyorlar.

err_fsd
Parametre olarak geçilen err_fds çok kullanılmıyor. OOB (Out of band) gönderilen veriyi okumak için kullanıldığı yazılmış.

timeval
Bu sistem çağrısına verilen bekleme süresi ise aşağıdaki gibi.

Buradaki soruda da gösterildiği gibi select sistem çağrısı sonunda timeval değeri değişmiş olabilir. Yeni değer verilen bekleme süresinden geriye kaç saniye kaldığını gösterir.

Dikkat edilmesi gereken hususlardan birisi bekleme süresinin çözünürlüğünün microsaniye (saniyenin milyonda biri) seviyesinde olması. Diğeri ise sistem çağrısına geçen n_fds değerinin bit array içindeki en büyük elemanın index değerinden bir fazla olması. (the maximum file descriptor across all the sets, plus 1)

macrolar
select() ile kullanılan bitmap veriyapılarını daha kolay kullanabilmek içinse bazı macrolar tanımlanmış.

select'in sınırları
select() sistem çağrısı ile aynı anda işlenebilecek socket sayısı FD_SETSIZE makro değeri ile sınırlı. Bu değer de bir çok kütüphane de 1024 olarak tanımlı. Yani fd_set veri yapısına konulabilecek en büyük socket numarasını sınırlıyor. Bu yöntemim çalışması için Posix dokümanlarında geçmemesine rağmen Preventing reuse of file descriptors sorusunda cevaplandığı gibi socket() metodununda mümkün olan en küçük socket descriptor numarasını kullandığını tahmin ediyorum.


Bu konu ile ilgili olarak C10K problemi başlıklı yazıya göz atabilirsiniz. Dolayısıyla select() metodu aynı anda binlerce bağlantıya hizmet etmesi gereken sunucularda kullanılamaz.

Bu çağrı sonucunda dönen setin doldurulma sebeplerini gösteren tabloyu aşağıda bulabilirsiniz.

Berkeley Socketlerinde en çok kullanılan bazı metotları bilgi için aşağıya ekledim.

`select` on same fd from multiple threads sorusuna verilen cevapta birden fazla thread'in aynı anda select metodunu çağırabileceği söylenmiş. Bunu engelleyen bir uyarı POSIX standardında yok, ancak bu işlemin faydalı olmayacağı da söyleniyor.

select ve self_pipe
self pipe trick olarak anılan bu kullanım şeklinde, select içinde bekleyen thread'e socketler yanında bir de pipe file descriptor veriliyor. Böylece pipe'a bir şey yazarak select çağrısından çıkmak mümkün.  Örneği kısaltarak buradan aldım.

static int pfd[2];                      // File descriptors for pipe
static void handler(int sig)
{
    write(pfd[1], "x", 1);
}
int main(int argc, char *argv[])
{
    fd_set readfds;
    FD_ZERO(&readfds);
    //..populate with sockets
   
    //Create pipe before establishing signal handler to prevent race
    pipe(pfd);
    FD_SET(pfd[0], &readfds);           //Add read end of pipe to 'readfds'
    int nfds = max(nfds, pfd[0] + 1);
   
    //Make read and write ends of pipe nonblocking
    int flags = fcntl(pfd[0], F_GETFL);
    flags |= O_NONBLOCK;
    fcntl(pfd[0], F_SETFL, flags);
   
    flags = fcntl(pfd[1], F_GETFL);
    flags |= O_NONBLOCK;
    fcntl(pfd[1], F_SETFL, flags);
   
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_RESTART;           //Restart interrupted reads()s
    sa.sa_handler = handler;
    sigaction(SIGINT, &sa, NULL);
   
    select(nfds, &readfds, NULL, NULL, NULL);
   
    if (FD_ISSET(pfd[0], &readfds)){} // Handler was called
}

C# ve select()
C# gibi dillerde artık BSD socket seviyesinden iyice uzaklaşıldığı için select() sistem çağrısı da gizlenmiş durumda ancak halen select'e benzer yapılar kurmak mümkün. Aşağıdaki örneği buradan aldım ve bir TCPListener sınıfı ile select()'e kullanımına benzer döngü kurulmasını sağlıyor.

QT ve select()

QT QIODevice sınıfı ile gelen waitForReadyRead() ve diğer waitFor..() metodları ile select() kullanımını biraz daha soyutlamış vaziyette. Böylece signal/slot kullamadan yani event loop çevirmeden de socket kullanabilmek mümkün.

Yine QEventDispatcherUNIXPrivate kaynak kodunda select kullanıldığını görmek mümkün.

poll sistem çağrısı
poll() sistem çağrısı da select'e çok benziyor. Aşağıda metodu görmek mümkün.

select() çağrısından farklı olarak ayrı ayrı bit array sınıfları kullanmak yerine, bu sınıflar pollfd veri yapısı içinde toplanmış.Örnek:

poll() ile select() sistem çağrılarının socket sayısı arttıkça yavaşlamasının sebepleri arasında iki tane önemli madde sıralanıyor.

• Her select() ve poll() çağrısı için verilen array sınıfları user space'den kernel space'e kopyalanıyor
• Her çağrıda hem kernel hem de uygulama tüm array elemanlarını teker teker taramak zorunda

Bu sebeplerden aşağıdaki tabloda da görülebileceği gibi select() ve poll() diğer yöntemlere göre daha yavaş kalıyorlar.

 

epoll sistem çağrısı

epoll metodu yazısına taşıdım

 

Asenkron I/O

Unix üzerinde aio_read(), aio_write gibi metodlar ile yapılır. aio_write metodu ile verilen tampon arka planda bizim için yazılır. Yazma işlemi yine write işleminde olduğu gibi peyder pey de olabilir.

Akışı gösteren bir şekil aşağıda.

  

Asenkron Hata Kodları

Asenkron kodlarda metod çağrısı -1 döner ve hata kodu errno değişkenine bakılarak öğrenilir.

Bazı hata kodlarının açıklaması aşağıda.

EINPROGRESS : Bu  değer kodu aslında gerçek bir hatayı değil, istenilen işlemin yapılmaya devam ettiğini gösteriyor. 

EAGAIN : Socket olmayan bir başka file descriptor (örneğin pipe) üzerinde yapılan okuma işleminin  veri olmadığı için tekrarlanması gerektiğini bildirir.

EAGAIN  veya EWOULDBLOCK : Socket olan bir file descriptor üzerinde yapılan okuma işleminin  veri olmadığı için tekrarlanması gerektiğini bildirir. POSIX bu iki hatadan herhangi birisini dönebilir. Hata kodları farklı olabileceği için her iki kodu da kontrol etmek gerekir.

Aşağıdaki açıklaması mevcut.