进程状态转换
3.2.4 被挂起的进程
交换的需要
前面描述的三个基本状态（就绪态、运行态和阻塞态）提供了一种为进程行为建立模型的系统方法，并指导操作系统的实现。许多实际的操作系统都是按照这样的三种状态进行具体构造的。但是，可以证明往模型中增加其他状态也是合理的。为了说明加入新状态的好处，考虑一个没有使用虚拟内存的系统，每个被执行的进程必须完全载入内存，因此，图3.8b 中，所有队列中的所有进程必须驻留在内存中。
所有这些设计机制的原因都是由于I/O 活动比计算速度慢很多，因此在单道程序系统中的处理器在大多数时候是空闲的。但是图3.8b 的方案并没有完全解决这个问题。在这种情况下，内存保存有多个进程，当一个进程正在等待时，处理器可以转移到另一个进程，但是处理器比I/O 要快得多，以至于内存中所有的进程都在等待I/O 的情况很常见。因此，即使是多道程序设计，大多数时候处理器仍然可能处于空闲状态。
一种解决方法是内存可以被扩充以适应更多的进程，但是这种方法有两个缺陷。首先是内存的价格问题，当内存大小增加到兆位及千兆位时，价格也会随之增加；再者，程序对内存空间需求的增长速度比内存价格下降的速度快。因此，更大的内存往往导致更大的进程，而不是更多的进程。
另一种解决方案是交换，包括把内存中某个进程的一部分或全部移到磁盘中。当内存中没有处于就绪状态的进程时，操作系统就把被阻塞的进程换出到磁盘中的“挂起队列”（suspendqueue），这是暂时保存从内存中被“驱逐”出的进程队列，或者说是被挂起的进程队列。操作系统在此之后取出挂起队列中的另一个进程，或者接受一个新进程的请求，将其纳入内存运行。
“交换”（swapping）是一个I/O 操作，因而也可能使问题更加恶化。但是由于磁盘I/O 一般是系统中最快的I/O（相对于磁带或打印机I/O），所以交换通常会提高性能。
为使用前面描述的交换，在我们的进程行为模型（见图3.9a）中必须增加另一个状态：挂起态。当内存中的所有进程都处于阻塞态时，操作系统可以把其中的一个进程置于挂起态，并将它转移到磁盘，内存中释放的空间可被调入的另一个进程使用。
当操作系统已经执行了一个换出操作，它可以有两种将一个进程取到内存中的选择：可以接纳一个新近创建的进程，或调入一个以前被挂起的进程。显然，通常比较倾向于调入一个以前被挂起的进程，给它提供服务，而不是增加系统中的负载总数。
但是，这个推理也带来了一个难题，所有已经挂起的进程在挂起时都处于阻塞态。显然，这时把被阻塞的进程取回内存没有任何意义，因为它仍然没有准备好执行。但是，考虑到挂起状态中的每个进程最初是阻塞在一个特定的事件上，当这个事件发生时，进程就不再阻塞，可以继续执行。
因此，我们需要重新考虑设计方式。这里有两个独立的概念：进程是否在等待一个事件（阻塞与否）以及进程是否已经被换出内存（挂起与否）。为适应这种2×2 的组合，需要4 个状态：
就绪态：进程在内存中并可以执行。
阻塞态：进程在内存中并等待一个事件。
阻塞/挂起态：进程在外存中并等待一个事件。
就绪/挂起态：进程在外存中，但是只要被载入内存就可以执行。
在查看包含两个新挂起状态的状态转换图之前，必须提到另一点。到现在为止的论述都假设没有使用虚拟内存，进程或者都在内存中，或者都在内存之外。在虚拟内存方案中，可能会执行到只有一部分内容在内存中的进程，如果访问的进程地址不在内存中，则进程的相应部分可以被调入内存。虚拟内存的使用看上去会消除显式交换的需要，这是因为通过处理器中的存储管理硬件，任何期望的进程中的任何期望的地址都可以移入或移出内存。但是，正如在第8 章中将会看到的，如果有足够多的活动进程，并且所有进程都有一部分在内存中，则有可能导致虚拟内存系统崩溃。因此，即使在虚拟存储系统中，操作系统也需要不时地根据执行情况显式地、完全地换出进程。
现在来看图3.9b 中我们已开发的状态转换模型（图中的虚线表示可能但并不是必需的转换）。比较重要的新的转换如下：
阻塞→阻塞/挂起：如果没有就绪进程，则至少一个阻塞进程被换出，为另一个没有阻塞的进程让出空间。如果操作系统确定当前正在运行的进程，或就绪进程为了维护基本的性能要求而需要更多的内存空间，那么，即使有可用的就绪态进程也可能出现这种转换。
阻塞/挂起→就绪/挂起：如果等待的事件发生了，则处于阻塞/挂起状态的进程可以转换到就绪/挂起状态。注意，这要求操作系统必须能够得到挂起进程的状态信息。
就绪/挂起→就绪：如果内存中没有就绪态进程，操作系统需要调入一个进程继续执行。此外，当处于就绪/挂起态的进程比处于就绪态的任何进程的优先级都要高时，也可以进行这种转换。这种情况的产生是由于操作系统设计者规定调入高优先级的进程比减少交换量更重要。
就绪→就绪/挂起：通常，操作系统更倾向于挂起阻塞态进程而不是就绪态进程，因为就绪态进程可以立即执行，而阻塞态进程占用了内存空间但不能执行。但如果释放内存以得到足够空间的唯一方法是挂起一个就绪态进程，那么这种转换也是必需的。并且，如果操作系统确信高优先级的阻塞态进程很快将会就绪，那么它可能选择挂起一个低优先级的就绪态进程，而不是一个高优先级的阻塞态进程。
还需要考虑的几种其他转换有：
新建→就绪/挂起以及新建→就绪：当创建一个新进程时，该进程或者加入到就绪队列，或者加入到就绪/挂起队列中。不论哪种情况，操作系统都必须建立一些表以管理进程，并为进程分配地址空间。操作系统可能更倾向于在初期执行这些辅助工作，这使得它可以维护大量的未阻塞的进程。通过这个策略，内存中经常会没有足够的空间分配给新进程，因此使用了（新建→就绪/挂起）转换。另一方面，我们可以证明创建进程的适时（just-in-time）原理，即尽可能推迟创建进程以减少操作系统的开销，并在系统被阻塞态进程阻塞时允许操作系统执行进程创建任务。
阻塞/挂起→阻塞：这种转换在设计中比较少见，如果一个进程没有准备好执行，并且不在内存中，调入它又有什么意义？但是考虑到下面的情况：一个进程终止，释放了一些内存空间，阻塞
/挂起队列中有一个进程比就绪/挂起队列中的任何进程的优先级都要高，并且操作系统有理由相信阻塞进程的事件很快就会发生，这时，把阻塞进程而不是就绪进程调入内存是合理的。
运行→就绪/挂起：通常当分配给一个运行进程的时间期满时，它将转换到就绪态。但是，如果由于位于阻塞/挂起队列的具有较高优先级的进程变得不再被阻塞，操作系统抢占这个进程，也可以直接把这个运行进程转换到就绪/挂起队形中，并释放一些内存空间。
各种状态→退出：在典型情况下，一个进程在运行时终止，或者是因为它已经完成，或者是因为出现了一些错误条件。但是，在某些操作系统中，一个进程可以被创建它的进程终止，或当父进程终止时终止。如果允许这样，则进程在任何状态时都可以转换到退出态。
挂起的其他用途
到目前为止，挂起进程的概念与不在内存中的进程概念是等价的。一个不在内存中的进程，不论它是否在等待一个事件，都不能立即执行。
我们可以总结一下挂起进程的概念。首先，按照以下特点定义挂起进程：
1）进程不能立即执行。
2）进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。
3）为阻止进程执行，可以通过代理把这个进程置于挂起状态，代理可以是进程自己，也可以是父进程或操作系统。
4）除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。
表3.3 列出了进程的一些挂起原因。已经讨论过的一个原因是提供更多的内存空间，这样可以调入一个就绪/挂起态进程，或者增加分配给其他就绪态进程的内存。操作系统因为其他动机而挂起一个进程，例如，记账或跟踪进程可能用于监视系统的活动，可以使用进程记录各种资源（处理器、内存、通道）的使用情况以及系统中用户进程的进行速度。在操作员控制下的操作系统可以不时地打开或关闭这个进程。如果操作系统发现或怀疑有问题，它可以挂起进程。死锁就是一
个例子，将在第6 章讲述。另一个例子是，如果在进程测试时检测到通信线路中的问题，操作员让操作系统挂起使用该线路的进程。
另外一些原因关系到交互用户的行为。例如，如果用户怀疑程序中有缺陷，他（她）可以挂起执行程序并进行调试，检查并修改程序或数据，然后恢复执行；或者可能有一个收集记录或记账的后台程序，用户可能希望能够打开或关闭这个程序。
表3.3 导致进程挂起的原因
时机的选择也会导致一个交换决策。例如，如果一个进程周期性地被激活，但大多数时间是空闲的，则在它在两次使用之间应该被换出。监视使用情况或用户活动的程序就是一个例子。
最后，父进程可能会希望挂起一个后代进程。例如，进程A 可以生成进程B，以执行文件读操作；随后，进程B 在读文件的过程中遇到错误，并报告给进程A；进程A 挂起进程B，调查错误的原因。
在所有这些情况中，挂起进程的活动都是由最初请求挂起的代理请求的。
词法分析程序设计与实现
` 实验一词法分析程序设计与实现 一、实验目的及容 调试并完成一个词法分析程序，加深对词法分析原理的理解。 二、实验原理（状态转换图） 1、C语言子集 （1）关键字： begin if then while do end 所有关键字都是小写。 （2）运算符和界符： := + – * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码 文档Word
` 3、词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（syn，token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 二、软件平台及工具 PC机以及VISUAL C++6.0软件。 三、实验方法、步骤（或：程序代码或操作过程）（1）程序代码： #include
实验2 进程状态转换及其PCB的变化
实验2进程状态转换及其PCB的变化 1.目的 自行编制模拟程序，通过形象化的状态显示，使学生理解进程的概念、进程之间的状态转换及其所带来的PCB内容、组织的变化，理解进程与其PCB间的一一对应关系。 2. 内容及要求 1）设计并实现一个模拟进程状态转换及其相应PCB内容、组织结构变化的程序。 2）独立编写、调试程序。进程的数目、进程的状态模型（三状态、五状态、七状态或其它）以及PCB的组织形式可自行选择。 3）合理设计与进程PCB相对应的数据结构。PCB的内容要涵盖进程的基本信息、控制信息、资源需求及现场信息。 4）设计出可视性较好的界面，应能反映出进程状态的变化引起的对应PCB 内容、组织结构的变化。 5）代码书写要规范，要适当地加入注释。 6）鼓励在实验中加入新的观点或想法，并加以实现。 7）认真进行预习，完成预习报告。 8）实验完成后，要认真总结，完成实验报告。 3.程序流程图 进程的三种基本状态及其转换如下图所示。
开始 输入要执行的指令 1？N 2？N 3？N 4？ N 5？N 0？Y Y 结束 N 提示输入错误 就绪队列已 满？ N 创建进程 Y 提示就绪队列 已满Y 有进程处于运行状态? Y 该进程执行一个时间片 后放回就绪队列 N 将就绪队列中优先级最高的进程放入运行队列 有进程处于运行状态? Y 该进程所需执行时间减1，并回到就绪队列 Cputime++ Y 有进程处于运行状态？ Y 将该进程放入阻塞 队列 N 提示无运行的进程 输入事件发生的进程名称 阻塞队列中有该 进程？ Y 将该进程放入就绪队列 N 提示该进程并 未阻塞 4.数据结构及说明 在本实验中，主要的数据结构是PCB 的数据结构，具体如下： struct process{
操作系统精髓与设计原理-第3章 进程描述和控制
第3章进程描述和控制 复习题： 3.1什么是指令跟踪？ 答：指令跟踪是指为该进程而执行的指令序列。 3.2通常那些事件会导致创建一个进程？ 答：新的批处理作业；交互登录；操作系统因为提供一项服务而创建；由现有的进程派生。（详情请参考表3.1） 3.3对于图3.6中的进程模型，请简单定义每个状态。 答：运行态：该进程正在执行。就绪态：进程做好了准备，只要有机会就开始执行。 阻塞态：进程在某些事件发生前不能执行，如I/O操作完成。新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。 3.4抢占一个进程是什么意思？ 答：处理器为了执行另外的进程而终止当前正在执行的进程，这就叫进程抢占。 3.5什么是交换，其目的是什么？ 答：交换是指把主存中某个进程的一部分或者全部内容转移到磁盘。当主存中没有处于就绪态的进程时，操作系统就把一个阻塞的进程换出到磁盘中的挂起队列，从而使另一个进程可以进入主存执行。 3.6为什么图3.9（b）中有两个阻塞态？ 答：有两个独立的概念：进程是否在等待一个事件（阻塞与否）以及进程是否已经被换出主存（挂起与否）。为适应这种2*2的组合，需要两个阻塞态和两个挂起态。3.7列出挂起态进程的4个特点。 答：1.进程不能立即执行。2.进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。3.为了阻止进程执行，可以通过代理把这个进程置于挂起态，代理可以是进程自己，也可以是父进程或操作系统。4.除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。 3.8对于哪类实体，操作系统为了管理它而维护其信息表？ 答：内存、I/O、文件和进程。 3.9列出进程控制块中的三类信息。 答：进程标识，处理器状态信息，进程控制信息。 3.10为什么需要两种模式（用户模式和内核模式）？ 答：用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系统受到破坏或者修改。而在内核模式下则没有这些限制，从而使它能够完成其功能。 3.11操作系统创建一个新进程所执行的步骤是什么？ 答：1.给新进程分配一个唯一的进程标识号。2.给进程分配空间。3.初始化进程控制块。 4.设置正确的连接。 5.创建或扩充其他的数据结构。 3.12中断和陷阱有什么区别？ 答：中断与当前正在运行的进程无关的某些类型的外部事件相关，如完成一次I/O操作。陷阱与当前正在运行的进程所产生的错误或异常条件相关，如非法的文件访问。 3.13举出中断的三个例子。 答：时钟终端，I/O终端，内存失效。 3.14模式切换和进程切换有什么区别？ 答：发生模式切换可以不改变当前正处于运行态的进程的状态。发生进程切换时，一个正在执行的进程被中断，操作系统指定另一个进程为运行态。进程切换需要保存更
大数据结构课程设计——进制转换
数据结构课程设计 设计说明书 进制转换的实现 学生JUGG 学号￥#·· 班级Dota all star——成绩优秀 指导教师Puck dota科学与技术 天灾元年 3 月 14 日
Dota all star
课程设计任务书 天灾元年—近卫戊年第二学期 专业：ganker 学号：sadofaiofo ： 课程设计名称：数据结构课程设计 设计题目：进制转换的实现 完成期限：自天灾元年年 3 月 1 日至近卫戊年年 3 月14 日共 2 周 设计依据、要求及主要容（可另加附页）： 进制数制是人们利用符号进行计数的科学方法。数制有很多种，在计算机中常用的数制有：十进 制，二进制、八进制和十六进制。十六进制数有两个基本特点:它由十六个字符0～9以及A，B，C，D， E，F组成（它们分别表示十进制数0～15），十六进制数运算规律是逢十六进一，例如：十六进制数4AC8 可写成（4AC8）16，或写成4AC8H。 要求： （1）输入一个十进制数N，将它转换成R进制数输出，并可以进行逆转换。 （2）输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<>10）。 （3）为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考 16进制（比如，10用A表示，等等）。 （4）界面友好。 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 摘要
由于数制计算和不同数制之间转换的需要，设计了一个10进制转换其它进制(36进制以)及逆转换的软件，该软件具有简单的将10进制数转换成2、8、16进制数以及较复杂的高进制数的转换和逆转功能。本软件采用C语言编写以VC++作为软件开发环境，采用顺序栈存储方式来存储运算中的数位，借助栈后进先出的特点，易于结果输出。操作简单，界面清晰，易于为用户所接受。 关键词：进制转换；顺序栈；逆转换
实验1-3 《编译原理》词法分析程序设计方案
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表
操作系统实验报告+进程状态转换
实验进程状态转换及其PCB的变化 一、程序流程图： 二、使用的数据结构及说明： 在本实验中，主要用到的数据结构是PCB的结构，其中PCB的数据结构如下： struct PCB { int P_Id; //PCB的ID号 char P_Name[10]; //PCB的名称 char P_State[10]; //PCB状态 int P_Runtime; //PCB的所需要的运行时间 int P_Requiry; //PCB所需要的资源要求 struct PCB * next ; //PCB块的下一个指针 } ; 其中，P_Id,和P_Name用来标示一个进程，而P_State用来标示进程的五种状态：
Create_state,Ready_state,Block_state,Run_state,Exit_state。P_Runtime标示要完成一个进程所需要的时间。P_Requiry标示一个进程的执行所需要的其他条件，当其他的条件满足，则P_Requiry 置1，否则置0。Struct PCB * next 用来指向同一队列中的下一个PCB块。 三、程序源代码: #include"stdlib.h" #include"stdio.h" #include"string.h" /********** globle structure and viable ******/ struct PCB { int P_Id; //PCB的ID号 char P_Name[10]; //PCB的名称 char P_State[10]; //PCB状态 int P_Runtime; //PCB的所需要的运行时间 int P_Requiry; //PCB所需要的资源要求 struct PCB * next ; //PCB块的下一个指针 } ; struct PCB * Create_state; //创建状态 struct PCB * Run_state; //运行状态 struct PCB * Ready_state; //就绪状态 struct PCB * Block_state; //阻塞状态 struct PCB * Exit_state; //退出状态 int signal4=0; //标示进程4的完成状态 int signal5=0; //标示进程5的完成状态 void InsertQueue(struct PCB **head,struct PCB *node) /* insert node function */ { struct PCB * p,*q; node->next=NULL; if(*head==NULL) //如果队列为空 { *head=node; } Else //队列不空 { p=*head; q=p->next; while(q!=NULL) //找到最后的元素位置 { p=q; q=q->next; } p->next=node; //将节点插入队列 }
十进制和二进制相互转化程序设计书
摘要 VC++是微软公司开发的一个集成开发环境(IDE),就是使用 c++的一个开发平台。本系统就是根据现阶段的需要，通过VC++开发一个二进制与十进制相互转换系统来实现对二进制向十进制转换、十进制向二进制转换。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成了对二进制与十进制互换的过程，包括转换类型、二进制位数、输入是否有误，以及简介信息，数字信息和位数信息等常用工作。 关键词：二进制，十进制，转换，VC++
目录 1 需求分析 (1) 1.1 数据需求分析 (1) 1.2 功能需求分析 (2) 2 系统总体设计 (2) 2.1 模块划分 (2) 2.2 系统模块结构图 (3) 3 系统详细设计 (3) 3.1 程序流程图 (3) 3.2 中文DOS界面 (5) 3.3 程序代码清单 (5) 4 模块划分系统连编与运行结果 (7) 4.1 程序运行起始界面 (7) 4.2 输入一个十进制的正整数，转化为二进制 (8) 4.3 输入一个十进制的负数，转化为二进制 (8) 4.4 输入一个十进制的负数，转化为二进制 (9) 4.5 输入一个十进制小数，转化为二进制时，提示为 (9) 总结 (10) 参考文献 (10)
1需求分析 随着技术的不断提高，进制转换向着简单化，规模化发展，而对于只能识别二进制0和1码的计算机来说，如何翻译成人类可以认识和编译的语言，和安全加密等给信息管理有关的信息随之增加。在这种情况下单靠人工来处理这些信息不但显得大不从心，而且极容易出错。因此，需要开发二进制与十进制互换系统，该系统可以实现由计算机代替人工执行一系列复杂而繁琐的操作，使得办公人员可以轻松快捷的完成进制转换的任务。 总结系统需求分为大体分为5个模块： 首先第一个需要数据的信息输入，即输入数据的基本信息包括输入的进制选项，所输入的二进制位数，所输入的二进制数，所输入的十进制数和判断是否全1或全0五个模块。 第二个需求是判断数据进制选项信息，在信息和科技不断进步的今天，数据及时准确的更新成了任何一个系统的首要任务，本系统应时代所需设计了数制信息功能，包括对包括数据的进制，二进制数据的位数，十进制数据，进行进制转换计算。 第三个需求是所输入的二进制数据，数据的运行使用主要是解决向十进制转换 第四个需求是所输入的十进制数据，数据运行使用主要是解决向二进制转换。 第五个需求是打印退出，在对系统进行操作后，退出系统。 1.1 数据需求分析 本系统的主要数据进制转换的实现。转换包括:二进制数向十进制数转换，十进制数向二进制数转换，判断是否为全0或全1，是否继续执行等。
实验一 进程状态转换
实验一进程的状态及其转换 一、实验目的: 自行编制模拟程序，通过形象化的状态显示，加深理解进程的概念、进程之间的状态转换及其所带来的PCB内容、组织的变化，理解进程与其PCB间的一一对应关系。 二、实验内容及要求： 1)设计并实现一个模拟进程状态转换及其相应PCB内容、组织结构变化的程序。 2)独立编写、调试程序。进程的数目、进程的状态模型（三状态、五状态、七状 态或其它）以及PCB的组织形式可自行选择。 3)合理设计与进程PCB相对应的数据结构。PCB的内容要涵盖进程的基本信息、控 制信息、资源需求及现场信息。 4)设计出可视性较好的界面，应能反映出进程状态的变化引起的对应PCB内容、 组织结构的变化。 三、程序流程图：
四、使用的数据结构及说明： 在本实验中，主要用到的数据结构是PCB的结构，其中PCB的数据结构如下： struct PCB { int P_Id; //PCB的ID号 char P_Name[10]; //PCB的名称 char P_State[10]; //PCB状态 int P_Runtime; //PCB的所需要的运行时间 int P_Requiry; //PCB所需要的资源要求 struct PCB * next ; //PCB块的下一个指针 } ; 其中，P_Id,和P_Name用来标示一个进程，而P_State用来标示进程的五种状态：Create_state,Ready_state,Block_state,Run_state,Exit_state。P_Runtime标示要完成一个进程所需要的时间。P_Requiry标示一个进程的执行所需要的其他条件，当其他的条件满足，则P_Requiry置1，否则置0。Struct PCB * next 用来指向同一队列中的下一个PCB 块。 五、参考程序源代码: #include"stdlib.h" #include"stdio.h" #include"string.h" #include
编译原理词法分析--A__状态转换图-直接转向法-伪代码描述
int code, value; strToken := ““; GetChar(); //将下一字符读入ch中, 搜索指示器前移一个字符位置 GetBC(); //检查ch中的字符是否为空白,若是调用GetChar直至读入非空白字符if (IsLetter())//判断ch中的字符是否为字母 begin while (IsLetter() or IsDigit()) begin Concat(); //将ch中的字符连接到strToken之后 GetChar(); End Retract(); //将搜索指示器回退一个字符位置, 将ch置为空 code = Reserve(); //对strToken中的字符串查找保留字表,若是,返回编码;否则返回0 if (code = 0) begin value := InsertId(strToken); //将strToken中的标识符插入符号表,返回指针 return ($ID, value); end else return (code, -); end else if (IsDigit())//判断ch中的字符是否为数字 begin while (IsDigit)) begin Concat(); GetChar(); End Retract(); Value := InsertToken(); //将strToken中的标识符插入常数表,返回指针 return ($INT, value); end else if (ch = ‘=’)return ($ASSIGN, -); else if (ch = ‘+’)return ($PLUS, -); else if (ch = ‘*’) begin GetChar(); if (ch = ‘*’) return ($POWER,-); Retract(); return ($STAR,-); end else if (ch = ‘;’)return ($SEMICOLON, -); else if (ch = ‘(’)return ($LPAR, -);
词法分析课程设计
《词法分析》设计说明书 学生姓名 学 号 5011110122 5011110133 5011110128 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机15-1班 信息工程学院 《编译原理及实践》结课大作 业
摘要 编译，简单的说，就是把源程序转换为可执行程序。从hellow worl说程序运行机制里面简单的说明了程序运行的过程，以及一个程序是如何一步步变成可执行文件的。在这个过程中，编译器做了很多重要的工作。对于编译的内部实现，也就是编译的原理。 这篇论文主要说的是编译器前端，词法分析器的原理，最后会给出一个词法分析器的简单实现。 编译简单的说，就是把源程序转化为另一种形式的程序,而其中关键的部分就是理解源程序所要表达的意思，才能转化为另一种源程序。 可以用一个比喻来说明问题：人A和人B想要交谈，但是他们都不知道彼此的语言，这就需要一个翻译C，同时懂得A和B的语言。有了C做中间层，A和B才能正常交流。C的作用就有点像编译器，它必须能理解源程序所要表达的意思，才能把信息传递给另一个。编译器也一样，它的输入是语言的源文件（一般可以是文本文件）对于输入的文件，首先要分离出这个输入文件的每个元素（关键字、变量、符号、、），然后根据语言的文法，分析这些元素的组合是否合法，以及这些组合所表达的意思。 程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文没有关系，只有它自身决定。 这篇论文主要说的就是词法分析，也就是把输入的符号串整理成特定的词素。 关键词：单片机；词法分析
操作系统实验一模拟进程状态转换
实验一模拟进程状态转换及其PCB的变化 一、实验目的： 自行编制模拟程序，通过形象化的状态显示，使学生理解进程的概念、进程之间的状态转换及其所带来的PCB内容、组织的变化，理解进程与其PCB间的一一对应关系。 二、实验内容及要求： （1）、设计并实现一个模拟进程状态转换及其相应PCB内容、组织结构变化的程序。 （2）、独立编写、调试程序。进程的数目、进程的状态模型（三状态、五状态、七状态或其它）以及PCB的组织形式可自行选择。（3）、合理设计与进程PCB相对应的数据结构。PCB的内容要涵盖进程的基本信息、控制信息、资源需求及现场信息。 （4）、设计出可视性较好的界面，应能反映出进程状态的变化引起的对应PCB内容、组织结构的变化。 （5）、代码书写要规范，要适当地加入注释。 （6）、鼓励在实验中加入新的观点或想法，并加以实现。 （7）、认真进行预习，完成预习报告。 （8）、实验完成后，要认真总结，完成实验报告。 三、实现: 数据结构 struct PCB{
char name; int priority; int needtime; bool operator < (const PCB &b) const{ return priority>b.priority; } }; 五状态进程模型 最高优先数优先调度算法流程图
四、运行结果：
图1创建2个进程，因为这时cpu空闲所以内核调度，b优先级高先执行 图2超时，因为这时cpu空闲所以内核调度，b优先级还是比a高所以先执行
图32个进程均被阻塞，其中一旦进程被阻塞就会引发调度 图4唤醒1个进程，从阻塞队列取队首放到就绪队列队尾，由于这时cpu空闲所以内核调 度
数制转换数据结构课程设计报告
《数据结构》 课程设计报告书 题目：数制转换 系别：计算机科学与应用系学号： 学生姓名： 指导教师： 完成日期：2013—6—1
数制转换 1.需求分析 任意给定一个M进制的数x ，实现如下要求 1)求出此数x的10进制值（用MD表示） 2)实现对x向任意的一个非M进制的数的转换。 3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。 2.概要设计 程序流程可以用以下流程图来刻画： A用数组实现 B用栈实现 3.详细设计 A．用数组实现该问题 D2M()函数和M2D()函数是实现该问题的主要函数。D2M()函数是实现十进制转换为其他进制的函数，它是将输入的十进制数x首先对需要转换的进制M取余，然后在对其取整，接着通过递归调用D2M()函数一次将得到的整数部分一次先取余后取整，并将所得的余数依次存入下一数组，然后逆向去除数组中的元素，即得到转换后的结果。而M2D()函数是实现其他进制M转换为十进制，并将其转换为非M进制。M进制转十进制则是从该M 进制数的
最后一位开始运算，依次列为第0、1、2、……..N位并分别乘以M的0、1、2、…..N次方，将得到的次方相加便得到对应的十进制数，再调用D2M()函数将其转换为非M进制的数。 B.用栈实现 栈具有后进先出的性质，具体实现方法和数组的方法有很大联系，不再过多解释。 4.调试分析 （1）构造栈的方法通过查阅书籍知道了。 （2）数组的递归调用查阅相关书籍了解了。 （3）为了让界面表达更清晰，多次调试完善了界面。 5.测试结果 下面是我的测试函数及运行结果： A.数组测试结果
数据结构课程设计 数制转换 数组和栈
中北大学 数据结构与算法课程设计 说明书 学院、系：软件学院 专业：软件工程 学生姓名：xxx 学号：xxxx 设计题目：数制转换问题 起迄日期: 2013年12月9日- 2013年12月20日指导教师:xxx 2013 年12月 20 日
1、需求分析 任意给定一个M进制的数x ，请实现如下要求 1) 求出此数x的10进制值（用MD表示） 2) 实现对x向任意的一个非M进制的数的转换。 3) 用两种方法实现上述要求（用栈解决和用数组解决）。 2、概要设计 流程图 数组的流程图：
栈的流程图：
算法思想 １、用数组实现该问题： DtoM()函数和MtoD()函数是实现该问题的主要函数。DtoM()函数是实现十进制转换为其它进制的函数，它是将输入的十进制数ｘ取首先对需要转换的进制M取余，然后再对其取整，接着通过递归调用DtoM()函数依次将得到的整数部分依次先取余后取整，并将所得的余数依次存入一个数组中，然后逆向取出数组中的元素，即得到转换后的结果。而MtoD()函数则是实现其他进制M转换为十进制，并将其转换为非M进制的数。M进制转十进制则是从该M进制数的最后一位开始算，依次列为第０、１、２…ｎ位并分别乘以M的０、１、２…ｎ次方，将得到的次方相加便得到对应的十进制数，再调用DtoM()函数将其转换为非M进制的数。 ２、用栈实现该问题： 同样是利用DtoM()和MtoD()两个函数实现。两个函数的思想同利用数组实现时相同。只是栈具有后进先出的性质，故其用Pop()取数较数组的逆向取数方便些。 模块划分 １、用数组实现该问题： ⑴i,j,y,n,s,m,r,reminder,x是定义的全局变量，初始值都为０； ⑵DtoM(int g,int h)是实现十进制数转换为M进制数的函数； ⑶MtoD()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并 在其中调用D2M(int g,int h)实现向非M进制数的转换； ⑷HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(int g,int h)实现向非十六进制数的转换； ⑸void main()是主函数，功能是给出测试的数据，并在特定条件下调用D2M()
C语言课程设计--进制转换
C 语言 课程设计报告 设计题目：进制转换 学生姓名： 学生学号：20101010110 专业班级：数学与应用数学一班 学院名称：数学与计量经济学院 同组人姓名： 指导老师： 2011年6 月16 日
目录 1．需求分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1．1问题描述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1．2输入数据的要求．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1．3输出数据的要求．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1．4开发环境和工具．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1。.5成员分工．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 2．总体设计．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．2 2．1设计思路．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．3 2。.2模块结构图．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．4 3．详细设计．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．7 3．1数据类型的定义．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．7 3．2总的实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．8 4．系统测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．9 5．总结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．·10 6．参考文献及附录．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11
操作系统实验一模拟进程状态转换
实验一模拟进程状态转换及其PCB的变化一、实验目的： 自行编制模拟程序，通过形象化的状态显示，使学生理解进程的概念、进程之间的状态转换及其所带来的PCB内容、组织的变化，理解进程与其PCB间的一一对应关系。 二、实验内容及要求： （1）、设计并实现一个模拟进程状态转换及其相应PCB内容、组织结构变化的程序。 （2）、独立编写、调试程序。进程的数目、进程的状态模型（三状态、五状态、七状态或其它）以及PCB的组织形式可自行选择。（3）、合理设计与进程PCB相对应的数据结构。PCB的内容要涵盖进程的基本信息、控制信息、资源需求及现场信息。 （4）、设计出可视性较好的界面，应能反映出进程状态的变化引起的对应PCB内容、组织结构的变化。 （5）、代码书写要规范，要适当地加入注释。 （6）、鼓励在实验中加入新的观点或想法，并加以实现。 （7）、认真进行预习，完成预习报告。 （8）、实验完成后，要认真总结，完成实验报告。 三、实现: 数据结构 struct PCB{
char name; int priority; int needtime; bool operator < (const PCB &b) const{ return priority>; } }; 五状态进程模型 最高优先数优先调度算法流程图
四、运行结果：
图1 创建2个进程，因为这时cpu空闲所以内核调度，b优先级高先执行 图2 超时，因为这时cpu空闲所以内核调度，b优先级还是比a高所以先执行
图3 2个进程均被阻塞，其中一旦进程被阻塞就会引发调度 图4 唤醒1个进程，从阻塞队列取队首放到就绪队列队尾，由于这时cpu空闲所以内核调 度 五、源代码： #include
进程的运行状态
进程在运行过程中主要是在就绪、运行和阻塞三种状态间进行转换。创建状态和退出状态描述进程创建的过程和进程退出的过程。 1)运行状态(Running)：进程占用处理器资源；处于此状态的进程的数目小于等于处理器的数目。在没有其他进程可以执行时(如所有进程都在阻塞状态)，通常会自动执行系统的空闲进程。 2)就绪状态(Ready)：进程已获得除处理器外的所需资源，等待分配处理器资源；只要分配了处理器进程就可执行。就绪进程可以按多个优先级来划分队列。例如，当一个进程由于时间片用完而进入就绪状态时，排人低优先级队列；当进程由I／O操作完成而进入就绪状态时，排入高优先级队列。 3)阻塞状态(Blocked)：当进程由于等待I/O操作或进程同步等条件而暂停运行时，它处于阻塞状态。 4)创建状态(New)：进程正在创建过程中，还不能运行。操作系统在创建状态要进行的工作包括分配和建立进程控制块表项、建立资源表格(如打开文件表)并分配资源、加载程序并建立地址空间表等。 5)退出状态(Exit)：进程已结束运行，回收除进程控制块之外的其他资源，并让其他进程从进程控制块中收集有关信息(如记帐和将退出代码传递给父进程)。 五状态进程模型中的状态转换主要包括下列几种。操作系统中多个进程的并发执行是通过调度与超时两种转换间的循环，或调度、等待事件和事件出现三种转换间的循环来描述的。 1)创建新进程：创建一个新进程，以运行一个程序。创建新进程的可能原因包括用户登录、操作系统创建以提供某项服务、批处理作业等。 2)收容(Admit，也称为提交)：收容一个新进程，进入就绪状态。由于性能、内存等原因，系统会限制并发进程总数。 3)调度运行(Dispatch)：从就绪进程表中选择一个进程，进入运行状态。 4)释放(Release)：由于进程完成或失败而终止进程运行，进入结束状态。 为了简洁，状态变迁图中只画出了运行状态到退出状态间的释放转换；但实际上，还存在从就绪状态或阻塞状态到退出状态的释放转换。运行到结束的转换可分为正常退出(Exit)和异常退出(abort)；其中异常退出是指进程执行超时、内存不够、非法指令或地址访问、I／0操作失败、被其他进程所终止等原因而退出。从就绪状态或阻塞状态到结束状态的释放转换可能是由于多种原因引发，如父进程可在任何时间终止子进程。 5)超时(Timeout)：由于用完时间片或高优先级进程就绪等原因导致进程暂停运行 6)事件等待(Event Wait)：进程要求的事件未出现而进入阻塞；可能的原因包括申请系统服务或资源、通信、I/O操作等。 7)事件出现(EventOccurs)：进程等待的事件出现；如操作完成、申请成功等。
数制转换问题(完整)
数据结构课程设计 题目名称：数制转换问题 课程名称：数据结构 学生姓名： 学号： 学院名称： 指导教师：
目录 一．需求分析………………………………………………………二．概要设计………………………………………………………三．详细设计………………………………………………………四．调试测试………………………………………………………五．总结……………………………………………………………
一．需求分析 应用环境设定：生活中我们需要将M进制的数转换为我们所需要 的进制，从键盘任意输入一个M进制的数，对其 进行转换成其他三种进制的数，然后再从电脑中 显示出来，最终得到我们的结果。 用户界面：命令行界面，根据自己的要求，对界面的提示进行操作，正确输入我们需要的数据。 输入方式：首先输入将转换的进制数，回车确认；然后输入确定的数据，回车确认；接着选择要转换为的进制数，回车确 认。 输出方式：界面直接输出，启动程序后，按照界面提示，输入数据，直接回车确认，显示屏即输出我们的数据结果。 数据储存方式：全部在内存存放，不使用硬盘上的文件或其他数据 源，程序执行过程中和结束后不保存数据。 程序功能：1.根据界面提示输入M进制数据。 2.对任意M进制数据实行非M进制的转换。 二．概要设计 在此说明数据结构设计和关键的算法设计思想 1.用数组实现该问题 D2M()函数和M2D()函数是实现该问题的主要函数。D2M()函数是实现十进制转换为其它进制的函数，它是将输入的十进制数ｘ取首先对需要转换的进制M取余，然后再对其取整，接着通过递归调用D2M()函数依次将得到的整数部分依次先取余后取整，并将所得的余
编译原理实验报告2-词法分析程序的设计
实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图；
数据结构课程设计报告-进制转换
课程设计报告 设计题目：进制转换问题 学生姓名： 专业：信息安全 班级：信息安全10-02 学号： 指导教师： 完成日期：2011年12月 课程设计报告的内容及要求 一、问题描述： 任意给定一个M进制的数x ，请实现如下要求： 1、求出此数x的10进制值（用MD表示） 2、实现对x向任意的一个非M进制的数的转换 3、至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）软件环境：Vc6.0编程软件 二、实验环境 运行平台：Win32 硬件：普通个人pc机 软件环境：VC++6.0编程软件 三、解决办法： １、用数组实现该问题： ten_else()函数是实现十进制转换为其它进制的函数，先设置一个while循环，当十进制数g等于零时停止，再将输入的十进制数ｘ取首先对需要转换的进制M取余，然后再对其取整，并将所得的余数依次存入一个数组中，然后逆向取出数组中的元素，即得到转换后的结果。将其他进制M转换为十进制，并将其转换为非M进制数是在主函数中实现的。M进制转十进制则是从该M进制数的最后一位开始算，依次列为第０、１、２…ｎ位并分别乘以M 的０、１、２…ｎ次方，将得到的次方相加便得到对应的十进制数，再调用ten_else（）函数将其转换为非M进制的数。实际上十进制起到了一个桥梁作用。 ２、用栈实现该问题： 与数组方法核心思想相同，stack定义栈，初始化一个空栈，然后判断是否为空，接着是去栈顶元素（用z表示栈顶元素），数据入栈，出栈的操作。栈具有后进先出的性质，故其用s.pop()取数较数组的逆向取数较为方便，体现了栈的优越性。
四、设计和编码的回顾讨论和分析 （1）函数ten_else()的作用体现在将任意10进制数转换为非10进制数，程序能实现1~16进制的相互转换。在10进制以上的数需要用字母表示，由此设计了switch函数，当出现余数大与10的情况可以调用相应的字母。考虑到最终结果是所求余数的倒序，添加新的整型变量j，通过一个for循环实现倒序。 （2）编程初期设计了else_ten函数，后几经修改将其融入main函数中较为直观。 （3）当输入10进制以下的数向10进制转换时候较为简单，程序中设计char型数组s[maxnum]来统计所输入数据的位数，不需要用户输入。在求10进制的时候通过for循环求一个累和即可。 （4）当输入10进制以上的数设计字母较为复杂，通过对ASCⅡ表的理解设计程序。 （5）在用栈法实现非10进制向10进制转换的时候遇到了些麻烦，当输入8A的时候程序将8当成字符类型，将其编译为数字56，导致最终转换结果出现错误。于是通过查阅ASCⅡ表对程序做出了修正，设计了条件语句if(z<=57)z-=48;if(z>=65){z-=65;z+=10;} 五、程序框图 六、经验和体会 （1）我们在写程序的时候要多角度考虑问题，比如题目中要求栈法与数组方法同时去实现进制转换问题。在编译过程中我们可以将特殊的问题逐渐的化为一般问题，比如10进制转换到16进制是，我举的例子是200转换为C8。 （2）通过此次课程设计的考验，让我们回顾了算法与数据结构这门课的主要内容。掌握了如何分别用数组和栈来实现数据存储与转换，加深了对栈的掌握和操作，以及栈先进后出的特点。 （3）在程序的调试初期，我们遇到了许多问题，暴露了对编译软件不熟悉的弊端，如设置断
郑州大学操作系统课后习题
第三章 1某系统的进程状态如下图所示，a 是 运行 状态，b 是 就绪 状态，c 是 阻塞状态；1表示分派，2表示超时，3表示发生事件等待，4表示事件发生。 2设系统中有n(n>2)个进程，且当前不在执行进程调度程序，试考虑下列说法的正确性： 1. 没有运行进程，有2个就绪进程，n-2个进程处于等待/阻塞状态 2. 有1个运行进程，没有就绪进程， n-1个进程处于等待/阻塞状态 3. 有1个运行进程，有1个就绪进程，n-2个进程处于等待/阻塞状态 4. 有1个运行进程，n-1个就绪进程，没有进程处于等待/阻塞状态 错 错 对 对 3 在一个单处理器系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进程最多有4个；最少有0个 4 在单处理器分时系统中，分配给进程P 的时间片用完后，系统进行切换，结果调度到的进程仍然是进程P 。有可能出现上述情况吗？如果可能，请说明理由。 其一，若果系统中除了0号和1号进程外，就只有P 进程，那永远调度的是P 进程； 其二，其他进程处于休眠状态，等待资源会进入休眠状态，例如一些守护进程等，调度的进程还会使P 进程；其三，经过计算之后，动态优先级仍然是P 进程比较高；还有些比较复杂的情况下也有可能，在这里就不多说了，总之，在调度的时候是会按照动态优先级进行的。 5 某系统的进程状态转换图如下图所示，请说明： – 引起各种状态转移的典型事件有哪些？ – 当我们观察系统中某些进程时，能够看到某一进程产生的一次转换能引起另 外进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另外一个进程发生转换1？ – 试说明是否会发生下述因果转换： ? 2->1 ? 3->2 ? 4->1