在操作系统中 同步与互斥是一个重要问题,这里主要研究一下怎样用Java来实现操作系统中的一些同步互斥算法。
一,软件实现临界区域问题
在《操作系统概念(第七版)》中,7.2讨论了临界区域问题,下面给出算法和Java实现代码。
1.1 算法2
算法2的伪代码如下:
do{
flag[i]=true;
while(flag[j]);
临界区;
flag[i]=false;
剩余区;
}while(1)
Java实现代码如下:
package mutiple_thread;
public class OS_SYN_A2{
public static int flag[]=new int [3];
public static int cnt=0;
public static void main(String args[]){
class proo implements Runnable{
public proo(){
}
@Override
public void run() {
// TODO Auto-generated method stub
while(true){
flag[1]=1;
while(flag[2]==1){
}
if(cnt==5){
flag[1]=0;
}else{
cnt++;
System.out.println("pro ++! now id"+cnt);
flag[1]=0;
}
}
}
}
class conn implements Runnable{
@Override
public void run() {
// TODO Auto-generated method stub
while(true){
flag[2]=1;
while(flag[1]==1){
}
//临界区
if(cnt==0){
flag[2]=0;
}else{
cnt--;
System.out.println("con --! now id"+cnt);
//退出临界区
flag[2]=0;
}
}
}
}
new Thread(new proo()).start();
new Thread(new conn()).start();
}
}
这个算法的主要思路是通过设置flag来确定执行哪个线程,但是可能会造成饥饿,因此不行。
1.2 算法3
算法3通过共享两个变量 flag 和turn来实现同步。
package mutiple_thread;
public class OS_SYN_A3{
public static int flag[]=new int [3];
public static int turn=0;
public static int cnt=0;
public static void main(String args[]){
class proo implements Runnable{
public proo(){
}
@Override
public void run() {
// TODO Auto-generated method stub
while(true){
flag[1]=1;
turn=2;
while(flag[2]==1&&turn==2){
}
if(cnt==5){
flag[1]=0;
}else{
cnt++;
System.out.println("pro ++! now id"+cnt);
flag[1]=0;
}
}
}
}
class conn implements Runnable{
@Override
public void run() {
// TODO Auto-generated method stub
while(true){
flag[2]=1;
turn=1;
while(flag[1]==1&&turn==1){
}
//临界区
if(cnt==0){
flag[2]=0;
}else{
cnt--;
System.out.println("con --! now id"+cnt);
//退出临界区
flag[2]=0;
}
}
}
}
new Thread(new proo()).start();
new Thread(new conn()).start();
}
}
这是一种正确的软件实现方法。
2.经典同步问题的Java实现
2.1 读者写者问题
这里实现的读者优先的算法,使用了Java并发包的信号量来实现。
实现的伪代码如下:
读者进程:
while(1){
wait(mutex)
count++;
if(readercount==1){
wait(writer);
}
signal(mutex);
do reading;
wait(mutex);
cnt--;
if(cnt==0){
signal(writer);
}
signal(mutex);
}
}
算法通过共享writer和mutex两个信号量,来处理同步问题
package mutiple_thread;
import java.util.concurrent.Semaphore;
public class OS_Readerwriter{
static Semaphore sem=new Semaphore(1);
static Semaphore sem_wrt=new Semaphore(1);
static int readercount=0;
static String a="hahaha";
public static void main(String args[]){
class reader implements Runnable{
public reader(){
}
@Override
public void run() {
// TODO Auto-generated method stub
try {
sem.acquire();
readercount++;
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
if(readercount==1){
try {
sem_wrt.acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
sem.release();
System.out.println("Reading "+a);
try {
sem.acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
readercount--;
if(readercount==0){
sem_wrt.release();
}
sem.release();
}
}
class writer implements Runnable{
public writer(){
}
@Override
public void run() {
// TODO Auto-generated method stub
try {
sem_wrt.acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
a=a+"abc";
System.out.println("Writing "+a);
sem_wrt.release();
}
}
for(int i=1;i<=10;i++){
new Thread(new writer()).start();
new Thread(new reader()).start();
}
}
}
2.2 哲学家问题
算法思路:通过对每一只筷子设置信号量,来进行同步判断。
Java实现代码如下:
package mutiple_thread;
import java.util.concurrent.Semaphore;
public class OS_Philosopher{
static int chop[]=new int [7];
static Semaphore []sem=new Semaphore[7];
public static void main(String args[]) throws InterruptedException{
for(int i=0;i<=6;i++){
sem[i]=new Semaphore(1);
}
Thread.sleep(1000);
class philosopher implements Runnable{
int i;
public philosopher(int i){
this.i=i;
}
@Override
public void run() {
// TODO Auto-generated method stub
while(true){
try {
synchronized(this){
sem[i].acquire();
sem[(i+1)%5].acquire();
}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("Phi"+i+" is Eating");
//sleep();
try {
Thread.sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
sem[i].release();
sem[(i+1)%5].release();
System.out.println("Phi"+i+" is Thinking");
//sleep();
try {
Thread.sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
philosopher t1=new philosopher(1);
philosopher t2=new philosopher(2);
philosopher t3=new philosopher(3);
philosopher t4=new philosopher(4);
philosopher t5=new philosopher(5);
new Thread(t1).start();
new Thread(t2).start();
new Thread(t3).start();
new Thread(t4).start();
new Thread(t5).start();
}
}
2.3 理发店问题:
理发店理有一位理发师、一把理发椅和 5 把供等候理发的顾客坐的椅 子。如果没有顾客,理发师便在理发椅上睡觉。一个顾客到来时,它必须叫 醒理发师。如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,就 坐下来等待,否则就离开。
算法思路如下:采用信号量进行判断。初始值为1,即是有一个理发师在服务。
实现代码如下:
package mutiple_thread;
import java.util.concurrent.Semaphore;
public class OS_Barber1{
static int cnt = 0;
static int MAX = 5;
static int busy = 0;
static Semaphore sem=new Semaphore(1);
public static void main(String args[]) throws InterruptedException{
OS_Barber1 bar=new OS_Barber1();
for(int i=1;i<=20;i++){
new Thread(new Bar1(bar,i)).start();
Thread.sleep((int) (400 - Math.random() * 300));
}
}
public synchronized boolean isFull() {
if (cnt == MAX) {
return true;
}
return false;
}
public synchronized boolean isEmpty() {
if (cnt == 0) {
return true;
}
return false;
}
public synchronized boolean isBusy() {
if (busy == 1) {
return true;
}
return false;
}
public void Gobar(int index) throws InterruptedException{
System.out.println("Con"+index+" is coming");
cnt++;
//判断是否满
if(isFull()){
System.out.println("Is full,"+"Con"+index+" is leaving");
cnt--;
}else{
if(busy==1){
System.out.println("Con"+index+" is waitting");
}
//sem.acquire();
synchronized (this){
while(busy==1){
//若有人在理发,则等待
wait();
}
}
if(cnt==1){
System.out.println("Con"+index+" is wake");
}
busy=1;
System.out.println("Con"+index+" is Serving");
Thread.sleep(1000);
System.out.println("Con"+index+" is leaving");
cnt--;
//sem.release();
synchronized (this){
busy=0;
//唤醒
notify();
}
if(cnt==0){
System.out.println("Bar is sleep");
}
}
}
}
class Bar1 implements Runnable {
OS_Barber1 ob;
int index;
public Bar1(OS_Barber1 ob,int i) {
this.ob = ob;
index=i;
}
@Override
public void run() {
// TODO Auto-generated method stub
try {
ob.Gobar(index);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
在算法中我使用了wait(),notify()来实现,也可以使用信号量来实现,注释部分就是使用信号量的实现。
在实现过程中,我发现了一些问题,也就是下面要讨论的wait() 和notify() 和notifyAll()
3 wait() ,notify() 和notifyAll()
synchronized 方法控制对类成员变量的访问:每个类实例对应一把锁,每个 synchronized 方法都必须获得调用该方法的类实例的锁方能执行,否则所属线程阻塞,方法一旦执行,就独占该锁,直到从该方法返回时才将锁释放,此后被阻塞的线程方能获得该锁,重新进入可执行状态。
wait()/notify():调用任意对象的 wait() 方法导致线程阻塞,并且该对象上的锁被释放。而调用 任意对象的notify()方法则导致因调用该对象的 wait() 方法而阻塞的线程中随机选择的一个解除阻塞(但要等到获得锁后才真正可执行)。
synchronized和wait()、notify()的关系
1.有synchronized的地方不一定有wait,notify
2.有wait,notify的地方必有synchronized.这是因为wait和notify不是属于线程类,而是每一个对象都具有的方法,而且,这两个方法都和对象锁有关,有锁的地方,必有synchronized。
另外,请注意一点:如果要把notify和wait方法放在一起用的话,必须先调用notify后调用wait,因为如果调用完wait,该线程就已经不是current thread了。
注:调用wait()方法前的判断最好用while,而不用if;while可以实现被wakeup后thread再次作条件判断;而if则只能判断一次;
线程的四种状态
1. 新状态:线程已被创建但尚未执行(start() 尚未被调用)。
2. 可执行状态:线程可以执行,虽然不一定正在执行。CPU 时间随时可能被分配给该线程,从而使得它执行。
3. 死亡状态:正常情况下 run() 返回使得线程死亡。调用 stop()或 destroy() 亦有同样效果,但是不被推荐,前者会产生异常,后者是强制终止,不会释放锁。
4. 阻塞状态:线程不会被分配 CPU 时间,无法执行。
首先,前面叙述的所有方法都隶属于 Thread 类,但是这一对 (wait()/notify()) 却直接隶属于 Object 类,也就是说,所有对象都拥有这一对方法。初看起来这十分不可思议,但是实际上却是很自然的,因为这一对方法阻塞时要释放占用的锁,而锁是任何对象都具有的,调用任意对象的 wait() 方法导致线程阻塞,并且该对象上的锁被释放。而调用 任意对象的notify()方法则导致因调用该对象的 wait() 方法而阻塞的线程中随机选择的一个解除阻塞(但要等到获得锁后才真正可执行)。
其次,前面叙述的所有方法都可在任何位置调用,但是这一对方法却必须在 synchronized 方法或块中调用,理由也很简单,只有在synchronized 方法或块中当前线程才占有锁,才有锁可以释放。
同样的道理,调用这一对方法的对象上的锁必须为当前线程所拥有,这样才有锁可以释放。因此,这一对方法调用必须放置在这样的synchronized 方法或块中,该方法或块的上锁对象就是调用这一对方法的对象。若不满足这一条件,则程序虽然仍能编译,但在运行时会出现IllegalMonitorStateException 异常。
wait() 和 notify() 方法的上述特性决定了它们经常和synchronized 方法或块一起使用,将它们和操作系统的进程间通信机制作一个比较就会发现它们的相似性:synchronized方法或块提供了类似于操作系统原语的功能,它们的执行不会受到多线程机制的干扰,而这一对方法则相当于 block 和wakeup 原语(这一对方法均声明为 synchronized)。它们的结合使得我们可以实现操作系统上一系列精妙的进程间通信的算法(如信号量算法),并用于解决各种复杂的线程间通信问题。关于
wait() 和 notify() 方法最后再说明两点:
第一:调用 notify() 方法导致解除阻塞的线程是从因调用该对象的 wait() 方法而阻塞的线程中随机选取的,我们无法预料哪一个线程将会被选择,所以编程时要特别小心,避免因这种不确定性而产生问题。
第二:除了 notify(),还有一个方法 notifyAll() 也可起到类似作用,唯一的区别在于,调用 notifyAll() 方法将把因调用该对象的wait() 方法而阻塞的所有线程一次性全部解除阻塞。当然,只有获得锁的那一个线程才能进入可执行状态。
谈到阻塞,就不能不谈一谈死锁,略一分析就能发现,suspend() 方法和不指定超时期限的 wait() 方法的调用都可能产生死锁。遗憾的是,Java 并不在语言级别上支持死锁的避免,我们在编程中必须小心地避免死锁。
以上我们对 Java 中实现线程阻塞的各种方法作了一番分析,我们重点分析了 wait() 和 notify()方法,因为它们的功能最强大,使用也最灵活,但是这也导致了它们的效率较低,较容易出错。实际使用中我们应该灵活使用各种方法,以便更好地达到我们的目的。
分享到:
相关推荐
java并发编程 基础知识,守护线程与线程, 并行和并发有什么区别? 什么是上下文切换? 线程和进程区别 什么是线程和进程? 创建线程有哪几种方式?,如何避免线程死锁 线程的 run()和 start()有什么区别? 什么是 ...
Java并发编程 背景介绍 并发历史 必要性 进程 资源分配的最小单位 线程 CPU调度的最小单位 线程的优势 (1)如果设计正确,多线程程序可以通过提高处理器资源的利用率来提升系统吞吐率 ...
第一章 Java 并发编程实践基础..............................................................1 1.1 进程与线程.................................................................................................
本资源涵盖了Java并发编程的理论基础和实践,主要包括可见性、原子性和有序性的详细介绍,以及多线程的使用原因、好处和坏处等方面的内容。 Java并发编程是一种高效的编程技术,通过多线程实现将计算过程中不必要的...
本篇文章提供了20道高难度的Java多...通过研究和解答这些高难度问题,您将提升自己的并发编程能力,展现出对Java多线程编程的深刻理解和掌握。不仅可以帮助您在面试中脱颖而出,更能够在实际项目开发中应对并发挑战。
在进行多线程编程时,经常要使用同步互斥机构,但Java本身没有提供的同步互斥机构,仅提供了两个与同步互斥有关的方法:wait()和notify(),可以用来设计信号量类:mySemaphore,它是按照Dijkstra提出的计数信号量的...
在Java领域中, 尤其是在并发编程领域,对于多线程并发执行一直有两大核心问题:同步和互斥。其中: - 互斥(Mutual Exclusion):一个公共资源同一时刻只能被一个进程或线程使用,多个进程或线程不能同时使用公共...
在并发编程领域,有两大核心问题:一个是互斥,即同一时刻只允许一个线程访问共享资源;另一个是同步,即线程之间如何通信、协作。 主要原因是,对于多线程实现实现并发,一直以来,多线程都存在2个问题: ● 线程...
线程安全问题的产生是因为多个线程并发访问共享数据造成的,如果能将多个线程对共享数据的并发访问改为串行访问,即一个共享数据同一时刻只能被一个线程访问,就可以避免线程安全问题。锁正是基于这种思路实现的一种...
并发编程解决的核心问题 分工(如何高效地拆解任务并分配给线程)Fork/Join 框架 同步(指的是线程之间如何协作)CountDownLatch 互斥(保证同一时刻只允许一个线程访问共享资源)可重入锁 如何学习 跳出来,看全景...
Synchronized是Java中解决并发问题的一种常用的方法,也是简单的一种方法。Synchronized的作用主要有三个:(1)确保线程互斥的访问同步代码(2)保证共享变量的修改能够及时可见(3)有效解决重排序问题。从语法...
4. 多线程:面试官可能会提问关于多线程编程的问题,如线程的生命周期、线程同步和互斥、线程安全等。您还可能会被要求解释Java中的锁机制、线程池、并发工具类等。 5. 异常处理:面试官可能会询问您关于Java异常...
为了对多个相关进程在执行次序上进行协调,以使并发执行的诸程序之间能有效地共享资源和相互合作,使程序的执行具有可再现性,所以引入了进程同步的概念。信号量机制是一种卓有成效的进程同步工具。 在生产者---消费...
并发编程的模型分类在并发编程需要处理的两个关键问题是:线程之间如何通信和线程之间如何同步。通信通信是指线程之间以何种机制来交换信息。在命令式编程中,线程之间的通信机制有两种:共享内存和消息传递。在共享...
在并发编程中,我们需要处理两个关键问题:线程之间如何通信及线程之间如何同步(这里的线程是指并发执行的活动实体)。通信是指线程之间以何种机制来交换信息。在命令式编程中,线程之间的通信机制有两种:共享内存...
锁是java并发编程中重要的同步机制。锁除了让临界区互斥执行外,还可以让释放锁的线程向获取同一个锁的线程发送消息。 下面是锁释放-获取的示例代码: class MonitorExample { int a = 0; public ...
在并发编程中,多个线程之间采取什么机制进行通信(信息交换),什么机制进行数据的同步?在Java语言中,采用的是共享内存模型来实现多线程之间的信息交换和数据同步的。线程之间通过共享程序公共的状态,通过读-写...