操作系统存储管理（完）ppt课件.ppt

计算机软件技术基础,存储管理,第四章 存储管理,4.1 概述一、存储器的层次：三级存储器结构,本章主要讨论几种常用的内存管理技术。,计算机软件技术基础,存储管理,二、用户程序的处理过程,4.1 概述,绝对装入方式：按模块中的地址，将程序和数据装入到内存对应位置。可重定位方式：在装入程序时，根据当时内存的实际使用情况，重新调整装入的内存位置，把程序装入到内存的适当地方。,数学模型,计算机软件技术基础,存储管理,三、地址重定位（映射）-Relacation1. 术语,4.1 概述,名字空间：用户源程序中由符号指令，数据说明等符号名字构成的空间,经汇编或编译后其目标程序占有的地址范围称为地址空间；这些地址编号是相对于起始地址（0）而定的，称为逻辑地址或相对地址。,存储空间是目标程序装入内存后占用的一系列物理单元的集合。 这些物理单元编号称为物理地址或绝对地址。,把程序中的逻辑地址变成内存中的物理地址的过程。,计算机软件技术基础,存储管理,2. 重定位的两种方式静态重定位:在程序执行之前进行；由重定位装配程序根据将要装入的内存起始位置直接修改模块中的有关使用地址的指令。固定在内存的某个连续区域，不能再移动。重定位装配程序来实现(一对界地址寄存器实现保护),三、地址重定位（映射）,内存中起始地址,内存中结束地址,计算机软件技术基础,存储管理,三、地址重定位（映射）,特点：程序执行前一次性全部完成。性能分析：优点-实现简单，不需要硬件机构；缺点-程序重定位之后就不能再在内存中移动；要求程序的存储空间是连续的，不能放在若干个不连续的区域内；各个用户进程很难共享内存中的同一程序副本。,例：假设已知一段程序的经汇编连接后逻辑地址空间如图所示，采用静态地址重定位，上，下界地址寄存器如图，试给出其存储空间图。,与地址有关的量要做变更X=x+D,1300,计算机软件技术基础,存储管理,(2)动态重定位时机：在程序执行过程中进行，当CPU访问内存指令时由动态变换机构自动进行地址转换。实现：目标模块不加任何修改而装入内存，由定位寄存器和加法器硬件完成地址转换。,三、地址重定位（映射）,例：假设已知一段程序的经汇编连接后逻辑地址空间如图所示，采用动态地址重定位，试给出其存储空间图。,程序不做任何修改装入内存，在执行时访问内存时利用重定位寄存器进行地址重定位,计算机软件技术基础,存储管理,特点：程序执行时动态地完成。性能分析：优点-程序装入内存之后再搬迁也不会影响其正确执行；每个目标模块装入的存储区不必顺序相邻，只需要各自对应的定位寄存器即可。-是虚拟存储器技术的基础缺点-需要硬件支持。,三、地址重定位（映射）,计算机软件技术基础,存储管理,四、存储管理的功能内存的分配与回收；地址重定位；内存信息的共享与保护；内存的扩充（满足用户对内存超容量要求）；,4.1 概述,计算机软件技术基础,存储管理,1。可由CPU调用执行的程序所对应的地址空间为 。A. 名称空间B. 虚拟地址空间C. 相对地址空间D. 物理地址空间,2。当程序经过编译或者汇编以后，形成了一种由机器指令组成的集合被称为 。A. 源程序B. 目标程序C. 可执行程序D. 非执行程序,3。目标程序指令的顺序都以0作为一个参考地址，这些地址被称为 。A. 虚拟地址B. 物理地址C. 绝对地址D. 重定位地址,4。若调用指令LOAD A,Data，经动态重定位后，其对应指令代码 。A. 保持不变B. 会变化，随装入起始地址变化而变化C. 会变化，固定在某一存储区域D. 重定位项等于重定位寄存器内容,计算机软件技术基础,存储管理,目的：为了满足多道程序设计思想。方法：将内存划分为若干个分区，每个分区分配给一个作业，用静态重定位方式进行地址转换，提供必要的保护手段，保证各作业互不干扰。在分区的划分方式上有固定分区和可变分区两种。,4.2 早期的存储管理技术-分区式分配方式,计算机软件技术基础,存储管理,一、固定式分区（静态分区）,一、固定式分区,(b)分区说明表,例：已知内存分配如图a所示，此时分区说明表如图b所示，现有后备作业队列如图c所示，试采用固定分区法进行内存分配，并给出相应的分区说明表。,性能：分区大小固定，分区表的结构可以是顺序表也可以是链表；实现了多个作业共享内存；分区的分配和回收算法简单；缺点是内存利用不充足，有“碎片”，即作业所需空间和分区大小不一定恰好相等。,Job A(6k),Job B(25k),Job C(40k),外部碎片剩余165K但不能分配给D,计算机软件技术基础,存储管理,4.2 分区式分配方式,二、可变式分区（动态分区）思想：又称动态存储管理，只有当作业调入内存时，才按作业大小建立分区，当作业执行完后又释放此空间。,计算机软件技术基础,存储管理,2. 分区的管理与组织方式采用可变分区方式管理内存储器时，内存中有两类性质的分区：一类是已经分配给用户使用的“已分配区”，另一类是可以分配给用户使用的“空闲区”。对分区的管理，常用的方式有三种：表格法、单链表法和双链表法。,二、可变式分区,计算机软件技术基础,存储管理,（1）表格法,二、可变式分区,内存分区的管理表格,计算机软件技术基础,存储管理,（2）单链表法,二、可变式分区,单链表形式分区管理,在每块开始与结束的几个字节中存放有关本块状态的信息，称为控制信息区, 如图a所示。,计算机软件技术基础,存储管理,二、可变式分区,（3）双链表法,空闲块链表,计算机软件技术基础,存储管理,空间分配例题,设某系统用户区大小为5000字节，地址为1 5000，初始状态如下图a所示，依次分配给5个作业P1 P5, 作业占用区大小分别为1000，300，600，900，700。 P0 为余下的空闲块，各占用块和空闲块情况如下页图b和c所示。,二、可变式分区,注意：空间分配回收时使用空闲块链表,计算机软件技术基础,存储管理,空间回收过程图（无空闲块合并发生）,空间回收过程图（有空闲块合并发生）,当P5作业完成后，回收时由于其左右邻居均为空闲块，因此应进行合并。,计算机软件技术基础,存储管理,分配算法：最先适应算法(First-Fit)：空闲表按空闲块的物理起始地址递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。最佳适应算法(Best-Fit)：空闲表按空闲块的大小递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。最差适应算法：(Worst-Fit):空闲表按空闲块的大小递减次序排列，分配时，将空闲块链表中第一块分配给用户。,二、可变式分区,计算机软件技术基础,存储管理,三、多重式分区一个作业装入内存中多个不一定相邻的分区。优点：灵活利用内存；缺点：碎片小了，但可能数量更多。,4.2 分区式分配方式,计算机软件技术基础,存储管理,四、分区管理的存储保护界地址法：静态重定位使用,4.2 分区式分配方式,一对基地址、限长寄存器。动态重定位使用。,计算机软件技术基础,存储管理,4.2 分区式分配方式,五、可重定位式分区（紧缩分区）1. 实现：向一个方向移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。2. 问题：地址项的修改-动态地址重定位；基址限长寄存器保护；b. 紧缩时机:回收时进行-每当作业结束,释放所占分区时;分配时进行-当新作业到来又没有能容纳的空闲区分配时;3. 性能：消除了碎片，提高了内存利用率；但花费了大量的cpu时间。,计算机软件技术基础,存储管理,1.分区管理要求对每一个作业都分配 内存单元。A. 地址连续B. 若干地址不连续C. 若干连续的帧D. 若干不连续的帧,2.碎片是指 。A. 存储分配完后剩余的空闲区B. 没有被使用的存储区C. 不能被使用的存储区D. 未被使用，而又暂时不能使用的存储区,计算机软件技术基础,存储管理,引入：最早用于分时系统中提高内存利用率的一种内存扩充技术。思想（roll-in roll-out）：除操作系统外，剩余的全部内存都分给当前正在执行的用户使用，当调度转向下一个用户时，当前用户内存区中的内容要写到外存中，被选中的用户的信息读入内存。实现：由换入和换出两个过程构成的交换进程完成。核心问题：保证对换信息量要最少-只要保证当前正在执行的用户进程在内存中完整保存。技术支持一般都有动态重定位机构-因而一个作业换入内存时不一定要装入它被换出前所占据的区域中.需要较多软件的支持.,4.3 多道程序对换技术,计算机软件技术基础,存储管理,一、引入目的：为了解决分区存储管理中，当某作业需求空间大于内存物理空闲空间时，该作业无法运行的问题。二.原理:程序执行时的局部性原理三、思想：在一个程序执行过程中，不需要全部装入内存，而把不经常被进程访问的程序段和数据放在外存中，待需要访问它们时再将它们调入内存。（部分装入内存）,4.4 虚拟存储器的概念,计算机软件技术基础,存储管理,三、虚拟存储器：是指仅把作业的一部分装入内存便可运行该作业的存储器系统，具有请求调入和置换功能。,4.4 虚拟存储器的概念,虚拟存储管理技术需要解决的问题： （1）什么时候把哪部分程序装入内存。 （2）放在内存什么位置。 （3）当内存空间不足时，把哪部分程序淘汰出内存。常用的虚拟存储技术有：分页存储管理、分段存储管理、段页存储管理。,计算机软件技术基础,存储管理,四、物质基础二级存储器(内/外存)-实现内/外存有机联系;动态地址转换机构(DAT)-实现动态定位,实际上用户的虚拟地址空间并不可能是无限大，它受到以下两个条件制约： 1. 指令中地址长度的限制。 2. 外存储器容量的限制。,计算机软件技术基础,存储管理,1. 能够实现对内外存进行统一管理，为用户提供一种宏观上似乎比实际内存容量大得多的存储器。A. 覆盖技术B. 交换技术C. 物理扩充D. 虚拟存储技术,2.若处理器有32位地址，则它的虚拟地址空间为 字节。A. 2GBB. 4GBC. 100KBD. 640KB,计算机软件技术基础,存储管理,4.5 请求分页式存储管理,一、分页式存储管理（静态分页）-程序一次装入内存中若干个不连续的区域1. 分页管理的基本概念 (1)页面、页架（块）页：把每个作业的地址空间分成一些大小相等的片，称为“页”。页架”或者“块：把内存的存储空间也分成大小与页相同的片，称为“页架”或者“块”。,(2)页表与页表地址寄存器页表：系统为每个作业建立一个页面映像表（PMT），简称“页表”。页表中应包括：页号、页架号、状态。,作业各页的页号，每个作业页号从零开始。,该页面在内存中的页架号。,表示该页是否在内存中，用“0”表示该页不在内存，用“1”表示在内存中。,虚地址空间,实地址空间,5,计算机软件技术基础,存储管理,例：系统选择页的大小为1k字节，则块的大小也为1K。主存空间如图所示。,（1）已经分配空间给作业1，2，如图。,（2）作业3有3k字节。其分配空间与相应的页表如图。,计算机软件技术基础,存储管理,一、分页式存储管理（静态分页）,(3)分页系统中的地址结构在分页系统中，每个虚拟地址用一个数对（p,d）来表示，其中p为页号。d是该虚拟地址在页面号为p中的相对地址，称为页内地址。,计算机软件技术基础,存储管理,如何将逻辑地址转化为页号p与页内位移d？,例1：设U=552为逻辑地址,页面大小为P=512，则页号p与页内位移d是多少？,例2：设U=552为逻辑地址,页面大小为P=512，则页号p与页内位移d是多少？,U=(552)10=(1 0 0 0 1 0 1 0 0 0)2,解：P=(512)10=2n=29,n=9,公式：,计算机软件技术基础,存储管理,2. 分页管理的原理逻辑地址如何转化为物理地址？进程的逻辑地址(虚地址)=页号(P)+页内地址(位移d)由硬件地址变换机构通过页表地址寄存器,页表PMT实现地址转换。,一、分页式存储管理（静态分页）,当某作业被调度到处理器上运行时，操作系统自动将该作业的页表的起始地址和长度装入页表地址寄存器中,计算机软件技术基础,存储管理,例题:假如某系统页面大小为（512)10字节，即相当于（1000)8字节，若逻辑地址为（1320)8，其转换为物理地址地址变换过程如图。,分页管理的地址转换图,地址变换机构,23285,1320,计算机软件技术基础,存储管理,二、请求分页存储管理系统（动态分页）1.设计思想：允许只装入若干页（而非全部）的用户程序和数据，便可启动运行，以后根据请求陆续把即将要运行的页面调入内存。初启时，只装入第一页。 2.实现：在分页系统的基础上，增加请求调页功能和页面置换功能。3.技术措施：请求分页的页表机制-对纯分页页表进行扩展,4.5 请求分页式存储管理,每个作业都有存入其JCB中私有页表；当访问页不在内存时，产生缺页中断；OS管理一张总的存储分块表。,=1,表示该页修改过,=1,表示最近访问过,=1,表示该页在内存中,=0,表示该页不在内存中，发生缺页中断,该页面在外存的地址,计算机软件技术基础,存储管理,请求分页存储管理技术例：系统选择页的大小为4KB，则块的大小也为4KB。设某时刻系统有3个作业，现执行作业2，作业2的虚拟地址空间如下图。此时系统内存分配图如图a，内存存储分块表如图b，作业表如图c，各作页页表如图d。,8300=(p,d)=?,计算机软件技术基础,存储管理,请求分页存储管理技术图例,指令Call 8300 经动态地址重定位后，实际执行指令为Call（28K108）,计算机软件技术基础,存储管理,5. 硬件支持动态地址映射机构-利用页表将虚地址转换物理地址；页表实现形式：用专用内存区实现：用一组专用寄存器实现:用一个高速联想寄存器保存页表-快表实现：,二、请求分页存储管理系统,缺页中断响应机构,计算机软件技术基础,存储管理,利用快表实现地址转换一,计算机软件技术基础,存储管理,页表、快表地址转换机构,计算机软件技术基础,存储管理,工作区入内存填写页表各项,进程调度该进程,启动待执行指令,计算页号与页内相对地址,该页在内存吗？,地址变换,访内存执行完成该指令,执行下一条指令,是,硬件完成,否,保护当前进程现场,有空闲块吗？,选择一页淘汰,该页修改过吗？,把该页写回外存,调入所需页,调整页表及空闲块表,恢复被中断进程现场,是,否,是,否,状态位,引用位,改变位,否,请求分页系统程序执行过程,缺页中断,计算机软件技术基础,存储管理,缺页中断处理过程,计算机软件技术基础,存储管理,6.请求分页系统的性能：有效存取时间：t=（1-P）ma+P缺页处理时间其中，P-缺页中断概率；ma-内存存取时间。有快表时，存取时间短。速度与命中率相关。无快表时，执行速度降低。（二次访问内存）,4.5 请求分页式存储管理,计算机软件技术基础,存储管理,三、页面淘汰算法（置换）页面淘汰：由于分页管理中分配给每道程序的页架数有限，因此内存中的页面要随时进行更换，称为页面淘汰。,4.5 请求分页式存储管理,页面淘汰算法评价准则：在特定存储访问序列上运行页面淘汰算法，用其缺页率来衡量。,计算机软件技术基础,存储管理,四、页面淘汰算法,页面走向：评价时用于量化缺页率的存储访问序列。 （人工获得）随机产生；实际跟踪记录地址,量化：对于给定的页面(大小确定), 只关心页号, 不关心完整地址;如果对P页进行了访问,随后立即对P页的访问不会缺页;,计算机软件技术基础,存储管理,3. 几种常用页面淘汰算法（1）先进先出法（FIFOFirst Input First Output）：算法思想：认为最先进入内存的页面，不再被使用的可能性最大，所以最先进入内存的页面，最先被调出内存。,四、页面淘汰算法,例：设有一用户程序共分为6页，页面大小为100,设执行时访问虚拟地址依次为450,440,320,330,210,150,453,350,355,550,456,330,299,199,500. 分配给该程序的内存块数M为3，内存存储地址从0开始分配.(1)给出页面走向P(2)采用FIFO淘汰算法，给出其页面淘汰过程(3)求缺页率。,4,+,+,+,+,+,+,+,+,+,注意:如果对P页进行了访问,随后立即对P页的访问不会缺页;,计算机软件技术基础,存储管理,四、页面淘汰算法,例：设有一用户程序共分为6页，页面走向P为1，2，3，4，1，2，5，1，2，3，4，5，分配给该程序的内存块数M为3，采用FIFO淘汰算法，其页面淘汰过程如下，并求缺页率。,计算机软件技术基础,存储管理,四、页面淘汰算法,例：设有一用户程序共分为6页，页面走向P为1，2，3，4，1，2，5，1，2，3，4，5，分配给该程序的内存块数M为4，采用FIFO淘汰算法，其页面淘汰过程如下，并求缺页率。,计算机软件技术基础,存储管理,性能分析：这一算法适用于按线性顺序访问地址的程序，否则效率不高。算法简单, 但性能较差(实验证明),表现为:内存利用率不高。存在异常现象。,（1）先进先出法,计算机软件技术基础,存储管理,四、页面淘汰算法,(2)最优淘汰法(OPT Optimal Replacement)思想：淘汰将在最长的时间后才要访问的页面。实现：非常困难，因为需要跟踪各页面方可预测未来。“看将来”,OPT页面淘汰过程,4,例：设有一用户程序共分为6页，页面走向P为4，3，2，1，4，3，5，4，3，2，1，5，分配给该程序的内存块数M为3，采用OPT淘汰算法，其页面淘汰过程如下，并求缺页率。,性能分析：a. 最优算法,目的在于减少页面交换次数,节约处理机时间；b. 缺页率,f=7/12=58%,计算机软件技术基础,存储管理,(3)最久未使用法(LRU Least Recently Used)思想：基于“过去一段时间里不曾被访问过的页，在最近的将来可能也不再会被访问”假设。淘汰一页时，选取在最近一段时间内最久未使用过的页面予以淘汰。,四、页面淘汰算法,常采用近似算法：最不频繁使用法(LRU)-把最不常用的页面先淘汰。b. 最近没有使用法(NUR)-把最近没有使用过的页面淘汰。,计算机软件技术基础,存储管理,性能分析:近似算法是较为实用的算法，效果较好，实现不难,(3)最久未使用法,例：设有一用户程序共分为6页，页面走向P为4，3，2，1，4，3，5，4，3，2，1，5，分配给该程序的内存块数M为3，采用LRT淘汰算法，其页面淘汰过程如下，并求缺页率。,缺页率f=10/12=83%,计算机软件技术基础,存储管理,(4) 第二次机会算法(SCR)-FIFO的改进思想：保护经常被访问的“老页”不被淘汰。实现：每页被访问时，置访问位“1”，需要淘汰一页时，依FIFO顺序检查各页的访问位，为“0”者，淘汰；为“1”者，给予第二次机会，同时，清0。,计算机软件技术基础,存储管理,用循环链表表示的第二次机会算法,计算机软件技术基础,存储管理,四、物理块分配算法-内存空闲块分配最少块数原则-不允许一条指令在执行过程中缺页最少块数必须保证访问指令执行期间不缺页。结论: 每个进程的最少块数由指令集结构决定; 每个进程的最多块数由可用内存的总量决定。2. 全局分配与局部分配允许缺页时在全体进程中选择淘汰者(可变分配)缺页时只在自己驻内页中选择淘汰者(固定分配),4.5 请求分页式存储管理,计算机软件技术基础,存储管理,3. 分配算法等分法: 总块数m /总进程数n性能-一视同仁，但有的剩余；有的不够。按需比例法： si/s*m其中:si-进程pi地址空间大小; s=si(i=1n) m-内存总块数4. 抖动问题: 刚被淘汰出去的页面,很快又要访问,又调回内存, 如此反复。由于淘汰算法不当产生.,五、物理块分配算法,计算机软件技术基础,存储管理,五、请求时分页存储管理系统的性能优点： 1. 提供大容量的多个虚拟存储器 2. 提高了内存利用率; 3. 作业地址空间不受内存限制，有利于组织多道程序执行; 4. 不要求作业在内存中连续存放，有效解决碎片问题;缺点： 1. 要求相应的硬件支持; 2. 增加系统开销; 3. 算法选择不当,会产生抖动.,4.5 请求分页式存储管理,计算机软件技术基础,存储管理,1.页式存储管理中，页表的大小由 决定。A. 作业所占页的多少B. 操作系统C. 计算机编址范围D. 系统统一指定,2.一进程刚获得三个存储块的使用权，若该进程访问页面的次序是1,3,2,1,2,1,5,1,2,3，当采用先进先出调度算法时，发生缺页的次数是 次。A. 4B. 5C. 6D. 7,计算机软件技术基础,存储管理,4.6 段式存储管理,一、分段的基本思想引入：为了满足用户（程序员）在编程和使用上多方面的要求。2. 分段：(用户编程时决定)把程序按内容或过程（函数）关系划分 成若干个段，每段定义一组逻辑上完整的程序和数据，且每段有自己的名字和长度。,计算机软件技术基础,存储管理,4.6 段式存储管理,3. 分段管理的基本概念（1）段一个程序由若干个程序模块组成，可以按模块来分配存储空间。分段管理把每个模块的地址空间称为“段”。每个段规定一个段号，每个段的地址空间都从“0”地址开始。（2）分段管理中的地址结构在分段情况下，每一个虚拟地址需要用两部分来描述，如下图。,！在分页存储管理中，一个虚拟地址可以分解为页号和页内地址。二者是否相同？,计算机软件技术基础,存储管理,段式虚地址空间-二维程序地址=段名(s)+段内位移(w相对于每段起始)注意:与页式虚地址(一维)的区别:段名(号)之间无顺序关系;页号之间是连续的。段的长度是不固定的.(与完整的逻辑信息有关)。页长度固定，一般一页中的信息不是完整的逻辑信息单位。,！在分页存储管理中，一个虚拟地址可以分解为页号和页内地址。二者是否相同？,计算机软件技术基础,存储管理,段表、段地址寄存器系统为每个作业建立一个段映象表（SMT），简称段表，段表中包括：段号、段的长度、段在主存中的起始地址、段的状态以及存取权限等。同时系统设立一个段表地址寄存器，指出当前运行作业的段表在主存中的起始地址b以及段表长度L。,4.6 段式存储管理,计算机软件技术基础,存储管理,三、段式管理的实现,1. 段式管理中的地址转换,例：将逻辑地址s=2，w=292转换成实际地址8292。,分段管理的地址转换图,二、段式管理的实现,计算机软件技术基础,存储管理,三、段式管理的实现,3. 段式管理的存储保护(1)越界保护(2)存取控制保护,计算机软件技术基础,存储管理,4.6 段式存储管理,三、分段管理的优缺点1. 优点便于程序模块化处理。便于处理变化的数据。便于共享分段。,2. 缺点：要求一定的硬件支持，增加了成本。分段尺寸的大小受到主存的限制。,计算机软件技术基础,存储管理,4.7 段页式存储管理,一、段页式管理的基本概念1、段页结构段页式管理是分页和分段管理结合的结果。段页式管理中，作业的地址空间采用分段方式，而作业的每一段采用分页方式。整个主存分成大小相等的存储块，称为页架，主存以页架为单位分配给每个作业。2、段页管理的地址结构段页式管理中的逻辑地址用三个参数表示，如下图,段页式管理地址结构,计算机软件技术基础,存储管理,一、段页式管理的基本概念,3、段表、页表、段地址寄存器系统为每个作业建立一个段表，并为每个段建立一个页表，并设置一个段地址寄存器来指出当前运行作业的段表起始地址和段表长度。,计算机软件技术基础,存储管理,段页管理的地址转换图,二、段页式管理的地址转换,计算机软件技术基础,存储管理,三、段页式管理的优缺点优点: 段页式管理具有分页、分段管理的优点，是使用的最广泛、最灵活的一种存储管理技术。缺点：需要更多的硬件支持，增加了硬件的成本，同时也增加了软件的复杂性和管理开销。,4.7 段页式存储管理,计算机软件技术基础,存储管理,1. 是一种动态存储分配方式。A. 固定分区B. 可变式分区C. 简单分页管理D. 请求分页管理2. 是一种静态存储分配方式A. 简单分页B. 请求分页管理C. 段式管理D. 段页式管理,3.在分段管理中 。A. 以段为单元分配，每段是一个连续存储区B. 段与段之间必定不连续C. 段与段之间必定连续D. 每段是等长的,4.以下主存管理方案中，不采用动态重定位的是 。A. 页式管理B. 固定分区C. 可变分区D. 段式管,计算机软件技术基础,存储管理,作业：P1221,2,3,4,5,6,7,8,9,10,12,14,16,17,19,22,23,24,25,26,28,29,