16

进程

进程调度

进程是活动实体,包括处理器的内容和程序计数器的值,通常还包括堆栈段,数据段,可能还包含堆,即出程序运行期间动态分配的内存。进程的状态有:运行,等待,就绪,终止等状态。

进程进入系统的时,会被加到作业队列中,该队列通常用链表来实现,其节点指针指向第一个和最后一个PCB块。

linux中的进程表示方法

//task_struct 的字段包括:
pid_t pid;                         //process identifier
long state;                         //state of the process
unsigned int time_slice         //scheduling information
struct files_struct * files;        //list of open files
struct mm_struct * mm;          //address space of this process

操作系统中还有其他的队列,当给进程分配了CPU的后,接下来或称被执行,完成,中断,等待I/O等状态。如果在进行I/O请求的时候,需要对设备进行请求,那么会有设备队列。

当创建了一个新的进程的时候,新进程就会处于就绪队列,当进程被分配到CPU并执行的时候,可能一下的状况:

  • 进程可能发出I/O请求,并放到I/O队列。

  • 进程可能创建一个新的子进程,并等待其结束。

  • 进程可能会由于中断被强制放回到就绪队列中

    长期调度程序从大容量设备的缓冲池中选择进程,并装入内存中以准备执行。短期调度程序从准备执行的进程中选择进程,并未其分配CPU

    CPU切换到另一个进程需要保存当前的进程状态并恢复到另一个进程的状态。当发生上下文切换的时候,内核会将就旧进程的状态保存在其PCB中, 然后装入经调度的已保存的新进程的上下文。

进程操作

进程创建

进程在运行的过程中可以通过创建,进程系统调用,来创建多个新进程。用来描述进程id的称之为pid(process identify),当创建新的进程后,父进程于子进程:可能是父进程与子进程并发执行,可能父进程等待子进程全部执行完毕。新进程的地址空间也有两种执行可能:子进程是父进程的复制品;子进程装入另外一个程序。

UNIX系统中,通过调用fork()可以创建子进程,子进程的地址空间是通过复制原来进程的空间地址而成,这种机制允许在父子进程进行通信,两个进程都将执行fork()之后的指令。不同的是对于子进程,fork()的返回值是0,对于父进程而言则是子进程的pid

//UNIX的系统调用
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>


void main(int argc, char *argv[])
{
    pid_t pid;
    pid = fork();

    if(pid < 0){
        fprintf(stderr, "fork error");
        exit(-1);    
    }
    else if (pid == 0){
        execlp("/bin/ls","ls",NULL);    
    }
    else{
        wait(NULL);
        printf("child complete");
        exit(0);    
    }
}

Windows中,Win32 API采用CreateProcess()来创建进程,不同的是UNIX,fork()采用了子进程继承父进程的地址空间,而在Windows中,需要将一个特殊程序装入子进程的地址空间中,fork()不需要传入参数,而CreateProcess则需要至少传入十个参数。

//Windows 系统创建进程
#include <stdio.h>
#include <windows.h>

int main(void)
{
    STARTUPINFO si;
    PROCESS_INFORMATION pi;

    //allocate memory
    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    //create child process
    if (!CreateProcess(NULL,  // use command line
    "C:\\WINDOWS\\system32\\mspaint.exe", //command line
    NULL,
    NULL,
    FALSE,
    0,
    NULL,
    NULL,
    &si,
    &pi))
    )) {
        fprintf(stderr, "create Process Failed");
        return -1;    
    }

    Printf("child complete");


    //close handles
    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);
}

进程通信

协作进程需要有进程通信机制,进程间通信的方式有两种:共享内存,消息传递。

共享内存

采用共享内存的进程会通过建立一个共享内存区域,然后允许进程对该区域的读写完成通信。生产者-消费者模型是一种典型的协作进程的案例。下面是共享内存如何使用有限缓冲:

#define  BUFFER_SIZE 10

typedef struct {
    //other codes
    } item;

    item buffer[BUFFER_SIZE];
    int in =0;          //指向缓冲中下一个空位
    int out = 0;        //指向缓冲中第一个满位

in当 in == out 的时候,缓冲区为空;当 (in+1)%BUFFER_SIZE == out 的时候,缓冲区为满。

item nextProduced;

while(true){
    while((in + 1) % BUFFER_SIZE == OUT)
        ;//do nothing
    buffer[i] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
}

item nextConsumed;

while(true){
    while(in == out){
        ;//do nothing
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    }
}

消息传递系统

消息传递机制允许进程不必通过共享内存来通信,逻辑线路实现send()recevie()的方法:直接或间接通信/同步或异步通信/自动或显示缓冲。

直接通信:send(A,message)recevie(B,message)

间接通信:通过邮箱或端口来接受和发送消息一个进程可能通过许多不同的邮箱与其它进程通信,但是两个进程至少共享至少一个邮箱时可以相互通信。

客户机/服务器系统通信

共享内存以及消息传递机制都可以用于客户机/服务器系统的通信,其他的三种方式是:Socket/RPC/RMI。

线程

线程库

三种主要的线程库:POSIXthread,Win32,Java。

//构造一个多线程程序基本的PthreadAPI

#include <pthread.h>
#include <stdio.h>

int sum; // shared by all threads;
void * runner(void * param);

int main(int argc, char * argv[])
{
    pthread_t tid;              //thread id
    pthread_attr_t attr;        //set attributes

    if( argc != 2) {
        fprintf(stderr, "usage: a.out \n");
        return -1;
    }
    if(atoi(argv[1] < 0)){
        fprintf(stderr, "%d must be <= 0\n", atoi(argv[1]));
        return -1;    
    }

    pthread_attr_init(&attr);

    pthread_create(&tid, &attr, runner, argv[1]);

    pthread_join(tid, NULL);

    printf("sum == %d\n",sum);
} 

void * runner(void * param)
{
        int i, upper = atoi(param);
        sum = 0;

        for(i = 1; i <= upper; i++)
            sum += i;

        pthread_exit(0);
}

Win32线程

#include <windows.h>
#include <stdio.h>

DWORD WINAPI Summation(LPVOID Param)
{
    DWORD Upper = *(DWORD *)Param;
    for(DWORD i = 0; i <= Upper; i++)
        sum += i;
    return 0;    
}

int main(int argc, char *argv[])
{
    DWORD ThreadId;
    HANDLE ThreadHandle;
    int Param;

    if(arge != 2){
        fprintf(stderr, "An integer >= 0 is required in \n");
        return -1;    
    }            
    Param = atoi(argv[1]);
    if(Param < 0){
        fprintf(stderr, "An integer >= 0 is required \n");
        return -1;    
    }

    ThreadHandle = CreateThread(
        NULL,
        0,
        Summation,
        &Param,
        0,
        &Thread 
    );

    if(ThreadHandle != NULL){
        WaitForSingleObject(ThreadHandle, INFINITE);
        CloseHandle(ThreadHandle);

        printf("sum = %d\n", Sum);    
    }
}

CPU 调度算法

  • 先到先服务(first-come,first-serve)

  • 最短作业优先调度(short-job-first scheduling algorithm)

  • 优先级调度(priority-scheduling-algorithm)

  • 轮转法调度(专门为分时系统设计的,round-robin)

死锁

死锁的必要条件:

  • 互斥:一个资源一次只有一个进程在使用

  • 占有并等待: 一个进程占有资源并且等待其他资源

  • 非抢占: 正在使用的资源不能被转移

  • 循环等待: 所需要的资源互相占有

资源分配图

        P = {p1, p2, p3}   R = {r1, r2, r3}
        p1->r1 进程申请资源,申请边
        p2->r2 资源分配给进程, 分配边

如果分配图没有环,那么则不会出现死锁的情况,如果有环,那么则可能会出现死锁的情况。

Scope-1-py