怎么让客户做网站,东莞+网站+建设+汽车,seo裤子的关键词首页排名有哪些,做网络平台的网站有哪些1 背景
同步互斥回顾:
并发问题: 竞争条件(竞态条件)
多程序并发存在大量问题
同步
多线程共享公共数据的协调执行包括互斥与条件同步互斥: 在同一时间只有一个线程可以执行临界区
确保线程同步
需要高层次的编程抽象(如: 锁)从底层硬件支持编译
2 信号量
信号量是抽象数…1 背景
同步互斥回顾:
并发问题: 竞争条件(竞态条件)
多程序并发存在大量问题
同步
多线程共享公共数据的协调执行包括互斥与条件同步互斥: 在同一时间只有一个线程可以执行临界区
确保线程同步
需要高层次的编程抽象(如: 锁)从底层硬件支持编译
2 信号量
信号量是抽象数据类型
信号量用一个整形(sem)表示, 具有两个原子操作P(): sem减1, 如果sem 0, 等待, 否则继续V(): sem加1, 如果sem 0, 唤醒一个等待的P
3 信号量使用
3.1 信号量的一些属性
信号量是整数(有符号)信号量是被保护的变量初始化完成后, 唯一改变一个信号量的值的办法是通过P()和V()操作必须是原子P()能够阻塞, V()不会阻塞我们限定信号量是公平的没有线程被阻塞在P()仍然阻塞如果V()被无限频繁调用(在同一个信号量)在实践中, FIFO(先阻塞先被唤醒)经常被使用(如果只能唤醒一个进程)(忙等的锁没有这种先等先唤醒机制)3.2 信号量的实现简介
信号量实现一般有两种:
二进制信号量: 可以是0或1一般/计数信号量: 可取任何非负值两者互相表现(给定一个可以实现另一个)
信号量可以用在两个方面:
互斥条件同步(调度约束 -- 一个线程等待另一个线程的事情发生)
用二值信号量实现互斥功能:
mutex new Semaphore(1); //初始化一个值为1的信号量作为一个锁mutex-P(); //信号量减1
//执行临界区代码, 此时如果有其他线程要进入临界区, 也需要mutex-P(), 也就会让信号量的值为-1,
//也就会被阻塞
mutex-V(); //信号量加1
用二值信号量实现同步:
condition new Semaphore(0);// Thread A
condition-P() //A线程等待condition-V()// Thread B
condition-V() //B线程唤醒, 也就是同步
用计数信号量还可以实现生产者 - 消费者问题:
有界缓冲区(buffer)的生产者 - 消费者问题, 有以下性质:
一个或多个生产者产生数据将数据放在一个缓冲区(buffer)里单个消费者每次从缓冲区取出数据在任何一个时间只有一个生产者或消费者可以访问该buffer
这个问题用互斥(锁机制)是不够的.
而且具有正确性要求:
在任何一个时间只能有一个线程操作buffer(互斥)当buffer为空, 消费者必须等待生产者(调度/同步约束)当缓存区满, 生产者必须等待消费者(调度同步约束)
根据以上要求和性质:
如果每个约束用一个单独的信号量, 有以下信号量设计:
二进制信号量互斥一般信号量fullBuffers一般信号量emptyBuffers
代码设计:
class BoundedBuffer{mutex new Semaphore(1);fullBuffers new Semaphore(0);emptyBuffers new Semaphore(n);
}BoundedBuffer::Deposit(c) {emptyBuffers-P(); //需保证buffer还有空闲, 如果无空闲, 则等待mutex-P(); //要保证对buffer的操作的互斥性Add c to the buffer;mutex-V();fullBuffers-V(); //有数据进入
}BoundedBuffer::Remove(c) {fullBuffers-P(); //需保证buffer有数据, 如果无数据, 则等待mutex-P(); //要保证对buffer的操作的互斥性Remove c from buffer;mutex-V();emptyBuffers-V(); //取出数据
}
4 信号量实现
针对信号量的P()和V()操作的实现, 需要使用硬件原语:
禁用中断原子指令(Test - And - Set)
具体实现:
class Semaphore{int sem;WaitQueue q;
}Semaphore::P(){sem --;if (sem 0) {Add this thread t to q;block(p);}
}Semaphore::V(){sem ;if (sem 0) {Remove a thread t from q;wakeup(t);}
}
实现中需要注意的细节:
信号量的双用途互斥和条件同步但等待条件是独立的互斥读/开发代码比较困难程序员必须非常精通信号量容易出错使用的信号量已经被另一个线程占用忘记释放信号量 不能够处理死锁问题
5 管程
管程的目的:
分离互斥和条件同步的关注
什么是管程:
一个锁: 指定临界区0或者多个条件变量: 等待/通知信号量用于管理并发访问的共享数据
一般方法:
收集在对象/模块中的相关共享数据定义方法来访问共享数据
简单步骤:
获取进入管程的锁从而进入管程管程中对共享资源进行操作当需要等待时候, 信号量调用wait自身睡眠并把进入管程的锁进行释放当资源得到满足, 信号量会调用signal从而唤醒正在这个信号量睡眠的线程
条件变量的实现:
class Condition{int numWaiting 0;WaitingQueue q;
}Condition::Waiting(lock){numWaiting ;Add this thread to q;release(lock);schedule(); //need mutex, 选择下一个线程去执行require(lock)
}Condition::Signal(){if (numWaiting 0) {Remove a thread t from q;wakeup(t); //need mutex, 把该线程置为ready状态numWaiting --;}
}
管程实现生产者 - 消费者问题:
需要维持每个条件队列线程等待的条件等待signal()
class BoundedBuffer{Lock lock;int count 0;Condition notFull, notEmpty;
}BoundedBffer::Deposit(c){lock-Acquire();while(count n)notFull.Wait(lock);Add c to the buffer;count ;notEmpty.Signal();lock-Release();
}BoundedBuffer::Remove(c){lock-Acquire();while(count 0)notEmpty.Wait(lock);Remove c from buffer;count --;notFull.Signal();lock-Release();
}
6 经典同步问题
6.1 读者 - 写者问题
问题动机:
共享数据的访问
两种类型的使用者:
读者: 不需要修改数据写者: 读取和修改数据
问题的约束:
允许同一时间有多个读者, 但在任何时候只有一个写者当没有写者时读者才能访问数据当没有读者和写者时写者才能访问数据在任何时候只能有一个线程可以操作共享变量
设计思路:
需要有以下共享数据:数据集, 也就是要进行读或者写的数据信号量CountMutex初始化为1信号量WriteMutex初始化为1整数Rcount初始化为0(正在执行读操作的数量)6.1.1 读者优先
基于读者优先策略的方法: 只要有一个读者处于活动状态, 后来的读者都会被接纳. 如果读者源源不断出现的话, 那么写者就始终处于阻塞状态.
写操作: Writer
sem_wait(WriteMutex); //相当于WriteMutex-P(), 保证只有一个线程在执行写操作, 以及在写操作过程中没有读操作write;sem_post(WriteMutex); //相当于WriteMutex-V()读操作: Reader
sem_wait(CountMutex); //保证对Rcount操作的互斥性
if(Rcount 0)sem_wait(WriteMutex); //说明此时没有读操作, 是有可能有写操作的, 所以需要等待写操作结束Rcount;
sem_post(CountMutex);read;sem_wait(CountMutex);
-- Rcount;if (Rcount 0)sem_post(WriteMutex);sem_post(CountMutex);
6.1.2 写者优先
基于写者优先策略的方法: 一旦写者就绪, 那么写者会尽可能快地执行写操作. 如果写者源源不断地出现的话, 那么读者就始终处于阻塞状态.
需要的变量:
AR 0 //active readers正在执行读操作的线程个数AW 0 //active writers正在执行写操作的线程个数WR 0 //waiting readers正在等待读操作的线程个数WW 0 //waiting writers正在等待写操作的线程个数Condition okToReadCondition okToWriteLock lock
读操作:
Read(){//wait until no writersstartRead();read database;//check out - wake up waiting writers;doneRead();
}startRead(){lock.Acquire();while ((AW WW) 0) { //如果有写者, 写者优先WR ;okToRead.wait(lock);WR --;}AR ;lock.release();
}doneRead(){lock.Acquire();AR --;if (WW 0 AR 0) { //需要唤醒等待的写者okToWrite.signal();}lock.Release();
}
写操作:
Write() {//Wait until no readers/writersstartWrite();write database;//check out - wake up waiting readers/writers;doneWrite();
}startWrite(){lock.Acquire();while((AR AW) 0) { //需要等待正在写或者读的操作结束后WW ;okToWrite.wait(lock);WW --;}lock.Release();
}doneWrite() {lock.Acquire();AW --;if (WW 0) {okToWrite.signal();} else if (WR 0) {okTORead.broadcast();}lock.Acquire();
} 6.2 哲学家就餐问题
问题描述(1965年由Di jkstra首先踢出并解决):
5个哲学家围绕一张圆桌而坐, 桌子上放着5支叉子, 每两个哲学家之间放一支; 哲学家的动作包括思考和进餐, 进餐时需要同时拿起他左边和右边的两支叉子, 思考时则同时将两支叉子放回原处. 如何保证哲学家们的动作有序进行? 如: 不会出现有人永远拿不到叉子.
共享数据:
bowl of rice(data set)Semaphore fork[5] initialized to 1
思路:
必须有数据结构, 来描述每个哲学家的当前状态
#define N 5 //哲学家个数
#define LEFT i //第i个哲学家的左邻居
#define RIGHT (i 1) % N //第i个哲学家的右邻居
#define THINKING 0 //思考状态
#define HUNGRY 1 //饥饿状态
#define EATING 2 //进餐状态
int state[N]; //记录每个人的状态
该状态是一个临界资源, 每个哲学家对它的访问应该互斥地进行 -- 进程互斥
semaphore mutex; //互斥信号量, 初值1
一个哲学家吃饱后, 可能要唤醒它的左邻右舍, 两者之间存在着同步关系 -- 进程同步
semaphore s{N}; //同步信号量, 初值0
函数philosopher定义(哲学家流程定义)
void philosopher(int i){ //i的取值: 0到N - 1, 代表着第几个哲学家while(true){ //封闭式循环think();take_forks(i); //拿到两把叉子或被阻塞eat();put_forks(i); //把两把叉子放回原处}
}
函数take_forks的定义
void take_forks(int i){ //i的取值: 0到N - 1P(mutex); //进入临界区state[i] HUNGRY;test_take_left_right_forks(i); //试图拿两把叉子V(mutex); //退出临界区P(s[i]); //没有叉子便被阻塞
}void test_take_left_right_forks(int i) {if (state[i] HUNGRY state[LEFT] ! EATING state[RIGHT] ! EATING) {state[i] EATING;V(s[i]); //通知第i个人可以拿起左右叉子吃饭了}
}
函数put_forks定义
//功能: 把两把叉子放回原处, 并在需要的时候,
//去唤醒左邻右舍
void put_forks(int i){P(mutex);state[i] THINKING; //交出两把叉子//提醒左右邻居其相邻状态有改变, 让其从阻塞态恢复, 重新执行循环检查test_take_left_right_forks(LEFT);test_take_left_right_forks(RIGHT);V(mutex);
}
