精华内容
下载资源
问答
  • 信号量与互斥锁

    2014-11-16 21:18:06
     临界区:临界区是指并发进程中与共享变量有关的程序段 ——关键程序段  信号量s是非负整数的全局变量,表示可用资源数量(我们可以引申,当它的值小于0时,其绝对值表示等待使用该资源的进程个数)  值得注意...

    这是多线程并发两个非常重要的概念,二者有很亲密的关系,但又不相同。

    1.概念:

       临界区:临界区是指并发进程中与共享变量有关的程序段 ——关键程序段

       信号量s是非负整数的全局变量,表示可用资源数量(我们可以引申,当它的值小于0时,其绝对值表示等待使用该资源的进程个数)

       值得注意的是,信号量的值能且只能由两种特殊的操作即P(P操作原语)和V(V操作原语)来处理:

       P(s):如果s是非零的,那么P将s 减1(表示可用资源的数量减少),并且立即返回(返回到哪里?重复对s操作,判断s是否非零,是则挂起线程,不是则减1)。如果s为零,那么就挂起这个线程,直到s变为非零,而一个V操作会重启这个线程。在重启之后,P操作将s减1,并将控制返回给调用者。

       P(S):
                ①将信号量S的值减1,即S=S-1;

                ②如果S>=0,则该进程继续执行;否则该进程置为等待状态

      

        V(s):V操作将s加1(释放资源)。如果s为零,那么V就有重启任意且唯一一个的线程的功能,然后该线程将s减1,完成它的P操作。

        V(S):
                ①将信号量S的值加1,即S=S+1;

                ②该进程继续执行;如果该信号的等待队列中有等待进程就唤醒一等待进程。


       信号量的特性如下:信号量是一个非负整数(车位数),所有通过它的线程/进程(车辆)都会将该整数减一(通过它当然是为了使用资源),当该整数值为零时,所有试图通过它的线程都将处于等待状态。在信号量上我们定义两种操作: Wait(等待) 和 Release(释放)。当一个线程调用Wait操作时,它要么得到资源然后将信号量减一,要么一直等下去(指放入阻塞队列),直到信号量大于等于一时。Release(释放)实际上是在信号量上执行加操作,对应于车辆离开停车场,该操作之所以叫做“释放”是因为释放了由信号量守护的资源。      ——百度百科

       二元信号量:信号量提供了一种很方便的方法来确保对共享变量的互斥访问,即将每个共享变量与一个信号量s(初始为1)联系起来,然后P(s)和V(S)操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量就是二元信号量(因为它的值只为0和1,即对于一个资源(这里一般是一个关键段(代码,有共享变量,不可冲突使用))来说,只有可用不可用两种情况,0为忙。1为空闲可用).

       互斥锁:以提供互斥为目的的二元信号量。

       加锁:在一个互斥锁上执行P操作。

       解锁:在一个互斥锁上执行V操作。

       两个线程不能同时对同一个互斥对象加锁。

       互斥对象是这样工作的:如果线程 a 试图锁定一个互斥对象,而此时线程 b 已锁定了同一个互斥对象时,线程 a 就将进入睡眠状态。一旦线程 b 释放了互斥对象(通过 V(&mutex) 调用),线程 a 就能够锁定这个互斥对象(换句话说,线程 a 就将从 P(&mutex) 函数调用中返回,同时互斥对象被锁定)。同样地,当线程 a 正锁定互斥对象时,如果线程 c 试图锁定互斥对象的话,线程 c 也将临时进入睡眠状态。对已锁定的互斥对象上调用P(&mutex) 的所有线程都将进入睡眠状态,这些睡眠的线程将“排队”访问这个互斥对象。通常使用P(&mutex) 和 V(&mutex) 来保护数据结构。这就是说,通过线程的锁定和解锁,对于某一数据结构,确保某一时刻只能有一个线程能够访问它。可以推测到,当线程试图锁定一个未加锁的互斥对象时,POSIX 线程库将同意锁定,而不会使线程进入睡眠状态。


       信号量不变性:P和V的定义确保了一个正在运行的程序绝不可能进入一个s变为负值的状态。

       

        线程同步:所谓同步,就是在发出一个功能调用时,在没有得到结果之前,该调用就不返回,同时其它线程也不能调用这个方法。在多线程编程里面,一些敏感数据(共享变量——临界资源)不允许被多个线程同时访问,此时就使用同步访问技术,保证数据在任何时刻,最多有一个线程访问,以保证数据的完整性。线程必须先获得互斥锁才能访问临界资源,访问完临界资源后释放该锁。如果无法获得锁,线程会阻塞直到获得锁为止。

        总而言之:同步是针对步调即线程的执行过程而言的,而互斥则是针对数据的保护而言的(只能是二元信号量),二者是一个问题的两个方面。

    展开全文
  • 中断(硬中断、软中断、Tasklet、下半部)与进程之间访问共享内存资源的代码区称为“临界区”,临界区需要被以某种互斥机制加以保护,中断屏蔽、原子操作、自旋锁和信号量等linux设备驱动可采用的互斥途...

    并发指的是多个执行单元同时、并行被执行,而并发的执行单元对共享资源的访问则很容易导致竞态

    linux内核中主要竞态
    1.多对称处理器的多个CPU  2.单CPU内进程与抢占它的进程 3.中断(硬中断、软中断、Tasklet、下半部)与进程之间
    访问共享内存资源的代码区称为“临界区”,临界区需要被以某种互斥机制加以保护,中断屏蔽、原子操作、自旋锁和信号量等
    是linux设备驱动中可采用的互斥途径。

    这几个互斥的介绍:

    1.中断屏蔽,这个主要用于单CPU,中断屏蔽将使得中断和进程之间的并发不再发生。使用方法:

    local_irq_disable();//屏蔽中断
    ...
    ...
    临界区
    ...
    local_irq_enable();//开中断
    由于linux的异步IO、进程调度等很多重要的操作都依赖于中断,中断对于内核的运行非常重要,在屏蔽中断期间所有的中断都无法处理,
    因此长时间的屏蔽中断很危险,有可能导致数据丢失甚至系统崩溃。所以这个不作为重点讨论。

    **********************************************************************************************************************************************************

    2.原子操作,原子操作是一系列的不能被打断的操作。linux内核提供了一系列的函数来实现内核中的原子操作,这些函数分为2类,分别针对位和整型变量
    进行原子操作。
    实现原子操作的步骤:

    1.定义原子变量并设置变量值
    void atomic_set(atomic_t *v , int i); //设置原子变量值为i
    atomic_t v = ATOMIC_INIT(0); //定义原子变量v,初始化为0
    2.获取原子变量的值
    atomic_read(atomic_t *v);
    3.原子变量加减操作
    void atomic_add(int i,atomic_t *v);//原子变量加i
    void atomic_sub(int i ,atomic_t *v);//原子变量减i
    4.原子变量自增/自减
    void atomic_inc(atomic_t *v);//自增1
    void atomic_dec(atomic_t *v);//自减1
    5.操作并测试:对原子变量执行自增、自减后(没有加)测试其是否为0,如果为0返回true,否则返回false。
    int atomic_inc_and_test(atomic_t *v);
    int atomic_dec_and_test(atomic_t *v);
    int atomic_sub_and_test(int i ,atomic_t *v);
    6.操作并返回
    int atomic_add_return(int i , atomic_t *v);
    int atomic_sub_return(int i , atomic_t *v);
    int atomic_inc_return(atomic_t * v);
    int atomic_dec_return(atomic_t * v);

    **********************************************************************************************************************************************************
    3.自旋锁
    自旋锁是一个忙锁,它在一个小的循环内不断的重复测试并设置的操作。
    自旋锁保护临界区的特点:临界区要小,并且临界区内不能有导致睡眠的操作,否则可能引起系统崩溃。自旋锁可能导致系统死锁,
    引发这个问题最常见的情况是递归使用一个自旋锁。

    自旋锁的操作步骤:

    1.定义自旋锁
    spinlock_t lock;
    2.初始化自旋锁
    spin_lock_init(lock);这是个宏,它用于动态初始化自旋锁lock;
    3.获得自旋锁
    spin_lock(lock);该宏用于加锁,如果能够立即获得锁,它就能马上返回,否则,他将自旋在那里,直到该自旋锁的保持者释放。
    spin_trylock(lock);能够获得,则返回真,否则返回假,实际上是不在原地打转而已。
    4.释放自旋锁
    spin_unlock(lock);
    与上面的两个配对使用。
    例子:

    spinlock_t lock;
    spin_lock_init(&lock);
    spin_lock(&lock);  //获取自旋锁,保护临界区

    。。。。临界区

    spin_unlock(&lock);//释放自旋锁

    自旋锁不关心锁定的临界区究竟是如何执行的。不管是读操作还是写操作,实际上,对共享资源进行读取的时候是应该可以允许多个执行单元同时
    访问的,那么这样的话,自旋锁就有了弊端。于是便衍生出来一个读写锁。

    它保留了自旋的特性,但在对操作上面可以允许有多个单元进程同时操作。当然,读和写的时候不能同时进行。

    现在又有问题了,如果我第一个进程写共享资源,第二个进程读的话,一旦写了,那么就读不到了,可能写的东西比较多,但是第二个进程读很小,那么
    能不能第一个进程写的同时,我第二个进程读呢?
    当然可以,那么引出了顺序锁的概念。都是一样的操作。


    **********************************************************************************************************************************************************
    4.信号量
    是用于保护临界区的一种常用的方法,它的使用与自旋锁差不多,但是它不在原地打转,当获取不到信号量时候,进程会进入休眠等待状态。

    主要操作:

    1.定义sem信号量
    struct semaphore sem;
    2.初始化信号量
    void sema_init(struct semaphore *sem, int val);
    初始化信号量,并设置sem的值为val
    初始化的时候还可以这样用,init_MUTEX(sem),这是个宏 #define init_MUTEX(sem) sema_init(sem , 1)
           init_MUTEX_LOCKED(sem),这是个宏 #define init_MUTEX_LOCKED(sem) sema_init(sem , 0)

     

     

    3.获得信号量
    void down(struct semaphore * sem);
    该函数用于获得信号量sem,他会导致睡眠,所以不能在中断中使用。
    int down_interruptible(struct semaphore* sem);
    与上面功能类似,因为down进入睡眠状态的进程不能被信号打断,而它能被信号打断,信号也会导致该函数返回。
    int down_trylock(struct semaphore * sem);

    4.释放信号量
    void up(struct semaphore * sem);
    该函数用于释放信号量,同时唤醒等待者。
    信号量一般这样使用:

    DECLARE_MUTEX(sem);

    down(&sem);

    .....临界区

    up(&sem);

    linux自旋锁和信号量采用的“获取锁-访问临界区-释放锁”的方式。


    *************************************************************************************************************************

    5.互斥体


    互斥体和信号量基本上差不多。不介绍了。


    总结:并发和竞态广泛存在,这几个机制是解决问题的好方法,中断屏蔽很少单独使用,原子操作只能针对整数进行,因此,自旋锁和信号量应用最为广泛。
    自旋锁会导致死循环,锁定期间不允许阻塞,因此要求锁定的临界区要小。信号量允许临界区阻塞,可以适用于临界区较大的情况。读写自旋锁和读写信号量是
    放宽了条件的自旋锁和信号量,他们允许多个进程并发的读取共享空间。

     

    一个fifo的综合例子

    /*======================================================================
        A globalfifo driver as an example of char device drivers  
        This example is to introduce poll,blocking and non-blocking access
          
        The initial developer of the original code is Baohua Song
        <author@linuxdriver.cn>. All Rights Reserved.
    ======================================================================*/
    #include <linux/module.h>
    #include <linux/types.h>
    #include <linux/fs.h>
    #include <linux/errno.h>
    #include <linux/mm.h>
    #include <linux/sched.h>
    #include <linux/slab.h>
    #include <linux/init.h>
    #include <linux/cdev.h>
    #include <asm/io.h>
    #include <asm/system.h>
    #include <asm/uaccess.h>
    #include <linux/poll.h>
    #include <linux/time.h>
    #include <linux/timer.h>
    #include <linux/kernel.h>
    #include <linux/spinlock.h>
    #include <linux/interrupt.h>
    
    #define GLOBALFIFO_SIZE 0x1000 /*全局fifo最大4K字节*/
    #define FIFO_CLEAR 0x1  /*清0全局内存的长度*/
    #define GLOBALFIFO_MAJOR 250    /*预设的globalfifo的主设备号*/
    
    static int globalfifo_major = GLOBALFIFO_MAJOR;
    /*globalfifo设备结构体*/
    struct globalfifo_dev                                     
    {                                                        
      struct cdev cdev; /*cdev结构体*/                       
      unsigned int current_len;    /*fifo有效数据长度*/
      unsigned char mem[GLOBALFIFO_SIZE]; /*全局内存*/        
      struct semaphore sem; /*并发控制用的信号量*/           
      wait_queue_head_t r_wait; /*阻塞读用的等待队列头*/     
      wait_queue_head_t w_wait; /*阻塞写用的等待队列头*/     
      struct tasklet_struct tlet;
    };
    
    struct globalfifo_dev *globalfifo_devp; /*设备结构体指针*/
    /*文件打开函数*/
    int globalfifo_open(struct inode *inode, struct file *filp)
    {
      /*将设备结构体指针赋值给文件私有数据指针*/
      filp->private_data = globalfifo_devp;
      return 0;
    }
    /*文件释放函数*/
    int globalfifo_release(struct inode *inode, struct file *filp)
    {
      return 0;
    }
    
    /* ioctl设备控制函数 */
    static int globalfifo_ioctl(struct inode *inodep, struct file *filp, unsigned
      int cmd, unsigned long arg)
    {
      struct globalfifo_dev *dev = filp->private_data;/*获得设备结构体指针*/
    
      switch (cmd)
      {
        case FIFO_CLEAR:
         down(&dev->sem); //获得信号量     
          dev->current_len = 0;
          memset(dev->mem,0,GLOBALFIFO_SIZE);
          up(&dev->sem); //释放信号量
             
          printk(KERN_INFO "globalfifo is set to zero\n");      
          break;
    
        default:
          return  - EINVAL;
      }
      return 0;
    }
    
    static unsigned int globalfifo_poll(struct file *filp, poll_table *wait)
    {
      unsigned int mask = 0;
      struct globalfifo_dev *dev = filp->private_data; /*获得设备结构体指针*/
      
      down(&dev->sem);
      
      poll_wait(filp, &dev->r_wait, wait);
      poll_wait(filp, &dev->w_wait, wait);  
      /*fifo非空*/
      if (dev->current_len != 0)
      {
        mask |= POLLIN | POLLRDNORM; /*标示数据可获得*/
      }
      /*fifo非满*/
      if (dev->current_len != GLOBALFIFO_SIZE)
      {
        mask |= POLLOUT | POLLWRNORM; /*标示数据可写入*/
      }
         
      up(&dev->sem);
      return mask;
    }
    
    
    /*globalfifo读函数*/
    static ssize_t globalfifo_read(struct file *filp, char __user *buf, size_t count,
      loff_t *ppos)
    {
      int ret;
      struct globalfifo_dev *dev = filp->private_data; //获得设备结构体指针
      DECLARE_WAITQUEUE(wait, current); //定义等待队列
    
      down(&dev->sem); //获得信号量
      add_wait_queue(&dev->r_wait, &wait); //进入读等待队列头
    
      /* 等待FIFO非空 */
      if (dev->current_len == 0)
      {
        if (filp->f_flags &O_NONBLOCK)
        {
          ret =  - EAGAIN;
          goto out;
        } 
        __set_current_state(TASK_INTERRUPTIBLE); //改变进程状态为睡眠
        up(&dev->sem);
    
        schedule(); //调度其他进程执行
        if (signal_pending(current))
        //如果是因为信号唤醒
        {
          ret =  - ERESTARTSYS;
          goto out2;
        }
    
        down(&dev->sem);
      }
    
      /* 拷贝到用户空间 */
      if (count > dev->current_len)
        count = dev->current_len;
    
      if (copy_to_user(buf, dev->mem, count))
      {
        ret =  - EFAULT;
        goto out;
      }
      else
      {
        memcpy(dev->mem, dev->mem + count, dev->current_len - count); //fifo数据前移
        dev->current_len -= count; //有效数据长度减少
        printk(KERN_INFO "read %d bytes(s),current_len:%d\n", count, dev->current_len);
         
        wake_up_interruptible(&dev->w_wait); //唤醒写等待队列
        
        ret = count;
      }
      out: up(&dev->sem); //释放信号量
      out2:remove_wait_queue(&dev->w_wait, &wait); //从附属的等待队列头移除
      set_current_state(TASK_RUNNING);
      return ret;
    }
    
    
    /*globalfifo写操作*/
    static ssize_t globalfifo_write(struct file *filp, const char __user *buf,
      size_t count, loff_t *ppos)
    {
      struct globalfifo_dev *dev = filp->private_data; //获得设备结构体指针
      int ret;
      DECLARE_WAITQUEUE(wait, current); //定义等待队列
    
      down(&dev->sem); //获取信号量
      add_wait_queue(&dev->w_wait, &wait); //进入写等待队列头
    
      /* 等待FIFO非满 */
      if (dev->current_len == GLOBALFIFO_SIZE)
      {
        if (filp->f_flags &O_NONBLOCK)
        //如果是非阻塞访问
        {
          ret =  - EAGAIN;
          goto out;
        } 
        __set_current_state(TASK_INTERRUPTIBLE); //改变进程状态为睡眠
        up(&dev->sem);
    
        schedule(); //调度其他进程执行
        if (signal_pending(current))
        //如果是因为信号唤醒
        {
          ret =  - ERESTARTSYS;
          goto out2;
        }
    
        down(&dev->sem); //获得信号量
      }
    
      /*从用户空间拷贝到内核空间*/
      if (count > GLOBALFIFO_SIZE - dev->current_len)
        count = GLOBALFIFO_SIZE - dev->current_len;
    
      if (copy_from_user(dev->mem + dev->current_len, buf, count))
      {
        ret =  - EFAULT;
        goto out;
      }
      else
      {
        dev->current_len += count;
        printk(KERN_INFO "written %d bytes(s),current_len:%d\n", count, dev
          ->current_len);
    
        wake_up_interruptible(&dev->r_wait); //唤醒读等待队列
        
        ret = count;
      }
    
    
    tasklet_schedule(&dev->tlet);
    printk("in write jiffies=%ld\n",jiffies);
    
      out: up(&dev->sem); //释放信号量
      out2:remove_wait_queue(&dev->w_wait, &wait); //从附属的等待队列头移除
      set_current_state(TASK_RUNNING);
      return ret;
    }
    
    
    /*文件操作结构体*/
    static const struct file_operations globalfifo_fops =
    {
      .owner = THIS_MODULE,
      .read = globalfifo_read,
      .write = globalfifo_write,
      .ioctl = globalfifo_ioctl,
      .poll = globalfifo_poll,
      .open = globalfifo_open,
      .release = globalfifo_release,
    };
    
    /*初始化并注册cdev*/
    static void globalfifo_setup_cdev(struct globalfifo_dev *dev, int index)
    {
      int err, devno = MKDEV(globalfifo_major, index);
    
      cdev_init(&dev->cdev, &globalfifo_fops);
      dev->cdev.owner = THIS_MODULE;
      dev->cdev.ops = &globalfifo_fops;
      err = cdev_add(&dev->cdev, devno, 1);
      if (err)
        printk(KERN_NOTICE "Error %d adding LED%d", err, index);
    }
    
    
    void jit_tasklet_fn(unsigned long arg)
    {
     printk("in jit_tasklet_fn  jiffies=%ld\n",jiffies);
    }
    
    
    /*设备驱动模块加载函数*/
    int globalfifo_init(void)
    {
      int ret;
      dev_t devno = MKDEV(globalfifo_major, 0);
    
      /* 申请设备号*/
      if (globalfifo_major)
        ret = register_chrdev_region(devno, 1, "globalfifo");
      else  /* 动态申请设备号 */
    
      {
        ret = alloc_chrdev_region(&devno, 0, 1, "globalfifo");
        globalfifo_major = MAJOR(devno);
      }
      if (ret < 0)
        return ret;
      /* 动态申请设备结构体的内存*/
      globalfifo_devp = kmalloc(sizeof(struct globalfifo_dev), GFP_KERNEL);
      if (!globalfifo_devp)    /*申请失败*/
      {
        ret =  - ENOMEM;
        goto fail_malloc;
      }
    
      memset(globalfifo_devp, 0, sizeof(struct globalfifo_dev));
    
      globalfifo_setup_cdev(globalfifo_devp, 0);
    
      init_MUTEX(&globalfifo_devp->sem);   /*初始化信号量*/
      init_waitqueue_head(&globalfifo_devp->r_wait); /*初始化读等待队列头*/
      init_waitqueue_head(&globalfifo_devp->w_wait); /*初始化写等待队列头*/
     /* register the tasklet */
     tasklet_init(&globalfifo_devp->tlet, jit_tasklet_fn, (unsigned long)globalfifo_devp);
    
      return 0;
    
      fail_malloc: unregister_chrdev_region(devno, 1);
      return ret;
    }
    
    
    /*模块卸载函数*/
    void globalfifo_exit(void)
    {
      cdev_del(&globalfifo_devp->cdev);   /*注销cdev*/
      kfree(globalfifo_devp);     /*释放设备结构体内存*/
      unregister_chrdev_region(MKDEV(globalfifo_major, 0), 1); /*释放设备号*/
    }
    
    MODULE_AUTHOR("Song Baohua");
    MODULE_LICENSE("Dual BSD/GPL");
    
    module_param(globalfifo_major, int, S_IRUGO);
    
    module_init(globalfifo_init);
    module_exit(globalfifo_exit);
    
     

     

    转载于:https://www.cnblogs.com/liugf05/archive/2012/07/11/2587162.html

    展开全文
  • 共享是指系统的资源可以被多个并发进程共同使用。 有两种共享方式:互斥共享和同时共享。 互斥共享的资源称为临界资源,操作临界资源的代码称为临界区。例如打印机等,在同一时间只允许一个进程访问,...

    概述

    基本特征:

    并发:

    并发是指宏观上在一段时间内能同时运行多个程序,而并行则指同一时刻能运行多个指令。
    并行需要硬件支持,如多流水线或多处理器。
    操作系统通过引入进程和线程,使得程序能够并发运行。

    共享:

    共享是指系统中的资源可以被多个并发进程共同使用。
    有两种共享方式:互斥共享和同时共享。
    互斥共享的资源称为临界资源,操作临界资源的代码称为临界区。例如打印机等,在同一时间只允许一个进程访问,需要用同步机制实现对临界资源的访问。一般读操作可以同时共享,写操作需要互斥共享。

    虚拟:

    虚拟技术把一个物理实体转换为多个逻辑实体。
    主要有两种虚拟技术:时分复用技术和空分复用技术。
    多个进程能在同一处理器上 并发执行使用了时分复用 技术,让每个进程轮流占有处理器,每次只执行一个小的时间片并快速切换。
    虚拟内存使用了空分复用技术 ,它将物理内存抽象为地址空间,每个进程都有自己的地址空间。地址空间和物理内存使用页表进行交换 ,地址空间的页并不需要全部在物理内存中,当使用到一个没有物理内存的页时,执行页面置换算法,将该页置换到内存中。

    异步:

    异步指进程不是一次性执行完毕,,而是走走停停,以不可知的速度向前推进。

    基本功能:
    进程管理:

    进程控制,进程同步,进程通信,死锁处理,处理器调度等。

    内存管理:

    内存分配,地址映射,内存保护与共享,虚拟内存等。

    文件管理:

    文件存储空间的管理,目录管理,文件读写管理和保护。

    设备管理:

    完成用户IO请求,方便用户使用各种设备,并提高设备使用率。
    主要包括缓冲管理,设备分配,设备处理,虚拟设备等。

    系统调用:

    如果一个进程在用户态需要使用内核态的功能,仅需要进行系统调用从而陷入内核,由操作系统代为完成。
    在这里插入图片描述

    linux的系统调用主要有以下:
    Task(工作) Commands(命令)
    进程控制 fork();exit();wait()
    进程通信 pipe();shmget();mmap()
    文件操作 open();read();write()
    设备操作 ioctl();read();write()
    信息维护 getpid();alarm();sleep()
    安全 chmod();umask();chown()

    大内核和微内核

    大内核

    大内核是将操作系统功能作为一个整体放入内核,由于各模块共享信息,因此性能很高。

    微内核

    由于操作系统不断复杂,因此将一部分操作系统功能移出内核,从而降低内核复杂性。移出的部分根据分层的原则划分为若干服务,互相独立。
    在微内核结构下,操作系统被划分为小的,定义良好的模块,只有微内核这一模块运行在内核态,其余模块运行在用户态。
    因为需要频繁的在用户态和内核态之间进行切换,所以有一定的性能损失。
    在这里插入图片描述

    • Application Program :应用程序。
    • Device Driver:设备驱动程序。
    • Interprocess Communication: 进程间通信。
    • memory managment:内存管理。
    • CPU scheduling: CUP调度。

    中断分类:

    外中断:

    由CPU执行指令以外的事件引起,如IO完成中断,表示设备输入/输出处理已经完成,处理器能够发送下一个输入/输出请求。此外还有时钟中断,控制台中断等。

    异常:

    由CPU执行指令的内部事件引起,如非法操作码,地址越界,算术溢出等。

    陷入:

    在用户进程中使用系统调用。

    进程管理

    进程与线程

    进程:

    进程是资源分配的基本单位。
    进程控制块(Process Control Block,PCB)描述进程的基本信息和运行状态,所谓的创建进程和撤销进程,是指对PCB的操作。
    下图四个程序创建了四个进程,这四个进行可以并发执行。
    在这里插入图片描述
    上图的四个进程在单核处理器上运行,采用时分复用技术,实现并发但是不并行。
    在这里插入图片描述

    线程:

    线程是独立调度的基本单位。
    一个进程可以有多个线程,它们共享线程资源。
    qq和浏览器是两个进程,浏览器进程中有很多线程,如HTTP请求线程,实现响应线程,渲染线程等,线程的并发执行使得在浏览器中点击一个新链接从而发起HTTP请求时,浏览器还可以响应用户的其它事件。
    在这里插入图片描述

    区别:
    • 拥有资源: 进程是资源分配的基本单位,但线程不拥有资源,线程可以访问隶属进程的资源。
    • 调度: 线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程内的线程切换到另一个进程中的线程时,会引起进程切换。
    • 系统开销: 由于创建或撤销进程时,系统都需要为之分配资源或者回收资源,如内存空间,IO设备等,所付出的开销远大于创建或撤销线程时的开销。类似的,在进行进程切换时,涉及当前执行进程CPU环境的保存以及新调度进程CPU环境的设置,而线程切换时只需要保存和设置少量寄存器内容,开销很小。
    • 通信方面: 进程间通信(IPC)需要进程同步和互斥手段的辅助,以保证数据的一致性。而线程间的通信可以通过直接读/写同一进程中的数据段(如全局变量Volatile) 来进程通信。

    进程状态切换:

    在这里插入图片描述

    • 就绪状态(ready):等待被调度。
    • 运行状态(running):
    • 阻塞状态(waiting):等待资源。
    注意:
    • 只有就绪状态和运行状态可以相互转换,其它都是单向转换。就绪状态的进程通过调度算法从而获得CPU时间,转为运行状态;而运行状态的进程,在分配给它的CPU时间片用完之后就会转为就绪状态,等待下一次调度。
    • 阻塞状态是缺少需要的资源从而由运行状态转换而来,但是该资源不包括CPU时间,缺少CPU时间将会从运行态转换为就绪态。

    进程调度算法:

    不同环境的调度算法目标不同,因此需要针对不同环境进行讨论。

    批处理系统:

    批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止时间,注意是提交不是运行)。

    • 先来先服务(FCFS): 按照请求的顺序进行调度。有利于长作业。但不利于短作业,因为短作业必须一直等待前面的长作业执行完毕后才能执行,而长作业又需要执行很长时间,从而造成了短作业等到时间过长。
    • 短作业优先: 按照估计运行时间最短的顺序进行调度。长作业可能会被饿死,处于一直等到短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。
    • 最短剩余时间优先: 按照估计的剩余时间最短的顺序进程调度。
    交互式系统:

    交互式系统有大量的用户交互操作,该系统中的调度算法的目标是快速的进行响应。

    • 时间片轮转:
      将所有就绪进程按照FCFS的原则排成一个队列,每次调度时,把CPU时间分配给队首进程,该进程可以执行一个时间片,当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把CPU时间分配给队首进程。
      时间片轮转算法的效率和时间片的大小由很大关系:
    • 因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换太频繁,在进程切换上就会花过多时间。
    • 如果时间片时间过长,那么实时性就不能得到保证。

    在这里插入图片描述

    • 优先级调度:
      为每个进程分配一个优先级,按照优先级进行调度。
      为防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。
    • 多级反馈队列:
      如果一个进程需要执行100个时间片,如果采用时间片轮转算法,那么就需要交换100次。
      多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片 大小都不同 ,如1,2,4,8等。进程在第一个队列没被执行完,那么就会被移到下一个队列,这种方式,之前的进程只需要交换7次。
      每个队列优先权也是不同的,最上面的优先权最高。因此只有上一个队列没有进程排队,才能调度当前队列上的进程。
      这种调度算法可以看成时间片轮转算法和优先级调度算法的结合。

    在这里插入图片描述

    实时系统:

    实时系统要求一个请求在一个确定时间内得到响应。
    分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。

    进程同步:

    临界区:

    对临界资源访问的那段代码称为临界区。
    为了互斥访问临界资源,每个进程在进入临界区之前,需要先进行检查。

    同步和互斥:
    • 同步:多个进程按照一定顺序执行;
    • 互斥:多个进程在同一时刻只有一个进程能进入临界区;
    信号量:

    信号量是一个整型变量,可以对其执行down和up操作,也就是常见的P和V操作。

    • down: 如果信号量大于0,执行-1操作;如果信号量等于0,进程休眠,等待信号量大于0;
    • up: 对信号量执行+1操作,唤醒睡眠的进程让其完成-1操作。
      down和up操作需要被设计成原语,不可分割,通常的做法是在执行这些操作的时候屏蔽中断
      如果信号量只能取0或者1,那么就变成互斥量(Mutex) , 0表示临界区已经加锁,1表示临界区解锁。
    typedef int semaphore;
    semaphore mutex=1;
    void p1(){
        down(&mutex);
        //临界区
        up(&mutex);
    }
    
    
    管程:

    在同一时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程否则其它进程永远不能使用管程。
    管程引入了条件变量以及相关操作:wait()和signal()来实现同步操作。对条件变量执行wait()操作会导致调用进程阻塞,把管程让出来给另一个进程持有。single()操作用于唤醒被阻塞的进程。

    进程通信:

    进程同步和进程同步很容易搞混,区别在于:

    • 进程同步:控制多个进程按一定顺序执行。
    • 进程通信:进程间传输信息。
      进程通信是一种手段,而进程同步是一种目的。可以说,为了能够达到进程同步的目的,需要让进程进行通信,传输一些进程同步所需要的信息。
    管道:

    在C中管道是通过调用pipe()函数创建的,fd[0]用于读,fd[1] 用于写;

    #include<unistd.h>
    int pipe(int fd[2]);
    

    管道通信具有以下特点:

    • 只支持半双工(单向交替传输);
    • 只能在子父进程中使用;

    -

    有名管道:FIFO

    去除了管道只能在父子进程中使用的限制。
    FIFO常用于客户-服务器应用程序中,FIFO用作汇聚点,在客户进程和服务器进程之间传输数据。
    在这里插入图片描述

    消息队列:

    相对FIFO,消息队列具有以下优点:

    • 消息队列可以独立于读写进程存在,从而避免了FIFO中同步管道打开和关闭时可能产生的困难。
    • 避免了FIFO的同步阻塞问题,不需要进程自己提供同步方法。
    • 读进程可以根据消息类型有选择地接收消息,而不是向FIFO默认接收。
    信号量:

    它是一个计数器,用于为多个进程提供对共享对象地访问。

    共享存储:

    允许多个进程共享一个给定的存储区。因为数据不需要再进程之间复制,所以这是一种最快的IPC。
    需要使用信号量用来同步对共享存储的访问。
    多个进程可以将同一个文件映射到它们的地址空间从而实现了共享内存。另外,XSL共享内存不是使用文件,而是使用内存的匿名段。

    套接字:socket

    用于可以同于不同机器间的进程通信。

    展开全文
  • 2.3 进程同步

    2020-10-16 20:43:08
    2.3.1 进程同步的基本概念 多道程序环境下,进程是并发执行的,不同进程之间存在着不同的...同步亦称直接制约关系是指多个进程中发生的事件存在某种先后顺序 3.互斥 互斥也称间接制约关系是指多个进程不允许使用同一 临

    2.3.1 进程同步的基本概念

    多道程序环境下,进程是并发执行的,不同进程之间存在着不同的制约关系。为了协调进程之间的相互制约关系,引入进程同步的基本概念。
    异步性:各并发执行的进程以各自独立的,不可预知的速度向前推进。


    1.临界资源

    许多资源只能为一个进程所用,我们将一次仅允许一个进程使用的资源称为临界资源
    对临界资源的访问必须 互斥 进行
    访问临界资源的代码叫做 临界区

    2.同步

    同步亦称直接制约关系是指多个进程中发生的事件存在某种先后顺序

    3.互斥
    互斥也称间接制约关系是指多个进程不允许使用同一 临界资源


    为了禁止两个进程同时进入临界区,同步机制应遵循以下原则:
    1)空闲让进
    2)忙则等待
    3)有限等待
    4)让权等待 当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。

    2.3.2 实现临界区互斥的基本方法


    一、软件实现方法
    1)算法一 :单标志法
    违背 空闲让进 设置变量 turn,turn=0允许P0进入,turn=1允许P1进入。若P0顺利离开,此时临界区空闲,但是P1没有进入临界区的打算,turn=1就一直成立,其他进程无法进入。
    在这里插入图片描述

    2)算法二 :双标志法先检查

    每个进程在访问临界区之前,先查看临界资源是否正在被访问。为此设置一个数据flag[i],如第i个元素值为FALSE,表示进程Pi未进入临界区,TRUE为进入临界区。
    在这里插入图片描述
    优点: 不用交替进入,可连续使用
    缺点: 若按照①②③④顺序执行,两个进程会同时进入临界区违背 忙则等待 原则

    3)算法三 :双标志法后检查

    算法二先检查对方的进程状态,在设置自己的标志,会造成两个进程同时进入临界区。
    为此算法三先将标志位设为TRUE,再检测对方标志,若对方为TRUE则进程等待,否则进入
    在这里插入图片描述
    两个进程几乎同时都想进入临界区时,他们分别将自己的标志位flag设为TRUE并检测对方flag,发现对方也要进入,则导致两个进程都不进入临界区。

    导致饥饿现象

    4)算法四 :Peterson’s Algorithm

    为了防止两个进程无限期的等待,设置变量turn,每个进程先设置自己的flag标志再设置自己的turn标志turn表示谦让,flag表示意愿

    在这里插入图片描述
    在这里插入图片描述
    不遵循 “让权等待原则”会发生忙等


    二、硬件实现方法

    1)中断屏蔽法
    防止其他进程进入临界区进行访问的最简单方法是禁止一切中断发生,或称之为屏蔽中断、关中断

    在这里插入图片描述
    只适用于单处理系统(操作系统内核)


    2)硬件指令方法

    TestAndSet指令:这条指令是原子操作,执行该代码不允许被中断

    bool TSL(bool *lock){
    bool old;
    old = *lock;
    *lock=true;
    return old;
    }
    while(TSL(&lock));
    //临界区代码段
    lock = false;
    //剩余区代码段
    

    不满足让权等待原则

    Swap指令:也不满足让权等待原则

    展开全文
  • 并发编程基础

    2021-01-18 23:28:55
    临界资源是指一次只能被一个进程使用的共享资源。各进程之间采用互斥的方式,实现共享的资源称为临界资源。属于临界资源的硬件有打印机,磁带机等,软件有队列,变量,数组,缓冲等。诸进程之间采用互斥的方式实现...
  • 7.1 并发与竞态并发是指多个执行单元同时、并发的被执行,而并发的执行单元对共享资源(硬件资源、软件上的的全局变量、静态变量等)的访问则很容易导致竟态竟态发生在以下几种情况 对称多处理器(SMP)的多个CPU单...
  • ***进程***一个具有一定独立功能的程序的一次运行活动 进程特点: 动态性 并发性 独立性 异步性 进程状态 进程id 进程ID(pid):标识进程...进程中访问临界资源的那段程序代码称为临界区。为实现对临界资源的互斥访
  • Java并发概念-1

    2019-10-03 03:23:40
    一,同步 和 异步:  同步:调用方需要等待被调用方回应之后,才能进行下一步动作。  异步:调用方不需要等待被调用方回应,直接继续自己的动作。... 每个进程中访问临界资源的那段代码称为临界...
  • 关于信号量的文章,生产者消费...并发进程中与共享变量有关的程序段定义为临界区。进入临界区的准则:①一次只准一个进程进入临界区;②本进程结束负责通知下一进程;③进程调度,不能阻塞。 (3)原语 。。。。。。
  • 先上图,进程同步、互斥的概念。 进程具有异步性的特征,异步性是指各个并发执行的进程以独立的不可预知的进度进行。读进程与写进程并发地运行,...临界区是访问临界资源的地方。进入区和退出区是负责实现互斥..
  • 进程控制理论基础 进程特点:动态性,并发性,独立性,异步性 进程三态:就绪,执行,阻塞 进程ID:PID 父进程ID:PPID 启动进程的用户ID:UID 进程互斥是指若干进程都要使用某一共享...临界区——进程中访问临界
  • 临界资源(临界区一次只能允许一个进程使用的共享资源称为临界资源 同步 为完成某种任务而建立的两个和多个进程,这些进程在合作的过程需要协调工作次序进行有序的访问而出现等待所产生的制约关系 ...
  • 前言 参考王道书。 后续会进一步整理,包括添加笔记内容,标明参考资料。 更新。。...目录一、进程同步的基本概念进程同步进程互斥临界资源互斥临界资源互斥访问的四个逻辑...异步性是指,各并发执行的进程以各自独立
  • Java并发程序设计基础

    2018-05-15 07:14:47
    1.并发程序设计的基本概念1.并发和并行:并发偏重于多个任务交替执行,而多个任务之间有可能还是串行的;并行真正意义上的“同时执行”。...4.死锁:两个或两个以上的进程在执行过程,由于...
  • 1. 并发:在操作系统是指一个时间段有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是在同一个处理机上运行。其中两种并发关系分别是同步和互斥 2. 互斥:进程间相互排斥的使用临界资源的现象,...
  • 并发与多线程

    2019-11-17 14:04:37
    多线程协作时,因为对资源的锁定与等待会产生死锁,这里需要了解产生死锁的四个基本条件,要明白竞争条件与临界区的概念,知道可以通过破坏造成死锁的 4 个条件来防止死锁。 前面讲过进程间的通信方式,这里还要知道...
  • 两种相互作用 同步 多个相关进程在执行次序上的协调。 制约关系:直接制约。 ...如图所示:一个进程在执行操作的时候,另一个进程必须等待,体现在次序上的等待和协调,并不...当一个进程想进入其临界区(进程中涉及..
  • 一、实验目的 1.掌握基本的同步与互斥算法,理解P,V操作。...同步对象是指Windows用于实现同步与互斥的实体,包括信号量(Semaphore)、互斥量(Mutex)、临界区(Critical Section)和事件(Events)等。本实验使
  • 进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系。 进程同步:指为完成共同任务的并发进程基于某个条件来协调其活动,因为需要在某些...临界区并发进程中与共享变量有关的程序段称为“临界区
  • 1.在操作系统,并发是指(C)。 A. 若干个事件在不同时刻发生 B. 若千个事件在同- -时刻发生 C. 若干个事件在同一时间间隔内发生 D. 若干个时间在不同的时间间隔内发生 2.以下描述,(D)是临界区。 A. 用于...
  • 操作系统练习-信号量

    千次阅读 2018-02-07 15:28:24
    临界区是指()  并发进程中用于实现进程互斥的程序段 进程中访问临界资源的那段代码 一段缓冲区 一个数据区 解释:每个进程有一个代码段称为临界区,在该区中进程可能改变共同变量、更新一个表、写一个文件...
  • 操作系统经典题目

    2018-04-09 16:41:20
    进程和线程的区别? 进程系统进行资源调度和分配的一个独立单元,线程进程的实体,CPU调度和分配的...临界区:每个进程中访问临界资源(一次仅允许一个进程使用的共享资源)的那段代码称为临界区,每次只准许一
  • 操作系统第二章

    2018-10-13 19:41:25
    一、名词解释 1.进程上下文 进程执行活动全过程的静态描述。...进程同步是指一组并发进程由于相互合作,共同完成某种任务,因而相互等待,使得各进程按一定的速度执行的过程。 5.内核线程 由操作系统完成创建和...
  • 3、临界区指在每个进程中访问临界资源的那段代码 4,现在操作系统中申请资源的基本单位进程,在CPU得到执行的基本单位线程,进程由程序段、数据段、PCB组成的 5,对临界资源应采取互斥访问方式来实现共享 6...
  • 面试笔试--操作系统知识点

    千次阅读 2016-09-17 10:12:47
    3、临界区指在每个进程中访问临界资源的那段代码 4,现在操作系统中申请资源的基本单位进程,在CPU得到执行的基本单位线程,进程由程序段、数据段、PCB组成的 5,对临界资源应采取互斥访问方式来实现共享 6...

空空如也

空空如也

1 2 3 4
收藏数 73
精华内容 29
关键字:

临界区是指并发进程中