공정성 : 어디에서 더 잘 처리 할 수 ​​있습니까?

Question

여기서 다중 프로그래밍에 대한 실용적인 경험을 나누고 싶습니다.

어제 저는 멀티 프로그램을 작성했습니다. P (뮤텍스)와 V (뮤텍스)로 보호되는 중요 섹션 아래에 공유 가능한 리소스에 대한 수정 사항을 넣었으며 이러한 중요한 섹션 코드는 공용 라이브러리에 저장되었습니다. 라이브러리는 (내 자신의) 동시 응용 프로그램에서 사용됩니다.

라이브러리의 공통 코드를 사용하고 독립적으로 작업을 수행 할 세 가지 응용 프로그램이 있습니다.

my library 
--------- 
work_on_shared_resource 
{ 
    P(mutex) 
    get_shared_resource 
    work_with_it 
    V(mutex) 
} 
    --------- 

my application 
----------- 
application1 
{ 
    *[ 
     work_on_shared_resource 
     do_something_else_non_ctitical 
    ] 
} 


application2 
{ 
    *[ 
     work_on_shared_resource 
     do_something_else_non_ctitical 
    ] 
} 


application3 
{ 
    *[ 
     work_on_shared_resource 
    ] 
} 

*[...] denote a loop. 
------------ 

Linux OS에서 응용 프로그램을 실행해야했습니다. 나는 OS가 모든 공정성으로 그 밑에서 실행되는 모든 프로세스를 스케줄링해야한다는 생각을 수년간 생각해왔다. 즉, 모든 프로세스와 리소스 사용량을 동일하게 제공합니다.

처음 두 응용 프로그램이 작동되면 데드락없이 완벽하게 실행됩니다. 그러나 세 번째 응용 프로그램이 실행되기 시작하면 항상 세 번째 응용 프로그램이 자원을 확보하지만 비 핵심 영역에서는 아무 것도하지 않기 때문에 다른 작업이 다른 작업을 수행 할 때 공유 리소스를 더 자주 가져옵니다. 따라서 다른 두 응용 프로그램은 거의 완전히 중단되었습니다. 세 번째 응용 프로그램이 강제 종료 된 경우 이전 두 응용 프로그램은 이전과 마찬가지로 작업을 다시 시작합니다.

나는 이것이 기아의 사례라고 생각하는데, 처음 두 응용 프로그램은 굶어 야했다.

이제 공정성을 어떻게 보장 할 수 있습니까?

이제 OS 스케줄러가 결백하고 장님이라고 믿기 시작했습니다. 누가 레이스에서 우승 했느냐에 달렸습니다. 그는 CPU와 리소스의 최대 파이를 확보했습니다.

라이브러리의 중요 섹션 코드에서 리소스 사용자의 공정성을 보장합니까?

아니면 우리는 욕심이 아닌 자유 주의적으로 공정성을 보장하기 위해 신청서에 남겨 두어야합니까?

제 생각에 공통 라이브러리에 대한 공평성을 보장하는 코드를 추가하는 것은 압도적 인 작업입니다. 반면에 응용 프로그램을 믿는다면 결코 100 % 공정성을 보장 할 수 없습니다. 공유 자원으로 작업 한 후 아주 작은 작업을 수행하는 응용 프로그램은 공유 자원으로 작업 한 후 무거운 처리를하는 응용 프로그램이 항상 굶어야하는 경주에서 우승해야합니다.

이 경우 가장 좋은 방법은 무엇입니까? 공정성과 방법을 보장하는 곳은 어디입니까? 감사합니다

,
스 리니 바스 나약

Answer 1

가 발생했습니다 연구는 동일한 공유를 보장하기 또는 감지하고 교착 상태를 피하기 위해 뮤텍스의 소유권을 취소에서 수행. 그러나 이것은 과도하고 과소 평가되어서 특히 계산을 수행하는 중에 프로그램이 어떻게 작동해야하는지, 리소스의 소유권을 잃어 버렸을 때와 같이 완전히 새로운 웜을 열 수 있기 때문에 그만한 가치는 없습니다. 다양한 스레드가 서로 공평하게 작동하고 교착 상태가 발생하지 않는 방식으로 리소스를 소비하도록하는 것은 애플리케이션에 달려 있습니다.

약간 다른 다양성이 있지만 다른 옵션이 있는데, 이는 메시지 전달 스타일의 병렬 프로그래밍을 사용한다는 것입니다. 메시지 전달과 함께, 동기화는 통신에 내재되어 있습니다. 명시적인 동기화가 필요하지 않으므로 이러한 오류를 피할 수 있습니다.

Answer 2

"응용 프로그램 3"프로세스가 뮤텍스를 잠금 해제 한 후에 계속 실행되므로 즉시 다시 획득 할 수 있기 때문에 문제가 발생합니다.

각 스레드가 차단 될 때 각 스레드가 큐에 추가되고 큐의 첫 번째 스레드가 리소스를 사용할 수있게되면 항상 가져 오는 공정한 큐잉 시스템을 구현할 수 있습니다. 조건 변수를 사용하여이를 빌드 할 수 있습니다. pthreads 프리미티브를 기반으로 작성된 "공정한"티켓 잠금은 다음과 같을 수 있습니다.

#include <pthread.h> 

typedef struct ticket_lock { 
    pthread_cond_t cond; 
    pthread_mutex_t mutex; 
    unsigned long queue_head, queue_tail; 
} ticket_lock_t; 

#define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER } 

void ticket_lock(ticket_lock_t *ticket) 
{ 
    unsigned long queue_me; 

    pthread_mutex_lock(&ticket->mutex); 
    queue_me = ticket->queue_tail++; 
    while (queue_me != ticket->queue_head) 
    { 
     pthread_cond_wait(&ticket->cond, &ticket->mutex); 
    } 
    pthread_mutex_unlock(&ticket->mutex); 
} 

void ticket_unlock(ticket_lock_t *ticket) 
{ 
    pthread_mutex_lock(&ticket->mutex); 
    ticket->queue_head++; 
    pthread_cond_broadcast(&ticket->cond); 
    pthread_mutex_unlock(&ticket->mutex); 
}