/*
* ptw32_OLL_lock.c
*
* Description:
* This translation unit implements extended reader/writer queue-based locks.
*
* --------------------------------------------------------------------------
*
* Pthreads-win32 - POSIX Threads Library for Win32
* Copyright(C) 1998 John E. Bossom
* Copyright(C) 1999,2005 Pthreads-win32 contributors
*
* Contact Email: rpj@callisto.canberra.edu.au
*
* The current list of contributors is contained
* in the file CONTRIBUTORS included with the source
* code distribution. The list can also be seen at the
* following World Wide Web location:
* http://sources.redhat.com/pthreads-win32/contributors.html
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library in the file COPYING.LIB;
* if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*/
/*
* About the OLL lock (Scalable Reader-Writer Lock):
*
* OLL locks are queue-based locks similar to the MCS queue lock, where the queue
* nodes are local to the thread but where reader threads can enter the critical
* section immediately without going through a central guard lock if there are
* already readers holding the lock.
*
* Covered by United States Patent Application 20100241774 (Oracle)
*/
#include "pthread.h"
#include "sched.h"
#include "implement.h"
/*
* C-SNZI support
*/
typedef union ptw32_oll_counter_t_ ptw32_oll_counter_t;
typedef struct ptw32_oll_snziRoot_t_ ptw32_oll_snziRoot_t;
typedef struct ptw32_oll_snziNode_t_ ptw32_oll_snziNode_t;
typedef union ptw32_oll_snziNodeOrRoot_t_ ptw32_oll_snziNodeOrRoot_t;
typedef struct ptw32_oll_queryResult_t_ ptw32_oll_queryResult_t;
typedef struct ptw32_oll_ticket_t_ ptw32_oll_ticket_t;
typedef struct ptw32_oll_csnzi_t_ ptw32_oll_csnzi_t;
enum
{
ptw32_archWidth = sizeof(size_t)*8,
ptw32_oll_countWidth = ptw32_archWidth-2
};
#define PTW32_OLL_MAXREADERS (((size_t)2<<(ptw32_oll_countWidth-1))-1)
union ptw32_oll_counter_t_
{
size_t word : ptw32_archWidth;
struct
{
/*
* This needs to be a single word
*
* ------------------------------------
* | STATE | ROOT | COUNT (readers) |
* ------------------------------------
* 63 / 31 62 / 30 61 / 29 .. 0
*/
size_t count : ptw32_oll_countWidth;
size_t root : 1; /* ROOT or NODE */
size_t state : 1; /* OPEN or CLOSED (root only) */
} internal;
};
struct ptw32_oll_snziRoot_t_
{
/*
* "counter" must be at same offset in both
* ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t
*/
ptw32_oll_counter_t counter;
};
enum
{
ptw32_oll_snziRoot_open = 0,
ptw32_oll_snziRoot_closed = 1
};
enum
{
ptw32_oll_snzi_root = 0,
ptw32_oll_snzi_node = 1
};
/*
* Some common SNZI root whole-word states that can be used to set or compare
* root words with a single operation.
*/
ptw32_oll_snziRoot_t ptw32_oll_snziRoot_openAndZero = {.counter.internal.count = 0,
.counter.internal.root = ptw32_oll_snzi_root,
.counter.internal.state = ptw32_oll_snziRoot_open};
ptw32_oll_snziRoot_t ptw32_oll_snziRoot_closedAndZero = {.counter.internal.count = 0,
.counter.internal.root = ptw32_oll_snzi_root,
.counter.internal.state = ptw32_oll_snziRoot_closed};
struct ptw32_oll_queryResult_t_
{
BOOL nonZero;
BOOL open;
};
union ptw32_oll_snziNodeOrRoot_t_
{
ptw32_oll_snziRoot_t* rootPtr;
ptw32_oll_snziNode_t* nodePtr;
};
struct ptw32_oll_snziNode_t_
{
/* "counter" must be at same offset in both
* ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t
*/
ptw32_oll_counter_t counter;
ptw32_oll_snziNodeOrRoot_t parentPtr;
};
struct ptw32_oll_ticket_t_
{
ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot;
};
ptw32_oll_ticket_t ptw32_oll_ticket_null = {NULL};
struct ptw32_oll_csnzi_t_
{
ptw32_oll_snziRoot_t proxyRoot;
ptw32_oll_snziNode_t leafs[];
};
/*
* FOLL lock support
*/
typedef struct ptw32_foll_node_t_ ptw32_foll_node_t;
typedef struct ptw32_foll_local_t_ ptw32_foll_local_t;
typedef struct ptw32_foll_rwlock_t_ ptw32_foll_rwlock_t;
enum
{
ptw32_srwl_reader,
ptw32_srwl_writer
};
enum
{
ptw32_srwl_free,
ptw32_srwl_in_use
};
struct ptw32_foll_node_t_
{
ptw32_foll_node_t* qNextPtr;
ptw32_oll_csnzi_t* csnziPtr;
ptw32_foll_node_t* nextPtr;
int kind;
int allocState;
BOOL spin;
};
struct ptw32_foll_local_t_
{
ptw32_foll_node_t* rNodePtr; // Default read node. Immutable
ptw32_foll_node_t* wNodePtr; // Write node. Immutable.
ptw32_foll_node_t* departFromPtr; // List node we last arrived at.
ptw32_oll_ticket_t ticket; // C-SNZI ticket
};
struct ptw32_foll_rwlock_t_
{
ptw32_foll_node_t* tailPtr;
ptw32_foll_node_t* rNodesPtr; // Head of reader node
};
/*
* ShouldArriveAtTree() returns true if:
* the compare_exchange in Arrive() fails too often under read access; or
* ??
* Note that this is measured across all access to
* this lock, not just this attempt, so that highly
* read-contended locks will use C-SNZI. Lightly
* read-contended locks can reduce memory usage and some
* processing by using the root directly.
*/
BOOL
ptw32_oll_ShouldArriveAtTree()
{
return PTW32_FALSE;
}
size_t
ptw32_oll_GetLeafForThread()
{
return 0;
}
/*
* Only readers call ptw32_oll_Arrive()
*
* Checks whether the C-SNZI state is OPEN, and if so,
* increments the surplus of the C-SNZI by either directly
* arriving at the root node, or calling TreeArrive on one
* of the leaf nodes. Returns a ticket pointing to the node
* that was arrived at. If the state is CLOSED, makes no
* change and returns a ticket that contains no pointer.
*/
ptw32_oll_ticket_t
ptw32_oll_Arrive(ptw32_oll_csnzi_t* csnzi)
{
for (;;)
{
ptw32_oll_ticket_t ticket;
ptw32_oll_snziRoot_t oldProxy = csnzi->proxyRoot;
if (oldProxy.counter.internal.state != ptw32_oll_snziRoot_open)
{
ticket.snziNodeOrRoot.rootPtr = (ptw32_oll_snziRoot_t*)NULL;
return ticket;
}
if (!ptw32_oll_ShouldArriveAtTree())
{
ptw32_oll_snziRoot_t newProxy = oldProxy;
newProxy.counter.internal.count++;
if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
(PTW32_INTERLOCKED_SIZEPTR)&csnzi->proxyRoot.counter,
(PTW32_INTERLOCKED_SIZE)newProxy.counter.word,
(PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
== (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word)
{
/* Exchange successful */
ticket.snziNodeOrRoot.rootPtr = &csnzi->proxyRoot;
return ticket;
}
}
else
{
ptw32_oll_snziNode_t* leafPtr = &csnzi->leafs[ptw32_oll_GetLeafForThread()];
ticket.snziNodeOrRoot.nodePtr = (ptw32_oll_TreeArrive(leafPtr) ? leafPtr : (ptw32_oll_snziNode_t*)NULL);
return ticket;
}
}
}
/*
* Decrements the C-SNZI surplus. Returns false iff the
* resulting state
Windows下POSIX多线程编程pthreads库
需积分: 0 139 浏览量
更新于2022-08-11
收藏 1.21MB ZIP 举报
在Windows操作系统上进行多线程编程时,通常我们会选择使用微软提供的API,如CreateThread或BeginThreadEx。然而,对于那些习惯于Unix/Linux环境下的POSIX线程(pthreads)编程模型的开发者,Windows同样提供了一个名为pthreads-w32的库,使得在Windows上可以使用POSIX线程接口。这个库是开源的,可以在跨平台项目中提供一致性,从而简化开发流程。
pthreads-w32库是一个移植层,它实现了大部分的POSIX线程函数,包括但不限于pthread_create、pthread_join、pthread_exit、pthread_mutex_init、pthread_rwlock_init等。这个库使得开发者能够在Windows环境下使用与Linux或Unix相似的线程API,无需关心底层操作系统差异。
1. **线程创建**:`pthread_create()`函数用于创建新的线程。它接受一个线程ID参数,一个线程属性参数,一个线程函数指针以及传递给该函数的任何参数。在Windows API中,对应的函数是`CreateThread()`。
2. **线程同步**:线程同步是多线程编程中的关键部分,防止数据竞争和死锁的发生。pthreads-w32提供了互斥量(`pthread_mutex_t`)和读写锁(`pthread_rwlock_t`)来实现这一目的。互斥量通过`pthread_mutex_lock()`和`pthread_mutex_unlock()`确保同一时间只有一个线程访问资源,而读写锁允许多个读线程同时访问,但写线程独占资源。
3. **线程终止**:`pthread_exit()`函数用于线程的正常退出,可以传递一个退出状态码。Windows API中,线程可以通过`ExitThread()`结束。
4. **线程等待**:`pthread_join()`函数用于等待一个特定线程的结束,并可获取其返回状态。在Windows API中,这相当于调用`WaitForSingleObject()`或`WaitForMultipleObjects()`。
5. **线程属性**:`pthread_attr_t`结构体用于设置线程属性,如栈大小、调度策略和优先级。这些属性可以通过`pthread_attr_init()`和`pthread_attr_set*()`系列函数初始化和设置。
6. **调度策略**:虽然Windows和Unix/Linux的调度策略有所不同,但pthreads-w32提供了基本的调度兼容性,如SCHED_RR和SCHED_FIFO。
7. **线程局部存储**:pthreads-w32也支持线程局部存储(TLS,Thread Local Storage),允许每个线程拥有自己的变量副本,避免了同步问题。
8. **线程安全的函数**:在pthreads-w32中,许多标准C库函数被标记为线程安全,这意味着它们可以在多线程环境中安全地使用。
9. **安装和使用pthreads-w32**:下载pthreads-w32-2.9.1-release压缩包后,需要按照官方文档进行编译和链接。开发者需要将头文件和库文件路径添加到项目设置中,以便编译器能够找到相应的函数声明和实现。
10. **调试和性能**:在Windows下使用pthreads-w32,开发者需要注意性能和调试方面可能存在的问题,因为这并不是原生的Windows API,可能需要额外的调试工具或技巧。
通过pthreads-w32库,开发者可以在Windows平台上编写与Unix/Linux系统兼容的多线程程序,这对于跨平台项目特别有帮助。同时,了解并熟练使用这个库能增强开发者对多线程编程的理解和实践能力。